数据结构试题库

数据结构试题库

一、 单项选择题

1．下列程序段所代表的算法的时间复杂度为（ D ）。

x=n; y=0;

while (x>=(y+1)*(y+1)) y++;

(A)O(n) (B)O(n2) (C)O(log2n) (D)O(n)

2．在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置删除

元素的概率相等，则删除一个元素时线性表所需移动元素的平均次数为（ B ）。 (A) n2 (B)(n-1)/2 (C)(n+1)/2 (D)n/2

3．在一个栈顶指针为HS的链栈中插入一个*s结点时，应执行执行操作为

（ C ）。

(A)HS->next=s; (B)s->next=HS->next;HS->next=s; (C)s->next=HS;HS=s; (D)s->next=HS;HS=HS>next;

4．假设以带头结点的循环链表表示队列Q，并且队列只设一个头指针front，不设

队列尾指针。若要进队一个元素*s，则在下列程序算法的空白处应添加的操作语句是（ A ）。

void AddQueue(struct linkqueue Q) { p=Q->front;

while(p->next!=Q->front) p=p->next; } (A)p->next=s;s->next=Q->front; (B)Q->front->next=s;Q->front=s; (C)s->next=p;p->next=Q->front; (D)Q->front->next=s;s->next=p;

5．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的

结点数至少为（ B ）。

(A)2h-1 (B)2h-1+1 (C)2h-1 (D)2h-1-3

第 1 页 共 100 页

6．现有数据集{53,30,37,12,45,24,96}，从空二叉树逐个插入数据形成二叉排序树，

若希望查找此二叉树中任一结点的平均查找长度最小，则应选择下面哪个序列输入（ C ）。

(A)45,24,53,12,37,96,30 (B) 30,24,12,37,45,96,53 (C) 37,24,12,30,53,45,96 (D) 12,24,30,37,45,53,96

7．有一组数值{5,12,9,20,3}，用以构造哈夫曼树，则其带权路径长度WPL值为

（ D ）。

(A)93 (B)96 (C)123 (D)103

8．已知一个有向图G的顶点v={v1,v2,v3,v4,v5,v6}，其邻接表如下图所示，根据有

向图的深度优先遍历算法，从顶点v1出发，所得到的顶点遍历序列是（ B ）。 (A)v1,v2,v3,v6,v4,v5 (B)v1,v2,v3,v6,v5,v4 (C)v1,v2,v5,v6,v3,v4 (D)v1,v2,v5,v3,v4,v6

v1 v2 v3 v4 v5 v6 ^ ^ ^ v4 v6 ^ v3 ^ v2 v3 v6 ^ v5 v5 ^ v4 ^ 9．设有m=2n-1个关键字，假设对每个关键字查找的概率相等，查找失败的概率为

0，若采用二分法查找一个关键字，则平均查找长度为（ D ）。 (A)n-1 (B) n-n/m (C) (n-1)-n/m (D) (n-1)+n/m

10． 已知一个待散列存储的线性表{18,81,58,34,26,75,67,49,93}，散列函数为

h(k)=k，散列地址空间为0~10。若采用线性探查法解决冲突，则平均查找长度为（ A ）。

(A)5/3 (B)13/9 (C)16/9 (D)3/2

11． 下列程序段所代表的算法的时间复杂度为（ C ）。

y=n; x=1;

第 2 页 共 100 页

while(x<=y) x*=2;

(A)O(n) (B)O(n2) (C)O(log2n) (D)O(n)

12． 在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置插入

元素的概率相等，则插入一个元素时线性表所需移动元素的平均次数为（ D ）。 (A)n2 (B)(n+1)/2 (C)(n-1)/2 (D)n/2（p23）

13． 若对一个已有序的线性表最频繁的操作是查找值为x的元素(假设存在的话)，

则采用（ D ）存储方式实现查找，其算法的时间复杂度为最小。（怀疑） (A)单链表 (B)双链表 (C)单循环链表 (D)顺序表

14． 一个带头结点head的循环单链表为空的判断条件是（ C ）。

(A)head==NULL (B)head->next==NULL (C)head->next==head (D)head!=NULL

15． 若链队列HQ中只有一个结点，则队列的头指针和尾指针满足下列条件

（ D ）。

(A)HQ->rear->next==HQ->front (B)HQ->front->next==HQ->rear->next (C)HQ->front==HQ->rear (D)HQ->front->next==HQ->rear

16． 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删除结点的值，

则应执行操作为（ A ）。

(A)x=HS->data; HS=HS->next; (B)x=HS->data;HS->NEXT=NULL; (C)HS=HS->next;x=HS->data; (D)x=HS->data; HS=NULL;

17． 一棵有n个结点的满二叉树，有m个叶子结点，深度为h，那么n、m和h满

足条件（ D ）。

(A)n=m+h (B)h+m=2n (C)m=h-1 (D)n=2h-1

18． 一棵左、右子树均不为空的二叉树在先序线索化后，其空指针域数为

（ B ）。

(A)0 (B)1 (C)2 (D)不确定

19． 有一组数值{5,12,9,20,3}，用以构造哈夫曼树，则其带权路径长度WPL值为

（ C ）。

第 3 页 共 100 页

(A)49 (B)96 (C)103 (D)125

20． 在一个n个结点的二叉排序树中查找一个关键字，进行关键字比较次数最大值

为（ A ）。

(A)n (B)n/2 (C)log2n (D)n*log2n

21． 已知有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}，则下列边集合E中

（ A ）所对应的有向图没有拓扑序列。

(A) E={,,,,,,,} (B) E={,,,,,,,} (C) E={,,,,,,,,

v6>,}

(D) E={,,,,,,,}

22． 冒泡排序算法在最好情况下的时间复杂度为（ B ）。

(A)O(log2n) (B)O(n) (C)O(1) (D)O(n2)

23． 在下列内部排序方法中，排序时不稳定的，而且关键字的比较次数与记录的初

始排列次序无关的是（ D ）。

(A)快速排序 (B)冒泡排序 (C)归并排序 (D)堆排序

24． 已知一个待散列存储的线性表{18,81,58,34,26,75,67,49,93}，散列函数为

h(k)=k，散列地址空间为0~10。若采用线性探查法解决冲突，则平均查找长度为（ A）。

(A)5/3 (B)13/9 (C)16/9 (D)3/2

25． 下列程序段所代表的算法的时间复杂度为（ D ）。

i=1;j=0; while(i<=n) {

i+=j; j++;

}

(A)O(n) (B)O(n2) (C)O(log2n) (D)O(n)（怎么算？）

第 4 页 共 100 页

26． 将两个各有n个元素的有序表归并成一个有序表，在最坏的情况下，其比较次

数是（ A ）。

(A)2n-1 (B)n (C)n+1 (D)n-1

27． 若某链表中最常用的操作是在最后的一个结点之后插入一个结点或删除最后

一个结点，则采用（ D ）存储方式最节省运行时间。

(A)单链表 (B)单循环链表 (C)无头双向链表 (D)带头双向链表

28． 已知head是一个非空单链表的头指针，指针p指向单链表的最后一个结点，

若要在p之后插入一个新结点*s，并将单链表变为循环单链表，则应执行的操作是（ B ）。

(A)s->next=p->next;p->next=s; (B)s->next=head;p->next=s; (C)s->next=p->next;p->next=head; (D)s->next=p->next; s->next=p;

29． 已知用循环链表表示的队列长度为n，若只设头指针，则出队和入队一个元素

的时间复杂度分别是（ B ）。

(A)O(1)和O(1) (B)O(1)和O(n) (C)O(n)和O(1) (D)O(n) 和O(n)

30． 设链队列Q的头指针和尾指针分别为front和rear，初始时队列为空，若向队

列插入一个元素*s，则应执行的指针操作为（ C ）。 (A)Q->front->next=s;s->next=Q->rear;Q->rear=NULL; (B)s->next=Q->front;Q->rear->next=s;Q->rear=NULL; (C)Q->rear->next=s;Q->rear=s;s->next=NULL; (D)Q->front->next=s;Q->rear=s;s->next=NULL;

31． 已知一个带权图的顶点集V和边集G分别为：

V={1,2,3,4,5,6,7,8};

E={(3,1)6，(3,4)7，(3,7)5，(1,2)3，(1,4)4，(4,7)8，(4,5)4，(7,8)5，(2,6)3，(2,5)5,

(5,8)8, (5,6)5, (8,6)6},

则该图的最小生成树的权值为（ C ）。 (A)24 (B)29 (C)30 (D)31

32． 当待排序的关键字个数n很小，且初始排列为逆序时，采用下列排序方法中的

（ D ），算法的时间复杂度最小。

第 5 页 共 100 页

(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个结点的有序单链表中插入一个新结点并仍然有序，则该操作

的时间复杂度是（ D ）。

(A)O(1) (B)O(n2) (C)O(nlog2n) (D)O(n)

40． 在一个头结点为head的空循环链表中插入一个结点s，则指针s应执行操作

第 6 页 共 100 页

（D ）。

(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共有（ B ）个结点。

(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． 已知一棵二叉树的结点数据采用顺序存储结构，数组内容如下表所示，则该二

叉树的后序遍历序列为（C ）。 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的叶子结点数为（ D）。

(A)n/2 (B)(n-2)/2 (C)(n-1)/2 (D)(n+1)/2

46． 有一组数值14,21,32,15,28，用以构造huffman树，则其WPL值为（249 ）。

(A)267 (B)189 (C)110 (D)294

47． 采用折半插入排序，关键字的比较次数与移动次数分别为（ D ）。

(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个位置插入一个新元素的算

法的时间复杂度为（C ）。(1≤i≤n+1)

(A)O(0) (B)O(1) (C)O(n) (D)O(n2)

54． 若在线性表中采用折半查找法查找元素，该线性表应该（ C）。

(A)元素按值有序 (B)采用顺序存储结构 (C)元素按值有序，且采用顺序存储结构 (D)元素按值有序，且采用链式存储结构

55． 已知一算术表达式的中缀形式为A＋B *C-D/E，后缀形式为ABC *+DE/-，其

前缀形式为（ D ）。

(A)–A+B*C/DE (B)–A+B*CD/E (C)-+*ABC/DE (D)-+A*BC/DE

56． 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利

用（ C ）遍历方法最合适。

(A)前序 (B)中序 (C)后序 (D)按层次

57． 对二叉排序树进行（B ）遍历，可以得到该二叉树所有结点构成的排序序列。

(A) 前序 (B)中序 (C)后序 (D)按层次

58． 具有n个顶点的有向图最多有（ B ）条边。

(A)n (B)n(n—1) C n(n+1) (D)n2

59． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后

将其放在已排序序列的合适位置，该排序方法称为（ A ）排序法。 (A)插入 (B)选择 (C)shell (D)二路归并

60． 排序趟数与序列的原始状态有关的排序方法是（ A）排序法。

(A)插入 (B)选择 (C)冒泡 (D)快速

61． 下面给出的四种排序法中（D ）排序法是不稳定性排序法。

第 9 页 共 100 页

(A)插入 (B)冒泡 (C)二路归并 (D)堆

62． 一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最

左位置的对象为基准而得到的第一次划分结果为（ C ）。

(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 ）。

(A)随机访问 (B)不必事先估计所需存储空间大小 (C)插入与删除时不必移动元素 (D)所需空间与线性表长度成正比

64． 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中

右指针域为空的结点有（ C ）个。

(A)n-1 (B)n (C)n+1 (D)n+2

65． 具有65个结点的完全二叉树的高度为（ B）。（根的层次号为0）

(A)8 (B)7 log2n（65）＋1 (C)6 (D)5

66． 若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（A ）方法

比较次数最少。

(A)直接插入排序 (B)快速排序 (C)归并排序 (D)直接选择排序

67． 在一个无向图中，所有顶点的度数之和等于所有边数的（ B ）倍。

(A)3 (B)2 (C)1 (D)1/2

68． 对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于

给定值，此时元素比较顺序依次为（ C ）。

(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,则非叶结点的个数为（C ）。

(A)[(n+1)/(m+1)]-1 (B)[n/m]-1 (C)[(n-1)/(m-1)] (D)[n/(m-1)]-1

第 10 页 共 100 页

70． 下面关于算法说法错误的是（ B ）。

(A)算法最终必须由计算机程序实现

(B)为解决某问题的算法同为该问题编写的程序含义是相同的 (C)算法的可行性是指指令不能有二义性 (D)以上几个都是错误的

71． 以下与数据的存储结构无关的术语是（ C ）。

(A)循环队列 (B)链表 (C)哈希表 (D)栈

72． 以下数据结构中，哪一个是线性结构（ D ）。

(A)广义表 (B)二叉树 (C)稀疏矩阵 (D) 串

73． 以下那一个术语与数据的存储结构无关？（ B ）

(A)栈 (B)哈希表 (C)线索树 (D) 双向链表

74． 在下面的程序段中，对x的赋值语句的频度为（ C ）。

FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;

(A) O(2n) (B)O(n) (C)O(n2) (D)O(log2n)

75． 以下哪个数据结构不是多型数据类型（ D ）。

(A)栈 (B)广义表 (C)有向图 (D)字符串

76． 连续存储设计时，存储单元的地址（ A ）。

(A)一定连续 (B)一定不连续

(C)不一定连续 (D)部分连续，部分不连续

77． 一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后，其空链域数

为（ A ）。

(A)0 (B)1 (C)2 (D)不确定

78． 设图G采用邻接表存储，则拓扑排序算法的时间复杂度是（ B ）。

第 11 页 共 100 页

(A)O(n) (B)O(n+e) (C)O(n2) (D)O(n*e)

79． 下列排序算法中，时间复杂度为O(nlog2n)且占用额外空间最少的是（ A ）。

(A)堆排序 (B)冒泡排序 (C)快速排序 (D)SHELL排序

80． 已知数据表A中每个元素距其最终位置不远，则采用（ B ）排序算法最节省

时间。

(A)堆排序 (B)插入排序 (C)快速排序 (D)直接选择排序

81． 串是（ D ）。

(A)不少于一个字母的序列 (B)任意个字母的序列

(C)不少于一个字符的序列 (D)有限个字符的序列

82． 一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（ A ）。

(A)23415 (B)54132 (C)31245 (D)14253

83． 设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个

数为（ D ）。

(A)r-f (B)r-f+1 (C)(r-f) mod n +1 (D)(r-f+n) mod n

84． 二叉树在线索化后，仍不能有效求解的问题是（ D ）。

(A)先序线索二叉树中求先序后继 (B)中序线索二叉树中求中序后继

(C)中序线索二叉树中求中序前驱 (D)后序线索二叉树中求后序后继

85． 求最短路径的FLOYD算法的时间复杂度为（ D ）。

(A)O(n) (B)O(n+e) (C)O(n2) (D)O(n3)

86． 一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（ B ）。

(A)0 (B)1 (C)2 (D)不确定

87． 数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为

1000的连续的内存单元中，则元素A[5,5]的地址为（ A ）。

(A)1140 (B)1145 (C)1120 (D)1125

88． 在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是

（ A ）。

(A)快速排序 (B)希尔排序 (C)冒泡排序 (D)堆排序

89． 对有18个元素的有序表做折半查找，则查找A[3]的比较序列的下标依次为

（ D ）。

(A)1-2-3 (B)9-5-2-3 (C)9-5-3 (D)9-4-2-3

第 12 页 共 100 页

90． 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是

（ D ）。

(A)堆排序 (B)冒泡排序 (C)快速排序 (D)直接插入排序

91． 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已

知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（ B ）型调整以使其平衡。

(A)LL (B)LR (C)RL (D)RR

92． 下列各式中，按增长率由小至大的顺序正确排列的是（ D ）。

(A)n,n!,2n,n3/2 (B)n3/2,2n,nlogn,2100 (C)2n, logn, nlogn, n3/2 (D)2100, logn, 2n, nn

93． 若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（ A ）。

(A)s-＞next=p-＞next; p-＞next=s;

(B)p-＞next=s; s-＞next=p-＞next (C)p-＞next=s-＞next; s-＞next=p; (D)s-＞next=p;p-＞next=s-＞next;

94． 若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环

链表各设置一个指针，分别指向（ ）。

(A)各自的头结点 (B)各自的尾结点

(C)各自的第一个元素结点 (D)一个表的头结点，另一个表的尾结点

95． 栈的两种常用存储结构分别为（A ）。

(A)顺序存储结构和链式存储结构 (B)顺序存储结构和散列存储结构

(C)链式存储结构和索引存储结构 (D)链式存储结构和散列存储结构

96． 已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值

分别为8和3，则该队的当前长度为（ C ）。

(A)5 (B)6 (C)16 (D)17

97． 已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该

链串的存储密度为（ D ）。 typedef struct node{ char date[8];

struct node * next; } LinkStrNode;

第 13 页 共 100 页

(A)1/4 (B)1/2 (C)2/3 (D)3/4

98． 应用简单的匹配算法对主串s=“BDBABDABDAB”与子串t=“BDA”进行模

式匹配，在匹配成功时，进行的字符比较总次数为（ C ）。 (A)7 (B)9 (C)10 (D)12

99． 二维数组A[20][10]采用列优先的存储方法，若每个元素占2个存储单元，且

第1个元素的首地址为200，则元素A[8][9]的存储地址为（ C ）。 (A)574 (B)576 (C)578 (D)580

100． 对广义表L=((a,b),c,d)进行操作tail (head (L))的结果是（ D ）。

(A)(c,d ) (B)(d ) (C)b (D)(b)

101． 已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行

层次遍历得到的序列为（ D ）。

(A)ABCDEF (B)ABCEFD (C)ABFCDE (D)ABCDFE

102． 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算

该有向图中某个顶点出度的时间复杂度为（ A ）。

(A)O(n) (B)O(e) (C)O(n+e) (D)O(n2)

103． 在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键

字为45，89和12的结点时，所需进行的比较次数分别为（ B ）。 (A)4，4，3 (B)4， 3， 3 (C)3，4，4 (D)3，3，4

104． 下列排序方法中，最好与最坏时间复杂度不相同的排序方法是（ A ）。

(A)冒泡排序 (B)直接选择排序 (C)堆排序 (D)归并排序

105． 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概

率情况下查找成功的平均查找长度等于（ B ）。

(A)1.0 (B)2.9 (C)3.4 (D)5.5

106． 在下列各种文件中，不能进行顺序查找的文件是（ C ）。

(A)顺序文件 (B)索引文件 (C)散列文件 (D)多重表文件

107． 下面带有@标记的语句的频度(n>10)是（ ）。

for(int i=0;i

for(int j=i+1;j

(A)n*(n-1)/2 (B)n*n/2 (C) n*(n+1)/2 (D)不确定

第 14 页 共 100 页

108． 已知使用顺序表存储数据，表长为n，假设在表中的任意位置插入元素的

概率相等，则插入一个元素，平均需要移动的元素个数（ ）。 (A)(n-1)/2 (B)n/2 (C)(n+1)/2 (D)不确定

109． 在双向链表p所指结点之后插入s所指结点的操作是（ D ）。

(A)p?right=s;s?left=p;p?right?left=s;s?right=p?right;

(B)p?right=s;p?right?left=s;s?left=p;s?right=p?right; (C)s?left=p;s?right=p?right;p?right=s;p?right?left=s; (D)s?left=p;s?right=p?right;p?right?left=s;p?right=s;

110． 字符串相等的充分必要条件是（ ）。

(A)串长度相等 (B)串使用相同的存储结构

(C)串相同位置对应的字符相等 (D)A和C

111． 将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。

(A) 数组

(B) 栈 (C) 队列 (D)二叉树

112． 一个栈的入栈序列1, 2, 3, 4, 5, 则栈的不可能的输出序列是（ C ）。

(A) 12345 (B)54321 (C)32514 (D)12354

113． 设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素

个数为（ D ）。

(A)r-f (B)r-f+1 (C)(r-f) mod n +1 (D)(r-f+n) mod n

114． 某二叉树的前序遍历结点访问顺序是ABDEFCGH, 中序遍历的结点访问

顺序是DBFEAGHC, 则其后序遍历的结点访问顺序是（ B ）。

(A) DFEBHCGA (B)DFEBHGCA (C)DEFBHGCA (D)DFEHBGCA

115． 正则二叉树是只有度为0和2的结点的二叉树，已知正则二叉树的叶子结

点个数为n，则该二叉树总得结点数为（ D ）。

(A) n+1 (B)2*n (C) 2*n+1 (D)2*n-1

116． 下面关于排序的说法错误的是（ ）。

(A)快速排序、归并排序都是一种不稳定的排序方法

(B)直接插入排序和折半插入排序移动元素的次数相同 (C)简单选择排序移动元素的次数最少

(D)根据排序需要的平均时间，快速排序是目前最好的一种内部排序方法

117． 折半查找有序表（3，4，5，10，13，14，20，30），若查找元素3， 则

第 15 页 共 100 页

被比较的元素依次为（ D ）。

(A)10,20,30 (B)10,14,30 (C)13,3 (D)10, 4, 3

118． 下面关于栈和队列的说法正确的是（ C ）。

(A)栈是先进先出的线性表，队列是后进先出的线性表

(B)栈是先进先出的线性表，队列也是先进先出的线性表 (C)栈是后进先出的线性表，队列是先进先出的线性表 (D)栈是后进先出的线性表，队列也是后进先出的线性表

119． 两个各有n个元素的有序列表并成一个有序表，其最少的比较次数是

（ A ）。

(A)n (B)2n-1 (C)2n (D)n-1

120． 设循环队列中数组的下标范围是0~ n-1，f表示队首元素的前驱位置，r表

示队尾元素的位置，则队列中元素个数为（ ）。 (A)r-f (B)r-f 1 (C)(r-f 1)mod n (D)(r-f n)mod n

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的结点，则此二叉树中所包含

的结点数至少为（ B ）个（设只含根结点的二叉树的高度为1）。 (A)2h (B)2h-1 (C)2h+1 (D)h+1

124． 对一棵二叉检索树进行（ B ） 得到的结点序列是一个有序序列。

(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

第 16 页 共 100 页

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 ）。

(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

第 17 页 共 100 页

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)

第 18 页 共 100 页

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 ）。

第 19 页 共 100 页

(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 (C) 15，20，40，45

(B) 15，40，60，20 (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 ）。

第 20 页 共 100 页

do {

while (q!=NULL) {

top++; s[top]=q; [6] ; }

if (top= =0) [7] ; else {

[8] ; top--;

if (q->data

[9] ; }

else if (q->datarch; } } while (bool);

printf(―%d,%d‖,x1,x2); } [6] q=q->lch [7] bool=0 [8] q=s[top] [9] x1=q->data [10] x2=q->data

12. 已知单链表结点的存储结构如下：

struct node { int data;

struct node *next; };

这里，单链表的头指针为head, 数据域为data，指针域为next。试在下列A~J中选择一个正确答案，填入相应的空格处，分别实现下列四小题的算法功能，注意各个小题之间没有联系。

1）将单链表中值相同的多余结点删除。 void test1(struct node *head) { struct node *p,*q,*r; p=head;

while (p!=NULL) {

第 46 页 共 100 页

r=p;

(1) E while (q!=NULL) {

if (q->data==p->data) (2) I else r=q; q=q->next; }

(3) G } }

2）将值为y的结点插入到值为x的结点之后，如果值为x的结点不存在，则将其插入到单链表的表尾。

void test2(struct node *head,int x,int y) { struct node *p,*q,*r;

r=(struct node *)malloc(sizeof(struct node)); r->data=y; int sgn=0; p=head;

while (p!=NULL)&&(sgn==0) { if (p->data==x) sgn=1; (4) C p=p->next; }

if (sgn==1) (5) H else (6) J q->next=r; } }

3）假设在上述单链表结点的存储结构中增加另一个指针域prior，将该单链表改造成双向循环链表(假设该单链表中至少有一个结点)。 void test3(struct node *head) { struct node *p,*q; p=head;

while (p!=NULL) { q=p->next;

if (q!=NULL) (7) D else {

第 47 页 共 100 页

(8) F head->prior=p; break; }

p=p->next; } }

4）若采用单链表结构去存储一个堆栈，分别实现在堆栈中入栈和出栈一个元素的算法。

void test4(struct node *head,int x) { struct node *p;

p=(struct node *)malloc(sizeof(struct node)); p->data=x; p->next=head; (9) B }

int test5(struct node *head) { struct node *p; if (head!=NULL) { p=head;

(10) A x=p->data; return(x); } else exit(1); }

本题选项：

(A)head=head->next; (B)head=p; (C)q=p; (D)q->prior=p; (E)q=p->next; (F)p->next=head; (G)p=p->next; (H)r->next=p; (I)r->next=q->next; (J)r->next=NULL;

13. 已知二叉树结点的链表存储结构如下：

struct node { char data;

struct node *lch,*rch; };

第 48 页 共 100 页

这里，树结点的数据域为data，左孩子指针域为lch，右孩子指针域为rch，根结点所在链结点的指针由BT给出。试在下列A~J中选择一个正确答案，填入相应的空格处，分别实现下列两个小题的算法功能，注意各个小题之间没有联系。 1）利用中序遍历算法，查找二叉树BT中值为x的这个结点的双亲、左孩子及右孩子。

void test6(struct node *BT,char x) {

struct node *p,*q,*s[100]; struct node *x1,*x2,*x3; int top=0;

x1=x2=x3=NULL; p=BT;

while ((top!=0)||(p!=NULL)) { if (p!=NULL) while(p!=NULL) { top++; s[top]=p;

p= (11) F } else {

p=s[top];

(12) J if (p->data==x) {

(13) B =p->lch; (14) C =p->rch; } q=p;

p=p->rch;

if (p!=NULL)&&(p->data==x) (15) A =q; } } if(x1!=NULL) printf(\结点x的双亲是:%c\\n\else printf(\结点x是树根\\n\

if(x2!=NULL) printf(\结点x的左孩子是:%c\\n\else printf(\结点x无左孩子\\n\

if(x3!=NULL) printf(\结点x的右孩子是%c\\n\else printf(\结点x无右孩子\\n\

第 49 页 共 100 页

}

2）假设上述二叉树BT为一个二叉排序树，实现在该二叉排序树中插入一个结点s的算法。

void test7(struct node *BT,struct node *s) {

struct node *p,*q;

if (BT==NULL) BT=s; else {

(16) G while (p!=NULL) { q=p;

if (s->datadata) (17) D else (18) E }

if(s->datadata) (19) H else (20) I } }

本题选项：

(A)x1 (B)x2 (C)x3 (D)p=p->lch; (E)p=p->rch; (F)p->lch; (G)p=BT; (H)q->lch=s; (I)q->rch=s; (J)top--;

14. 下列程序用来统计一个非空链队列Q中结点值为素数的元素个数，请在空格处

填入正确合理的内容。 struct Nodetype {

int data;

struct Nodetype *next; };

struct LinkQueue {

struct Nodetype *front,*rear; };

int countqueue(struct LinkQueue *Q) {

struct Nodetype *p; int i,k,num=0;

p=(5) ;

第 50 页 共 100 页