计算机软件技术基础题库

《计算机软件技术基础题库》第1章数据结构

一、选择题

L算法指的是(D)。

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

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

2.在数据的树形结构中，数据元素之间为(C)的关

系。

A0:0B1:1Cl:nDm:n

3.数据的存储结构包括顺序、链接、散列和(工)4

种基本类型。

A索引B数组C集合D向量

4.一个数组元素a[i]与(B)的表示等价。

A&a+iB*(a+i)C*a+iDa+i

7.下面程序的时间复杂性的量级为(C)。

inti=0,sl=,s2=0；

while(i++<n)

{if(i%2)sl+=i;

elses2+=i;

)

A.O(l)B.O(lbn)C.O(n)D.O(2n)

8,下面程序段的时间复杂度为(D)o

for(inti=O;i<m;i++)

for(intj=O;j<n;j++)

a[i]U]=i*j；

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

9,执行下面程序段时，S语句的执行次数为(B)。

for(inti=l;i<=n;i++)

for(intj=lj<=i;j++)

S；

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

10.在一个长度为n的顺序存储结构的线性表中，向第

i个元素(lWi<n+l)位置插入一个元素时，需要从

后向前依次后移(B)个元素。

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

11.在一个长度为n的顺序存储结构的线性表中，删

除第i个元素(IWiWn+l)时，需要从前向后依次后

移(A)个元素。

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

12.在一个长度为n的线性表中，删除值为x的元素时

需要比较元素和移动元素的总次数为(C)。

A.(n+l)/2B.n/2C.nD.n+1

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

为(B)o

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

14.在一个顺序表中的任何位置插入一个元素的时间

复杂度为(A)。

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

15.在一个单链表中删除p所指向结点的后继结点时，

其算法的时间复杂度为(C)。

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

16.线性表的链式存储比顺序存储更有利于进行(D)

操作。

A.查找B.表尾插入和删除

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

17.线性表的顺序存储比链式存储更有利于进行(B)

操作。

A.查找B.表尾插入和删除

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

18.在一个单链表中，若要在P所指向的结点之后插入

一个新结点，则需要相继修改(D)个指针域的值.

A.lB.2C.3D.4

19.在一个带头结点的循环双向链表中，若要在P所指

向的结点之前插入一个新结点，则需要相继修改(C)

个指针域的值。

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

20.在一个表头指针为ph的单链表中，若要向表头插

入一个由指针P指向的结点，则应执行（B）操作。

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所指向的结点，则

执行（D）操作。

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所指向结

点的后继结点（若存在的话），则执行（C）操作。

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赋值为（B）。

A.P->priorB.p->next

C.p->next->nextD.p->prior->prior

24.在一个带头结点的循环双向链表中，若要在指针p

所指向的结点之前插入一个q指针所指向的结点，则

需要对p->prior->next赋值为（A）。

A.qB.pC.p->nextD.p->prior

25.在一个带头结点的循环双向链表中，若要删除指

针P所指向的结点则执行（A）操作。

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

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

27.当利用大小为N的数组顺序存储一个栈时,假定用

top=N表示栈空，则向这个栈插入一个元素时，首先

应执行（B）语句修改top指针。

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

28.假定利用数组a[N]顺序存储一个栈，用top表示栈

顶指针，用top=N+l表示栈空，该数组所存储的栈的

最大长度为N,则表示栈满的条件为（A）。

A.top==lB.top==-1C.top=0D.top=N-l

29.假定利用数组a[N]顺序存储一个栈，用top表示

栈顶指针，用top==-l表示栈空，并已知栈未满，当

元素x进栈时所执行的操作为（C）。

A.a[-top]=xB.a[top-]=xC.a[++top]=x

D.a[top++]=x

30.假定利用数组a[N]顺序存储一个栈，用top表示

栈顶指针，用top==-l表示栈空，并已知栈未空，当

退栈并返回栈顶元素时所执行的操作为（B）o

Areturna[-top]Breturna[top-]Creturn

a[++top]Dreturna[top++]

31.假定一个链式栈的栈顶指针用top表示，该链式栈

为空的条件（C）。

A.top!=NULL;B.top==top->next;C.top==

NULL;D.top!=top->next;

32.假定一个链式栈的栈顶指针用top表示，每个结点

结构为应优%当p所指向的结点进栈时，执行的操作

为（D）o

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表示，每个结点

结构为叵"，退栈时所执行的操作为(C)。

A.top->next=top；B.top=top->data;

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

34.若让元素1,2,3,4依次进栈，则出栈次序不可

能出现(D)的情况。

A.3,2,1,4B.2,1,4,3

C.4,3,2,1D.1,4,2,3.

35.在一个顺序循环队列中，队首指针指向队首元素的

(A)位置。

A前一个B后一个C当前D最后

36.当利用大小为N的数组循环存储一个队列时,该队

列的最大长度为(B)。

A.N-2B.N-1C.ND.N+1

37.从一个顺序循环队列中删除元素时,首先需要(B)。

A.前移队首指针B.后移队首指

针

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

针所指位置上的元素

38.假定一个顺序循环队列的队首和队尾指针分别用f

和r表示，则判断队空的条件为(D)o

A.f+l==rB.r+l==fC.f==0D.f==r

39.假定一个顺序循环队列存储于数组a[N],其队首和

队尾指针分别用f和r表示,则判断队满的条件为(B)。

A.(r-1)%N==fB.(r+1)%N==fC.

(f-1)%N==rD.(f+1)%N==r

40.假定利用数组a[N]循环顺序存储一个队列，其队首

和队尾指针分别用f和r表示，并已知队列未满，当

元素x入列时所执行的操作为(A)。

A.a[++r%N]=xB.a[r++%N]=xC.a[-r%N]=x

D.a[r-%N]=x

4L假定利用数组a[N]循环顺序存储一个队列，其队首

和队尾指针分别用f和r表示，并已知队列未空，当

出列并返回队首元素时所执行的操作为(C)。

A.returna[++r%N]B.returna[—r%N]

C.returna[++f%N]D.returna[f++%N]

42.假定一个链式队列的队首和队尾指针分别为front

和rear,则判断队空的条件为(D)。

A.front==rearB.front!=NULLC.rear!

=NULLD.front==NULL

43.假定一个链式队列的队首和队尾指针分别为front

和rear,每个结点结构为皿曲,当出列时所进行的操

作为(A)o

A.front=front->nextB.rear=rear->next

C.front->next=rear；rear=rear->next

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

44.假定一个带头结点的循环链式队列的队首和队尾

指针分别用front和rear表示，则判断对空的条件为

(D)o

A.front=rear->nextB.rear==NULLC.

front==NULLD.front==rear

45.假定一个链式队列的队首和队尾指针分别为front

和rear,每个结点结构为包含值域data和指针域next,

则使P所指结点入列所执行的操作为(B)。

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

表示，则该队列中数组元素个数为(B)。

A.(rear-front)%NB.(rear-front+N)%N

C.(rear+N)%ND.(front+N)%N

47•二维数组A[12,10]采用行优先存储，每个数据元素

占用4个存储单元，该数组的首地址(即A[0,0]的

地址)为1200,则A[6,5]的地址为(D)o

A.1400B.1404C.1372D.1460

48.有一个MXN的矩阵A,若采用行优先进行顺序存

储，每个元素占用8个字节，贝IIAij(lWiWM,lWjW

N)元素的相对字节地址(相对首元素地址而言)为

(B)o

A.((i-1)XN+j)X8B.((i-1)XN+j-1)X8

C.(iXN+j-1)X8D.((i-1)XN+j+1)X8

49.有一个NXN的下三角矩阵A,若采用行优先进行

顺序存储，每个元素占用k个字节，则Aij(lWiWN,l

WjWi)元素的相对字节地址(相对首元素地址而言)

为(C)o

A.(iX(i+1)/2+j-l)X4B.(iXi/2+j)X4

C.(iX(i-1)/2+j-l)X4D.(iX(i-1)/2+j)

X4

50.树中所有结点的度等于所有结点数加(C)。

A.OB.lC.-lD.2

5L在一棵树中，(C)没有前驱结点。

A.树枝结点B.叶子结点C树根结点D.空结

点

52.在一棵树中，每个结点最多有(B)个前驱结点。

A.OB.lC.2D.任意多个

53.在一棵二叉树的二叉链表中，空指针域数等于非空

指针域数加（A）。

A.2B.lC.OD.-l

54.在一棵具有n个结点的二叉树中，所有结点的空子

树个数等于（C）。

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

55.在一棵具有n个结点的二叉树的第i层上，最多具

有（C）个结点。

A.21B.2i+1C.2hlD.2n

〃56.在一棵深度为h的完全二叉树中，所含结点个数

不小于（D）o

A.2hB.2h+1C.2h4D.2hl

〃57.在一棵深度为h的完全二叉树中，所含结点个数

不大于（C）o

A.2hB.2h+1C.2h4D.2hl

〃58.在一棵具有35个结点的完全二叉树中，该树的深

度为（A）o

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

59.在一棵完全二叉树中，若编号为i的结点存在左孩

子，则左孩子结点编号为（A）。

A.2iB.2i-1C.2i+1D.2i+2

60.在一棵完全二叉树中，若编号为i的结点存在右孩

子，则右孩子结点编号为（C）。

A.2iB.2i-1C.2i+1D.2i+2

61.在一棵完全二叉树中，对于编号为i（i>l）的结点

其双亲结点的编号为（D）。

A.（i+1）/2B.（i-1）/2

C.i%2D.i/2

62.有如用工r所示的一棵二叉

树，则该二叉树所含单支结点数

为（B）o

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

63.有如图1.2所示的一棵二叉树，则该二叉树的中序

遍历序列为（C）。

A.ABCDEFGB.CDBGFEAC.CBDAEGF

D.ABECDFG

64.有如图1.2所示的一棵二叉树，则该二叉树的先序

遍历序列为（A）。

A.ABCDEFGB.CDBGFEAC.CBDAEGF

D.ABECDFG

65.有如图L2所示的一棵二叉树，则该二叉树的后序

便利序列为（B）。

A.ABCDEFGB.CDBGFEAC.CBDAEGF

D.ABECDFG

66.利用n个值生成的哈夫曼树中共有（D）个结点。

A.nB.n+1C.2nD.2n-1

67,利用3,6,8,12这4个值作/”

为叶子结点的权，生成一棵哈/B\

夫曼树，该树的带权路径长度C°/'F

为(A)。©

图1.2

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

68.在一个具有n个顶点的有向图中，若所有顶点的出

度数之和为s,则所有的入度数之和为(A)。

A.sB.s-1C.s+1D.n

69.在一个具有n个顶点的有向图中，若所有顶点的出

度数之和为s,则所有的度数之和为(D)。

A.sB.s-1C.s+1D.2s

70.在一个具有n个顶点的无向图中，若具有e条边，

则所有顶点的度数为(D)。

A.nB.eC.n+eD.2e

71.在一个具有n个顶点的无向完全图中，所含的边数

为(C)o

A.nB.n(n-1)C.n(n-1)/2D.n

(n+1)/2

72.在一个具有n个顶点的有向完全图中，所含的边数

为(B)o

A.nB.n(n-1)C.n(n-1)/2D.n

(n+1)/2

73.在一个具有n个顶点的无向连通图中，它包含的连

通分量的个数为（C）。

A.OB.lC.nD.n+l

74.若有一个图中包含k个连通分量，若按照深度优先

搜索的方法访问所有顶点，则必须调用（A）次深

度优先搜索遍历的算法。

A.kB.lC.k-1D.k+1

75.若要把n个顶点连接为一个连通图，则至少需要

（C）条边。

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

76.在一个具有n个顶点和e条边的无向图的邻接矩阵

中，表示边存在的元素（又称为有效元素）的个数

为（D）o

A.nB.neC.eD.2e

77.在一个具有n个顶点和e条边的有向图的邻接矩阵

中，表示边存在的元素的个数为（C）。

A.nB.neC.eD.2e

78.在一个具有n个顶点和e条边的无向图的邻接矩阵

中，边结点的个数为（D）。

A.nB.neC.eD.2e

79.对于一个有向图，若一个顶点的度为kl,出度为

k2,则对应邻接表中该顶点单链表的边数结点为

(B)o

A.klB.k2C.kl-k2D.kl+k2

80.对于一个有向图，若一个顶点的度为kl,出度为

k2,则对应逆邻接表中该顶点单链表的边数结点为

(C)o

A.klB.k2C.kl-k2D.kl+k2

81.对于一个无向图，下面(A)的说法是正确的。

A.每个顶点的入度等于出度B.每个顶点的度等

于入度和出度之和

C每个顶点的入度为0D.每个顶点的出度

为0

82.在一个有向图的邻接表中，每个顶点单链表中结点

的个数等于该顶点的(A)。

A.出边数B.入边数C.度数D.度数减一

83.若一个图的边集为{(A,B)(A,C)(B,D)(C,

F)(D,E)(D,F)},则从顶点A开始对该图进

行深度优先搜索，得到的顶点序列可能为(B)。

A.ABCFDEB.ACFDEBC.ABDCFED.

ABDFEC

84.若一个图的边集为{(A,B)(A,C)(B,D)(C,

F)(D,E)(D,F)},则从顶点A开始对该图进

行广度优先搜索，得到的顶点序列可能为(D)。

A.ABCDEFB.ABCFDEC.ABDCEF

D.ACBFDE

85.若一个图的边集{(1,2)(1,4)(2,5)(3,1)

(3,5)(4,3)},则从顶点1开始对该图进行深度

优先搜索，得到的顶点序列可能为(A)。

A.1,2,5,4,3B.1,2,3,4,5C.1,2,5,

3,4D.1,4,3,2,5

88.若查找每一个元素的概率相等，则在长度为n的顺

序表上查找任一元素的平均查找长度为(D)。

A.nB.n+1C.(n-l)/2D.(n+l)/2

89.对长度为n的单链有序表，若查找每个元素的概率

相等，则查找任一个元素的平均查找长度为(B)。

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

90.对于长度为9的顺序存储的有序表，若采用二分查

找，在等概率情况下的平均查找长度为(C)的值除

以90

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

91.对于长度为18的顺序存储的有序表，若采用二分

查找，则查找第15个元素的查找长度为(B)。

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

92.对于顺序存储的有序表(5,12,20,26,37,42,

46,50,64),若采用二分查找，则查找元素26的查

找长度为(C)。

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

93.在分块查找中，若用于保存数据元素的主表长度为

n,它被分为k个子表，每个子表的长度均为n/k,若

用顺序查找确定块，则分块查找的平均查找长度为

(D)o

A.n+kB.k+n/kC.(k+n/k)/2D.(k+n/k)/2+1

94.在分块查找中，若用于保存数据元素的主表长度为

144,它被分为12个子表，每个子表的长度均为12,

若用顺序查找确定块，则分块查找的平均查找长度为

(A)o

A.13B.24C.12D.79

95.在一棵深度为h的具有n个元素的二叉排序树中，

查找所有元素的最长查找长度为(D)。

A.nB.IbnC.(h+1)/2D.h

96.在一棵平衡二叉排序树中，每个结点的平衡因子的

取值范围是(B)o

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

97.若根据查找表(23,44,36,48,52,73,64,58)

建立线性哈希表，采用H(K)=K%13计算哈希地址,

则元素64的哈希地址为(C)。

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

98.若根据查找表（23,44,36,48,52,73,64,58）

建立线形哈希表，采用H（K）=K%13计算哈希地址,

则哈希地址为3的元素个数为（B）。

A.lB.2C.3D.4

99.若根据查找表建立长度为m的线性哈希表，采用

线性探测再哈希法处理冲突，假定对一个元素第一次

计算的哈希地址为d,则下一次的哈希地址为（D）。

A.dB.d+1C.（d+1）/mD.（d+1）%m

100.在采用线性探测再哈希法处理冲突的线性哈希表

上，假定装填因子a的值为0.5,则查找任一个元素的

平均查找长度为（B）。

A.lB.1.5C.2D.2.5

102.若对n个元素进行直接插入排序，则进行第i趟

排序过程前，有序表中元素的个数为（A）。

A.iB.i+1C.i-1D.l

103.若对n个元素进行直接插入排序，在进行第i趟

排序时，为寻找插入位子最多需要进行（C）次元素

的比较，假定第0号元素放有待查的键值。

A.iB.i-1C.i+1D.l

104.若对n个元素进行直接插入排序，在进行第i趟

排序时，假定元素r[i+l]的插入位置为rU],则需要移

动元素的次数为(D)。

A.j-iB.i-j-1C.i-jD.i-j+1

105.若对n个元素进行直接插入排序，在进行任意一

趟排序的过程中，为寻找插入位置而需要的时间复杂

度为(B)o

A.O(1)B.O(n)C.O(n2)D.O(Ibn)

106,在对n个元素进行直接插入排序的过程中，共需

要进行(C)趟。

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

107.对n个元素进行直接插入排序的时间复杂度为

(C)o

A.O(1)B.O(n)C.O(n2)D.O(Ibn)

108,在对n个元素进行冒泡排序的过程中，第一趟排

序至多进行(B)对相邻元素之间的交换。

A.nB.n-1C.n+1D.n/2

109.在对n个元素进行冒泡排序的过程中，最坏情况

下的时间复杂度为(D)。

A.O(1)B.O(Ibn)C.O(n2)D.O(n)

110.在对n个元素进行冒泡排序的过程中，至多需要

(A)趟完成。

A.1B.nC.n-1D.n/2

UL在对n个元素进行快速排序的过程中，最好情况

下需要进行(C)趟。

A.nB.n/2C.lbnD.2n

112.在对n个元素进行快速排序的过程中，最坏情况

下需要进行(B)趟。

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

113.对下列4个序列进行快速排序，各以第一个元素

为基准进行第一次划分，则在该次划分过程中需要移

动元素次数最多的序列为(D)。

A.1,3,5,7,9B.9,7,5,3,1C.5,3,1,

7,9D.5,7,9,1,3

114.假定对元素序列(7,3,5,9,1,12,8,15)

进行快速排序，则进行第一次划分后，得到的左区间

中元素的个数为(B)o

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

115.在对n个元素进行简单选择排序的过程中，在第i

趟需要从(A)个元素中选择出最小值元素。

A.n-i+1B.n-iC.iD.i+1

116.若对n个元素进行简单选择排序，则进行任一趟

排序的过程中，为寻找最小值元素所需要的时间复杂

度为(D)o

A.O(1)B.O(Ibn)C.O(n2)D.O(n)

117.假定一个初始堆为(1,5,3,9,12,7,15,10),

则进行第一趟堆排序后得到的结果为（A）。

A.3,5,7,9,12,10,15,1B.3,5,9,7,

12,10,15,1

C.3,7,5,9,12,10,15,1D.3,5,7,12,

9,10,15,1

118,若一个元素序列基本有序，则选用（A）方法较快。

A.直接插入排序B.简单选择排序C.堆排序D.

快速排序

119.若要从1000个元素中得到10个最小元素，最好

采用（B）方法。

A.直接插入排序B.简单选择排序C.堆排序

D.快速排序

120,在平均情况下速度最快的排序方法为（D）。

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

快速排序

二、填空题

L数据的逻辑结构可分为和两大类。

2.数据的存储结构被分为,,和4

种。

5.线性表的两种存储结构分别为顺序和链式

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

结构称为链式表。

7•若经常需要对线性表进行插入和删除运算，则最好

采用链式存储结构,若经常需要对线性表进行查找

运算，则最好采用.顺序__存储结构。

8.对于一个长度为n的顺序存储的线性表，在表头插

入元素的时间复杂度为0

9.对于一个单链表存储的线性表，在表头插入结点的

时间复杂度为__,在表尾插入结点的时间复杂度为

10.在线性表的单链表存储中，若一个元素所在结点的

地址为P，则其后的断结点的地址为。

12.在循环链表中,既可以通过设定一个头指针，

也可以通过设定一个尾指针来确定它，即通过头指针

或尾指针可以访问到该链表的每个结点。

13.在一个单链表中删除指针p所指向结点的后继结

点时，需要把的值赋给p->next指针域。

14.在一个单链表中指针p所指向结点的后面插入一

个指针q所指向的节点时，首先把—的值赋给

p->next,然后把的值赋给p->nexto

15.假定指向单链表中第一个结点的头指针为head,

则像该单链表的表头插入指针p所指向的新结点

时，首先执行赋值操作，然后执行——赋值操

作。

16.访问一个顺序表和一个单链表中第i个元素的时间

复杂度分别为__和—o

17.在一个带头结点的循环单链表中，在表头插入或删

除与在其它位置插入和删除，其操作过程是否相同？

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

向其__结点，另一个指向其___结点。

19.在一个双向链表中指针p所指向的结点之后插入

一个指针q所指向的结点时，需要对p->next->prior

指针域赋值为__o

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,l),Push(s,2),,Pop(s),Push(s,4),Pop(s),

,,Pop(s),Pop(s)o

29.设元素a,b,c,d依次进栈，若要在输出端得到

序列cbda,则应进行的操作序列为

Push(s,a),Push(s,b),Push(s,c),,,

Pop(s),Pop(s)o

30,队列的插入操作在—进行，删除操作在进

行。

31.一个顺序循环队列存在于a[M]中，假定队首和队尾

指针分别为front和rear,则判断对空的条件为,

判断对满的条件为__o

32.一个顺序循环队列存在于a[M]中，假定队首和队尾

指针分别为front和rear,则求出队首和队尾指针

的下一个位置的计算公式分别为和

33.在一个用一维数组a[N]存储的顺序循环队列中，该

队列中的元素个数最少为个，最多为个。

34.向一个顺序循环队列中插入元素时，需要首先移动

__,然后再向它所指位置____新元素。

35.在一个空链队列中，假定队首和队尾指针分别为f

和r,当向他插入一个新结点*p时，则首先执行

操作，然后执行___操作。

36.在一个带头结点的循环链队列中，假定队首和队尾

指针分别为f和r,当向它插入一个新结点*p时，

则首先执行__操作，然后执行__操作。

37.假定front和rear分别为一个链队列的对首和队尾

指针,则该链队列中只有一个结点的条件为o

38•在一个链栈中，若栈顶指针等于NULL则为；

在一个链队列中，若对首和队尾的指针相同，则表示

该队列为___或该队列___。

39.一个二维数组A[15,10]采用行优先方式存储，每

个数据元素占用4个存储单元，以该数组第3列第

0行的地址（即A[3,0]的地址）1000为首地址，

则A[12,9]的地址为o

40.在二维数组a[10,20]中，每个元素占8个存储单元,

假定该数组的首地址为2000,则数组元素a[6,15]的字

节地址为O

4L有一个8X8的下三角矩阵A,若将其进行顺序存

储于一维数组a[N]中，则N的值为。

42.有一个10X10的下三角

矩阵A,若将其进行顺序存

储于一维数组a[N]中，则Aij

存储于aEFHX

中的下标位置为O图1.3

43.有一个8X8的下三角矩阵A,若将其进行顺序存

储，每个元素占用4个字节，则A5.4元素的相对字节

地址为（相对首元素地址而言）。

44.一种数据结构的元素集合K和它的二元关系R为:

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

R={<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,

ve,f>}则该数据结构具有结构。

45.对于一棵具有n个结点的树，则该树中所有结点的

度数之和为一。

46.在一棵树中，结点没有前驱结点，其余每个结

点有并且只有一个,可以有人以多个结点。

47.如图L3所示为一棵树，该树的叶子结点数为____

个，单支结点数为个，双分支结点数为一个,

三分支结点数为一个。

48.如图L3所示的一棵树，结点

K的所有祖先的结点数为__

个，结点B的所有子孙结点数为

一个。

图1.4

49.如图1.3所示的一棵树，结点

D和X的层数分别为—和

50.如图1.4所示的一棵树，则树中所含的结点数为

个，树的深度为—，树的度为

51.如图L4所示的一棵树，则度为3,2,1,0的结点

数分别为__，—，—o

52.如图1.4所示一棵树，则结点H的双亲为—,孩

子结点为___o

53.在一棵二叉树中，假定双分支结点数为5个，单分

支结点数为6个，则叶子结点数为。

54.对于一棵二叉树，若一个结点的编号i,若它的左

孩子结点存在，则其编号为—,若右孩子结点存在,

则其编号为___，若双亲结点存在，则其编号为—。

55.在一棵二叉树中，第5层上的结A

点数最多为—oE

56.假定一棵二叉树的结点数为18,cnP

图L5

则它的最小深度为——，最大深度为—O

57.如图所示为一棵二叉树，则E结点的双亲结点

数为一,左孩子结点为___，右孩子结点为一o

58.如图1.5所示为一棵二叉树，它含有双支结点

个，单分支结点一个，叶子结点__个。

59.假定一棵二叉树顺序存储在一维数组a中，若a[5]

元素的左孩子存在则对应的元素为____,若右孩子存

在则对应的元素为一，双亲元素为

60.若对一棵二叉树从0开始进行结

点编号，并按此编号把它存储到一

维数组a中，即编号为0的结点存

储到a[0]中，依次类推，则a[i]元素图1.6

的左孩子为，右孩子为__，

双亲元素（i>0）为o

6L对于一棵具有n个结点的二叉树，对应二叉链

表中指针总数为__个，其中__个用于指向孩子结

点，一个指针空闲。

62.在一棵深度为h的完全平衡二叉树中，最少含有

个结点，最多含有__个结点。

63.一棵深度为5的完全二叉

树中的结点数最少为一个，

最多为个。

图1.7

64.如图1他所示为一棵二叉树，对它进行先序遍历结

果为__o

65.若将加电7］所示为一棵树转换为二叉树，该二叉

树中双支结点的个数为__个，单支结点的个数为

个，叶子结点个数为

66.一棵树转换为二叉树后女L8

I_____________________

所示，则原树中分支结点数为

__，叶子结点数为—O

67.一个树林转换成二叉树后撅图

可所示,则该素林中包含一棵

树。

68.若由3,6,8,12,10作为叶子

结点的值生成一棵哈夫曼树，则该树的深度为一，

带权路径长度为O

69.一种数据结构的元素集合K和它的二元关系R为:

K={b2,3,4,5,6}

R={(1,2)(2,3)(2,4)(3,4)(3,5)(3,6)

(4,5)(4,6)}

则该数据结构具有数据结构。

70.在一个图中，所有顶点的度数之和

等于所有边数的___倍。

71.在一个具有n个顶点的无向完全图

图1.9

中，包含有条边，在一个具有n个顶点的有向完

全图中，包含有条边。

72.已知一个连通图的边集为{(1,2),(1,3),(1,

4),(2,3),(2,5),(3,5),(4,5)},则度为3

的顶点的个数有一个。

73.假定一个有向图的顶点的集为{a,b,c,d,e,f},边集

{<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,ve,d>},则出度

为0的顶点个数为一，入度为1的顶点个数为—o

74.在一个具有n个顶点的无向图中，要连通所有顶点

则至少需要一条边。

75.表示图的两种存储结构为—和一o

76.在一个连通图中存在着一个连通分量。

77.若一个图的顶点集为伯力其,(1声岛边集为{(a,b),

(a,c),(b,c),(d,e)},则该图含有个连通分量。

78.若一个图的边集为｛vO,l>,<0,2>,<0,3>，<0,4>,

<1,2>,<2,4>,<3,4>},则从顶点Vo

到顶点V4共有一条简单路径。

79.如囱1为所示为一个带权有向图,

从顶点V。到顶点V4的最短路径长度图1.10

为O

80.对于一个具有n个顶点的图，若采用邻接矩阵表

示，则矩阵大小至少为—X

81.对于一个具有n个顶点和e条边的有向图和无向

图，在其对应的邻接表中，所含边结点的个数分别为

和O

82.在有向图的邻接表和逆邻接表表示中，每个顶点邻

接表分别链接着该顶点的所有—和—o

83.有一个图的边集为{(a,c),(a,e),(b,e),(c,d),

(d,e)},从顶点a出发进行深度优先搜索遍历得到

的顶点序列为，从顶点a出发进行广度优先

搜索遍历得到的顶点序列为o

84•一个图的边集为{(a,c),(a,e),(c,f),(d,c),

(e,b),(e,d)},从顶点a出发出发进行深度优先搜索

遍历得到的顶点序列为，从顶点a出发进行

广度优先搜索遍历得到的顶点序列为o

85.图的—优先搜索遍历算法是一种递归算法，图的

—优先搜索遍历算法需要使用队列。

86.若一个连通图中每个边上的权值均不同，则得到的

最小生成树是—(唯一/不唯一)。

87.以顺序查找方法从长度为n的顺序表或单链表中

查找一个元素时，平均查找长度为一O

88.对长度为n的查找表进行查找时，假定查找第i个

元素的概率为P,查找长度(即在查找过程中依次同

有关元素比较的总次数）为C,则在查找成功的情况

下的平均查找长度的计算公式为O

89.假定一个顺序表的长度为40,并假定查找每个元素

的概率都相同，则在查找成功的情况下的平均查找长

度—，则在查找不成功的情况下的平均查找长度—

90.以折半查找方法从长度为n的有序表中查找一个

元素时，平均查找长度约等于一减一。

91.以折半查找方法从长度为50的有序表中查找一个

元素时，其查找长度不超过一。

92.从有序表（12,18,30,43,56,78,82,95）中

分别折半查找43和56元素时，其查找长度分别为—

—和O

93.假定对长度n=50的有序表进行折半查找，则对应

的判定树深度为一，最后一层的结点数为一o

94.在分块查找中，假定查找表（即主表）的长度为96,

被等分为8个子表，则进行分块查找的平均查找长度

为O

95.假定对长度为n的有序表进行分块查找，并假定每

个子表的长度为〃，则进行分块查找的平均查找长度

为O

96.在一棵二叉树排序中，每个分支结点的左子树上所

有结点的值一定—该结点的值，右子树上所有结点

的值一定—该结点的值。

97.从一棵二叉排序树中查找某个元素时，若元素的值

等于根结点的值，则表明—，若元素的值小于根结

点的值，则继续向一查找，若元素的值大于根结点

的值，则继续向—查找。

98.向一棵二叉排序树种插入一个元素时，若元素的值

小于根结点的值，则接着向根结点的—插入，若元

素的值大于根结点的值，则接着向根结点的一插入。

99.在一棵平衡二叉排序树中，每个结点的左子树深度

与右子树深度之差的绝对值不超过—o

100.假定对线性表(38,25,74,52,48),进行散列

存储，采用H(K)=K%7作为哈希函数，采用线性

探测再散列法处理冲突，则在建立哈希表过程中，将

会碰到一次冲突。

10L假定对线性表(38,25,74,52,48)进行散列

存储，采用H(K)=K%7作为哈希函数，采用线性

探测再散列法处理冲突，则平均查找长度为—o

102.在线性表的散列存储中，装填因子a又称装填系

数，若用m表示散列表的长度，n表示散列存储的元

素个数，则a等于—o

103.对线性表(18,25,63,50,42,32,90)进行

散列存储时，若选用H(K)=K%9作为哈希函数，

则散列地址为0的元素有一个，则散列地址为5的

元素有一个。

104.每次从无序子表中取出一个元素，把它插入到有

序子表的适当位置，此种排序方法叫做—排序；每

次从无序子表中挑选出一个最小或最大元素，把它交

换到有序表的一段，此种排序方法叫做—排序。

105.若对一组记录(46,79,56,38,40,80,35,

50,74)进行直接插入排序，当把第8个记录插入到

前面已排序的有序表时，为寻找插入位置需比较—

次。

106.—排序方法能够每次使无序表中的第一个记录

插入到有序表中。

107,对n个记录进行冒泡排序时，最少的比较次数为

—，最少的趟数为—o

108.假定一组记录为(46,79,56,38,40,84),在

冒泡排序过程中进行第一趟排序后的结果为—。

109.假定一组记录为(46,79,56,64,38,40,84,

43),在冒泡排序过程中进行第一趟排序时，元素97

将最终下沉到其后第一位置。

110.—排序方法使键值达的记录逐渐下沉，使键值

小的记录逐渐上浮。

Ill.假定一组记录为(46,79,56,38,40,80)对

其进行快速排序的过程中，共需要一趟。

112.假定一组记录为(46,79,56,25,76,38,40,

80)对其进行快速排序的第一次划分后，右区间内元

素个数为一o

113.假定一组记录为(46,79,56,38,40,80),对

其进行快速排序的第一次划分后的结果为—。

114.在所有排序方法中，―排序方法采用的是折半

查找法的思想。

115.在简单选择排序中，记录比较次数的时间复杂度

为一，记录移动次数的时间复杂度为一o

116.若对一组记录(46,79,56,38,40,80,35,

50,74)进行简单选择排序，用k表示最小值元素的

下标，进行第一趟是可得初值为1,则在第一趟选择

最小值的过程中，k的值被修改一次。

117.在时间复杂度为0(r?)的所有排序方法中，—

排序方法使不稳定的。

118.假定一个堆为(38,40,56,79,46,84),赚

用堆排序方法进行第一趟交换和对根结点筛运算后得

到的结果为—O

119.在所有排序方法中，一方法使数据的组织采用

的是完全二叉树的结构。

120.—排序方法能够每次从无序表中查找出一个最

小值。

三、名词解释

L数据2,数据元素3.数据对象4.数据结构

5.逻辑结构6.时间复杂度7.空间复杂度8.栈

9.队列10.压缩存储11.树形结构12.结点的度

13.树的度14.树的深度15.有序树16.遍历

17.哈夫曼树18.邻接关系19.路径20.连通图

21.强连通图22.完全无向图23.完全有向图24.主

关键字

四、简答题

L简述线性结构，树形结构，网状结构的不同。

2.简述算法复杂度的评价方法。

3.设有两个算法在同一台机器上运行，其执行时间分

别为lOOY和要使前者快于后者，n至少为多大？

4.在顺序表中插入和删除一个结点需平均移动多少个

结点，具体移动的次数取决于哪些因素？

5.简述定义：线性表、单链表、线性表的存储方式、

循环链表、双向链表。

6.在单链表，双向链表和单循环链表中，若仅知道指

针P指向某结点，不知道头指针，能否将P从相应的

链表中删去？若可以，其时间复杂度分别为多少？

7,有哪些链表可仅有一个尾指针来唯一确定，即从尾

指针出发能访问到链表上任何一个结点？

8.何时选用顺序表，何时选用链表作为线性表的存储

结构？

9.简述栈与队列的不同之处。

10.设将整数1,2,3,4依次进栈，但只要出栈时栈

非空，则可将出栈操作按任何次序压入其中，请回答

下述问题：

⑴若入、出栈次序为

Push(l),Pop(),Push(2),Push(3),

P。p(),P。p(),Pllsh(4),P。p(),贝lJ出栈的数字序列如何？

(2)能否得到出栈序列1423和1432,并说明为什

么不能得到或者如何得到。

(3)请分析1,2,3,4的各种排列中，哪些序列

是可以通过相应的入，出栈操作得到的。

1L举例说明栈的“上溢”和“下溢”现象。

12.循环队列的优点是什么？如何判别它的空和满？

13.假定用一维数组a[7]顺序存储一个循环队列，队首

和队尾指针分别用front和rear表示，当前队列中有

5个元素：23,45,67,80,34,其中23为队首元素,

front的值为3,请画出对应的存储

状态,当连续进行4次出队运算后,

再让15,36,48元素依次进队，

E、

请再次画出对应的存储状态。..

r；

14.空串和空格串有何区别？字符图L11

串中空格符有何意义？空串在串

的处理中有何作用？

15.两个字符串相等的充要条件是什么？

16.二叉树和树之间有何区别？一棵度为2的树与二叉

树有何区别？

17.在一棵二叉树如圆工113所示。写出对此树进行先

序，中序，后序遍历时得到的结点序列。

18.已知一棵二叉树的中序遍历

序列为CDBAEGF,先序遍历序0D、

列为ABCDEFG，试问能不能唯/；111

一确定一棵二叉树？若能，画L匕

出该二叉树。若给定先序遍历图112

序列和后序遍历序列，能否唯

一确定？

19.将图L12所示的树转换成二叉树。

20.一棵度为2的有序树与一棵二叉树有何区别？

21.试分别画出具有3个结点的树和3个结点的二叉树

的所有不同形态。

22.高度为h的完全二叉树至少11

2

有多少个结点？至多有多少个2

结点？

23.试采用顺序存储方法和链式44

图1.13

存储方法分别画出如团113n所

示各二叉树的存储结构。

24.假定用于通信的电文由8个字母组成，分别是A,

B,C,D,E,F,G,和H,各字母在电文中出现的

概率为：5%,25%,4%,7%,9%,12%,30%,

面问题：

(1)给出从结点V1出发按深度优先搜索遍历G所得

的结点序列，并给出按广度优先搜索遍历G所得的结

点序列。

(2)给出从结点Vi到结点V8的最短路径。

26.对于如图所示的有向图，请给出

(1)对应的邻接矩阵，并给出A,B,C三个顶点的

出度与入度。

(2)邻接表表示和逆邻接表表示。

(3)强连通分量。

27.假设图的顶点是A,B,C,D,…请根据下述邻接

矩阵画出相应的有向图和无向图。

(1)0111(2)01100

101100010

0000

111001010

28.对n个顶点的无向图和有向图，采用邻接矩阵和邻

接表表示时，如何判别下列有关问题：

(1)图中有多少条边？

(2)任意两个顶点i和j是否有边相连？

(3)任意一个顶点的度是多少？

29.试述顺序查找法，折半查找法和分块查找法对查找

表中元素的要求。

30.若有一个长度为n的表，其查找该表中每个元素的

概率相同，采用顺序查找、折半查找和分块查找3种

查找方法进行查找时的其平均查找长度各为多少？

31.设有一组关键字(17,13,14,153,29,35)需

插入到表长为12的散列表中，请回答下列问题：

(1)设计一个适合该散列表的哈希函数。

(2)用设计的哈希函数将上述关键字插入到散列表

中，画出其结构，并指出用线性探测再散列法解决冲

突时构造散列表的装填因子为多少？

32.选择排序算法是否稳定？为什么？

33•给出一组关键字(19,01,26,92,87,11,43,

87,21),进行冒泡排序，列出每一遍排序后关键字的

排列次序，并统计每遍排序进行的关键字比较次数。

34.直接插入排序算法是否稳定？为什么？

35.堆排序为什么是不稳定的排序？试举例说明。

五、应用题

L指出下列每个算法的功能并求出其时间复杂性。

(1)intsuml(intn)

{intp=l,s=0;

for(inti=l；i<=n;i++)

{P*=i；

s+=p；

)

returns;

(2)voidmtable(intn)

{for(inti=l；i<=n;i++)

for(intj=i；j<=n;j++)

printf("i*j=%d”,i*j)；

printf;

)

(3)voidcmatrix(inta[M][N],intd)/*M和N为全

局整型常量*/