数据结构试题库

更新时间：2024-02-02 23:46:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

数据结构试题库

一、单项选择题

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的以顺序结构存储的线性表中，假设在线性表的任何位置插入

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

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。若采用线性探查法解决冲突，则平均查找长度为（ C ）。

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

的时间复杂度是（）。

(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 页

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

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

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

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

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

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

（）。

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

的结点数至少为（）个（设只含根结点的二叉树的高度为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

第 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)直接插入排序 (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

(D) CBDA

135．设某完全无向图中有n个顶点，则该完全无向图中有（ A ）条边。

(A) n(n-1)/2 (B) n(n-1)

136．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C ）。

(A) 9

(B) 10

(D) 12

137．设某有向图中有n个顶点，则该有向图对应的邻接表中有（ B ）个表头结

点。

(A) n-1 (B) n

第 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

(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

151．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为

（ D ）。 (A) n

(B) e

(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

(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

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)

163．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，

度数为m的结点数为Nm，则N0=（ B ）。

第 20 页共 100 页

(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

(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

(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；

179．设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ A ）。

(A) O(n+e)

(B) O(n2) (C) O(ne)

(D) O(n3)

180．设某哈夫曼树中有199个结点，则该哈夫曼树中有（ B ）个叶子结点。

(A) 99

(B) 100

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

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

190．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ C ）。

(A) 20

(B) 256

(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;

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

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

(D) 5

198．设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为

3的结点，则该三叉链权中有（ C ）个度数为0的结点。 (A) 5

(B) 6

(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

(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 页

208．设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数

有1个，度数为1的结点数有2个，那么度数为0的结点数有（ C ）个。 (A) 4

(B) 5 (C) 6

(D) 7

209．设完全无向图中有n个顶点，则该完全无向图中有（ A ）条边。

(A) n(n-1)/2

(B) n(n-1)

(D) (n-1)/2

210．设顺序表的长度为n，则顺序查找的平均比较次数为（ C ）。

(A) n

(B) n/2 (C) (n+1)/2

(D) (n-1)/2

211．设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法

查找值为24的元素需要经过（ C ）次比较。 (A) 1

(B) 2 (C) 3 (D) 4

212．设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，

则其平均查找长度为（ D ）。 (A) 6

(B) 11 (C) 5 (D) 6.5

213．设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，

则下列属于该有向图G的一种拓扑排序序列的是（ A ）。 (A) 1，2，3，4

(B) 2，3，4，1

(D) 1，2，4，3

214．设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组

记录关键字生成的二叉排序树的深度为（ A ）。 (A) 4

(B) 5 (C) 6 (D) 7

215．下列程序段的时间复杂度为（ A ）。

i=0，s=0； while (s

(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)

216．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列

（ D ）存储方式最节省运算时间。 (A) 单向链表 (C) 双向链表

(B) 单向循环链表 (D) 双向循环链表

第 26 页共 100 页

217．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，

指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ B ）。

(A) s->next=p->next；p->next=-s；

(B) q->next=s； s->next=p；

218．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列

为（ B ）。

(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1 (C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3

219．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右

的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ B ）。 (A) 10

(B) 19

(D) 55

220．设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，

Nm个度数为m的结点，则该树中共有（ D ）个叶子结点。

mmmm (A)

?(i?1)Ni?1i (B)

?Ni?1i (C)

?Ni?2i1?

(D)

?(i?1)Ni?2i

221．二叉排序树中左子树上所有结点的值均（ A ）根结点的值。

(A) <

(B) > (C) = (D) !=

222．设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集

合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ D ）。 (A) 129 (B) 219

(D) 229

223．设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字

映射到HASH表中需要做（ D ）次线性探测。 (A) n2 (B) n(n+1)

(D) n(n-1)/2

224．设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，

则这棵二叉中共有（ C ）个结点。

第 27 页共 100 页

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

225．设一组初始记录关键字的长度为8，则最多经过（ B ）趟插入排序可以得

到有序序列。 (A) 6

(B) 7 (C) 8 (D) 9

226．设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，

X)，则按字母升序的第一趟冒泡排序结束后的结果是（ D ）。 (A) F，H，C，D，P，A，M，Q，R，S，Y，X (B) P，A，C，S，Q，D，F，X，R，H，M，Y (C) A，D，C，R，F，Q，M，S，Y，P，H，X (D) H，C，Q，P，A，M，S，R，D，F，X，Y

227．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位

置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。（ C ）

(A)688 (B) 678 (C)692 (D) 696

228．若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，

现进行二分查找，则查找A［3］的比较序列的下标依次为（ D ）。 (A) 1，2，3 (C) 9，5，3

(B) 9，5，2，3 (D) 9，4，2，3

229．对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（ C ）。

(A) O（1） (B) O（n） (C) O（1og2n） (D) O（n2）

230．对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用 H

（K）=K %9作为散列函数，则散列地址为1的元素有（ D ）个。 (A) 1 (B) 2 (C) 3 (D) 4

231．设有6个结点的无向图，该图至少应有（ A ）条边才能确保是一个连通图。

(A) 5 (B) 6 (C) 7 (D) 8

232．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈

夫曼树中总共有（ B ）个空指针域。

第 28 页共 100 页

(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 二、判断题

1．数据项是数据的最小单位。（） 2．链表的每个结点都恰好有一个指针。（）

3．同一组不重复输入序列执行不同的入栈出栈组合操作，所得结果也可能相同。

（）

4．改进的KMP算法中，字符串‖abaaaba‖的nextval数组值是0101110。（） 5．用六叉链表表示30个结点的六叉树，则树中共有151个空指针。（） 6．数组是一种线性结构，因此只能用来存储线性表。（）

7．若有向图不存在回路，即使不用访问标志位同一结点也不会被访问两次。（） 8．若装填因子a为1，则向散列表中散列元素时一定会产生冲突。（） 9．若把堆看成是一个完全二叉树，则该树一定是一棵排序二叉树。（） 10．外排中使用置换选择排序的目的，是为了增加初始归并段的长度。（） 11．抽象数据类型与计算机内部表示和实现无关。（Y ） 12．线性表的插入和删除总是伴随着大量数据的移动。（ N ） 13．队列在程序调用是必不可少，因此递归离不开队列。（ N ） 14．字符串‘aababaaaba‘的改进函数nextval数组值是0020200320。(Y )

15．二叉树中有双子女的父结点，在中序遍历中后继一定是其中一个子女结点。

（ N ）

16．不用递归就不能实现二叉树的前序遍历。（ N ） 17．若有向图有n个顶点，则其强连通分量最多有n个。(Y ) 18．平衡二叉树一定是一棵完全二叉树。（ N ）

19．若某内部排序算法不稳定，则该算法没有使用价值。（ N ）

第 29 页共 100 页

20．倒排文件的目的是为了多关键字查找。(Y )

21．已知指针curr指向链表中的某结点，执行语句curr=curr->next；不会删除该链

表中的结点。 ( )

22．若二叉树的叶结点数为1，则其高度等于结点数(仅含根结点的二叉树高度为

1)。（）

23．按中序周游二叉树时，某个结点的直接后继是它的右子树中第一个被访问的

结点。 ( )

24．完全二叉树的某结点若无左孩子，则它必是叶结点。 ( )

25．向二叉检索树中插入一个新结点，需要比较的次数不可能大于此二叉树的高

度。 ( )

26．对一个堆按层次周游，一定能得到一个有序序列。 ( )

27．一棵树中的叶子结点数一定等于其对应的二叉树中的叶子结点数。 ( ) 28．将一棵树转换为二叉树表示后，该二叉树的根结点没有右子树。 ( ) 29．任何有向图的结点都可以排成拓扑序列，而且拓扑序列不唯一。 ( ) 30．快速排序在最差情况下的时间复杂度是0(n2)，此时它的性能并不比冒泡排序

更好。 ( )

31． AVL树的任何子树都是AVL树。（ Y）

32．用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（ N） 33．霍夫曼树一定是满二叉树。（ Y） 34．栈是一种线性结构。（Y ）

35． B＋树既适于随机检索，也适于顺序检索。（N ） 36．记录是数据处理的最小单位。（）

37．数据的逻辑结构是指数据的各数据项之间的逻辑关系。( ) 38．算法的优劣与算法描述语言无关，但与所用计算机有关。（） 39．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( Y )

第 30 页共 100 页

40．算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描

述，则算法实际上就是程序了。（）

41．数据的物理结构是指数据在计算机内的实际存储形式。( Y ) 42．数据结构的抽象操作的定义与具体实现有关。（）

43．在顺序存储结构中，有时也存储数据结构中元素之间的关系。（） 44．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（） 45．数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独

立。( Y )

46．数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.

（）

47．数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的

运算三个方面。 (Y )

48．线性表中的每个结点最多只有一个前驱和一个后继。(Y )

49．线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接

存储。 ( )

50．栈和队列逻辑上都是线性表。 ( Y)

51．单链表从任何一个结点出发，都能访问到所有结点。( ) 52．设串S的长度为n, 则S的子串个数为n(n+1)/2。 (Y ) 53．一般树和二叉树的结点数目都可以为0。 (Y )

54．（101，88，46，70，34，39，45，58，66，10）是堆。 ......(Y ) 55．将一棵树转换成二叉树后，根结点没有左子树。( ) 56．用树的前序遍历和中序遍历可以导出树的后序遍历。 ( Y)

57．即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合

操作，所得的输出序列也一定相同。( )

58．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离很较近。 (Y )

第 31 页共 100 页

59．数据的基本单位是数据项。 ( )

60．带权的无向连通图的最小生成树是唯一的。 ( )

61．数组元素之间的关系，既不是线性的，也不是树形的。 ( )

62．对于有n个对象的待排序序列进行归并排序，所需平均时间为O（n log2n）。 (Y ) 63．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。 ( Y) 64．在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情

况应当特殊处理。 ( )

65．线性表采用顺序存储表示时，必须占用一片连续的存储单元。 (Y ) 66．由树转化成二叉树，其根的右子女指针总是空的。 ( Y) 67．直接选择排序是一种稳定的排序方法。 ( )

68．装载因子是散列表的一个重要参数，它反映了散列表的装满程度。(Y ) 69．若一个栈的输入序列为123?n，其输出序列的第一个元素为n，则其输出序列

的每个元素ai一定满足ai =n-i+1。(i=1,2,...,n) （Y）

70．二叉树中的叶子结点就是二叉树中没有左右子树的结点。（N）

71．一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。（N） 72．删除二叉排序树中的一个结点，再重新插入上去，一定能得到原来的二叉排序

树。（N）

73．线性表就是顺序表。（N）

74．若一棵树中某结点的度为1，则该结点仅有一棵子树。（Y）

75．所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。（N） 76． AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。

（N）

77．若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反。（Y） 78．在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。（N）

第 32 页共 100 页

79．对B-树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的

最小关键字一定都在非叶结点的最下层。（Y）

80．若一个连通无向图的以顶点1为起点的深度遍历序列唯一，则可唯一确定该

图。（Y）

81．若一个有向图的以顶点1为起点的深度遍历序列唯一，则可唯一确定该图。（N） 82．在数据表基本有序时，冒泡排序算法的时间复杂度一定接近O(n)。（N） 83．设指针p指向单链表中的一个结点，则语句序列u:=p^.next; u:=u^.next将删除

一个结点。（N）

84．线性表的长度是线性表所占用的存储空间的大小。（N） 85．双循环链表中，任意一结点的后继指针均指向其逻辑后继。（N） 86．在对链队列做出队操作时，不会改变front指针的值。（N） 87．如果两个串含有相同的字符，则说它们相等。（N）

88．如果二叉树中某结点的度为1，则说该结点只有一棵子树。（Y） 89．已知一棵树的先序序列和后序序列，一定能构造出该树。（N）

90．图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。

（Y）

91．图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。（N） 92． 9.对一个堆按层次遍历，不一定能得到一个有序序列。（Y）

93． 10.直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。

（Y）

94．如果两个串含有相同的字符，则这两个串相等。（N ）

95．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。

（N ）

96．在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与

表中元素个数有关，而且与每一块中元素个数有关。（ Y）

第 33 页共 100 页

97．在顺序表中取出第i个元素所花费的时间与i成正比。（N ） 98．在栈满情况下不能作进栈运算，否则产生“上溢”。 (Y ）

99．二路归并排序的核心操作是将两上有序序列归并为一个有序序列。（Y ） 100．对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，

即可访问图的每个顶点.（N ）

101．二叉排序树或者是一棵空二叉树，或者是具有下列性质的二叉树：若它的

左子树非空，则根结点的值大于其左孩子的值;若它的右子树非空，则根结点的值小于其右孩子的值。（N ）

102．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方

向移动，则该算法是不稳定的。（ N）

103．一个有向图的邻接表和逆邻接表中表结点的个数一定相等。（Y ） 104．算法与程序的主要区别是算法满足有穷性",并且算法不一定用机器可执行

的程序设计语言书写。（Y ）

105．某线性表采用顺序存储结构",元素长度为4",首地址为100",则下标为12

的",第13 个",元素的存储地址为148。（Y ）

106．在任何一种线性链表上都无法进行随机访问。（ N） 107．顺序栈是一种规定了元素进栈顺序的栈。（ N） 108．循环列表中每一个元素都有后继。（Y ）

109．树的先根遍历与该树对应二叉树的前序遍历结果不同。（ N） 110．任何有向网络",AOV 网络",拓扑排序的结果是唯一的。（ N） 111．无向图中的连通分量定义为无向图的极大连通子图。（Y ）

112．删除一个二叉树中的一个结点",再重新插入上去",一定能得到原来的二叉

排序树。（ N）

113．数据结构包括数据间的逻辑结构",数据的存储方式和数据的运算三个方面

的内容。（Y ）

第 34 页共 100 页

114．在动态单向链表中",每个结点总是占用一片连续的内存空间。（ N） 115．高级语言中通常利用“递归工作栈”来处理递归。（Y ） 116．中缀表示式",a+b",*(c+d)的后缀形式为ab+cd+*。（Y ） 117．栈和队列都不适合用散列存储法存储。（ N）

118．广义表的深度与广义表中含有多少个子表元素有关。（Y ）

119．如果树用二叉树链表表示",则判断某个结点是不是树叶的条件是该结点左

",右两个指针域的值都为空。（Y ）

120．一组关键码已完全有序时",最快的排序方法是快速排序。（Y ） 121． n 个结点的无向图最多有n*(n-1)/2 条边。（Y ）

122．线性结构中的结点按前驱",后继关系可以排成一个线性序列。（Y ） 123．在动态单向链表中",每个结点总是占用一片连续的内存空间。（ N） 124．算法的有穷性是指一个算法无论在什么情况下都应在执行有穷步后结束。

（Y ）

125．后缀表达式ABC+*的中缀形式为A*",B+C",。（Y ）

126．对顺序栈进行插入",删除操作",不涉及元素的前后移动问题。（ N） 127．广义表的长度是广义表中元素的个数。（Y ）

128．在任何一棵完全二叉树中",叶结点的个数或者和分支结点一样多，或者只

比分支结点多一个。（Y ）

129．直接选择排序是一种稳定的排序方法。（ N） 130． n 个顶点的生成树中有n-1 条边。（Y ）

131．有向图的邻接表和逆邻接表中表结点的个数不一定相等。(错 ) 132．对链表进行插入和删除操作时不必移动链表中结点。(对 ) 133．子串“ABC”在主串―AABCABCD”中的位置为2。(对 )

134．若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该

第 35 页共 100 页

二叉树的先序遍历序列中的最后一个结点。(对 )

135．希尔排序算法的时间复杂度为O(n2)。(错 )

136．用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无

关而与图中边数有关。(错 )

137．中序遍历一棵二叉排序树可以得到一个有序的序列。(对 )

138．入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情

况。(对 )

139．顺序表查找指的是在顺序存储结构上进行查找。（错） 140．堆是完全二叉树，完全二叉树不一定是堆。（对） 141．调用一次深度优先遍历可以访问到图中的所有顶点。（错）

142．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。

（对）

143．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（对） 144．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（对） 145．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。

（错）

146．层次遍历初始堆可以得到一个有序的序列。（错）

147．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（对） 148．线性表的顺序存储结构比链式存储结构更好。（错） 149．中序遍历二叉排序树可以得到一个有序的序列。（对） 150．快速排序是排序算法中平均性能最好的一种排序。（对）

151．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”

情况。（对）

152．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（对） 153．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为

第 36 页共 100 页

O(log2n)。（对）

154．完全二叉树中的叶子结点只可能在最后两层中出现。（对） 155．哈夫曼树中没有度数为1的结点。（对）

156．对连通图进行深度优先遍历可以访问到该图中的所有顶点。（对） 157．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（对） 158．由树转化成二叉树，该二叉树的右子树不一定为空。（错） 159．线性表中的所有元素都有一个前驱元素和后继元素。（错） 160．带权无向图的最小生成树是唯一的。（错）

161．如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。

（对）

162．设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。

（错）

163．分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字

可能存在的块号，然后再在相应的块内进行顺序查找。（对）

164．二维数组和多维数组均不是特殊的线性结构。（错）

165．向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。

（错）

166．如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。

（对）

167．非空的双向循环链表中任何结点的前驱指针均不为空。（对）

168．不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时

间复杂度均为O(n)。（对）

169．图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶

点是否被访问过。（对）

170．稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。

第 37 页共 100 页

（对）

171．数据元素是数据的最小单位。（对）

172．当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执

行时间最省。（）

173．数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、

删除等操作。（）

174．在树中，如果从结点K出发，存在两条分别到达K'，K\的长度相等的路径，

则结点K'和k\互为兄弟。（）

175．最佳两叉排序树的任何子树都是最佳的。（）

176．算法和程序没有区别，所以在数据结构中两者是通用的。（） 177．顺序存储方式只能用于存储线性结构。（）

178．在线性表链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

（）

179．如果某种排序算法是不稳定的，则该算法没有实际意义。（） 180．当两个字符出现的频率相同时，则其哈夫曼编码也相同。（）

三、程序选择填空

1.下列程序的算法是统计一个链队列HQ的结点个数。试在下列(A)~(H)选项中选择

正确语句填入各空白处。

int count(structure LinkQueue *HQ) {

struct LinkQueue *p; n=0;

(1) B ; while ( (2) G ) { n++; p=p->next; }

第 38 页共 100 页

return(n); }

(A)p=HQ->front (B)p=HQ->front->next (C)p=HQ->rear (D)p=HQ->rear->next (E)p!=NULL (F)p!=HQ->front (G)p!=HQ->rear (H)p->next!=HQ->front

2.下列程序的算法是在一个带头结点的单链表为尾端增加一个新结点，并将单链表

改造成循环链表。试在下列(A)~(H)选项中选择正确语句填入各空白处。 void add(struct node *head, int x) {

struct sequence *p,*q,*head;,*s;

s=(struct node *)malloc(sizeof(struct node)); s->data=x; p=head->next; q=head;

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

(4) A ; }

(A)q->next=s (B)p->next=s (C)p=s

(D)q=s (E)p->next=head (F)s->next=head (G)p=head (H)q=head

3.下列程序的算法是将一个已知的单向链表改造成双向链表，即根据单向链表中的

*next指针域，设置*prior指针域的值。试在下列(A)~(H)选项中选择正确语句填入各空白处。

void add(struct node *head) {

struct node *p,*q; p=head; q=head->next; while(q!=NULL) { (5) G ; p=q;

(6) A ;

第 39 页共 100 页

} }

(A)q=q->next (B)p=p->next (C)p=q->next (D)q->next=p (E)p->prior=q (F)p=q->prior (G)q->prior=p (H)q=p->prior

4.下列程序的算法是在一个已经中根线索化的二叉树上检索某结点的前趋结点。试

在下列(A)~(H)选项中选择正确语句填入各空白处。 struct nodex *inpre(struct nodex *p) {

if (p->ltag==1) q=p->lch; else {

(7) B ; while (r->rtag!=1) - (8) C ; q=r; } return(q); }

(A)r=p->rch (B)r=p->lch (C)r=r->rch (D)r=r->lch (E)r=q->rch (F)r=q->lch (G)q=p->rch (H)q=p->lch

5.下列程序是从一维数组A[n]中折半查找关键字为K的元素的递归算法，若查找成

功则返回对应元素的下标，否则返回-1。试在下列(A)~(H)选项中选择正确语句填入各空白处。

int Binsch(ElemType A[], int low, int high, KeyType K ) {

int low,high; if (low<=high) {

int mid=(low+high)/2; if (K==A[mid].key) return mid; else if (K

else return -1;

第 40 页共 100 页

}

(A)Binsch(A,mid+1,low,K) (B)Binsch(A,mid-1,low,K) (C)Binsch(A,mid+1,high,K) (D)Binsch(A,mid-1,high,K) (E)Binsch(A,low,mid+1,K) (F)Binsch(A,low,mid-1,K) (G)Binsch(A,high,mid+1,K) (H)Binsch(A,high,mid-1,K)

6.下列程序采用单链表作为存储结构，实现直接插入排序。已知单链表第一个结点

为h。试在下列(A)~(T)选项中选择正确语句填入各空白处。 struct node { int key;

struct node *next; }; void stinsort(struct node *h) {

struct node *p,*q,*r,*s; int t;

if (h==NULL) return; (11) E ; while(p!=NULL) { q=h;

while((q!=p)&&( (12) T )) { (13) C ; q=q->next; } (14) P ; if(p!=q){ r->next=p; q->next=p->next; (15) M ; }

p=s; } }

(A)r=q->next (B)q=r->next (C)r=q (D)r=p->next (E)p=h->next (F)q=h->next (G)p=h (H)q=h (I)q->next=s (J)p->next=s (K)s=p (L)q->next=p (M)p->next=q (N)s=q->next (O)s=q (P)s=p->next

第 41 页共 100 页

(Q)r->key>q->key (R)r->keykey (S)q->key>p->key (T)q->keykey

7.下列程序用来生成一个带头结点的单链表，并将字符串str中的每一个字符存放到

该单链表中去，要求单链表中每个结点存放4个字符。 struct node { char data[4];

struct node *next; };

void strqueue(char str[]) {

struct node *head,*p,*q; int i,j=0;

head=(struct node *)malloc(sizeof(struct node)); head->next=NULL; （1） =head; for (i=0; str[i]!=‘\\0‘; i++) { if(j==0) {

p=(struct node *)malloc(sizeof(struct node)); (2) =str[i]; j=1;

p->next=NULL; (3) ; q=p; } else {

(4) ; j++; if(j>3) j=0; } } }

q=head; p->data[0] q=>next=p

p->data[j]=str[i]

8.下列程序从哈希表中删除一个关键字为k的记录，假设所用哈希函数为HT，解决

第 42 页共 100 页

冲突的方法为链地址法。 struct node {

int key;

struct node *next; }HT[m];

void deletehash(struct node HT[],int k) {

struct node *p,*q,*r; j= （5） ; if(HT(j).key==0)

printf(\ else if(HT(j).key==k) {

if(HT(j).next==NULL) （6） ;

else {

q=HT(j).next;

while( （7） ) {

r=q; q=q->next; }

if(q!=NULL) {

（8） ; printf(\ free(q); }

else printf(\

} } }

k%p

HT[j].key=0

(q!=NULL)&&(q->key!=k) r->next=q->next;

9.已知Q是一个非空队列，S是一个栈。下列程序算法，仅用以下队列和栈的ADT

函数和少量工作变量，将队列Q中的所有元素逆置。栈的ADT函数有：

makeEmpty(s:stack); 置空栈

push(s:stack; value:datatype); 新元素value进栈 pop(s:stack):datatype; 出栈，返回栈顶值 isEmptyS(s:stack):boolean; 判栈空否

第 43 页共 100 页

队列的ADT函数有

enQueue(q:queue;value:datatype); 元素value进队 deQueue(q:queue):datatype; 出队列，返回队头值 isEmptyQ(q:queue):boolean; 判队列空否

void SetReverse(queue s) {

datatype x; stack s;

makeEmpty(s);

while (not isEmptyQ(q)) { x= (9) ;

(10) ; }

while (not isEmptyS(s)) { (11) ; (12) ; } }

deQueue(q) push(s,x) x:=pop(s) deQueue(q,x)

10. 下列程序从哈希表中查找一个关键字为k的记录，若关键字为k的记录不存在，

则将其插入其中。假设所用哈希函数为HT，解决冲突的方法为链地址法。请在空格处填入正确合理的内容。 struct node { int key;

struct node *next; } HT[m];

void linkhash(struct node HT[], int k, int p) {

struct node *q,*r,*s; j=k%p;

if (HT[j].key= =0) { HT[j].key=k;

第 44 页共 100 页

[1] ; }

else if (HT[j].key= =k) printf(―found! ], ]‖,j,k);

else {

q= [2] ; while(q!=NULL)&&(q->key!=k) { r=q;

[3] ; }

if ( [4] ) {

s=(struc node *)malloc(sizeof(struct node)); s->key=k; s->next=NULL; [5] ; }

else printf(―found! ], ]‖,j,k); } }

[1] HT[j].next=NULL [2] HT[j].next [3] q=q->next [4] q= =NULL [5] r->next=s

11. 已知二叉树中结点的数值域之值为整型，利用二叉树的中序非递归遍历算法，

要求经过一次遍历计算得到二叉树中结点数值域之值的最小值和次小值。请在空格处填入正确合理的内容。 struct nodex { char data,

struct nodex *lch,rch; } {

int x1,x2; x1=32767; x2=32767;

p=t; q=p; top=0; bool=1;

第 45 页共 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\