2023年数据结构题库

线性构造题

I.栈和队列的共同特点是(A)。

(A)只容许在端点处插入和删除元素

(B)都是先进后出

(C)都是先进先出

(D)没有共同点

如下数据构造中哪一种是非线性构造？(D)

(A)队列(B)栈(。线性表(D)二叉树

设有一种二维数组A[m]ln],假设A⑼[0]寄存位置在644(10),A[2]⑵寄存位置在

676(10),每个元素占一种空间，问A[3J[3](10)寄存在(C)位置。脚注(10)表达

用10进制表达。

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

4.设某数据构造的二元组形式表达为A=(D,R),D={01,02,03,04,05,06,07,08,

09),R={r},r={<0l,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,

<03,08>,<03,09>},则数据构造A是(B)。

(A)线性构造(B)树型构造(C)物理构造(D；图型构造

5.下而程序的时间复杂为(B)

for(i=l,s=0；i<=n；i++)(t=l；for(j=l；j<=i；j++)t=t*j；s=s+t；}

(A)0(n)(B)0(n2)(C)0(n3)(D)0(n4)

6.下列程序段的时间复杂度为(A)o

i=0,s=0；while(s<n){s=s+i：i++；}

(A)0(n12)(B)OS'，(C)0(n)(D)0(nz)

7.为处理计算机主机与打印机之间速度不匹配的问题，一般设置一种打印数据缓冲区。

主机将要打印输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数

据。该缓冲区日勺逻辑构造应当是...)

(A)栈(B)队列(C)树⑴)图

8.已知二级数组a[50][40]按行序为主序寄存，每个元素占4个字节空间，若数组a

的首元素地虻为2023,计算a[23][21]的内存地址为(B)。

(A)5600(B)5612(02912(D)3600

9.设输入序列为1.2.3.4.5.6,则通过栈H勺作用后可以得到的输出序列为

(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

10.设有一种10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右口勺

次序存储到持续的£5个存储单元中，每个数组元素占1个字节的存储空间，则

A[5][4]地址与A[0][0]的J地址之差为(B)□

(A)10(B)19(C)28(D)55

11.广义表A=(a,b(c,d),(e,(f,g))),则head(tail(head(tail(tail(A)))))值为

(D)

(A)(g)(B)(d)(C)(c)(D;(d)

12.数据的最小单位是(A)«

(A)数据项(B)数据类型(C)数据元素(D；数据变量

13.函数substr("DATASTRUCTURE"，5,9)的返回值为(A)。

(A)“STRUCTURE”(B)“DATA”

(0“ASTRUCTUR”(D)“DATASTRUCTURE”

14.在线性表中，一•种向量第一种元素的存储地址是100,每个元素的长度为2,则第5

个元素口勺地址是(Ar

(A)110(B)108(C)100(D)120

15.栈中元素的进出原则是(B)o

(A)先进先出(B)后进先出(C)栈空则进(D)栈满则出

16.设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指

向被插入的结点X,则在结点A和结点B插入结点XH勺操作序列为(B)。

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

(C)p->ncxt=s->ncxt；s->ncxt=p；(D)p->ncxt=s：s->next=q：

非线性构造

1.具有n（n>0）个结点的完全二叉树H勺深度为C°

（A）「Iog2（n）l（B）Llog2（n）J（C）Llog2（n）J+l（D）Flog2（n）+1~\

2.树最适合用来表达（C）o

（A）有序数据元素（B）无序数据元素

（C）元素之间具有分支层次关系的数据（D）元素之间无联络口勺数据

3.二叉树的第k层的结点数最多为（D）.

(A)2-1(B)2K+1(C)2K-1(D)2k

4.设一棵完全二叉树有700个结点,则共有（）个叶子结点。

(A)200(R)方0(C)300(I))渤

5.若有18个元素H勺有序表寄存在一维数组A[19]中，第一种元素放A[I]中，现进行二分

查找，则查找A[3]的比较序列H勺下标依次为（D）

(A)1.2,3(B)9.5,2,3

(C)9,5,3(D)9,4,2,3

6.对n个记录的文献进行迅速排序，所需要的辅助存储空间大体为(C)

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

7.设一组初始关键字记录关键字为(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,21

(D)15,10,14,18,20,36,40,21

8.设无向图G中有n个顶点a条边，则其对应的邻接表中H勺表头结点和表结点的个数分别

为(D)0

(A)n,c(B)c,n(C)2n,c(D；n,2e

9.设有500()个待排序的记录关键字，假如需要用最快的措施逃出其中最小的10个记录关

键字，则用下列(B)措施可以到达此目H勺。

(A)迅速排序(B)堆排序(C)归并排序(D)插入排序

10.下列四种排序中(D)的空间复杂度最大。

(A)插入排序(B)冒泡排序(C)堆排序(D；归并排序

11.设一棵二叉树的深度为k：则该二叉树中最多有(D)个结点。

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

12.设一组初始记录关键字序列为(25,50,15,35,80,85,20,40,36,70),其中具有5个长

度为2的有序子表，则用口并排序I的措施对该记录关键字序列进行一趟归并后H勺成果为

()。

(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

13.设有序表中有1(X)0个元素，则用二分查找查找元素X最多需要比较(B)次。

(A)25(B)IC(C)7(D)1

14.设某棵二叉树的高度为10,则该二叉树上叶子结点最多有(C

(A)20(B)2=6(0512(D;1024

15.在一种具有n个顶点的无向连通图中，要连通所有顶点至少需要(C)条边。

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

16.对于线性表(7,34,55,25,64,46,20,10)进行散列存储时，若选用H(K)=K%9

作为散列函数，则散列地址为1的元素有(D)个，

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

17.设有6个结点H勺无向图，该图至少应有(A)条边才能保证是一种连通图。

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

18.二叉排序树中左子树上所有结点的值均....)根结点的值。

(A)<(B)>(0=(D)!=

19.设一组权值集合的(15,3,14,2,6,9,16,17),规定根据这些权值集合构造一

棵哈夫曼树，则这棵哈夫曼树附带权途径长度为...)O

(A)129(B)219(C)189(D)229

20.设某棵二叉树中只有度数为0和度数为2H勺结点且度数为0H勺结点数为n,则这棵

二叉中共有(C)个结点。

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

21.设一组初始记录关键字序列为(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,E,D,F,X,Y

22.设用邻接矩阵A表达有向图G的存储构造，则有向图G中顶点i口勺入度为(B)»

(A)第i行非0元素的个数之和(B；第i列非。元素的个数之和

(0第i行0元素的个数之和(D；第i列。元素的个数之和

填空题：

1.设F和R分别表达次序循环队列的头指针和尾指针，该队列最存储空间为N个，则判断

该循环队列为空的条件为_F==A,判断队列为满时条件为

(R+1)%N==Fo

2.一种线性表是n^O个数据元素al,Q2,a3,……an的有限序列，表中每个数据元素，除

第一种和最终一种外，有且仅有一种直接前驱和一种直接后继。

3.不管是次序存储构造的栈还是链式存储构造的栈，其入栈和出栈操作的时间复杂度均

为-0⑴。

4.设输入序列为1.2.3,则通过栈的作用后可以得到—5种不一样的输出序列。

5.若用链表存储一棵二叉树时，每个结点除数据域外，尚有指向左孩子和右孩子的两个指

针。在这种存储构造中，n个结点的二叉树共有-2n一个指针域，其中有_n-l_个

指针域是寄存了地址，有n+1一个指针是空指针。

6.对于一种具有n个顶点和e条边的有向图和无向图，在其对应口勺邻接表中，所含边结点

分别有_个和个。在一种具有n个顶点的无向完全图中，包具有________条

边，在一种具有n个顶点的有向完全图中，包具有条边。

7.在迅速排序、堆排序、归并排序中，—归并排序是稳定日勺。

8.中序遍历二叉排序树中的结点可以得到一种递增的关键字序列(填先序、中

序或后序)。

9.设查找表中有100个元素，假如用二分法查找措施查找数据元素X,则最多需要

比较—7—次就可以断定数据元素X与否在查找表中。

10.设有向图G中有n个顶点c条有向边，所有口勺顶点入度数之和为d,则。和dH勺

关系为_e=d。设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和

为d,则e=_d/2_____,,

11.设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则运用筛

选法建立的初始堆为_31,38,44,56,75,80,55,63

已知一有向图H勺邻接表存储构造如下：从顶点1出发，深度优先搜索(Dfs)的输出序列是

134,5.2,广度优先搜索(BFS；遍历的输出序列是132,4.5

图的邻接表存储结构

12.假定一种线性表为表2,23,74,55,63,40),若给出哈希函数H(key)=Key%4条件进行

划分，使得同一余数的元素成为一种子表，则得到的四个子表分别为

和___________________________

13.

14.设有n个结点的完全二叉树，假如按照从自上到下、从左到右从1开始次序编号，则第

i个结点H勺双亲结点编号为_i/2.,右孩子结点的编号为—2i+l

15.设一组初始记录关键字为(72,73,71,23,94,16,5),则以记录关键字72为基准H勺

一趟迅速排序成果为。

16.设有向图G中有向边的集合E=kl,2>,<2,3>,<1,4>,<4,2>,<4,3>},则该图

的一种拓扑序列为—1,4,2,3―o

17.设哈夫曼树中共有n个结点，则该哈夫灵树中有__0_个度数为1的结点.

18.设有向图G用邻接矩阵A[n][n]作为存储构造，则该邻接矩阵中第i行上所有元素之和

等于顶点i的一行为出度第i列.上所有元素之和等于顶点i口勺一行为入度

19.为了能有效地应用HASH兖找技术，必须处理的两个问题是—构造好H'、Jhash函数—和

确定处理冲突措施。

20.中序遍历二叉排序树所得到的序列是—有序—序列(填有序或无序)。

折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它将依次与表中

元素28,6,12,20比较大小。

线性构造中元素之间存在一对一关系，树形构造中元素之间存在关系

一对多，图形构造中元素之间存在多对多关系。

问答题

设某棵二叉树的中序遍历序列为DBEAC,前序遍历序列为ABDEC,规定给出该二叉树的的后

序遍历序列并画出该二叉树。

2.已知待散列H勺线性表为(36,15,40,63,22),散列用的一维地址空间为[0..6],假定选用口勺

散列函数是H(K)=Kmod7,若发生冲突采用线性探查法处锂，试：il算出每一种元素H勺

散列地址并在下图中填写出散列表:

0123456

设无向图G(如右图所示)，画出该图的最小生成树的构造，并写出该图的最小生成树边口勺

集合及计算最小生成树各边上的权值之和。

4.已知序列(10,18,4,3,6,12,1,9,18*,8)请用迅速排序写出每一趟排序口勺成果。

5.设一组初始记录关键字序列为(45,80,48,40,22,78),则分别给出第4趟直接选择

排序和第4趟直接插入排序后的成果。

6.给定一姐权值(2,&5,4,3},构造对应口勺