(A)直接插入排序 (B)简单选择排序 (C)冒泡排序 (D)快速排序
33． 对二叉排序树进行（ C ）遍历，可以得到该二叉树所有结点构成的排序序列。
(A)层次 (B)前序 (C)中序 (D)后序
34． 已知一个长度为12的线性表（8，2，5，7，12，3，10，4，1，6，9，11），
并将线性表中的元素依次插入到一个原先为空的二叉排序树中去。假设查找每一个元素的概率相同，则查找该二叉树中任一结点的平均查找长度为（ A ）。 (A)10/3 (B)13/3 (C)37/12 (D)13/2
35． 一组关键字序列{15，92，124，5，27，28，18，6，36，34，30，26，32，259}，
将它们用散列函数H(key)=key MOD 11 按顺序散列到HASH表HT（0:10）中，用链地址解决冲突。假设查找每一个元素的概率相同，则查找该HASH表中任一元素的平均查找长度为（ C ）。
(A)3/2 (B)10/7 (C)11/7 (D)9/7
36． 以数据集{4，5，6，7，12，18，10}为结点权值所构造的哈夫曼树，则其带权
路径长度WPL为（ A ）。
(A)165 (B)203 (C)124 (D)187
37． 假定对线性表R[0…n-1]进行分块查找，若将表均匀地分为b块，每块含有n/b
个记录；又假定表中每个记录的查找概率相等，并用顺序查找确定所在的块，若要使分块查找的平均查找长度ASL最小，则分块数b的值应为（ B ）。 (A)n (B)n+1 (C)「log2n」 (D)「log2n」+1
38． 对n个记录进行直接插入排序，所需的关键字比较次数的最大值和最小值分别
是（ C ）。
(A)n(n+1)/2和n (B)n(n-1)/2和n-1 (C) n(n+1)/2-1和n-1 (D)n2和n
39． 若在一个具有n个结点的有序单链表中插入一个新结点并仍然有序，则该操作
的时间复杂度是（ ）。
(A)O(1) (B)O(n2) (C)O(nlog2n) (D)O(n)
40． 在一个头结点为head的空循环链表中插入一个结点s，则指针s应执行操作
第 6 页 共 100 页
（ ）。
(A)head->next=s;s->next=NULL; (B)s->next=head;head->next=NULL; (C)head->next=s;s->next=head->next; (D)s->next=head;head->next=s;
41． 设链队列Q的头指针和尾指针分别为front和rear，队中元素个数为n(n>1)，
指针*p指向队首元素m。若删除元素m，则应进行的指针操作为（ ）。 (A)Q->front->next=p->next (B)Q->rear=Q->front (C)Q->front=p->rear (D)Q->rear=p->next
42． 假设二叉树T中有n个叶子结点，且所有非叶子结点都有左、右子树，那么
二叉树T共有（ ）个结点。
(A)2n (B)2n-1 (C)2n+1 (D)2n+2
43． 已知有向图G的邻接矩阵如下所示，则下列序列中（ ）不可能是图G的拓
扑序列。
(A)v1,v6,v3,v4,v2,v5 (B)v1,v6,v4,v3,v2,v5 (C)v1,v3,v2,v4,v6,v5 (D)v1,v3,v6,v4,v5,v2 0 1 1 1 0 00 0 0 0 0 00 1 0 0 1 00 0 0 0 1 00 0 0 0 0 00 0 0 1 1 0 44． 已知一棵二叉树的结点数据采用顺序存储结构，数组内容如下表所示，则该二
叉树的后序遍历序列为（ ）。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 E A F D G C J I H B (A)ACBDJEFIGH (B)ABCDJEFHGI (C)BCJDAHIGFE (D)EADCBJFGIH
第 7 页 共 100 页
45． 若T为n个结点的完全二叉树，则T的叶子结点数为（ ）。
(A)n/2 (B)(n-2)/2 (C)(n-1)/2 (D)(n+1)/2
46． 有一组数值14,21,32,15,28，用以构造huffman树，则其WPL值为（ ）。
(A)267 (B)189 (C)110 (D)294
47． 采用折半插入排序，关键字的比较次数与移动次数分别为（ ）。
(A)O(n),O(log2n) (B)O(n2),O(log2n) (C)O(log2n),O(n2) (D)O(nlog2n),O(n2)
48． 假设结点序列为{60,30,90,50,95,70,40,80}，以此构成一棵二叉排序树，则在该
二叉排序树上查找一个结点的平均查找长度为（ ）。 (A)23/8 (B)11/4 (C)9/2 (D)4
49． 下面程序段的时间复杂性的量级为（ D ）。
for(i=1;i＜＝n; i++) for(j=1;j＜＝m; j++){ c[i][j]=0;
for(k=1;k＜＝w;k++) c[i][j]+=a[i][k]*b[k][j] }
(A)O(i*j*k) (B)O(n*m*k) (C)O(n*j*k) (D)O(n*m*w)
50． 在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的
总次数为（ C ）。
(A)（n+1）/2 (B)n/2 (C)n (D)n+1
51． 利用3，6，8，12，5，7这六个值作为叶子结点的权，生成一棵哈夫曼树，该
树的深度为（ B ）。
(A)3 (B)4 (C)5 (D)6
52． 一棵二叉树的广义表表示为a(b(c,d),e(,f(g))),则得到的层次遍历序列为
第 8 页 共 100 页
（ D ）。
(A)a,b,c,d,e,f,g (B)c,b,d,a,e,g,f (C)c,d,b,g,f,e,a (D)a,b,e,c,d,f,g
53． 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算
法的时间复杂度为（ ）。(1≤i≤n+1)
(A)O(0) (B)O(1) (C)O(n) (D)O(n2)
54． 若在线性表中采用折半查找法查找元素，该线性表应该（ ）。
(A)元素按值有序 (B)采用顺序存储结构 (C)元素按值有序，且采用顺序存储结构 (D)元素按值有序，且采用链式存储结构
55． 已知一算术表达式的中缀形式为A＋B *C-D/E，后缀形式为ABC *+DE/-，其
前缀形式为（ ）。
(A)–A+B*C/DE (B)–A+B*CD/E (C)-+*ABC/DE (D)-+A*BC/DE
56． 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利
用（ ）遍历方法最合适。
(A)前序 (B)中序 (C)后序 (D)按层次
57． 对二叉排序树进行（ ）遍历，可以得到该二叉树所有结点构成的排序序列。
(A) 前序 (B)中序 (C)后序 (D)按层次
58． 具有n个顶点的有向图最多有（ ）条边。
(A)n (B)n(n—1) C n(n+1) (D)n2
59． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后
将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。 (A)插入 (B)选择 (C)shell (D)二路归并
60． 排序趟数与序列的原始状态有关的排序方法是（ ）排序法。
(A)插入 (B)选择 (C)冒泡 (D)快速
61． 下面给出的四种排序法中（ ）排序法是不稳定性排序法。
第 9 页 共 100 页
(A)插入 (B)冒泡 (C)二路归并 (D)堆
62． 一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最
左位置的对象为基准而得到的第一次划分结果为（ ）。
(A){38，46，79，56，40，84} (B){38，79，56，46，40，84} (C){40，38，46，56，79，84} (D){38，46，56，79，40，84}
63． 线性链表不具有的特点是（ ）。
(A)随机访问 (B)不必事先估计所需存储空间大小 (C)插入与删除时不必移动元素 (D)所需空间与线性表长度成正比
64． 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中
右指针域为空的结点有（ ）个。
(A)n-1 (B)n (C)n+1 (D)n+2
65． 具有65个结点的完全二叉树的高度为（ ）。（根的层次号为0）
(A)8 (B)7 (C)6 (D)5
66． 若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ ）方法比
较次数最少。
(A)直接插入排序 (B)快速排序 (C)归并排序 (D)直接选择排序
67． 在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。
(A)3 (B)2 (C)1 (D)1/2
68． 对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于
给定值，此时元素比较顺序依次为（ ）。
(A)R[0]，R[1]，R[2]，R[3] (B)R[0]，R[13]，R[2]，R[3] (C)R[6]，R[2]，R[4]，R[3] (D)R[6]，R[4]，R[2]，R[3]
69． 若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为（ ）。
(A)[(n+1)/(m+1)]-1 (B)[n/m]-1 (C)[(n-1)/(m-1)] (D)[n/(m-1)]-1
第 10 页 共 100 页