数据结构习题及答案

第1章 数据结构

一、选择题

1.算法指的是（）。

A计算机程序 B解决问题的计算方法

C排序方法 D解决问题的有限运算序列

2.在数据的树形结构中，数据元素之间为（ ）的关系。 A 0:0 B 1:1 C 1:n D m:n

3.数据的存储结构包括顺序、链接、散列和（ ）4种基本类型。 A索引 B数组 C集合 D向量 4.一个数组元素a[i]与（ ）的表示等价。

A &a+i B *(a+i) C *a+i D a+i

5.若只需要利用形参间接访问实参指针所指向的对象，而形参本身具有相应的存储空间，则应把形参变量说明为（ ）参数。 A指针 B引用 C值 D指针引用

6.若只需要利用形参实现对实参值的拷贝，函数体操作形参时与实参无关，则应把形参变量说明为（ ）参数。

A指针 B引用 C值 D指针引用 7.下面程序的时间复杂性的量级为（）。 int i=0，s1=，s2=0； while（i++

else s2+=i; }

A.O(1) B.O(1bn) C.O（n） D.O(2n) 8.下面程序段的时间复杂度为（ ）。 for(int i=0;i

a[i][j]=i*j;

A.O(m2) B.O(n2) C.O(m+n) D.O(m*n)

9.执行下面程序段时，S语句的执行次数为（）。 for(int i=1;i<=n;i++) for(int j=1,j<=i;j++)

S;

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

10.在一个长度为n的顺序存储结构的线性表中，向第i个元素（1≤i≤n+1）位置插入一个元素时，需要从后向前依次后移（）个元素。

A.n-i B.n-i+l C.n-i-l D.i

11. 在一个长度为n的顺序存储结构的线性表中，删除第i个元素（1≤i≤n+1）时，需要从前向后依次后移（）个元素。

A.n-i B.n-i+l C.n-i-l D.i

12.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。

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

13.在一个顺序表的表尾插入一个元素的时间复杂度为（）。

A. O(n) B. O(1) C. O(n*n) D. O(lbn)

14.在一个顺序表中的任何位置插入一个元素的时间复杂度为（）。

A. O(n) B. O(n/2) C. O(1) D. O(n2)

15.在一个单链表中删除p所指向结点的后继结点时，其算法的时间复杂度为（）。 A. O(n) B. O(n/2) C. O(1) D. O(n2)

16.线性表的链式存储比顺序存储更有利于进行（）操作。 A.查找 B.表尾插入和删除

C.按值插入和删除 D.表头的插入和删除

17.线性表的顺序存储比链式存储更有利于进行（）操作。 A.查找 B.表尾插入和删除 C.按值插入和删除 D.表头的插入和删除

18.在一个单链表中，若要在P所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值.

A.1 B.2 C.3 D.4

19.在一个带头结点的循环双向链表中，若要在P所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。

A.2 B.3 C.4 D.6

20.在一个表头指针为ph的单链表中，若要向表头插入一个由指针p指向的结点，则应执行（）操作。

A. ph=p; p->next=ph; B. p->next=ph; ph=p;

C. p->next=ph; p=ph; D. p->next=ph->next; ph->next=p; 21.在一个表头指针为ph的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）操作。

A. q->next=p->next; p->next=q; B. p->next=q->next; q=p;

C. q->next=p->next; p->next=q; D. p->next=q->next; q->next=p;

22.在一个单链表HL中，若要删除由指针q所指向结点的后继结点（若存在的话），则执行（）操作。

A. p=q->next; p->next=q->next; B. p=q->next; q->next=p;

C. p=q->next; q->next=p->next; D. q->next=q->next->next; q->next=q;

23.在一个带头结点的循环双向链表中，若要在指针p所指向的结点之后插入一个q指针所指向的结点，则需要对q->next赋值为（）。 A. P->prior B. p->next

C. p->next->next D.p->prior->prior

24.在一个带头结点的循环双向链表中，若要在指针p所指向的结点之前插入一个q指针所指向的结点，则需要对p->prior->next赋值为（）。

A. q B. p C. p->next D. p->prior

25. 在一个带头结点的循环双向链表中，若要删除指针p所指向的结点则执行（）操作。 A. p->prior->next=p->next; p->next->prior=p->prior; B. p->next->prior=p; p->next=p->next->next; C. p->prior->next=p; p->next=p->next->prior;

D. p=p->next; p->prior->next=p->prior; 26.栈的插入和删除操作在（）进行。

A. 栈顶 B. 栈底C. 任意位置D. 指定位置

27.当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入

一个元素时，首先应执行（）语句修改top指针。

A.top++ B.top-- C.top=0 D.top=N-1

28.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top=N+1表示栈空，该数组所存储的栈的最大长度为N，则表示栈满的条件为（）。 A.top==1 B.top==-1 C.top=0 D.top=N-1

29. 假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（）。 A.a[--top]=x B.a[top--]=x C.a[++top]=x D.a[top++]=x

30. 假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作为（）。

A return a[--top] B return a[top--] C return a[++top] D return a[top++] 31.假定一个链式栈的栈顶指针用top表示，该链式栈为空的条件（）。

A.top！=NULL; B. top==top->next; C. top== NULL; D. top！= top->next;

32.假定一个链式栈的栈顶指针用top表示，每个结点结构为,当p所指向的结点进栈时，执行的操作为（）。

A. p->next=top; top=top->next; B. top=p; p->next=top;

C. p->next=top->next; top->next=p; D. p->next=top; top=p;

33.假定一个链式栈的栈顶指针用top表示，每个结点结构为,退栈时所执行的操作为（）。 A.top->next=top；B.top=top->data;

C.top=top->next; D. top->next=top->next->next;

34.若让元素1，2，3，4依次进栈，则出栈次序不可能出现（ ）的情况。 A.3，2，1，4 B.2，1，4，3 C.4，3，2，1 D.1，4，2，3.

35.在一个顺序循环队列中，队首指针指向队首元素的（）位置。 A前一个 B后一个 C当前 D最后

36.当利用大小为N的数组循环存储一个队列时，该队列的最大长度为（）。 A.N-2 B.N-1 C.N D.N+1

37.从一个顺序循环队列中删除元素时，首先需要（）。 A.前移队首指针 B.后移队首指针

C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素

38.假定一个顺序循环队列的队首和队尾指针分别用f和r表示，则判断队空的条件为（）。 A.f+1==r B.r+1==f C.f==0 D.f==r 39.假定一个顺序循环队列存储于数组a[N]，其队首和队尾指针分别用f和r表示，则判断队满的条件为（）。 A.（r-1）%N==f B.（r+1）%N==f C.（f-1）%N==r D.（f+1）%N==r 40.假定利用数组a[N]循环顺序存储一个队列，其队首和队尾指针分别用f和r表示，并已知队列未满，当元素x入列时所执行的操作为（）。

A.a[++r%N]=x B.a[r++%N]=x C.a[--r%N]=x D.a[r--%N]=x 41.假定利用数组a[N]循环顺序存储一个队列，其队首和队尾指针分别用f和r表示，并已知队列未空，当出列并返回队首元素时所执行的操作为（）。

A.return a[++r%N] B.return a[--r%N] C.return a[++f%N] D.return a[f++%N]

42.假定一个链式队列的队首和队尾指针分别为front和rear，则判断队空的条件为（）。 A.front==rear B.front！=NULL C.rear！=NULL D.front==NULL 43.假定一个链式队列的队首和队尾指针分别为front和rear，每个结点结构为,当出列时所进

行的操作为（）。

A.front=front->next B.rear=rear->next C.front->next =rear；rear=rear->next D.front=front->next；front->next =rear；

44.假定一个带头结点的循环链式队列的队首和队尾指针分别用front和rear表示，则判断对空的条件为（）。

A.front=rear->next B.rear==NULL C. front==NULL D. front ==rear

45.假定一个链式队列的队首和队尾指针分别为front和rear，每个结点结构为包含值域data和指针域next,则使p所指结点入列所执行的操作为（）。 A.p->next=NULL；rear=rear->next=p； B.p->next=rear->next；rear=rear->next=p； C.p->next=front；front=p；

D.p->next=front->next；front->next=p；

46.在一个长度为N的数组空间中，循环顺序存储着一个队列，该队列的队首和队尾指针分别用front和rear表示，则该队列中数组元素个数为（）。 A.（rear-front）%N B.（rear-front+N）%N

C.（rear+N）%N D.（front+N）%N

47.二维数组A[12,10]采用行优先存储，每个数据元素占用4个存储单元，该数组的首地址（即A[0，0]的地址）为1200，则A[6，5]的地址为（）。 A.1400 B.1404 C.1372 D.1460

48.有一个M×N的矩阵A，若采用行优先进行顺序存储，每个元素占用8个字节，则Aij(1≤i≤M,1≤j≤N)元素的相对字节地址（相对首元素地址而言）为（）。 A.（（i-1）×N+j）×8 B.（（i-1）×N+j-1）×8 C.（i×N+j-1）×8 D.（（i-1）×N+j+1）×8

49.有一个N×N的下三角矩阵A，若采用行优先进行顺序存储，每个元素占用k个字节，则Aij(1≤i≤N,1≤j≤i)元素的相对字节地址（相对首元素地址而言）为（）。 A.（i×（i+1）/2+j-1）×4 B.（i×i/2+j）×4 C.（i×（i-1）/2+j-1）×4 D.（i×（i-1）/2+j）×4 50.树中所有结点的度等于所有结点数加（）。 A.0 B.1 C.-1 D.2 51.在一棵树中，（）没有前驱结点。

A.树枝结点 B.叶子结点 C.树根结点 D.空结点 52.在一棵树中，每个结点最多有（）个前驱结点。 A.0 B.1 C.2 D.任意多个

53.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A.2 B.1 C.0 D.-1

54.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。 A.n B.n-1 C.n+1 D.2n

55.在一棵具有n个结点的二叉树的第i层上，最多具有（）个结点。 A.2i B.2i+1 C.2i-1 D.2n

56.在一棵深度为h的完全二叉树中，所含结点个数不小于（）。 A.2h B.2h+1 C.2h-1 D.2h-1

57.在一棵深度为h的完全二叉树中，所含结点个数不大于（）。 A.2h B.2h+1 C.2h-1 D.2h-1

58.在一棵具有35个结点的完全二叉树中，该树的深度为（）。

A.6 B.7 C.5 D.8

59.在一棵完全二叉树中，若编号为i的结点存在左孩子，则左孩子结点编号为（）。 A.2i B.2i-1 C.2i+1 D.2i+2

60.在一棵完全二叉树中，若编号为i的结点存在右孩子，则右孩子结点编号为（）。 A.2i B.2i-1 C.2i+1 D.2i+2

61.在一棵完全二叉树中，对于编号为i（i>1）的结点其双亲结点的编号为（）。 A.（i+1）/2 B.（i-1）/2 C.i%2 D.i/2

62.有如图1.1所示的一棵二叉树，则该二叉树所含单支结点数为（）。 A.2 B.3 C.4 D.5

63.有如图1.2所示的一棵二叉树，则该二叉树的中序遍历序列为（）。 A. ABCDEFG B. CDBGFEA C. CBDAEGF D. ABECDFG

64.有如图1.2所示的一棵二叉树，则该二叉树的先序遍历序列为（）。 A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG

65.有如图1.2所示的一棵二叉树，则该二叉树的后序便利序列为（）。 A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG 66.利用n个值生成的哈夫曼树中共有（）个结点。

A.n B.n+1 C.2n D.2n-1

67.利用3，6，8，12这4个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（）。

A.55 B.29 C.58 D.38

68.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有的入度数之和为（）。 A.s B.s-1 C.s+1 D.n

69.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有的度数之和为（）。 A. s B. s -1 C. s +1 D.2s

70.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数为（）。 A.n B.e C.n+e D.2e

71.在一个具有n个顶点的无向完全图中，所含的边数为（）。 A.n B.n（n-1） C.n（n-1）/2 D.n（n+1）/2 72.在一个具有n个顶点的有向完全图中，所含的边数为（）。 A.n B.n（n-1） C.n（n-1）/2 D.n（n+1）/2

73.在一个具有n个顶点的无向连通图中，它包含的连通分量的个数为（）。 A.0 B.1 C.n D.n+1

74.若有一个图中包含k个连通分量，若按照深度优先搜索的方法访问所有顶点，则必须调用（）次深度优先搜索遍历的算法。

A.k B.1 C.k-1 D.k+1

75.若要把n个顶点连接为一个连通图，则至少需要（）条边。 A.n B.n+1 C.n-1 D.2n

76.在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（）。 A.n B.ne C.e D.2e

77.在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素的个数为（）。 A.n B.ne C.e D.2e

78.在一个具有n个顶点和e条边的无向图的邻接矩阵中，边结点的个数为（）。

A.n B.ne C.e D.2e

79.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表的边数结点为（）。 A.k1 B.k2 C.k1-k2 D.k1+k2

80.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表的边数结点为（）。 A.k1 B.k2 C.k1-k2 D.k1+k2

81.对于一个无向图，下面（）的说法是正确的。

A.每个顶点的入度等于出度 B.每个顶点的度等于入度和出度之和 C.每个顶点的入度为0 D.每个顶点的出度为0

82.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（）。

A.出边数 B.入边数 C.度数 D.度数减一 83.若一个图的边集为{（A，B）（A，C）（B，D）（C，F）（D，E）（D，F）}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为（）。

A. ABCFDE B. ACFDEB C. ABDCFE D. ABDFEC 84.若一个图的边集为{（A，B）（A，C）（B，D）（C，F）（D，E）（D，F）}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为（）。 A.ABCDEF B.ABCFDE C.ABDCEF D.ACBFDE 85.若一个图的边集{（1，2）（1，4）（2，5）（3，1）（3，5）（4，3）}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为（）。 A.1，2，5，4，3 B.1，2，3，4，5 C.1，2，5，3，4 D.1，4，3，2，5 86.若一个图的边集{（1，2）（1，4）（2，5）（3，1）（3，5）（4，3）}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为（）。

A. 1，2，3，4，5 B. 1，2，4，3，5 C. 1，2，4，5，3 D. 1，4，2，5，3 87.由一个具有n个顶点的连通图生成的最小树中有（）条边。

A.n B.n-1 C.n+1 D.2n

88.若查找每一个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为（）。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2

89.对长度为n的单链有序表，若查找每个元素的概率相等，则查找任一个元素的平均查找长度为（）。 A. n/2 B.（n+1）/2 C. (n-1)/2 D.n/4

90.对于长度为9的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找长度为（）的值除以9。

A.20 B.18 C.25 D.22

91.对于长度为18的顺序存储的有序表，若采用二分查找，则查找第15个元素的查找长度为（）。

A.2 B.3 C.4 D.6

92.对于顺序存储的有序表（5，12，20，26，37，42，46，50，64），若采用二分查找，则查找元素26的查找长度为（）。 A.2 B.3 C.4 D.5

93.在分块查找中，若用于保存数据元素的主表长度为n，它被分为k个子表，每个子表的长度均为n/k，若用顺序查找确定块，则分块查找的平均查找长度为（）。

A.n+k B.k+n/k C.（k+n/k）/2 D.（k+n/k）/2+1

94.在分块查找中，若用于保存数据元素的主表长度为144，它被分为12个子表，每个子表的长度均为12，若用顺序查找确定块，则分块查找的平均查找长度为（）。 A.13 B.24 C.12 D.79

95.在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（）。 A.n B.lbn C.（h+1）/2 D.h

96.在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是（）。

A.-1~1 B.-2~2 C.1~2 D.0~1

97.若根据查找表（23，44，36，48，52，73，64，58）建立线性哈希表，采用H（K）=K计算哈希地址，则元素64的哈希地址为（）。

A.4 B.8 C.12 D.13

98.若根据查找表（23，44，36，48，52，73，64，58）建立线形哈希表，采用H（K）=K计算哈希地址，则哈希地址为3的元素个数为（）。 A.1 B.2 C.3 D.4

99.若根据查找表建立长度为m的线性哈希表，采用线性探测再哈希法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为（）。 A.d B.d+1 C.（d+1）/m D.（d+1）%m

100.在采用线性探测再哈希法处理冲突的线性哈希表上，假定装填因子a的值为0.5，则查找任一个元素的平均查找长度为（）。 A.1 B.1.5 C.2 D.2.5

101.在哈希查找中，平均查找长度主要与（）有关。

A.哈希表长度 B.哈希元素个数 C.装填因子 D.处理冲突方法 102.若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中元素的个数为（）。 A.i B.i+1 C.i-1 D.1

103.若对n个元素进行直接插入排序，在进行第i趟排序时，为寻找插入位子最多需要进行（）次元素的比较，假定第0号元素放有待查的键值。

A. i B.i-1 C.i+1 D.1

104.若对n个元素进行直接插入排序，在进行第i趟排序时,假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（）。 A.j-i B.i-j-1 C.i-j D.i-j+1

105.若对n个元素进行直接插入排序，在进行任意一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（）。 A.O（1） B.O（n） C.O（n2） D. O（lbn）

106.在对n个元素进行直接插入排序的过程中，共需要进行（）趟。 A.n B.n+1 C.n-1 D.2n

107.对n个元素进行直接插入排序的时间复杂度为（）。 A.O（1） B.O（n） C.O（n2） D. O（lbn）

108.在对n个元素进行冒泡排序的过程中，第一趟排序至多进行（）对相邻元素之间的交换。 A .n B.n-1 C.n+1 D.n/2

109.在对n个元素进行冒泡排序的过程中，最坏情况下的时间复杂度为（）。 A.O（1） B.O（lbn） C.O（n2） D.O（n）

110.在对n个元素进行冒泡排序的过程中，至多需要（）趟完成。 A .1 B.n C.n-1 D.n/2

111.在对n个元素进行快速排序的过程中，最好情况下需要进行（）趟。

A.n B.n/2 C.lbn D.2n

112.在对n个元素进行快速排序的过程中，最坏情况下需要进行（）趟。

A.n B.n-1 C.n/2 D.lbn

113.对下列4个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（）。 A.1，3，5，7，9 B.9，7，5，3，1 C.5，3，1，7，9 D.5，7，9，1，3

114.假定对元素序列（7，3，5，9，1，12，8，15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（）。 A.2 B.3 C.4 D.5

115.在对n个元素进行简单选择排序的过程中，在第i趟需要从（）个元素中选择出最小值元素。

A.n-i+1 B.n-i C.i D.i+1

116.若对n个元素进行简单选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂度为（）。 A.O（1） B.O（lbn） C.O（n2） D. O（n）

117.假定一个初始堆为（1，5，3，9，12，7，15，10），则进行第一趟堆排序后得到的结果为（）。

A.3，5，7，9，12，10，15，1 B.3，5，9，7，12，10，15，1 C.3，7，5，9，12，10，15，1 D.3，5，7，12，9，10，15，1 118.若一个元素序列基本有序，则选用（）方法较快。 A.直接插入排序 B.简单选择排序 C.堆排序 D.快速排序

119.若要从1000个元素中得到10个最小元素，最好采用（）方法。 A.直接插入排序 B.简单选择排序 C.堆排序 D.快速排序 120.在平均情况下速度最快的排序方法为（）。

A.简单选择排序 B.冒泡排序 C.堆排序 D.快速排序

二﹑填空题

1.数据的逻辑结构可分为____和____两大类。

2.数据的存储结构被分为____，_____，_____和____4种。

3.在下面的程序段中，s=s+p语句被执行次数为____，p*=j语句的执行次数为____,该程序的复杂度为____。 int i=0，s=0； while（++i<=n） { int p=1;

for(int j=1;j<=i;j++) p*=j; s=s+p;

}

4.一种数据结构的元素集合K和它的二元关系R为：K={a,b,c,d,e,f,g,h} R={，，，，，，} 则该数据结构具有____结构。

5.线性表的两种存储结构分别为____和____。

6.线性表的顺序存储结构称为____，链式存储结构称为____。

7.若经常需要对线性表进行插入和删除运算，则最好采用__存储结构，若经常需要对线性表

进行查找运算，则最好采用____存储结构。

8.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为____。

9.对于一个单链表存储的线性表，在表头插入结点的时间复杂度为____，在表尾插入结点的时间复杂度为____。

10.在线性表的单链表存储中，若一个元素所在结点的地址为p，则其后的断结点的地址为____。

11.在以HL为头指针的带头结点的单链表和循环单链表中，链表为空的条件分别为____和____。

12.在____链表中，既可以通过设定一个头指针，也可以通过设定一个尾指针来确定它，即通过头指针或尾指针可以访问到该链表的每个结点。

13.在一个单链表中删除指针p所指向结点的后继结点时，需要把____的值赋给p->next指针域。

14.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的节点时，首先把____的值赋给p->next，然后把____的值赋给p->next。

15.假定指向单链表中第一个结点的头指针为head，则像该单链表的表头插入指针p所指向的新结点时，首先执行____赋值操作，然后执行____赋值操作。

16.访问一个顺序表和一个单链表中第i个元素的时间复杂度分别为____和____。

17.在一个带头结点的循环单链表中，在表头插入或删除与在其它位置插入和删除，其操作过程是否相同？________。

18.在双向链表中每个结点包含有两个指针域，一个指向其____结点，另一个指向其____结点。

19.在一个双向链表中指针p所指向的结点之后插入一个指针q所指向的结点时，需要对p->next->prior指针域赋值为____。

20.在一个双向链表中删除指针p所指向的结点时，需要对p->next->prior指针域赋值为____。 21.栈又称为____表，队列又称为____表。

22.在一个用一维数组a[N]表示的顺序栈中，该栈所含元素的个数最少为____个，最多为____个。

23.像一个顺序栈插入一个元素时，首先使____后移一个位置，然后把新元素____到这个位子。

24.从一个栈删除元素时，首先取出____，然后再使____减一。

25.一个顺序栈存储一个一维数组a[M]中，栈顶指针用top表示，当栈顶指针等于____时为空栈，栈顶指针为____时为满栈。

26.假定一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当p所指向的结点入栈时，则首先执行____操作，然后执行____操作。

27. 假定一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当进行出栈运算时（假定栈非空），需要把栈顶指针修改为____的值。 28.设元素1，2，3，4，5依次进栈，若要在输出端得到序列34251，则应进行的操作序列为Push(s,1),Push(s,2),____,Pop(s),Push(s,4),Pop(s),____,____,Pop(s),Pop(s)。

29.设元素a，b，c，d依次进栈，若要在输出端得到序列cbda，则应进行的操作序列为push(s,a),push(s,b),push(s,c),____,____，____pop(s),pop(s)。 30.队列的插入操作在____进行，删除操作在____进行。

31.一个顺序循环队列存在于a[M]中,假定队首和队尾指针分别为front和rear，则判断对空的条件为____，判断对满的条件为____。

32.一个顺序循环队列存在于a[M]中,假定队首和队尾指针分别为front和rear，则求出队首和

队尾指针的下一个位置的计算公式分别为________和________。

33.在一个用一维数组a[N]存储的顺序循环队列中，该队列中的元素个数最少为____个，最多为____个。

34.向一个顺序循环队列中插入元素时，需要首先移动____，然后再向它所指位置____新元素。

35.在一个空链队列中，假定队首和队尾指针分别为f和r，当向他插入一个新结点*p时，则首先执行____操作，然后执行____操作。

36.在一个带头结点的循环链队列中，假定队首和队尾指针分别为f和r，当向它插入一个新结点*p时，则首先执行____操作，然后执行____操作。

37.假定front和rear分别为一个链队列的对首和队尾指针，则该链队列中只有一个结点的条件为________。

38.在一个链栈中，若栈顶指针等于NULL则为____；在一个链队列中，若对首和队尾的指针相同，则表示该队列为____或该队列____。

39.一个二维数组A[15，10]采用行优先方式存储，每个数据元素占用4个存储单元，以该数组第3列第0行的地址（即A[3，0]的地址）1000为首地址，则A[12，9]的地址为____。 40.在二维数组a[10,20]中，每个元素占8个存储单元，假定该数组的首地址为2000，则数组元素a[6,15]的字节地址为____。 41.有一个8×8的下三角矩阵A，若将其进行顺序存储于一维数组a[N]中，则N的值为____。 42.有一个10×10的下三角矩阵A，若将其进行顺序存储于一维数组a[N]中，则Aij（1≤i≤10,1≤j≤i）存储于a中的下标位置为____。

43.有一个8×8的下三角矩阵A，若将其进行顺序存储，每个元素占用4个字节，则A5，4元素的相对字节地址为（相对首元素地址而言）____。 44.一种数据结构的元素集合K和它的二元关系R为：

K={a,b,c,d,e,f,g,h}

R={，，，，，，}则该数据结构具有____结构。 45.对于一棵具有n个结点的树，则该树中所有结点的度数之和为____。

46.在一棵树中，____结点没有前驱结点，其余每个结点有并且只有一个____，可以有人以多个____结点。

47.如图1.3所示为一棵树，该树的叶子结点数为____个，单支结点数为____个，双分支结点数为____个，三分支结点数为____个。

48.如图1.3所示的一棵树，结点K的所有祖先的结点数为____个，结点B的所有子孙结点数为____个。

49.如图1.3所示的一棵树，结点D和X的层数分别为____和____。 50.如图1.4所示的一棵树，则树中所含的结点数为____个，树的深度为____，树的度为____。 51.如图1.4所示的一棵树，则度为3，2，1，0的结点数分别为____，____，____。 52.如图1.4所示一棵树，则结点H的双亲为____，孩子结点为____。

53.在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为____。 54.对于一棵二叉树，若一个结点的编号i，若它的左孩子结点存在，则其编号为____，若右孩子结点存在，则其编号为____，若双亲结点存在，则其编号为____。 55.在一棵二叉树中，第5层上的结点数最多为____。

56.假定一棵二叉树的结点数为18，则它的最小深度为____，最大深度为____。

57.如图1.5所示为一棵二叉树，则E结点的双亲结点数为____，左孩子结点为____，右孩子结点为____。

58.如图1.5所示为一棵二叉树，它含有双支结点____个，单分支结点____个，叶子结点____

本文来源：https://www.bwwdw.com/article/9q1g.html