208． 设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数
有1个，度数为1的结点数有2个，那么度数为0的结点数有（ C ）个。 (A) 4
(B) 5 (C) 6
(D) 7
209． 设完全无向图中有n个顶点，则该完全无向图中有（ A ）条边。
(A) n(n-1)/2
(B) n(n-1)
(C) n(n+1)/2
(D) (n-1)/2
210． 设顺序表的长度为n，则顺序查找的平均比较次数为（ C ）。
(A) n
(B) n/2 (C) (n+1)/2
(D) (n-1)/2
211． 设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法
查找值为24的元素需要经过（ C ）次比较。 (A) 1
(B) 2 (C) 3 (D) 4
212． 设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，
则其平均查找长度为（ D ）。 (A) 6
(B) 11 (C) 5 (D) 6.5
213． 设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，
则下列属于该有向图G的一种拓扑排序序列的是（ A ）。 (A) 1，2，3，4
(B) 2，3，4，1
(C) 1，4，2，3
(D) 1，2，4，3
214． 设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组
记录关键字生成的二叉排序树的深度为（ A ）。 (A) 4
(B) 5 (C) 6 (D) 7
215． 下列程序段的时间复杂度为（ A ）。
i=0，s=0； while (s (A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2) 216． 设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列 （ D ）存储方式最节省运算时间。 (A) 单向链表 (C) 双向链表 (B) 单向循环链表 (D) 双向循环链表 第 26 页 共 100 页 217． 设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B， 指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ B ）。 (A) s->next=p->next；p->next=-s； (B) q->next=s； s->next=p； (C) p->next=s->next；s->next=p； (D) p->next=s；s->next=q； 218． 设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列 为（ B ）。 (A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1 (C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3 219． 设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右 的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ B ）。 (A) 10 (B) 19 (C) 28 (D) 55 220． 设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……， Nm个度数为m的结点，则该树中共有（ D ）个叶子结点。 mmmm (A) ?(i?1)Ni?1i (B) ?Ni?1i (C) ?Ni?2i1? (D) ?(i?1)Ni?2i 221． 二叉排序树中左子树上所有结点的值均（ A ）根结点的值。 (A) < (B) > (C) = (D) != 222． 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集 合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ D ）。 (A) 129 (B) 219 (C) 189 (D) 229 223． 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字 映射到HASH表中需要做（ D ）次线性探测。 (A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2 224． 设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n， 则这棵二叉中共有（ C ）个结点。 第 27 页 共 100 页 (A) 2n (B) n+l (C) 2n-1 (D) 2n+l 225． 设一组初始记录关键字的长度为8，则最多经过（ B ）趟插入排序可以得 到有序序列。 (A) 6 (B) 7 (C) 8 (D) 9 226． 设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F， X)，则按字母升序的第一趟冒泡排序结束后的结果是（ D ）。 (A) F，H，C，D，P，A，M，Q，R，S，Y，X (B) P，A，C，S，Q，D，F，X，R，H，M，Y (C) A，D，C，R，F，Q，M，S，Y，P，H，X (D) H，C，Q，P，A，M，S，R，D，F，X，Y 227． 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位 置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。（ C ） (A)688 (B) 678 (C)692 (D) 696 228． 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中， 现进行二分查找，则查找A［3］的比较序列的下标依次为（ D ）。 (A) 1，2，3 (C) 9，5，3 (B) 9，5，2，3 (D) 9，4，2，3 229． 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（ C ）。 (A) O（1） (B) O（n） (C) O（1og2n） (D) O（n2） 230． 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用 H （K）=K %9作为散列函数，则散列地址为1的元素有（ D ）个。 (A) 1 (B) 2 (C) 3 (D) 4 231． 设有6个结点的无向图，该图至少应有（ A ）条边才能确保是一个连通图。 (A) 5 (B) 6 (C) 7 (D) 8 232． 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈 夫曼树中总共有（ B ）个空指针域。 第 28 页 共 100 页 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 二、判断题 1．数据项是数据的最小单位。（ ） 2．链表的每个结点都恰好有一个指针。（ ） 3．同一组不重复输入序列执行不同的入栈出栈组合操作，所得结果也可能相同。 （ ） 4．改进的KMP算法中，字符串‖abaaaba‖的nextval数组值是0101110。（ ） 5．用六叉链表表示30个结点的六叉树，则树中共有151个空指针。（ ） 6．数组是一种线性结构，因此只能用来存储线性表。（ ） 7．若有向图不存在回路，即使不用访问标志位同一结点也不会被访问两次。（ ） 8．若装填因子a为1，则向散列表中散列元素时一定会产生冲突。（ ） 9．若把堆看成是一个完全二叉树，则该树一定是一棵排序二叉树。（ ） 10． 外排中使用置换选择排序的目的，是为了增加初始归并段的长度。（ ） 11． 抽象数据类型与计算机内部表示和实现无关。（Y ） 12． 线性表的插入和删除总是伴随着大量数据的移动。（ N ） 13． 队列在程序调用是必不可少，因此递归离不开队列。（ N ） 14． 字符串‘aababaaaba‘的改进函数nextval数组值是0020200320。(Y ) 15． 二叉树中有双子女的父结点，在中序遍历中后继一定是其中一个子女结点。 （ N ） 16． 不用递归就不能实现二叉树的前序遍历。（ N ） 17． 若有向图有n个顶点，则其强连通分量最多有n个。(Y ) 18． 平衡二叉树一定是一棵完全二叉树。（ N ） 19． 若某内部排序算法不稳定，则该算法没有使用价值。（ N ） 第 29 页 共 100 页 20． 倒排文件的目的是为了多关键字查找。(Y ) 21． 已知指针curr指向链表中的某结点，执行语句curr=curr->next；不会删除该链 表中的结点。 ( ) 22． 若二叉树的叶结点数为1，则其高度等于结点数(仅含根结点的二叉树高度 为 1)。 （ ） 23． 按中序周游二叉树时，某个结点的直接后继是它的右子树中第一个被访问 的 结点。 ( ) 24． 完全二叉树的某结点若无左孩子，则它必是叶结点。 ( ) 25． 向二叉检索树中插入一个新结点，需要比较的次数不可能大于此二叉树的高 度。 ( ) 26． 对一个堆按层次周游，一定能得到一个有序序列。 ( ) 27． 一棵树中的叶子结点数一定等于其对应的二叉树中的叶子结点数。 ( ) 28． 将一棵树转换为二叉树表示后，该二叉树的根结点没有右子树。 ( ) 29． 任何有向图的结点都可以排成拓扑序列，而且拓扑序列不唯一。 ( ) 30． 快速排序在最差情况下的时间复杂度是0(n2)，此时它的性能并不比冒泡排序 更好。 ( ) 31． AVL树的任何子树都是AVL树。（ Y） 32． 用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（ N） 33． 霍夫曼树一定是满二叉树。（ Y） 34． 栈是一种线性结构。（Y ） 35． B＋树既适于随机检索，也适于顺序检索。（N ） 36． 记录是数据处理的最小单位。 （ ） 37． 数据的逻辑结构是指数据的各数据项之间的逻辑关系。( ) 38． 算法的优劣与算法描述语言无关，但与所用计算机有关。（ ） 39． 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( Y ) 第 30 页 共 100 页