精品文档
121． 一个5行6列的二维数组s采用从最后一行开始，每一行的元素从右至左
的方式映射到一维数组a中，s和a的下标均从0开始，则s[3][3]在a中的下标是（ ）。
(A)7 (B)8 (C)9 (D)10
122． 设只含根结点的二叉树的高度为1，则高度为n的二叉树中所含叶子结点
的个数最多为（ ）个。
(A)2n (B)n (C)2n -1 (D)2n-1
123． 设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所包含
的结点数至少为（ ）个（设只含根结点的二叉树的高度为1）。 (A)2h (B)2h-1 (C)2h+1 (D)h+1
124． 对一棵二叉检索树进行（ ） 得到的结点序列是一个有序序列。
(A)前序周游 (B)中序周游 (C)后序周游 (D)层次周游
125． 一棵前序序列为1，2，3，4的二叉树，其中序序列不可能是（ ） 。
(A)4,1,2,3 (B)4,3,2,1 (C)2,4,3,1 (D)3,4,2,1
126． 在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为（ ）。
(A)e (B)2e (C)n2-e (D)n2-2e
127． 具有n个顶点和e条边的图的深度优先搜索算法的时间复杂度为（ ）。
(A)O(n) (B)O(n3) (C)O(n2) (D)O(n e)
128． 如果具有n个顶点的图是一个环，则它有（ ）棵生成树。
(A)n (B)n l (C)n-l (D)2n
129． 堆排序算法在平均情况下的时间复杂度为（ ）。
(A)O(n) (B)O(nlogn) (C)O(n2) (D)O(logn)
130． 在待排序数据已基本有序的前提下，下述排序方法中效率最高的是（ ）。
(A)直接插入排序 (B)直接选择排序 (C)快速排序 (D)归并排序
131． 在理想情况下，散列表中查找元素所需的比较次数为（ ）。
(A)n (B)O (C)n／2 (D)1
132． 在一棵m阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，
则此结点中原有的关键字的个数是（ ）。 精品文档
精品文档
(A)m (B)m +1 (C)m-l (D)m／2
133． 设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总
是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ C ）。
(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M
134． 设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序
遍历该二叉树得到序列为（ A ）。
(A) BADC
(B) BCDA
(C) CDAB
(D) CBDA
135． 设某完全无向图中有n个顶点，则该完全无向图中有（ A ）条边。
(A) n(n-1)/2 (B) n(n-1)
(C) n2 (D) n2-1
136． 设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C ）。
(A) 9
(B) 10
(C) 11
(D) 12
137． 设某有向图中有n个顶点，则该有向图对应的邻接表中有（ B ）个表头结
点。
(A) n-1 (B) n
(C) n+1 (D) 2n-1
138． 设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基
准进行一趟快速排序的结果为（ C ）。 (A) 2，3，5，8，6 (C) 3，2，5，6，8
(B) 3，2，5，8，6 (D) 2，3，6，5，8
139． 设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，
06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ B ）。 (A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构
140． 下面程序的时间复杂为（ B ）
for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} (A) O(n) (B) O(n2) (C) O(n3)
(D) O(n4)
141． 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改
指针的操作序列为（ A ）。
(A) q=p->next；p->data=q->data；p->next=q->next；free(q)； 精品文档
精品文档
(B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)；
142． 设有n个待排序的记录关键字，则在堆排序中需要（ A ）个辅助记录单元。
(A) 1
(B) n
(C) nlog2n
(D) n2
143． 设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以
20为基准记录的一趟快速排序结束后的结果为（ A ）。 (A) 10，15，14，18，20，36，40，21 (B) 10，15，14，18，20，40，36，21 (C) 10，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，21
144． 设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为
（ B ）。
(A) O(1) (B) O(log2n) (C) log2n (D) O(n2)
145． 设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结
点的个数分别为（ D ）。 (A) n，e (B) e，n (C) 2n，e
(D) n，2e
146． 设某强连通图中有n个顶点，则该强连通图中至少有（ C ）条边。
(A) n(n-1)
(B) n+1 (C) n
(D) n(n+1)
147． 设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的
10个记录关键字，则用下列（ B ）方法可以达到此目的。 (A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序
148． 下列四种排序中（ D ）的空间复杂度最大。
(A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序
149． 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度
为（ C ）。
(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)
150． 设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。
精品文档
精品文档
(A) 2k-1 (B) 2k
(C) 2k-1 (D) 2k-1
151． 设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为
（ D ）。 (A) n
(B) e
(C) 2n
(D) 2e
152． 在二叉排序树中插入一个结点的时间复杂度为（ B ）。
(A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)
153． 设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ C ）
条有向边。 (A) n
(B) n-1 (C) m
(D) m-1
154． 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序
需要进行（ A ）趟的分配和回收才能使得初始关键字序列变成有序序列。 (A) 3
(B) 4
(C) 5
(D) 8
155． 设用链表作为栈的存储结构则退栈操作（ B ）。
(A) 必须判别栈是否为满 (B) 必须判别栈是否为空 (C) 判别栈元素的类型 (D) 对栈不作任何判别
156． 下列四种排序中（ A ）的空间复杂度最大。
(A) 快速排序 (B) 冒泡排序 (C) 希尔排序 (D) 堆
157． 设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2
的结点数为N2，则下列等式成立的是（ C ）。 (A) N0=N1+1 (B) N0=Nl+N2
(C) N0=N2+1 (D) N0=2N1+l
158． 设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最
多比较次数不超过（ A ）。
(A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)
159． 数据的最小单位是（ A ）。
(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量
160． 设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增
量d=4的一趟希尔排序结束后前4条记录关键字为（ B ）。 (A) 40，50，20，95 精品文档
(B) 15，40，60，20
精品文档
(C) 15，20，40，45
(D) 45，40，15，20
161． 设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，
其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ A ）。
(A) 15，25，35，50，20，40，80，85，36，70 (B) 15，25，35，50，80，20，85，40，70，36 (C) 15，25，35，50，80，85，20，36，40，70 (D) 15，25，35，50，80，20，36，40，70，85
162． 设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表
仍然保持有序，则该操作的时间复杂度为（ D ）。 (A) O(log2n) (B) O(1)
(C) O(n2) (D) O(n)
163． 设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，
度数为m的结点数为Nm，则N0=（ B ）。 (A) Nl+N2+……+Nm
(B) l+N2+2N3+3N4+……+(m-1)Nm (C) N2+2N3+3N4+……+(m-1)Nm (D) 2Nl+3N2+……+(m+1)Nm
164． 设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ B ）
次。 (A) 25
(B) 10 (C) 7
(D) 1
165． 设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，
(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ B ）。 (A) abedfc
(B) acfebd (C) aebdfc
(D) aedfcb
166． 设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素
是n，则输出序列中第i个输出元素是（ C ）。 (A) n-i (B) n-1-i
(C) n+1-i
(D) 不能确定
167． 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录
关键字45为基准而得到一趟快速排序的结果是（ C ）。 (A) 40，42，45，55，80，83 精品文档
(B) 42，40，45，80，85，88
最新数据结构试题库
