数据结构考试试卷(含六卷)

数据结构考试试卷（一）

总分：100分考试时间：90分钟

注意事项：

>考生要认真核对条形码上打印的姓名、座位号是否与本人准考证上一致

>作答有误需重新作答时,尽量避免使用橡皮擦除,以防卡面破损，个别错误可用正确的

删除和修改符号进行修改；不准修改答题卡上的题号，否则答案无效。

>考试结束信号发出后，要立即停笔并起立。

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

1、最大容量为n的循环队列，队尾指针为rear,队头指针为front,则队空的条件

是

A、rear==front

B、（rear+l）%n==front

C、rear+l==front

D、（rear-l）%n==front

【答案】A

2、带头结点的单链表L为空的条件是（）

A、L!=NULL

B、L==NULL

C、L->next==NULL

D、L->next==L

【答案】C

3、二叉树的深度为k,则二叉树最多有（）个结点。（3.0分）

A、2k

B、2k-l

C、2k-1

D、2k-l

【答案】C

4、设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点

的个数分别为（）。

A、n,e

、

Bezn

C、2n,e

D、n,2e

【答案】D

5、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包

含的结点数至少为

A、2h

B、2h-l

C、2h+l

D、h+1

【答案】B

6、插入和删除分别在两端端进行的线性表是

A、循环队列

B、栈

C、队列

D、循环栈

【答案】C

7、栈和队列的共同特点是

A、只允许在端点处插入和删除元素

B、都是先进后出

C、都是先进先出

D、没有共同点

【答案】A

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

A、N

B、(N-l)2

C、(N-1)*N

D、N*N

【答案】D

9、(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

【答案】A

10、在表长为n的链表中进行顺序查找，它的平均查找长度为()。(5.0分)

A、n/2

B.(n+l)/2

C、Vn+1

D.Ig(n+1)-1

【答案】B

11、顺序队列的初始化时，需要将front和rear分别设置为()

A、都是0

B、0和-1

C、都是-1

D、-1和0

【答案】A

12、分析以下程序段，其时间复杂度为T(n)=()i=l;While(i<=n)

i=3*i;

A、0(n)

B、0(nA2)

C、0(nA3)

D、0(1)

【答案】D

13、打印杨辉三角形时，可以使用的数据结构是()。

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

B、队列

C、线性表的链式存储结构

D、栈

【答案】B

14、如果以链表作为栈的存储结构,则退栈操作时

A、必须判别栈是否满

B、对栈不作任何判别

C、必须判别栈是否为空

D、判别栈元素的类型

【答案】C

15、递归函数调用时，处理参数及返回地址，要用一种称为（）的数据结

构。

A、队列

B、多维数组

C、栈

D、线性表

【答案】C

16、若广义表A满足heaD（A）=tail（A）厕A为（\

A、（）

B、（（））

C、（（）,（））

D、（（）,（）,（））

【答案】B

17、数据结构这门学科的研究内容下面选项最准确的是

A、研究数据对象和数据之间的关系

B、研究数据对象

C、研究数据对象和数据的操作

D、研究数据对象、数据之间的关系和操作

【答案】D

18、（4分）若栈采用链式存储结构，则下列说法中正确的是（B）。

A、需要判断栈满且需要判断栈空

B、不需要判断栈满但需要判断栈空

C、需要判断栈满但不需要判断栈空

D、不需要判断栈满也不需要判断栈空

【答案】B

19、一棵具有n个结点的完全二叉树的树高度（深度）是（A）

A、Flog2nJ+1

BxIog2n+1

Cs[Iog2nj

DxIog2n-1

【答案】A

20、在一棵深度为k的完全二叉树中，所含结点个数至少（）

A、2Ak

B、2Ak+l

C、2Ak-l

D、2Ak-l

【答案】D

21、(3分)用邻接表表示n个顶点e条边的无向图，其边表结点的总数是(C)。

A、nxe

B、e

C、2e

D、n+e

【答案】C

22、当待排序的整数是有序序列时，无论待排序序列排列是否有序，采用

()方法的时间复杂度都是0(n2)

A、快速排序

B、冒泡排序

C、归并排序

D、直接选择排序

【答案】D

23、可进行拓扑排序的图只能是(C)。

A、有向图

B、无向图

C、有向无环图

D、无向连通图

【答案】C

24、设某无向图有20个顶点很［］该无向图的邻接表中有()个表头结点。

A、40

B、20

C、5

D、380

【答案】B

25、对于顺序循环队列，以下说法正确的是（）

A、无法判断队列是否为空

B、无法判断队列是否为满

C、队列不可能满

D、以上说法都不对

【答案】D

26、对长度为4的顺序表进行查找,若查找第一个记录的概率为1/24,查找第

二个记录的概率为1/6,查找第三个记录的概率为2/3,查找第四个记录的概率

为1/8,则查找任意一个记录的平均查找长度为（）。（5.0分）

A、23/8

B、20/8

C、17/8

D、13/8

【答案】A

27、在平衡二叉树中插入一个结点后造成了不平衡,设最低不平衡结点为A,并

已知结点A的左孩子的平衡因子为0,右孩子的平衡因子为L则应做（）型调整其

平衡。

A、LL

B、LR

C、RL

D、RR

【答案】C

28、数据结构指的是数据之间的相互关系,即数据的组织形式。数据结构一般包

括()三方面内容。(5.0分)

A、数据的逻辑结构.数据的存储结构.数据的描述

B、数据的逻辑结构.数据的存储结构.数据的运算

C、数据的存储结构.数据的运算.数据的描述

D、数据的逻辑结构.数据的运算.数据的描述

【答案】B

29、设二叉树如下则后序序列为()

A、ABDEGCFH

B、DBGEAFHC

C、DGEBHFCA

D、ABCDEFGH

【答案】C

30、下面程序段的时间复杂度是(\for(i=0;i(1分)

A、0(mA2)

B、0(nA2)

C、0(m*n)

D、O(m+n)

【答案】C

31、某哈希查找表有n条记录，对应的哈希函数具有m个值很」i()

A、n<m

B、n>m

C、n<=m

D、n>=m

【答案】D

32、线性表(al,a2，…,an)以链接方式存储时，访问第i位置元素的时间复杂

性为(\

A、0(i)

B、0(1)

C、0(n)

D、0(i-1)

【答案】C

33、下列4种基本逻辑结构中，数据元素之间关系最弱的是('

A、集合

B、线性结构

C、树形结构

D、图形结构

【答案】A

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

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

A、0(Iog2n)

B、0(1)

C、0(n)

D、0(nA2)

【答案】C

35、n个顶点的强连通图，若该连通图含有最少的边，其形状是(I

A、无回路

B、有多个回路

C、环状

D、无法确定

【答案】C

36、队列的删除操作是在()。(4.0分)

A、队首

B、队尾

C、队前

D、队后

【答案】A

37、以下各阶时间复杂度中,性能最优的是()。

A、O(log2n)

B、O(n)

C、O(nA3)

D、0(2An)

【答案】A

38、下列程序段的时间复杂度为()。For(i=0;i<m;i++)for(j=0;j<t;

j++)c[i][j]=0;For(i=0;i<m;i++)for(j=0;j<t;j++)

for(k=0;k<n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];

A、O(m*n*t)

B、O(m+n+t)

C、O(m+n*t)

D、O(m*t+n)

【答案】A

39、线性表采用链式存储时,其地址()

A、必须是连续的

B、一定是不连续的

C、部分地址必须是连续的

D、连续与否均可以

【答案】D

40、关于线性表的说法不正确的是？

A、存在唯一的一个被称为〃第一个"的数据元素(开始结点)

B、存在唯一的一个被称为“最后一个"的数据元素(终端结点)

C、除第一个之外，集合中的每个数据元素均只有一个前驱

D、除第一个之外，集合中的每个数据元素均只有一个后继

【答案】D

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

前序遍历序列是（）

A、aCbeD

B、DeCaB

C、DeabC

D、CeDba

【答案】D

42、二维数组A行下标i的范围从1到12,列下标j的范围从3到10,采用

行序为主序存储，每个数据元素占用4个存储单元，该数组的首地址（即

的地址）为1200,则A[6]⑸的地址为（\

A、1400

B、1404

C、1372

D、1368

【答案】D

43、某班级的学生成绩表中查得张三同学的各科成绩记录,其中数据结构考了

90分，那么下面关于数据对象、数据元素、数据项描述正确的是

A、某班级的学生成绩表是数据元素，90分是数据项

B、某班级的学生成绩表是数据对象，90分是数据元素

C、某班级的学生成绩表是数据对象，90分是数据项

D、某班级的学生成绩表是数据元素,90分是数据元素

【答案】C

44、设F是由Tl、T2和T3三棵树组成的森林，与F对应的二叉树为B,

Tl、T2和T3的结点数分别为Nl、N2和N3,则二叉树B的根结点的左子树

的结点数为（\

A、N1-1

B、N2-1

C、N2+N3

D、N1+N3

【答案】A

45、设有向无环图G中的有向边集合E={<1,2>,<2,3>,<3,4>,<1,

4>},则下列属于该有向图G的一种拓扑排序序列的是（X

A、1,2,3,4

B、2,3,4,1

C、1,4,2,3

D、1,2,4,3

【答案】A

46、判断带头结点的单链表为空表的条件是（”段设头指针为head。（3.0

分）

A、this.head.next==null;

B、this.head==null;

C、this.head.next==this.head;

D、this.head!=null;

【答案】A

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

数为(B)。

A、n-i

B、n-i-1

C、i

D、i+1

【答案】B

48、广义表L=((a,b,c),(e,f))则L的长度和深度分别为()。

A、3,2

B、2,3

C、2,2

D、2,5

【答案】C

49、在长度为n的字符串S的第i个位置插入另外一个字符串,i的合法值应该

是()

A、i>0

Bxi<n

C、l<i«n

D、l<i<n+l

【答案】C

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

A、必须判别栈是否满

B、判别栈元素的类型

C、必须判别栈是否空

D、不做任何判别

【答案】C

数据结构考试试卷（二）

总分：100分考试时间：90分钟

注意事项：

＞考生要认真核对条形码上打印的姓名、座位号是否与本人准考证上一致

＞作答有误需重新作答时,尽量避免使用橡皮擦除，以防卡面破损，个别错误可用正确的

删除和修改符号进行修改；不准修改答题卡上的题号，否则答案无效。

＞考试结束信号发出后，要立即停笔并起立。

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

1、从没有排序序列中挑选元素，并将其一次插入已排序序列末端的方法，称（）

A、归并排序

B、冒泡排序

C、插入排序

D、选择排序

【答案】D

2、以下说法正确的是（）。

A、线性结构的基本特征是:每个结点有且仅有一个直接前驱和一个直接后继

B、线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结沟上

的实现效率要低

C、在线性表的顺序存储结构中插入和删除元素时移动元素的个数与该元素

位置有关

D、顺序存储的线性表的插入和删除操作不需要付出很大的代价，因此平均操

作只有近一半的元素需要移动

【答案】C

3、在下面的几种排序方法中,需要内存空间最大的方法是（A）。

A、归并排序

B、直接选择排序

C、快速排序

D、插入排序

【答案】A

4、向一个队首指针为front,队尾指针为rear的链队列中插入一个s所指

结点时，其操作步骤为（）

A、s->next=front;

B、front=front->next;front->next=s;

C、s->next=rear;

D、rear=s;rear=s;s->next=rear;

【答案】C

、设栈的顺序存储空间为初始状态为现经过一系列正常

5SQ:m）top=m+lo

的入栈与退栈操作后top=20厕栈中的元素个数为（）。

A、30

B、20

C、m-19

D、M-20

【答案】C

6、以下排序方法中,（）不需要进行关键字的比较。

A、快速排序

B、归并排序

C、基数排序

D、堆排序

【答案】C

7、设有1000个无序的元素，希望用最快的速度挑出其中前10个最大的元

素，最好（）排序法。

A、起泡排序

B、选择排序

C、堆排序

D、希尔排序

【答案】B

8、对一个满二叉树，它有m个树叶，n个结点，深度为h,则（）

A、n=h+m

B、、h+m=2n

C、、m=h-l

D、、n=2h-l

【答案】D

9、具有6个顶点的无向图至少有（）条边才能确保是一个连通图

A、5

B、6

C、7

D、8

【答案】A

、分析以下程序段，其时间复杂度为

10T(n)=()x=0;For(i=l;i<n;i++);

for(j=l;j<n;j++)；For(k=l;k<n;k++);x++;

A、O(n)

B、O(nA2)

C、O(nA3)

D、0(1)

【答案】A

11、数据的运算定义在数据的逻辑结构上，只有确定了()，才能具体实现这些运

算。(5.0分)

A、数据对象

B、逻辑结构

C、存储结构

D、数据操作

【答案】C

12、串"abcabcef"的nextval为()

A、01112341

B、01112111

C、01123111

D、01111123

【答案】A

13、设指针变量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;

【答案】D

14、数据结构只是研究数据的逻辑结构和物理结构，这种观点()

A、正确

B、错误

C、前半句正确，后半句错误

D、前半句错误，后半句正确

【答案】B

15、若INDEX(S,T)表示求T在S中的位置,则对于

S="BeiJing&Nanjing",T="jing",INDEX(S,T)=()。

A、2

B、3

C、4

D、5

【答案】C

16、设一棵完全二叉树中有65个结点，则该完全二叉树的深度为(\

A、8

B、7

C、6

D、5

【答案】B

17、有n个数据的二叉排序树最大可能深度是()

A、n

B、n+1

C、Iog2(n)

D、Iog2(n+1)

【答案】A

18、设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列

的队尾指针，指针变量s指向将要入队列的结点X,则入队列的操作序列为

(X

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

B、s->next=rear;rear=s;

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

D、s->next=front;front=s;

【答案】C

19、顺序栈是空栈的条件是(1

A、top==0

B、top==l

C、top==-l

D、top==m

【答案】A

20、算法分析的目的是（）。（5.0分）

A、分析算法的效率以求改进

B、找出数据结构的合理性

C、分析算法的可读性

D、研究算法中的输入输出关系

【答案】A

21、数据的基本单位（）

A、数据结构

B、数据元素

C、数据项

D、文件

【答案】B

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

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

出数据。该缓冲区的逻辑结构应该是（\

A、队列

B、栈

C、线性表

D、有序表

【答案】A

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

种先进先出的线性表。

23、已知线性表L=(al,a2,...,ai，…,an),下列说法正确的是()。

A、每个元素都有一个直接前驱和直接后继

B、线性表中至少要有一个元素

C、表中诸元素的排列顺序必须是由小到大或由大到小的

D、除第一个元素和最后一个元素外，其余每个元素都有一个数，且仅有一个直

接前驱和直接后继

【答案】D

24、用邻接表表示图进行广度优先遍历时，通常借助()来实现算法。

A、栈

B、队列

C、树

D、图

【答案】B

【解析】解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借

助栈来实现算法。

25、对一些特殊矩阱采用压缩存储的目的主要是为了()

A、表达变得简单

B、对矩阵元素的存取变得简单

C、去掉矩阵中的多余元素

D、减少不必要的存储空间的开销

【答案】D

26、设一组初始记录关键字序列为（13,18,24,35,47,50,62,83,

90,115,134）,则利用二分法查找关键字90需要比较的关键字个数为（X

A、1

B、2

C、3

D、4

【答案】B

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

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

A、2h

B、2h-l

C、2h+l

D、h+1

【答案】B

28、有n个十进制整数进行基数排序，其中最大的整数为5位很（］基数排序过程

中临时建立的队数个数是（）。

A、10

B、n

C、5

D、2

【答案】A

29、给定排序码值序列为｛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,I,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｝

【答案】A

30、深度为4的完全:二叉树的结点数至少为。

A、4

B、8

C、13

D、15

【答案】B

31、k=m*n;For(i=0;i<k;i++)i++;

A、O(m)

B、O(n)

C、O(m*n)

D、O(i)

【答案】C

32、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺

序查找法查找一个记录，其平均查找长度ASL为()

A、(n-1)/2

B、n/2

C、(n+l)/2

D、n

【答案】C

33、下面程序段的时间复杂性的量级为(\For(inti=0;i<m;i++)For(int

j=O;j<n;j++)A[i][j]=i*j;

A、0(m3)

B、0(n2)

C、O(m*n)

D、O(m+n)

【答案】C

34、下面关于串的叙述中，哪个是不正确的?()。

A、串是字符的有限序列

B、空串是由空格构成的串

C、模式匹配是串的一种重要运算

D、串既可以采用顺序存储,也可以采用链式存储

【答案】B

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

A、以顺序方式存储

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

C、以链接方式存储

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

【答案】B

36、有一份电文中共使用5个字符：a、b、c、d、e,它们的出现频率依次

为4、7、5、2、9,对应的哈夫曼树（请按左子树根结点的权小于等于右子树

根结点的权的次序构造）中字符a的赫夫曼编码长度为（）

A、1

B、2

C、3

D、4

【答案】C

37、顺序表中才再入一个元素所需移动的元素平均数是（）。

A、（n・l）/2

B、n

C、n+1

D、n/2

【答案】D

38、在二叉排序树的（）序列是一个递增有序序列。

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

【答案】B

39、森林F中有三棵树，每棵树上的结点个数分别为nl,N2和n3,森林

F转换二叉树后，根结点的右子树上结点个数为()

A、nl

B、nl+n2

C、n2+n3

D、nl+n2+n3

【答案】C

40、下列叙述中,不符合m阶B树定义要求的是()。

A、根结点最多有m棵子树

B、所有叶子结点都在同一层上

C、各结点内关键字均升序或降序排列

D、叶子结点之间通过指针链接

【答案】D

41、下列线性表中，能使用二分查找的是(C)。

A、顺序存储(2,12,5,6,9389,34,25)

B、链式存储(2,12,5,6,9389,34,25)

C、JII页序存储(2,3,5,6,9,12,25,34,89)

D、链式存储(23,5.6,9,12,25,34.89)

【答案】C

42、该二叉树对应的森林有()棵树。

A、1

B、2

C、3

D、4

【答案】D

43、下列关于栈叙述正确的是()。

A、栈顶元素最先能被删除

B、栈顶元素最后才能被删除

C、栈底元素永远不能被删除

D、栈底元素最先被删除

【答案】A

44、迪杰斯特拉(Djkstr)算法的功能是(A)。

A、求图中某顶点到其他顶点的最短路径

B、求图中所有顶点之间的最短路径

C、求图的最小生成树

D、求图的拓扑排序序列

【答案】A

45、存取任何J一个元素的时间复杂度是0(1)的数据结构称为()。(3.0分)

A、随机存取结构

B、简单结构

C、顺序结构

D、随机结构

【答案】A

46、(4分)若用一个大小为7的数组作为循环队列的存储结构,且当前rear和

front的值分别为2和4,在此之前的操作是从队列中删除了一个元素及加入两

个元素，请问这3个操作之前rear和front的值分别是(B)。

A、0和1

B、0和3

C、3和6

D、4和5

【答案】B

47、堆排序是一种()排序。

A、插入

B、选择

C、交换

D、归并

【答案】B

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

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

A、a[—top]=x;

B、a[top--]=x;

C、a[++top]=x;

D、a[top++]=x;

【答案】C

49、对有n个数的数列进行冒泡排序，至少应该交换()次？

A、0

B、n/2

c、n

D、2n

【答案】A

50、已知森林F={T1,T2,T3},各棵树Ti(i=l,2,3)中所含结点的个数分别

为7,3,5,则与F对应的二叉树的右子树中的结点个数不可能是(I

A、10

B、12

C、8

D、15

【答案】D

数据结构考试试卷（三）

总分：100分考试时间：90分钟

注意事项：

＞考生要认真核对条形码上打印的姓名、座位号是否与本人准考证上一致

＞作答有误需重新作答时,尽量避免使用橡皮擦除，以防卡面破损，个别错误可用正确的

删除和修改符号进行修改；不准修改答题卡上的题号，否则答案无效。

＞考试结束信号发出后，要立即停笔并起立。

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

1、在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的

结点数为2个，则度为0的结点数为

A、4

B、5

C、6

D、7

【答案】D

2、下面关于求关键路径的说法不正确的是（C）。

A、求关键路径是以拓扑排序为基础的

B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该

活动的持续时间的差

D、关键活动一定位于关键路径上

【答案】C

3、(3分)下列关于无向图广度优先搜索序列的叙述中，正确的是(C)。

A、广度优先搜索序列只有一种

B、广度优先搜索序列可能不存在

C、广度优先搜索序列可能有多种

D、广度优先搜索序列一定有多种

【答案】C

4、(3分)若某二叉树的后序遍历序列为dabec,中序遍历序列是debac,则它的

前序遍历序列是(B)。

A、acbed

B、cedba

C、deabc

D、decab.

【答案】B

5、下列叙述中正确的是()。

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

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

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

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

【答案】A

6、在哈夫曼编码中，根结点的权值是()。

A、根的左右两个子结点的权值之和

B、根的左右两个子结点的权值的平均值

C、所有结点的权值的平均值

D、所有结点的权值之和

【答案】A

7、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行

下标i的范围从。到4,列下标j的范围从。到5,M按行存储时元素M[3][5]

的起始地址与M按列存储时元素（）的起始地址相同。

A、M[2][4]

B、M[3][4]

C、M[3][5]

D、M[4][4]

【答案】B

8、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序

（）

A、不发生变化

B、发生变化

C、某些树中发生变化，某些树中不发生变化

D、没有规律，无法确定

【答案】A

9、用链式存储的栈，在进行出栈W入栈运算时（）

A、仅修改头指针

B、仅修改尾指针

C、头、尾指针都要修改

D、头、尾指针可能都要修改

【答案】D

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

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

A、50

B、48

C、45

D、47

【答案】A

11、下面()的时间复杂性最好，即执行时间最短。

A、O(n)

B、O(logn)

C、O(nlogn)

D、O(n2)

【答案】B

12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下

解释错误的是()

A、正确性算法应能正确地实现预定的功能

B、易读性算法应易于阅读和理解，以便调试、修改和扩充

C、健壮性当环境发生变化时,算法能适当地做出反应或进行处理，不会产生不

需要的运行结果

D、高效性即达到所需要的功能花费的时间和空间

【答案】D

13、一个无向图有20个顶点，共有50条边。则一个顶点的度最多是()。

A、50

B、49

C、20

D、19

【答案】D

14、若长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间

复杂度为()

A、O(n)

B、O(nA2)

C、O(nA3)

D、0(log2An)

【答案】B

15、(3分)设有一组关键字(19.14,23.1.6.20.4275.1109),用散列函数

H(key)=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数

为(C)。

A、1

B、2

C、3

D、4

【答案】C

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

A、p=p->next

B、p=null

C、p->next=null

D、p->next=p->next->next

【答案】D

17、用链式存储的栈，在进栈操作之前，需要（）

A、判断栈是否满了

B、判断栈是否空了

C、不需判断

D、以上答案都不对

【答案】C

18、采用邻接表存储的图的宽度优先遍万算法类似于二叉树的。

A、按层遍历

B、前序遍历

C、后序遍历

D、中序遍历

【答案】A

19、以下说法正确的是（X

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

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

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

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

【答案】D

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

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

20、一个队列的进队序列为:a,b,c,d,则出队序列是:()。

A、a,bed

、

Bd,cza,b

C、a,d,b,c

D、c,a,d,b

【答案】A

21、设有序顺序表中有n个数据元素很I」利用二分查找法查找数据元素X的最

多比较次数不超过()。

A、Iog2(n)+1

BxIog2(n)-1

C、Iog2(n)

D、Iog2(n+1)

【答案】A

22、若让元素1,2,3,4,5依次进栈，则出栈次序不可能出现在()种情

况。

A、5,4,3,2,1

B、2,1,5,4,3

C、4,3,1,2,5

D、2,3,5,4,1

【答案】C

【解析】解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先

出栈，违背了栈的后送先出原则，所以不可能出现C选项所示的情况。

23、(2分)苦一棵二叉树的前序遍历序列与后序遍历序列相同，则该二二叉树可

能的形状是(B)。

A、树中没有度为2的结点

B、树中只有一一个根结点

C、树中非叶结点均只有左子树

D、树中非叶结点均只有右子树

【答案】B

24、序列｛3,2,4,156,8,7｝是第一趟递增排序后的结果则采用的排序方法可能是

()o

A、快速排序

B、冒泡排序

C、堆排序

D、简单选择排序

【答案】A

25、循环队列的队空条件为()。

A、(sq.rear+l)%maxsize==(sq.front+l)%maxsize

B、(sq.rear+l)%maxsize==sq.front+l

C、sq.(rear+l)%maxsize==sq.front

D、sq.rear==sq.front

【答案】D

26、设森林F对应的二叉树有m个结点，二叉树的根节点的右子树上结点

个数为n,则森林F中第一个树的结点个数为（）

A、m-n

B、m-n-1

C、m-n+1

D、无法确定

【答案】A

27、对于顺序表的优缺点，以下说法不正确的是（）。（3.0分）

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

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

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

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

【答案】C

28、下面属于整数类I的实例的是（）

A、229

B、0.229

C、229E-2

D."229"

【答案】A

29、树的后序遍历等价于该树对应二叉树的。

A、层次遍历

B、前序遍历

C、中序遍历

D、后序遍历

【答案】C

30、设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号很(J

编号为i结点的左孩子结点的编号为()。

A、2i+l

B、2i

C、i/2

D、2i-l

【答案】B

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

中:V={a,b,c,d©f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优

先遍历彳导到的顶点序列正确的是(D)。

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

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

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

Dsa,e,d,tc,b

【答案】D

32、队列的插入操作是在()o

A、队尾

B、队头

C、队列任意位置

D、队头元素后

【答案】A

33、(4分)顺序表便于(D)。

A、插入结点

B、删除结点

C、：按值查找结点

D、按序号查找结点

【答案】D

34、difference(ABC)表示求集合A和B的差集差若A={bqd},B={c,e},则

difference(A,B,C)运算后C=(\

A、{b,c,d,e}

B、©

C、{b,d}

D、{b,c,c,d,e}

【答案】C

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

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

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

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

D、上述定义都不是

【答案】A

36、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时

间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为

A、O(l),O(n)

B、O(n),O(n)

C、0(1),0(1)

D、0(n),0(l)

【答案】A

37、算法的有穷性是指()。

A、算法程序的运行时间是有限的

B、算法程序所处理的数据量是有限的

C、算法程序的长度是有限的

D、算法只能被有限的用户使用

【答案】A

38、(3分)某索引顺序表共有元素395个，.平均分成5块。若先对引表采用顺序

查找,再对块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找

长度是(A)。

A、43

B、79

C、198

D、200

【答案】A

39、算法的时间复杂度取决于（X

A、问题的规模

B、待处理数据的初态

C、计算机的配置

D、A和B

【答案】D

【解析】解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因

素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为

此,有时会对算法有最好、最坏以及平均时间复杂度的评价。

40、链表适用于（）。（5.0分）

A、顺序查找

B、二分查找

C、插值查找

D、随机

【答案】A

41、下列四种排序中（）的空间复杂度最大。（2.0分）

A、快速排序

B、冒泡排序

C、希尔排序

D、堆排序

【答案】A

42、一棵二叉排序树采用二叉链存储，对于关键字最小的结点，它的（）。

A、左指针一定为空

B、右指针一定为空

C、左、右指针均为空

D、左、右指针均不为空

【答案】A

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

两趟排序后的结果。

A、选择排序

B、冒泡排序

C、插入排序

D、堆排序

【答案】C

44、在顺序表中，只要知道(),就可在相同时间内求出任一结点的存储地址。

A、基地址

B、结点大小

C、向量大小

D、基地址和结点大小

【答案】D

45、下列叙述中正确的是()。

A、对数据进行压缩存储会降彳氐算法的空间复杂度

B、算法的优化主要通过程序的编制技巧来实现

C、算法的复杂度与问题的规模无关

D、数值型算法只需考虑计算结果的可靠性

【答案】A

46、循环队列的队满条件为()。

A、(sq.rear+l)%maxsize==(sq.front+l)%maxsize

B、(sq.rear+l)%maxsize==sq.front+l

C、sq.(rear+l)%maxsize==sq.front

D、sq.rear==sq.front

【答案】C

47、若需要时间复杂度在O(nlog2n)内,对整数数组进行排序，且要求排序方法

是稳定的，则可选择的排序方法是()0

A、块速排序

B、归并排序

C、堆排序

D、直接插入排序

【答案】B

48、线性表的顺序存储结构是一种()的存储结构，线性表的链式存储结构是

一种()存储结构。

A、随机存取

B、顺序存取

C、索引存取

D、散列存取

【答案】A

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

A、存储结构

B、逻辑结构

C、链式存储结构

D、顺序存储结构

【答案】C

50、设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最

多比较次数不超过(\

A、Iog2n+1

B、Iog2n-1

C、Iog2n

DxIog2(n+1)

【答案】D

数据结构考试试卷（四）

总分：100分考试时间：90分钟

注意事项：

＞考生要认真核对条形码上打印的姓名、座位号是否与本人准考证上一致

＞作答有误需重新作答时,尽量避免使用橡皮擦除,以防卡面破损，个别错误可用正确的

删除和修改符号进行修改；不准修改答题卡上的题号，否则答案无效。

＞考试结束信号发出后，要立即停笔并起立。

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

L下面几种排序方法中，要求内存最大的是（）c

A、快速排序

B、归并排序

C、堆排序

D、冒泡排序

【答案】B

2、设顺序表的长度为16,对该表进行简单插入排序。在最坏情况下需要的比较

次数为（）

A、15

B、60

C、30

D、120

【答案】D

3、设栈S和队列Q的初始状态为空，元素el、e2、e3、e4、e5和e6依次

进入栈s,一个元素出栈后即进入Q,若6个元素出队的序列是e2、e4、

e3、e6、e5和el,则栈S的容量至少应该是（\

A、2

B、3

C、4

D、6

【答案】B

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

队的序列是e2、e4、e3、e6、e5和el,即元素出栈的序列也是e2、e4、

e3、e6、e5和el,而元素el、e2、e3、e4、e5和e6依次进入栈,易知栈

S中最多同时存在3个元素，故栈S的容量至少为30

4、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次

对结点进行编号，根结点的编号为L则编号为49的结点的左孩子编号为（）。

A、98

B、99

C、50

D、48

【答案】A

5、（4分）在单循环链表中,p指向表中任-结点，判断表不是访问结束的条件是

（B）o

A、p!=NULL

B、p!=head

C、p->next!=head

D、p->next!=NULL

【答案】B

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

A、n+1

B、n(-l)/2

C、n(n+l)

D、n-1

【答案】B

7、在具有2n个结点的完全二叉树中，叶子结点个数为()。

A、n

B、n+1

C、n-1

D、n/2

【答案】A

8、下列关于算法输出的叙述中，正确的是()。

A、算法一定没有输出

B、算法可以没有输出

C、算法至少有一个输出

D、算法必须有多个

【答案】C

9、在一个长度为n的顺序表中删除第i个元素，需要向前移动()个元素。

A、n-i

B、n-i+1

C、n-i-1

D、i+1

【答案】A

10、单链表不具备的特点是()«(3.0分)

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

B、链表长度可动态增长

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

D、可随机访问任一个元素

【答案】D

11、执行下面程序段时，S语句的执行次数为()For(inti=l;i<n-

l;i++)For(intj=i+l;j<=n;j++)S;

A、n(n-l)/2

B、n2/2

C、n(n-l)/2

D、n

【答案】A

12、链表不具有的特点是()。

A、可随机访问任一元素

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

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

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

【答案】A

13、从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入

已排序序列的正确位置上的方法，这种排序方法称为（\

A、归并排序

B、冒泡排序

C、插入排序

D、选择排序

【答案】C

14、一^栈的输入序列为123，…,"其输出序列为pLp2,p3,...,pn,若pn是n,

贝！Jpi是（）。

A、不确定

B、n-i+1

C、i

D、n-i

【答案】D

15、若已知一个栈的入栈序列是123,..,n,其输出序列为pl,p2,p3，…,pn,若pl

=n,则pn为（）。

A、1

B、n

C、n/2

D、n-1

【答案】A

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

()

A、7,1

B、6,1

C、5,1

D、8,1第九章排序

【答案】A

17、数据元素之间存在一对多的关系，这种数据间的结构属于()

A、集合

B、线性结构

C、树型结构

D、图型结构

【答案】C

18、假设以行序为主序存储二维数组A=array。..100,1...100],设每个数组元素

占个存储单元，基地址为则

210,LOC[5Z5]=

A、818

B、808

C、1010

D、1020

【答案】A

19、树最适合用来表示。

A、有序数据元素

B、无序数据元素

C、元素之间具有分支层次关系的数据

D、元素之间无联系的数据，是平衡二叉树。

【答案】C

20、队和栈的主要区别是(I(1分)

A、逻辑结构不同

B、存储结构不同

C、所包含的运算个数不同

D、限定插入和删除的位置不同

【答案】D

21、下面程序段的时间复杂度为()。i=l；while(i<=n)

A、O(n)

B、O(3n)

C、O(log3n)

D、O(n3)

【答案】C

22、某算法的空间复杂度为OQ),表明执行该算法时()

A、不需要储存空间

B、需要的临时存储空间为常量

C、需要的存储空间恰好为1

D、需要的临时存储空间为1

【答案】B

23、设有一个递归算法如下:Intfun(intn){if(n<=0)return0;else

n+fun(n-l);}则计算fun(n)(n>0)需要调用该函数的次数为()。

A、n+1

B、n-1

C、n

D、n+2

【答案】A

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

A、数据项

B、数据元素

C、数据域

D、担

【答案】B

25、栈和队列的共同点是(I

A、都是先进先出

B、都是先进后出

C、只允许在端点处插入和删除元素

D、没有共同点

【答案】C

【解析】解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插

入元素和在队头删除元素。

26、(6分)计算机算法指的是解决问题的有限运算序列,它必具备输入输出和()等

五个特性。

A、可行性、可移植性和可扩充性

B、可行^性、确定性和有穷性

C、确定性、有穷性和稳定性

D、易读性、稳定性和安全性

【答案】B

、设循环队列的存储空间为初始状态为现经过

27QQ:35)front=rear=35e

一系列入队与退队运算后fronts15,rear=15则循环队列中的元素个数为()。

A、15

B、16

C、20

D、0或35

【答案】D

28、一棵具有1028个结点的二叉树的深度h为()。

A、11

B、10

C、11-1028

D、10~1027

【答案】C

29、快速排序在下列哪种情况下最易发挥其长处()。

A、被排序的数据中含有多个相同排序码

B、被排序的数据已基本有序

C、被排序的数据随机分布

D、被排序的数据中最大值和最小值相差悬殊

【答案】C

30、后缀表达式"45*32+-"的值为（）

A、21

B、17

C、15

D、5

【答案】C

【解析】（4、5入栈,遇到*，取出4*5=20;20、3、2入栈，遇到+,取出

3+2=5;5入栈，遇到-,取出20-5=15）第2

31、由权值分别是8,7,2,5的叶子结点生成一棵赫夫曼树,它的带权路径

长度为（）

A、23

B、37

C、43

D、46

【答案】C

32、在下列情况中，可称为二叉树的是

A、每个结点至多有两棵子树的树

B、哈夫曼树

C、每个结点至多有两棵子树的有序树

D、每个结点只有一棵右子树

【答案】B

33、在一个图中，所有顶点的度数之后等于所有边数的（）倍。（4.0分）

A、1/2

B、1

C、2

D、4

【答案】A

34、设一组权值集合W=（15,3,14,2,6,9,16,17）,要求根据这些权

值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（L

A、129

B、219

C、189

D、229

【答案】D

35、算法具有五个重要特性不包括

A、有穷性

B、确定性

C、可行性

D、易读性

【答案】D

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

A、左子结点

B、右子结点

C、左子结点和右子结点

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

【答案】C

37、设广义表L=((a,b,c)),则L的长度和深度分别为(I

A、1和1

B、1和3

C、1和2

D、2和3

【答案】C

【解析】解释：广义表的深度是指广义表中展开后所含括号的层数，广义表的

长度是指广义表中所含元素的个数。根据定义易知L的长度为1,深度为20

38、由4个结点可以构造出多少种不同的二叉树？

A、9

B、14

C、16

D、27

【答案】B

39、某算法的时间复杂度是0(门人2),表明该算法的

A、执行时间与n，、2成正比

B、问题规模是「八2

C、执行时间等于”2

D、问题规模与n^2成正比

【答案】A

40、（）二叉排序树可以得到一个从小到大的有序序列。

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

【答案】B

41、在单链表L中才旨针p所指结点有后继结点的条件是（）。

A、p=p.next

B、p.next!=null

C、p.next=null

D、p.next=p.next.next

【答案】B

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

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

结点数大于2,p不是第一个结点\

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

B、

free(p);P->llink->rlink=p->rlink;p->llink->rlink=p->llink;Free(p);p->llink

->rlink=p->rlink;

C、p->llink->rlink=p->llink;

D、以上A,B,C都不对。free(p);P->llink->rlink=p->rlink;

【答案】D

43、索引顺序表的特点是顺序表中的数据()。

A、有序

B、无序

C、块间有序

D、散列

【答案】C

44、(4分)栈结构通常采用的两种存储结构是(A)。

A、顺序存储结构和链表存储结构

B、散链方式^口索引方式

C、链表存储结构和数组

D、线性存储结构和非线性存储结构

【答案】A

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

有1个，度数为1