2023年数据结构考试试卷(含五卷)

2023年数据结构考试试卷(一)

一、单项选择题(共50题，每小题2分，共100分)

1、若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的

顶点，则该图一定是(：)图

A、非连通

B、连通

C、强连通

D、有向

2、设有序表为{9,12,21,32,41,45,52},当二分查找值为52的结点时，元素

之间的比较次数是(C)。

A、1

13、2

C、3

D、4

3、关于顺序表的说法不正确的是？

A、逻辑关系上相邻的两个元素在物理存储位置上也相邻

B、可以随机存取表中任一元素，方便快捷

C、在线性表中插入某一元素时，往往需要移动大量元素

D、在线性表中删除某一元素时，无需移动大量元素

4、下列程序的空间复杂度是()。

For(i=l;i〈=n;++i){for(j=l;j<=m;++j){}}

A、0(m*n)

0(m+n)

C^O(m-n)

O(m/n)

5、树中所有结点的度等于所有结点数加()。

A、0

B、1

C^-1

D、2

6、以下排序方法中，()不需要进行关键字的比较。

A、快速排序

B、归并排序

C、基数排序

D、堆排序

7、顺序查找法适合于存储结构为()的线性表

A、散列存储

B、顺序存储或链式存储

c、压缩存储,

D、索引存储

8、如果按关键码值递增的顺序依次将99个关键码值插入到二叉排序树中，则对

这样的二又排序树检索时,在等概率情况下:查找成功时的平均查找长度ASL为

A、50

B、48

C、45

D、47I"；""：""；"；"；"

9、下述哪一条是顺序存储结构的优点

A、可方便地用于各种逻辑结构的存储表示

B、插入运算方便

C、删除运算方便

D、存储密度大

10、设二叉排序树上有n个结点,则在二叉排序树上查找结点的最多的时间复杂

度()

A、0(n)

B、O(n^2)

C^O(nlog2n)

D、O(log2n)

1k已知一个有序表为(11,22,33,44,55,66,77,88,99),则折半查

找55需要比较()次。(1分)

A、1

B、2

C、3

D、4

12、使用二叉线索树的目的是便于(D)。

A、二叉树中结点的插入与删除

B、在二叉树中查找双亲

c、确定二叉树的高度二;;丁；

D、查找-一个结点的前趋和后继

13、(4分)从一个栈顶指针为HS的链栈中删除一人结点时，用x保存被删结点的

值,则执行(D)。

A、x=HS;HS=HS->next;

B、x=HS->data;

C>HS=HS->next;x=HS->data;

D、x=HS->data;HS=HS->next;

14、一维数组与线性表的区别是()

A、前者长度固定，后者长度可变

B、两者长度均固定

C、后者长度固定，前者长度可变

D、两者长度均可变

15、(3分)在具有n个顶点的无向完全图G中边的总数为(B)。

A^ii+l

B、n(-l)/2

C、n(n+l)

D、n-1

16、(4分)设带头结点的单循环链表的头指针为head,指针变量P指向尾结点的

条件是⑻。

A、p->next->next=-head

B、p->next-head

C^p->next->next-NULL

D、p->next==NULL

17、下列关于线性链表的叙述中，正确的是()。

A、各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须

一致

B、各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须

连续B/Q

C、进行插入与删除时•，不需要移动表中的元素

D、以上说法均不正确

18、算法分析的两个主要方面是("(5.0分)

A、正确性和简明性

B、可读性和正确性,ll；；；

C、稳定性和健壮性

D、时间复杂度和空间复杂度

19、在完全二叉树中，若一个结点是叶结点，则它没

A、左子结点

B、右子结点

C、左子结点和右子结点

D、左子结点，右子结点和兄弟结点

20、对表长为n的有序顺序表进行折半查找,其判定树的高度为()

A、log2(n+1)

B、lug2(u+D-1

C^log2n

D、log2(n-l)

21、若采用邻接矩阵A存储有向图G,则结点k的入度等于A中。

A、结点k对应行元素之和

B、：结点k对应列元素之和

C、结点k对应行和列元素之和

D、非零元素之和

22、有一个关键字序列,采用依次插入方法建立一棵二叉排序树,该二叉排序树

的形状取决于0

A、该序列的存储结构

B、序列中的关键字的取值范围

C、关键字的输入次序

D、使用的计算机的软、硬件条件

23、根据初始关键字序列（19,22,01,38,10）建立的二叉排序树的高度为（）。

A、2"工：

B、3

C、4

D、5

24、在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修

改指针的操作是（）。

A、p->next=q;q->prior=p;p->next->prior=q;q->next=q;

B、p->ncxt=q;p->next->prior=q;q->prior=p;q->next=p->ncxt;

C、q->prior=p;q->ncxt=p->noxt;p->noxt->prior=q;p->noxt=q;

D、q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;

25、对有n个数的数列进行冒泡排序,至少应该交换（）次？

A、0

B、n/2

C、n

D、2u

26、给定排序码值序列为｛F,B,J,C,E,A,I,D,C,H],对其按字母的字

典序列的次序进行排列，冒泡排序（大数下沉）的第一趟排序结果应为

A、｛B,F,C,J,A,E,D,I,C,H｝

B、｛C,B,D,A,E,F,T,C,J,H｝

C、｛B,F,C,E,A,I,D,C,H,J｝

D、{A,B,D,C,E,F,I,J,C,H}

27、算法能正确的实现预定功能的特性称为算法的（）。

A、正确性

B、易读性

C、健壮性

D、高效性

28、下列叙述中正确的是（）。

A、在循环队列中，队头指针和队尾指针的动态变化决定队列的长度

B、在循环队列中，队尾指针的动态变化决定队列的长度

C、在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度

D、在带链的栈中，栈顶指针的动态变化决定栈中元素的个数

29、设栈S和队列Q的初始状态为空，元素。2,P4.P5和依

次通过栈S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,

e4,e3,e6,e5,el则栈S的容量至少应该是（）

A、6

C、3I"；"；［"；"；"；：】

D、2

30、已知指针p指向单链表L中的某结点，则删除其后继结点的语句是

A^p=p->next

B、p二null

C、p->next=null

D^p->next=p->next->next

31、（3分）线性表适合丁顺序查找的存储结构是（C）。

A、索引存储

B、压缩存储

C、顺序存储

D、散列存储

32、在下列存储形式中，（）不是树的存储形式?

A^双亲表示法

B、孩子链表表示法

C、孩子兄弟表示法

D、顺序存储表示法

33、顺序栈是空栈的条件是（）。

A、top==0

B、top==l

C、top--1

D、top-m

34、在数据结构中，从逻辑上可以把数据结构分成（）。（5.0分）

A、线性结构和非线性结构

R、线性结构和树形结构

C、动态结构和静态结构

D、内部结构和外部结构,

35、在一棵二叉树上第5层的结点数最多为（）

A、8

B、15

C、16

D、32

36、用邻接表存储图所用的空间大小（）

A、与图的顶点数和边数都有关

B、只与图的边数有关

C、只与图的顶点数有关

D、与边数的平方有关

37、深度为h的满m叉树的第k层有（）个结点。（IWkWH）

A、mk-1

B、mk-1

C、mh-l

D、mh-l

38、一个容量为15的循环队列中，若头指针front=5,尾指针rear=9,则

该循环队列中共有（）个元素。

A、5

B、9

C、4

D、14

39、设某散列表的长度为100,散列函数H（k）=k%P,则P通常情况下最好选

择（）。

A、99V/.

B、97:"二

91.:•••<•<-

I）、93

40、在以下的叙述中，正确的是（）。

A、线性表的顺序存储结构优于链表存储结构

B、线性表的顺序存储结构适用于频繁插入/删除数据元素的情况

C、线性表的链表存储结构适用于频繁插入/删除数据元素的情况

D、线性表的链表存储结构优于顺序存储结构

41、一个栈的入栈序列是A,B,C,D,E,则栈的不可能的输出序列是（）

A、EDCBA

B、DECBA

C、DCEAB

D、ABCDE

42、已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。

现要将指针M指向的新结点插入到指针P指向的结点之后，下面的操作序列

中正确的是（）

A、q=p->next;

B、p->next=q->next;p->next=q->next;q=p->next;

C、q->next=p->next;

D、p->next=q;P->next=q;q->next=p->next;

43、一个队列的入队序列是a,b,c,d,则队列输已序列是

A、d,c,b,a

B、a,b,c,d

Ca,d,c,b

D、c,b,cl,a

44、一棵深度为6的满二叉树一共有个()结点

A、31

B、32

C、63V/.

D、64

45、数据结构这门学科是针对什么问题而产生的？

A、针对非数值计算的程序设计问题

B、针对数值计算的程序设计问题

C、数值计算与非数值计算的问题都针对

D、两者都不针对

46、设一组权值集合收⑵3,4,5,6},则由该权值集合构造的哈夫夏树中带权路

径长度之和为()。

A、20

B、30

C、40

D、45

47、(4分)在一个单链表中，若删除p指向结点的后继结点,则执行的操作为

(A)o

A、q=p->ncxl;p->iicxl=p->iiuxl->iicxI;free(q)

B>p=p->next;q=p->next;p=q->next;fe(e)

C、q=p->next->next;p=p->next;free(q)

Dsp=p->next->next;q=p->next;feeq)

48、算法的计算量大小称为算法的()。

A、现实性

B、难度

C、时间复杂性

D、效率

49、对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,

所含边结点分别()个。

A、ee+1

B、e2e

C、2e2e+l

D、e2e-l

50、若串S="software”，其子串的数目是()。

A、8

R、37

C、36

D、9

参考答案

一、单项选择题

1、B

2、C

3、D

4、A

5、C

6、C

7、B

8、A

9、D

10、A

11、A

12、D

13、D

14、A

15、B

16、B

17、C

18、D

19、C

20、A

21、B

22、C

23、B

24、C

25、A

26、C

27、A

28、A

29、C

30、D

31、C

32、D

【解析】解释：树的存储结构有三种：双亲表示法、孩子表示法、孩子兄弟表

示法，其中孩子兄弟表示法是常用的表示法，任意一棵树都能通过孩子兄弟表

示法转换为二叉树进行存储。

33、AV/上

34、A.....二

36、A

37、A

38、C

39、B

40、C

41、CI"；""："["；"；"；

42、C

43、B

44、C

45、A

46、D

47、A

48、C

49、B

50、B

2023年数据结构考试试卷（二）

一、单项选择题（共50题，每小题2分，共100分）

1、以下数据结构中哪一个是非线性结构？

A、队列

B、栈

C、线性表

D、二叉树

2、下面程序段的时间复杂度是（）。I=s=0;

while（s<n）{i++;s+=i;}?应该是0（根号n）

A、0（n）

B、0（if2）

C、0（log2n）

D、0（—3）

3、算法的时间复杂度是由（）决定的。

A、问题的规模

B、待处理数据的初态

C、A和B

D、变量个数

4、设有100个元素，用折半查找法进行查找时，最大、最小比较次数分别时

A、7,1

B、6,1

C、5,1

D、8,1

5、若要求尽可能快地对序列进行稳定的排序，则应选（B）。

A、快速排序

B、归并排序

C、冒泡排序

D、选择排序

6、下面有关算法说法错误的是（）。

A、算法最终必须曰计算机程序实现

B、为解决某问题的算法同为该问题编写的程序含义是相同的

C、算法的可行性是指指令不能有二义性

D、算法有5大特性

7、数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的(C)

的两趟排序后的结果。

A、选择排序

B、冒泡排序

C、插入排序X

；D、堆排序：

8、用二分查找法查找具有n个结点的顺序表时,查找每个结点的平均比较次数

是(I(5.0分)

A、O(n2)

B、O(nlgn)

C、0(n)

D、0(lon)

9、在下面的程序段中,x=x+l;的语句频度为()。

for(i=l;i<=n;i++)for(j=l;j<=n;j++)x=x+l;

A、0(2n)

B、0(n)

C、0(rf2)

D、0(log2n)

10、设一组初始记录关键字序列为列,H,C,Y,P,A,M,S,R,D,F,X),

则按字母升序的笫一趟冒泡排序结束后的结果是()。

A、F,H,C,D,P,A,M,Q,R,S,Y,X

B、P,A,C,S,Q,D,F,X,R,II,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

11、设输入序列1、2、3、…、n经过栈作用后，输出序列中的第二个元素是n,

则输出序列中的第i个输出元素是()o

A、n-i

B、n-1-i

C、n+l-i

D、不能确定

12、一棵树的广义表表示为a(b(c),d(e(g(h)),f,k)),则该树的高度为

()

B、4"上：

.一

【)、6

13、插入和删除只能在一端进行的线性表是

A、循环队列

B、栈

C、队列

D、循环栈

14、具有10个叶结点的二叉树中有(B)人度为2的结点，

A、8

B、9

C、10

D、11

15、高度为K的二叉树最大的结点数为()

A、2k

B、2k-l

C、2k-1

D、2k-l-l

16、在任何情况下，时间复杂度均为0(nlgn)的K稳定的排序方法是()。

⑵0分)

A、直接插入

B、快速排序

C、堆排序

D、归并排序

17、设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中

的叶子数为（D）

A、5

B、6

D、8"工

18、串是（）。飞:

A、少于一个字母的序列

B、任意个字母的序列

C、不少于一个字符的序列

D、有限个字符的序列

19、在表长为n的链表中进行顺序查找，它的平均查找长度为（）。（5.0

分）

A、n/2

B、（n+l）/2

C、Jn+1

D、lg（n+l）-l

20、评价一个算法性能好坏的重要标准是

A、算法的正确性

B、算法易丁调试

C、算法的时间和竺间复杂度

D、算法易于理解

21、设有1000个元素，用二分法查找时，最小比较次数为（）。（1分）

A、0

B、1

C、10

D、500

22、将一棵有100个结点的完全-二叉树从根开始,每-层从左到右依次对结点进

行编号，根结点的编号为10,则编9的结点的左孩子编号为(B)。

A、99

B、98

C、50

D、48

23、无向图G=(V,E),其

中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(c,d)},对该

图进行深度优先遍历,得到的顶点序列正确的是(D)。

A、a,h,p,c,d,f

B、a,c,f,e,b,cl

C、a,e,b,c,f,cl

D、a,e,d,f,c,b

24、设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度

为()。

A、O(n)

B、O(nlog2n)

C、0(1)

D、O(n2)

25、线性表的链式存储结构是一种()存储结构

A、随机存取

B、顺序存取

C、索引存取

D、散列存取

26、判定一个循环队列队(最多元素为m0,m0==Maxsize-l)为满队列的条件

A、((rear-front)+Maxsize)%Maxsize==m0

B、rear-front-l==mO

C、front==rear

D、front==rear+1

27、在数据结构中，从逻辑上可以把数据结构分成

A、动态结构和静态结构

B、紧凑结构和非紧凑结构

C、线性结构和非线性结构

D、内部结构和外部结构

28、有向图采用邻接矩阵存储，某行中非零元素的个数等于。

A、对应顶点v的度二;

B、对应顶点v的巴度

C、对应顶点v的入度

D、依附于对应顶点v的边数

29、下面给出的四种排序法中(D)排序法是不稳定性排序法。

A、插入

B、冒泡

C、二路归并

D、堆积

30、下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。

(A)

A、选择排序法

B、插入排序法

C、快速排序法

D、堆积排序法

31、下面关于稀疏矩阵的快速转秩算法说法正确的是()。

A、算法时间复杂度要优于普通转秩算法

B、算法时间复杂度为0(n),n是矩阵的行数

C、算法空间复杂度要优于普通转秩算法

D、算法适合于行和列数基本相等的状况

32、对于一个有向图，若一个顶点的度为kl,出度为k2,则对应逆邻接表中该

顶点单链表中的边结点数为（）

A、kl

B、k2

C、kl-k2

D、kl+k2

33、排序方法中，从未排序序列中依次取出元素与己排序序列（初始时为空）

中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）

A、希尔排序X/,

B、起泡排序♦;匚；

C、插入排序

I）、选择排序

34、（4分）栈的操作原则是（C）。

A、顺序进出

B、后进后出

C、后进先出

D、先进先出

35、若栈采用顺序存储方式存储，现两栈共享空间V[m],top[i]代表第i个

栈（i=1,2）栈顶，栈1的底在v[0],栈2的底在V[m-1],则栈满的条件是

（）

A、top[2]-top[l]=0

top[l]+l=top[2]

C、top[l]+top[2]=m

D、lop[l]=lop[2]

36、下列数据结构中，不属于二叉树的是。

A、B树

B、AVL树

C、二叉排序树

D、哈夫曼树

37、在一个链队中，假设和分别为队首和队尾指针,则插入s所指结点的运算时

(B)o

A、f->next=s;f=s;

r->next=s;r=s;

C、s->next=r;r=s;

Dss->next=ff=s;

38、在平衡二叉树中，每个结点的平衡因子的取值范围为()。

A、-ri

B、o~iV/A

c、-2~2-

.•••••••

39、最大容量为maxs-ZP的循环队列，队尾指针是rear,队头是front,则

队满条件为()

A、(rear+1)maxsize==(front+l)maxsize

B、(front+1)niaxsize==rear

C、(rear+1)maxsize二二front

D^rear==front

40、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有()个结

点。

A、12

B、13

C、25

D、26

41、若对”阶矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所

有元素)依此存放于一维数组B[L.(n(n+l)/2]中,则在B中确定a[i][j](i<j)

的位置k的关系为()

A、i*(i-l)/2+j

B、j*(j-l)/2+i

C、i*(i+l)/2+j

D、j*(j+l)/2+i

42、树形结构是数据元素之间存在一种()

A、一对一关系

多对多关系

C、多对一关系

D、一对多关系

43、下面程序段执行的时间复杂度为()opublicstaticvoid

main(String[]args){inti=l,n=100;while(i<=n){i=i*2;

System,out.printin(i);}(5.0分)

A、0(n)号/二[J]

B、0(log2n)

C、0(n2)

D、0(n3)

44、数据在计算机存储器内表示时,物理地址与逻辑地址不相同的,称为()

A、存储结构

B、逻辑结构

C、链式存储结构

D、顺序存储结构

45、深度为4的二叉树至多可以有的结点数为。

A、17

B、13

C、18

D、15

46、N个顶点的无向连通图，其姓成树的边数为(A)。

A^n-l

B、n

C、n+1

D、nlogn

47、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为

(C)。

A、0(n)0(n)

B、0(n)0(1)

C、0(1)0(n)

D、0(1)0(1)

48、图中有关路径的定义是(A)。

A、由顶点和相邻顶点序偶构成的边所形成的序列

B、由不同顶点所形成的序列

C、由不同边所形成的序列

D、上述定义都不是

49、广度优先遍历类似于二叉树的()0

A、先序遍历

:B、中序遍历"，

C、后序遍历

D、层次遍历

50、(4分)长度为n的顺序表,删除位置i上的元素(Osisn-1),需要移动的元素

个数为(B)o

A^n-i

B、n-i-1

C、i

D、i+1

参考答案

一、单项选择题

1、D

2、A

3、A

4、A

5、B

6、B

7、C

8、D

9、C

10、D

11、D

12、C

13、B

14、B

15、C

16、C

17、D

18、D

19、B

20、C

21、B

22、B

23、D

24、C

25、B

26、A

27、C

28、B

29、D

30、A

31、A

32、C

33、C

34、C

35、B

36、A

37、B

38、A

39、C

40、C

41、A

42、D

43、B

44、C

45、D

46、A

47、C

48、A

49、D

50、B

2023年数据结构考试试卷（三）

一、单项选择题（共50题，每小题2分，共100分）

1、一个递归算法必须包括（）。

A、递归部分

B、终止条件

C、终止条件和递归部分

D、以上答案都不对

2、链表不具有的特点是（）。

A、可随机访问任一元素；，/；「；：二；•「】；

B、插入删除不需要移动元素

C、不必事先估计存储空间

D、所需空间与线性表长度成正比

3、对线性表进行二分查找时，要求线性表必须

A、以顺序方式存储

B、以顺序方式存储，且结点按关键字有序排序

C、以链接方式存储

D、以链接方式存储，且结点按关键字有序排序

4、下述哪一条是顺序存储结构的优点？（A

A、存储密度大

B、插入运算方便

C、删除运算方便

D、可方便地用于各种逻辑结构的存储表示

5、设有两个串p和q,求p和q首次出现的位置的运算称作（）

A、连接

B、模式匹配

C、求子串

D、求串长

6、设无向图G中有五个顶点，各顶点的度分别为2、4、3、1、2,则G中边

数为（）

A、4

B、5

C、6

D、无法确定

7、在单链表中设置头结点的作用是（）

A、单链表定义而已

B、为方便链表的操作

C、为双向链表做准备

D、为循环链表做准备

8、下列排序方法中,平均时间性能为O（nlogn）且空间性能最好的是（）。（1

分）•••••••

A、快速排序

】B、堆排序；：

C、归并排序

D、基数排序

9、判定一个顺序栈S（栈空间大小为n）为空的条件是（）

A^S->top==-l

B、S->top!=0

C^S->top==n

D^S->top!=n

10、下列排序算法中（）排序在一趟结束后不一定能选出一个元素放在其最终

位置上。（2.0分）

A、选择

B、冒泡

C、归并

D、堆

11、已知某二叉树的后序遍历序列是DabeC,中序遍历序列是DebaC,它的前序

遍历序列是（）

A、aCbeD

DeCaB

C、DeabC

D、CeDba

12、“二叉树为空”意味着二叉树（）o（3.0分）

A、由一些没有赋值的空结点构成

B、根结点没有子树

C、不存在

D、没有结点

13、将序列序00,80,90,60,120,110,130,1,2,3）生成二叉排序树，则该树的高度

R、5

C、6：

D、7

14、设指针变量p指向双向链表中结点A,指针变量s指向插.入的结点X,则

在结点A的后面插入结点X的操作序列为（）。

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；

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

（）O

A、n

B、e

C、2n

D、2e

16、i=0;S=0;While(s<n)s+=i++;

A、0(1)

B、0(n71/2))

C、0(n)

D、0(rT2)

17、在一个含n个顶点和e条边的无向图的邻接矩阵中,表示边存在的元素的个

数为()o(5.0分)

A、e

B、2e

C、n2-e

D、n2-2e

18、二维数组A中，每个元素的长度为3个字节，行下标i从0到7,列下标j

从0到9.从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节

数是

A、80

B、100

C、240

D、270I"；""：""；"；"；"

19、一棵完全二叉树上有101个结点，其中叶子结点的个数是()

A、50

B、51

C、52

D、53

20、循环链表的主要优点是()0

A、不再需要头指针

B、己知某结点位置后能容易找到其直接前驱

C、在进行插入、删除运算时能保证链表不断开

D、在表中任一结点出发都能扫描整个链表

21、设一组初始记录关键字序列⑸2,6,3,8),以第一个记录关键字5为基准进

行一趟快速排序的结果为()o

A^2,3,5,8,6

B、3,2,5,8,6

C、3,2,5,6,8

D、2,3,6,5,8

22、（4分）判定一个队列QU（最多元素为m）为空的条件是（C）。

AsQU->rear-QU->front==m

B、QU->rear-QU->front-l==m

C、QU->front==QU->rear

D、QU->front==QU->rear+l

23、在一个顺序循环队列中，队尾指向队尾元素的（）位置。

A、前一个

R、后一个

C、当前

D、最后

24、二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,…,8,列

下标j=l,2,…，10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存

储时的元素（）的起始地址相同。设每个字符占一个字节。

A、A[8,5]

B、A[3,10]

C、A[5,8]

D.A[0,9]

25、下列关于二叉树的说法正确的是（）

A、一棵二叉树中的结点个数大于0

B、二叉树中任何一个结点要么是叶子，耍么恰有两个子女

C、一棵二叉树中叶子结点的个数等于度为2的结点个数加1

D、二又树中任何一个结点的左子树和右子树上的结点个数一定相等

26、栈的插入和删除操作在（）o

A、栈底

B、栈顶

C、任意位置

D、指定位置

27、数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性

上，链式存储比顺序存储要

A^低

B、高

C、相同

D、不好说

28>一棵含有n个结点的树，（）形态达到最大深度

A、单支树:二:•

B、二叉树

C、二叉树

D、n叉树

29、以下数据结构中，（）是非线性数据结构

A、树

B、字符串

C、队列

D、栈

30、对n个不同的记录按排序码值从小到大次序重新排列,用快速排序方法,在

（）情况下排序码值总比较次数最多。

A、按排序码值从小到大排列

B、基本按排序码值降序排列

C、随机排列（完全无序）

D、基本按排序码值升序排列

31、一颗二叉树高度为h（根的高度为1）,所有结点的度为0,或者为2,则这颗二

叉树最少（）结点。（3.0分）

A、2h

B、2h-l

C、2h+l

D、h+1

32、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可

能出现的是（）

A、G中有弧<Vi,Vj>

B、G中有一条从Vi到Vj的路径

C、G中没有弧

D、G中有一条从Vj到Vi的路径

33、算法的时间复杂度取决于（）o

A、输入量的多少

B、数据初始状态.二;｝二

C、内存的大小

I）、硬盘的大小

34、关于二叉树的说法正确的是（）。

A、所有二叉树的度均为2

B、一棵二叉树的度可以小于2

C、一棵二叉树中至少有一个结点的度为2

D、一棵二叉树的根结点的度必为2

35、用顺序存储的方法将完仝二叉树中的所有结点逐层存放在数组中

R[l..n],结点R[i]若有左孩子，其左孩子的编号为结点

A、R[2i+1]

B、R[2i]

C、R[i/2]

D、R[2i-1]

36、对丁TOO个长度不等的初始归并段,构建5路最住归并树时，需要增加（）

个虚段。

A、0

B、1

C、2

D、3

37、用链式存储的栈，在进栈操作时，将要进栈的结点放在链表的（）

A、头部

B、尾部

C、中间

D、用户指定的位置

38、在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时,删除一

个元素所需移动的平均个数为（）0

A、（n-l）/2

B、n/2

C、（n+l）/2二【

D^n

39、双向链表中有两个指针域，11ink和rlink分别指向前趋及后继，设p

指向链表中的一个结点，现要求删去P所指结点，则正确的删除是（）（链

中结点数大于2,p不是第一个结点）。

A、p->l1ink->rlink=p->l1ink;

B、"]]

free（p）;P->llink->rlink=p->rlink;p->l1ink->rlink=p->l1ink;Free（p）;p->

Hink->r1ink=p->rlink;

C^p->l1ink->rlink=p->l1ink;

D、以上A,B,C者R不对。free（p）;P->11ink->r1ink=p->rlink;

40、在进栈运算时，应先判别栈是否①，在出栈运算时.应先判别栈是否②，

①②处应该是（）

A、空，满

B、满，空

C、满，上溢

D、空，下溢

41、数组A中，每个元素A的长度为3个字节，行下标i从1到5,列下标j

从1到6,从首地址开始连续存放在存储器内，存放该数组至少需要的单元数

是（）。

A、90

B、70

C、50

D、30

42、表长为n的顺序存储的线性表，当在任意位置上插入或删除一个元素的概

率相等时，插入一个元素所需移动元素的平均个数为(D、),删除一个元素

需要移动元素的平均个数为()

A、(n-l)/2

B、n

C、(n+l)/2二：：：」1

43、算法分析的两个主要方面是().

A、空间复杂性和时间复杂性

B、正确性和简明性,ll；；.

C、可读性和文档性

D、数据复杂性和程序复杂性

44、设栈S和队列Q的初始状态为空,元素。1、。2、。3、。4、°5和c6依次进

入栈S,一个元素出栈后即进入Q,若6个元素出队的序列是02、。4、。3、

e6、e5和el,则栈S的容量至少应该是()。

A、2

B、3

C、4

D、6

45、某二叉树的中序序列为ABCDEFG,后序序列为BDCAFGE,则其左子树数目为

()。(3.0分)

A、3

B、2

C、4

D、5

46、为解决计算机主机与打印机间速度不匹配问题，通常设一个打数据缓冲

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

出数据。该缓冲区的逻辑结构应该是()。

A、队列

B、栈

C、线性表

D、有序表

47、对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是

A、NV'.

B、(N-D2：

......

I)、N*N

48、以下说法正确的是()。

A、数据元素是数据的最小单位

B、数据项是数据的基本单位

C、数据结构是带有结构的各数据项的集合

D、一些表面上很大相同的数据可以有相同的逻辑结构

49、设带权连通图G中含有n(n>l)个顶点。条边。下列叙述中，正确的是

A、最小生成树中--定含有权值最小的e条边

B、最小生成树中可能含有权值最小的n+1条边

C、最小生成树中一定含有权值最小的n条边

D、最小生成树中可能含有权值最小的n-I条边

50、索引顺序表的特点是顺序表中的数据

A、有序

B、无序

C、块间有序

D、散列

参考答案

一、单项选择题

1、C

2、A

3、B

4、A

5、B

6、C

7、B"工

8、B

9、A

10、C

11、D

12、D

13、C

14、D

15、D

16、B

17、B

18、C

19、B

20、D

21、C

22、C

23、B

24、B

【解析】解释：设数组从内存首地址M开始顺序存放，若数组按行先存储，元

素A[8,5]的起始地址为:M+[(8-0)*10+(5-1)]*l=M+84；若数组按列先存

储，易计算出元素A[3,10]的起始地址为：M+[(10-1)*9+(3-0)]*1=M+84O

故选B。

25、C

26、B

27、B

28、A

29、A

30、A

31、BV/4

32、D

33、B

34、B

35、B

36、B

37、A

38、A

39、D

40、B

41、A

42、D

43、A

44、B

【解析】解释：元素出队的序列是e2、e4、e3、e6、e5和el,可知元素入队

的序列是c2、u4>e3、6e5和4,即元素出栈的序列也是e2、“、匕3、

e6、e5和el,而元素el、e2>e3、e4>e5和e6依次进入栈，易知栈S中最多

同时存在3个元素，故栈S的容量至少为3。

45、C

46、A

【解析】解释：解决缓冲区问题应利用一种先进先出的线性表，而队列正是一

种先进先出的线性表。

47、D

48、D

【解析】解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据

结构是带有结构的各数据元素的集合。

49、D

2023年数据结构考试试卷(四)

一、单项选择题(共50题，每小题2分，共100分)

1、广义表(A,(a,b,c))的表头和表尾是()o

A^A((a,b,c))

aB,c

C>(a,b,c)A

D、(a,b)c

2、不含任何结点的空树

A、是一棵树款

B、是一棵二叉树

C、是一棵树也是一棵二叉树

D、既不是树也不是二叉树

3、对于顺序表的优缺点，以下说法不正确的是()。(3.0分)

A、无需为表示结点间的逻辑关系而增加额外的存储空间

B、可以方便地随机存取表中的任一结点

C、插入和删除运算比较方便

D、容易造成一部分空间长期闲置而得不到充分利用

4、线性表是一个有限序列，组成线性表的基本单位是(B)。

A、数据项

B、数据元素

C、数据域

D、字符

5、一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是

(B)

A、CABDEFG

B、ABCDEFG

C、DACEFBG

D、ADCFEG

6、下面程序段的时间复杂性的量级为()For(i=l;i<=n;i++)

For(j=l;j<=I;j++)For(k=l;k<=j;k++)x=x+l;

A、0(1)

B、0(n)

C、0(n2)

D、0(n3)

7、在二叉排序树的()序列是一个递增有序序列。

A、先序遍历

B、中序遍历.

C、后序遍历

D、层次遍历

8、n个顶点的生成树有()条边.

A、n-1

B、n

C、n+1

D、2n

9、向一个栈顶指针为HS的链栈中插入一个s所有结点时，则执行(不带空的头

结点)

A^HS->next=s;

s—>next=HS—>next;HS—>next=s;

C、s—>next=HS;HS=s;

D、s->next=HS;HS=HS一>next;

10、设有向无环图G中的有向边集合E={<1,2>,<2,3>,<3,4>,<1,4>},假设每条

边长度为1,则1点到4点的最短距离为()

A、4

B、3

C、2

D、1

11、利用数组a[N]存储一个顺序栈时，用top标识栈顶指针，已知栈未满，

当元素x进行进栈时执行的操作是()

A、a[—top]=x;

B、a[top-]=x;

C、a[++top]=x;

Dsa[top++]=x;

12、在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印机

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

取出数据打印。该缓冲区应该是一个()结构

；A、栈；

B、队列

C、树

D、线性表

13、在一个单链表中，已知q所指结点是p所指结点的前驱结点,若在q和P之

间插入一个结点S,则执行()。

A^s->next=p->next;p->next=s;

B、p->ncxt=s->ncxt;s->next=p;

C、q->ncxt=s;s->noxt=p;

D、p->next=s;s->next=q;

14、执行完下列语句段后，i值为：()。intf(intx)

{return((x>0)?x*f(x-l):2);}inti;i=f(f(l)):

(4.0分)

A、2

B、4

C、8

D、无限递归

15、求单链表中当前结点的后继和前趋的时间复杂度分别是()。

A、0(n)和0(1)

B、0⑴和0(1)

C、0(1)和0(n)

D、0(一和08)

16、在一个链队中,假设和分别为队首和队尾指针,则删除一个结点的运算时

(C)o

A、r=f->next;

B、r=r->next;

C、f=f->next;

Dsf=r->next;

17、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和

删除运算,则利用(A)存储方式最节省时间。

A、顺序表

R、双链表

C、带头结点的双循环链表

D、单循环链表

18、设有100个元素，用折半查找法进行查找时，最大、最小比较次数分别时

()

A、7,1I"；""："["；"；"；

B、6,1

C、5,1

D、8,1第九章排序

19、数据的四种存储结构是()。

A、顺序存储结构、链式存储结构、引存储结构和散列存储

B、链式村储结构、非线性存储结构、树型存储结构和图型存储结构

C、集合存储结构一对-存储结构.一对多存储绪构和多对多存储结构

D、顺序存储结构、树型存储结构、图型存储结构和散列存储

20、算法的空间复杂度是指(

A、执行算法程序所占的存储空间

B、算法程序中的指令条数

C、算法程序的长度

D、算法执行过程中所需要的存储空间

21、如果以链表作为栈的存储结构,则退栈操作时()。

A、必须判别栈是否满

B、判别栈元素的类型

C、必须判别栈是否空

D、不做任何判别

22、(4分)队列的特点是(D)。

A、允许在表的任何位置进行插入和删除

B、只允许在表的一端进行插入和删除

C、允许在表的两端进行插入和删除

D、只允许在表的--端进行插入，在另一端进行删除

23、一个队列的入队序列是1,2,3,4,则队列的出队序列是()0(1分)

A、1,2,3,4

B、4,3,2,1

C、1,4,3,2

D、3,4,1,2

24、某哈希查找表有n条记录，对应的哈希函数具有ni个值，则()

A、n<m

n>m

C、n<=m

D、n>=m

25、若有向图G中顶点数为n,则图G至多有()条边。

A、0

C、n(n-l)/2

D>n(n-l)

26、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素

算法的时间复杂度()。(1分)

A^0(log2n)

B、0(1)

C、0(n)

D、0(if2)

27、由二叉树的前序利后序遍历序列()惟一确定这棵二叉树。

A、能

B、不能

C、如果是满二叉树就能

D、如果是完全二叉树就能

28、(3分)下列关于散列函数的说法正确的是(D)。

A、散列函数越复杂越好二;；丁；

B、用除余法构造的散列函数是最好的

C、散列函数越简单越好

D、在冲突尽可能少的情况下,散列函数越简单越好

29、下列结构中属于非线性结构的是()'

A、循环队列

B、二维数组

C、二叉链表

D、双向链表

30、时间复杂度不受数据初始状态影响而恒为0(nlog2n)的是()。

A、堆排序

B、冒泡排序

C、选择排序

D、快速排序

31、(4分)在一个单链表中，口知q指向p所指向结点的前趋结点，若在q.p所

指结点之间插入一个s所指向的新结点,则执行的操作是(A)。

A、q->next=s;s->next=p

B、p->next=s;s->next=q

C、s->next=p->next;p->next=s

D、p->next=s->nxt;s->next=p

32、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线

上所有元素)依次存放于一维数组B[l..(n(n+l))/2]中，则在B中确定aij

(i<j)的位置k的关系为()。

A、i*(i-l)/2+j

B、j*(j-l)/2+i

C、i*(i+l)/2+j

D、j*(j+l)/2+i

33、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。

表示该遗传关系最适合的数据结构为()

A、向量k:：】二:：

B、二叉树

C、树

D、图

34、设某有向图的邻接表中有n个表头结点和m个边结点，则该图中有(：条

有向边。

A、n

n-l

C、m

D、m-1

35、数据采用链式存储结构时，要求()

A、每个结点占用一片连续的存储区域

B、所有结点占用一片连续的存储区域

C、结点的最后一人域必须是指针域

D、每个结点有多〃后继结点，就必须设多少个针域

36、一个队列的数据入列序列是1,2,3,4,则队列的出队时输出序列是

A、4,3,2,1

B、1,2,3,4

C、1,4,3,2

D、3,2,4,1

37、对顺序表上的插入、删除算法的时间复杂性分析来说，常以()为标准操作。