(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 (C) 42，40，45，55，80，85
(B) 42，40，45，80，85，88 (D) 42，40，45，85，55，80
168． 设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中
带权路径长度之和为（ D ）。 (A) 20
(B) 30 (C) 40
(D) 45
169． 执行一趟快速排序能够得到的序列是（ A ）。
(A) [41，12，34，45，27] 55 [72，63] (B) [45，34，12，41] 55 [72，63，27] (C) [63，12，34，45，27] 55 [41，72] (D) [12，27，45，41] 55 [34，63，72]
170． 设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是
（ A ）。 (A) head==0
(C) head->next==head (D) head!=0
(B) head->next==0
第 21 页 共 100 页
171． 时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ A ）。
(A) 堆排序 (B) 冒泡排序 (C) 希尔排序 (D) 快速排序
172． 设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条
件是（ D ）。
(A) 空或只有一个结点 (B) 高度等于其结点数 (C) 任一结点无左孩子 (D) 任一结点无右孩子
173． 一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ D ）。
(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希尔排序
174． 设某棵三叉树中有40个结点，则该三叉树的最小高度为（ B ）。
(A) 3
(B) 4 (C) 5 (D) 6
175． 顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ A ）。
(A) O(n) (B) O(n2) (C) O(n1/2)
(D) O(1og2n)
176． 二路归并排序的时间复杂度为（ C ）。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(log2n)
177． 深度为k的完全二叉树中最少有（ B ）个结点。
(A) 2k-1-1
(B) 2k-1 (C) 2k-1+1 (D) 2k-1
178． 设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的
队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（ C ）。 (A) front->next=s；front=s；
(B) s->next=rear；rear=s；
(C) rear->next=s；rear=s； (D) s->next=front；front=s；
179． 设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ A ）。
(A) O(n+e)
(B) O(n2) (C) O(ne)
(D) O(n3)
180． 设某哈夫曼树中有199个结点，则该哈夫曼树中有（ B ）个叶子结点。
(A) 99
(B) 100
(C) 101 (D) 102
181． 设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂
度为（ D ）。
(A) O(n) (B) O(n2) (C) O(n log2n) (D) O(log2n)
第 22 页 共 100 页
182． 设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为
（ B ）。
(A) 第i行非0元素的个数之和 (B) 第i列非0元素的个数之和 (C) 第i行0元素的个数之和
(D) 第i列0元素的个数之和
183． 设某无向图有n个顶点，则该无向图的邻接表中有（ B ）个表头结点。
(A) 2n
(B) n (C) n/2 (D) n(n-1)
184． 设无向图G中有n个顶点，则该无向图的最小生成树上有（ B ）条边。
(A) n
(B) n-1
(C) 2n (D) 2n-1
185． 设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键
字45为基准而得到的一趟快速排序结果是（ C ）。 (A) 40，42，60，55，80，85 (C) 42，40，55，60，80，85
(B) 42，45，55，60，85，80 (D) 42，40，60，85，55，80
186． （ B ）二叉排序树可以得到一个从小到大的有序序列。
(A) 先序遍历 (B) 中序遍历 (C) 后序遍历 (D) 层次遍历
187． 设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，
则编号为i结点的左孩子结点的编号为（ B ）。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1
188． 程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ A ）。
(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)
189． 设带有头结点的单向循环链表的头指针变量为head，则其判空条件是
（ C ）。 (A) head==0
(B) head->next==0
(C) head->next==head (D) head!=0
190． 设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ C ）。
(A) 20
(B) 256
(C) 512
(D) 1024
191． 设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，
134),则利用二分法查找关键字90需要比较的关键字个数为（ B ）。
第 23 页 共 100 页
(A) 1 (B) 2 (C) 3 (D) 4
192． 设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为
（ D ）。 (A) top=top+1;
(B) top=top-1;
(C) top->next=top; (D) top=top->next;
193． 建立一个长度为n的有序单链表的时间复杂度为（ C ）
(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)
194． 设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选
择（ B ）。 (A) 99
(B) 97
(C) 91 (D) 93
195． 在二叉排序树中插入一个关键字值的平均时间复杂度为（ B ）。
(A) O(n) (B) O(log2n) (C) O(log2n) (D) O(n2)
196． 设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的
过程中比较元素的顺序为( C )。 (A) A[1]，A[2]，A[3]，A[4] (C) A[7]，A[3]，A[5]，A[4]
(B) A[1]，A[14]，A[7]，A[4] (D) A[7]，A[5] ，A[3]，A[4]
197． 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ B ）。
(A) 8
(B) 7
(C) 6
(D) 5
198． 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为
3的结点，则该三叉链权中有（ C ）个度数为0的结点。 (A) 5
(B) 6
(C) 7
(D) 8
199． 设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，
f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（ A ）。 (A) aedfcb
(B) acfebd
(C) aebcfd
(D) aedfbc
200． 下列程序段的时间复杂度为（ A ）。
for(i=0； i 第 24 页 共 100 页 for(i=0； i (A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n) 201． 设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（ A ） 个元素。 (A) n-i (B) n+l -i (C) n-1-i (D) i 202． 设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、 T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（A ）。 (A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3 203． 利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（ C ）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(log2n) 204． 设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X， 则在结点A的后面插入结点X的操作序列为（ D ）。 (A) p->right=s； s->left=p； p->right->left=s； s->right=p->right； (B) s->left=p；s->right=p->right；p->right=s； p->right->left=s； (C) p->right=s； p->right->left=s； s->left=p； s->right=p->right； (D) s->left=p；s->right=p->right；p->right->left=s； p->right=s； 205． 下列各种排序算法中平均时间复杂度为O(n2)是（ D ）。 (A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 冒泡排序 206． 设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n， 则输出序列中的第i个输出元素是（ C ）。 (A) n-i (B) n-1-i (C) n+l -i (D) 不能确定 207． 设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择 （ B ）。 (A) 小于等于m的最大奇数 (C) 小于等于m的最大偶数 (B) 小于等于m的最大素数 (D) 小于等于m的最大合数 第 25 页 共 100 页