1. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为C
2. A. O（1） B. O（n） C. O（1og2n） D. O（n2）
3. 后缀算式9 2 3 +- 10 2 / -的值为--1_。中缀算式（3+4X）-2Y/3对应的后缀算式为3 4 X
* + 2 Y * 3 / -
4. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为___O(log2n)，整个堆
排序过程的时间复杂度为____O(nlog2n)_____。
5. 12. 在快速排序、堆排序、归并排序中，__归并___排序是稳定的。 6. 5．设某完全无向图中有n个顶点，则该完全无向图中有（A ）条边。
22
7. (A) n(n-1)/2 (B) n(n-1) (C) n (D) n-1
8. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。 9. typedef struct {int s[100]; int top;} sqstack; 10. void push(sqstack &stack,int x) 11. {
12. if (stack.top==m-1) printf(“overflow”);
13. else {stack.top++;stack.s[stack.top]=x} 14. }
2
15. 快速排序的最坏时间复杂度为O(n)，平均时间复杂度为_O(nlog2n)______。 16.设有n个待排序的记录关键字，则在堆排序中需要（1）个辅助记录单元。 17.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ B）。
2
18. (A) O(1) (B) O(log2n) (C) (D) O(n) 19.设某强连通图中有n个顶点，则该强连通图中至少有（ C）条边。 20. (A) n(n-1) (B) n+1 (C) n (D) n(n+1)
21.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关
键字，则用下列（ B）方法可以达到此目的。 22. (A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序 23.10.下列四种排序中（ D）的空间复杂度最大。 24. (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序 25.1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ 1 ）。 26.4．在二叉排序树中插入一个结点的时间复杂度为（O(n) ）。
27.7．设用链表作为栈的存储结构则退栈操作（ 必须判别栈是否为空 ）。 28.8．下列四种排序中（ A ）的空间复杂度最大。
29. (A) 快速排序 (B) 冒泡排序 (C) 希尔排序 (D) 堆
30. 10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次
数不超过（ A ）。 31. (A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)
2
32. 设有n个无序的记录关键字，则直接插入排序的时间复杂度为___O(n).快速排序的平
均时间复杂度为__O(nlog2n)__。 33. 设哈夫曼树中共有99个结点，则该树中有_____50____个叶子结点；若采用二叉链表作
为存储结构，则该树中有__51__个空指针域。
34. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶
指针top2的初值为n，则判断共享栈满的条件是_top1+1=top2 35.5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有
序，则该操作的时间复杂度为（ D）。
2
36. (A) O(log2n) (B) O(1) (C) O(n) (D) O(n)
37.6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m
的结点数为Nm，则N0=（ B）。 38. (A) Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm 39. (C) N2+2N3+3N4+……+(m-1)Nm (D) 2Nl+3N2+……+(m+1)Nm
40. 在图的邻接表中用顺序存储结构存储表头结点的优点是_可以随机访问到任一个顶点的
简单链表