全国计算机等级考试二级公共基础知识总结(常考)

全国计算机等级考试二级公共基础知识总结(常考)内容摘要：

A） ABCDEF B） DBEAFC C） ABDECF D） DEBFCA （ 15）在深度为 7 的满二叉树中，叶子结点的个数为 A） 32 B） 31 C） 64 D） 63 （ 16）下列数据结构中，能用二分法进行查找的是 A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表 （ 17）下列关于栈的描述正确的是 A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入成删除元素 D）栈是特殊的线性表，只能在一端插入 元素，而在另一端删除元素 （ 18）下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，且各种存储结构不影响数据处理的效率 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响处理的效率 （ 19）数据的存储结构是指 A）存储在外存中的数据 B）数据所占的存储空间量 C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示 （ 20）下列关于栈的描述中错误的是 A）栈是先进后出 的线性表 B）栈只能顺序存储 C）栈具有记忆作用 D）对栈的插入与删除操作中，不需要改变栈底指针 （ 21）对于长度为 n 的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是 A）冒泡排序为 n/2 B）冒泡排序为 n C）快速排序为 n D）快速排序为 n(n1)/2 （ 22）对长度为 n 的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是 A） log2n B） n/2 C） n D） n+1 （ 23）下列对于线性链表的描述中正确的是 A）存储空间不一定是连续，且各元素的存储顺序是任意的 B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C）存储空间必须连续，且前件元素一定存储在后件元素的前面 D）存储空间必须连续，且各元素的存储顺序是任意的 二、填空题 A B C E E F 选择题第（ 14）题图 F C E A D G B 选择题第（ 11）题图 （ 1）线性表的存储结构主要分为顺序存储结构和链式存储结构。 队列是一种特殊的线性表，循环队列的 [1] 存储结构。 （ 2）对下列二叉地进行中序遍历的结果为 [2]。 （ 3）在深度为 7 的满二叉树中，度为 2 的结点个数为 [3]。 （ 4）按“先进后出”原则组织数据的数据结构是 [4]。 （ 5）数据结构分为线性结构 和非线性结构，带链的队列属于 [5]。 （ 6）对长度为 10 的线性表进行冒泡排序，最坏情况下需要比较的次数为 （ 6）。 （ 7）算法复杂度主要包括时间复杂度和 [7] 复杂度。 （ 8）一棵二叉树第六层（根结点为第一层）的结点数最多为 [8] 个。 （ 9）数据结构分为逻辑结构和存储结构，循不队列属于 [9] 结构。 （ 10）某二叉树中度为 2 的结点有 18个，则该二叉树中有 [10] 个叶子结点。 （ 11）问题处理方案的正确而完整的描述称为 [11]。 1． 1． 3 全真试题训练 一、选择 题 （ 1）长度为 10的顺序表的首地址是从 1023 开始的，顺序表中的每个元素的长度为 2，在第 4 个元素前面插入一个元素和删除第 7 个元素后，顺序表的总长度还是不变。 问在执行插入和删除操作前，顺序表中第 5 个元素在执行插入和删除操作后在顺序表中的存储地址是 A） 1028 B） 1029 C） 1031 D） 1033 （ 2）下列关于线性表的两种存储结构叙述正确的是 A）若存储相同数目的元素，则线性链表比顺序表要节省存储空间 B）对无序表的查找，顺序表和线性链表的效率基本上是一样的 C）顺序表适用于插入，删除等更新操作 频繁的场合 D）线性表适用于查询操作比较频繁的场合 （ 3）已知元素的人栈顺序为 abcde ，则下列哪种出栈顺序是不可能的（出栈和入栈操作可交叉进行）。 A） edcba B） cabde C） dcbae D） bcdea （ 4）在线性链表的插入算法中，若要把结点 q 插在结点 p 后面，下列操作正确的是： A）使结点 p 指向结点 q，再使结点 q 指向结点 p 的后件结点 B）使结点 q 指向 p 的后件结点，再使结点 p 指向结点 q C）使结点 q 指向结点 p 的后件结点，再使结点 q 指向结点 p D）使结点 p 指向 q 的后件结点，再使 结点 q 指向结点 p （ 5）下列叙述中错误的是： A）循环链表中，通过表中的任何一个结点可以访问到表中其他所有的结点 B）线性链表的插入和删除效率比顺序表的插入和删除效率高 C）线性链表与顺序表相比，它容易实现动态增长 D）在线性链表中查找一个元素要比在顺序中查找一个元素快 （ 6）一棵度数为 4 的树，它的 4 度结点有 1 个， 3 度结点有 2 个， 2 度结点有 3 个， 1 度结点 4 个，问它的叶子结点有多少个。 A） 5 B） 6 C） 9 D） 11 （ 7）一棵深度为 m的二叉树 2m1 个结点，则最多可以断定此二叉树是 A）满二叉树 B）一般的完全二叉树 C）一般的二叉树 D）一般的树 （ 8）以下四种树中不是完全二叉树的是 A） B） C） D） P F C E A D G H B 填空题第（ 2）题图 （ 9）在一个 x m 的二维线性表中顺序查找一个数据元素的算法时间复杂度是 A） O(n+m) B） O(n m) C） O(n2) D） O(m2) （ 10）下面排序算法中，平均排序速度最快的是 A）冒泡排序法 B）选择排序法 C）交换排序法 D）堆排序法 （ 11）下面哪一个不是算法的基本特征。 A）可靠性 B）确定性 C）有穷性 D）拥有足够的情报 （ 12）通过列举少量的特殊情况，经过分析，最后找出一般的关系的算法设计思想是 A）列举法 B）归纳法 C）递推法 D）递归法 （ 13）常用于解决“是否存在”或“有多少种可能”等类型的问题（例如求解不定议程的问题）的算法设计基本方法是 A）归纳法 B）递推法 C）列举法 D）减半递推技术 （ 14）以下算法设计基本方法中基本思想不属于归纳法的是 A）递推法 B）递归法 C）减半递推技术 D）回 溯法 （ 15）在用于分法求解议程在一个闭区间上的实根时，采用的算法设计技术是 A）列举法 B）归纳法 C）递归法 D）减半递推法 （ 16）右下图表示的数据结构是 A） D={di |1=i=6}={d1,d2,d3,d4,d5,d6} R={(d1,d2),(d1,d3),(d3,d4)(d5,d4),(d5,d6)} B） D={di|1=i=6}={d1,d2,d3,d4,d5,d6} R={(d1,d2),(d1,d3),(d3,d4),(d3,d5),(d5,d4),(d5,d6)} C） D={di|1=i=6}={d1,d2,d3,d4,d5,d6} R={(d1,d2),(d1,d3),(d3,d4),(d3,d5),(d5,d6)} D） D={di|1=i=6}={d1,d2,d3,d4,d5,d6} R={(d1,d2),(d1,d3),(d3,d4),(d5,d3),(d5,d4),(d5,d6)} （ 17）已知线性表的首元素的地址是 1025，每个数据元素的长度为 2，则第 10 个元素的地址为 A） 1035 B） 1045 C） 1027 D） 1043 （ 18） 下列关于链表结构的叙述正确的是 A）线性链表、带链的栈和带链的队列的结点的结构都是相同的 B）双向链表也就是循环链表 C）线性链表与带链的栈的结点的结构是不同的 D）在循环链表中通过任意一个结点可以找到链表中其他所有的结点，而在双向链表中做不到这一点 （ 19）在表示树的多重链表中，除了要存储结点的值和多个指针之外，还必须需要存储 A）结点的度 B）结点的层次 C）结点的高度 D）结点的深度 （ 20）树 T 的度为 4，其中度为 1， 2， 3， 4 的结点个数分别为 4， 2， 1， 1。 则 T 中的叶子结点数为 A） 8 B） 7 C） 6 D） 5 （ 21）具有 8 个结点的完全二叉树中编号为 4 的结点的右子结点的编号为 A） 8 B） 9 C）无此结点 D） 8 或是 9 （ 22）通过相邻数据元素的交换逐步将线性表变成有序的排序方法是 A）冒泡排序法 B）简单选择排序法 C）简单插入排序法 D）希尔排序法 （ 23）快速排序法属于 A）选择类排序法 B）交换类排序法 C）插入类排序法 D）归并类排序法 （ 24）对长度为 n 的线性表进行推排序的时间复杂度是 A） O(n) B） O(nlog2n) C） O(n2) D） O() 二、填空题 （ 1）假如刚开始时栈为空，依次有‘ A’，‘ B’，‘ C’，‘ D’四个元素入栈，此时栈底指针指向元素 [1] ，栈顶指针值为 [2] （假设每个元素的长度为 1）。 执行四次出栈操作后把‘ E’，‘ F’，‘ G’压入栈，问此时栈底指针指向元素 [3] ，此时栈的长度为 [4]。 （ 2）在一个容量为 15 的循环险旬中，若头指针 front=6, 尾指针 rear=4，则该循环队列中共有 [5]个元素；若头指针 front=4，尾指针 rear=6，则该循环队列中共有 [6] 个元素；若头指针 front=6，尾指针 rear=6，则该循环队列中共有 [7] 个元素。 （ 3）拥有奇数个结点的完全二叉树中有 4 个内部结点（非叶子结点），请问它的叶子结点数是 [8]。 （ 4）请写出用二分查找法在有序顺序表（ 1， 2， 3， 4， 6， 8， 9， 11）中查找 3 的比较序列 [9]。 （ 5）设一棵二叉树的中序遍历结果为 DBEACF，前序遍历结果为 ABDECF，则后序遍历结果为 [10]。 （ 6）请写出用冒泡排序法对序列（ 5， 1， 7， 3， 1， 6， 9， 3， 2， 7， 6）进行第一遍扫描后的中间结果是 [11]。 （ 7）请写 出用冒泡排序法对序列（ 5， 1， 7， 3， 1， 6， 9， 3， 2， 7， 6）进行第一遍扫描后的中间结果是 [12]。 （ 8）请写出用简单选择排序法对序列（ 5， 1， 7， 3， 1， 6， 9， 3， 2， 7， 6）进行第一遍扫描后的中间结果是 [13]。 （ 9）一个算法通常由两种基本要素组成，一是对数据对象的运算和操作，二是 [14]。 （ 10）在一般的计算机系统中，有算术运算、逻辑运算、关系运算和 [15] 四类基本的操作和运算。 （ 11）算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释，也不允许有多义 性，这是算法的 [16] 特征。 （ 12）算法必须能在有限的时间内完成，即算法必须能在执行有限个步骤之后终止，这是算法的 [17] 特征。 （ 13） [18] 是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 （ 14）算法中各操作之间的执行顺序称为 （ 19）。 描述算法的工具通常有 [20]、 [21] 、 [22] 等。 （ 15）一个算法一般都可以用 [23] 、 [24] 、 [25] 三种控制结构组合完成。 （ 16）根据提出的问题，列举所 有可能的情况，并且问题中给定的条件检验哪些是需要的，哪些是不需要的，这是算法设计基本方法中的 [26]。 （ 17）通过列举少量的特殊情况，经过分析，最后找出一般的关系，这是算法设计基本方法中的 [27]。 （ 18）从已知的初始条件出发，逐步推出所要求的各中间结果和最后结果，这是算法设计基本方法中的 [28]。 （ 19）将一个复杂的问题归结为若干个简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题的问题为止，这是算法设计基本方法中的 [29]。 如果 一个算法 P 显式地调用自己则称为 [30]。 如果算法 P 调用另一个算法 Q，而算法 Q 又调用算法 P，则称为 [31]。 （ 20）将问题的规模减半，而问题的性质不变，再重复“减半”的过程，这是算法设计基本方法中的 [32]。 （ 21）通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探，这是算法设计基本方法中的 [33]。 （ 22）数据的逻辑。