本科末考试数据结构历年试题与参考答案

国家开放大学（中央广播电视大学）2018年秋季学期“开放本科”期末考试

数据结构（本）试题2019年1月

一、单项选择题（每小题3分，共30分）

1.如下图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到

的一种顶点序列为（）。

A.acebdfB.aecbfd

C.aecbdfD.acefdb

参考答案：aecbdf

2.结构中的元素之间存在一对多的关系是（）。

A.集合

B.线性结构

C.树形结构

D.图状结构

参考答案：树形结构

3.设有一个长度为18的顺序表，要在第4个元素之前插入1个元素（也就是插入

元素作为新表的第4个元素），则移动元素个数为（）。

A.15B.16

C.5D.4

参考答案：15

4.一个不带头结点的单循环链表，尾指针为rear,在链表中插人一个s所指向的

新结点，并作为新的尾结点，可执行（）。

A.rear-＞next=s；s—＞next=rear一＞next；rear=s；

B.rear一＞next=s一＞next；rear=s；

C.s一＞next=rear一＞next；rear一＞next=s-＞next；rear=s；

D.s一＞next=rear-＞next；rear-＞next=s；rear=s；

参考答案：s->next=rear->next；rear—>next=s；rear=s；

5.元素a,b,c,d按顺序依次进栈，则该栈的不可能输出序列是（X进栈出栈

可以交替进行）.

A.c,b,a,dB.d,c,b,a

C.a,c,b,dD.d,c,a,b

参考答案：d,c,a,b

6.在一个栈顶指针为top的链栈中进行出栈操作，用变量x保存栈顶元素的值，

则执行（）。

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

C.top=top->next；x=top一〉data；D.top=top->next；x=data；

参考答案：x=top->data；top=top->next；

7.设有一个18阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序

为主序存储到一维数组B中（数组下标从1开始），则矩阵中al0.8元素对应于数

组中第（）号元素。

（矩阵中的第1个元素是al.1）

A.51B.53

C.52D.54

参考答案：53

8.一棵采用链式存储的二叉树中，共有n个指针域被有效使用（即指针域为非空）。

该二叉树有（）个指针域为空。

A.n+1B.n

C.n—1D.n+2

参考答案：n+2

9.在一棵二叉树中，若编号为9的结点存在右孩子，则右孩子的顺序编号

为（）o

A.18B.16

C.15D.19

参考答案：19

10.设一棵哈夫曼树共有15个非叶结点，则该树总共有（）个结点。

A.29B.27

C.31D.28

参考答案:31

二、填空题(每小题2分，共24分)

11.在n个整数中求最大数的算法中，其基本操作是.

参考答案：元素间的比较

12.设有一个长度为20的顺序表，要删除第5个元素，则最少要移动元素的个数

为.

参考答案：15

13.在双向链表中，要删除p所指的结点，其中所用的一条语句

(p->prior)->next=p->next；的功能是：

使P所指结点的直接前驱的右指针指向.

参考答案：P所指结点的直接后继

14.设有一个头指针为head的单向链表，p指向链表中的某结点，若要使该链

表成为单向循环链表，可用语句while(p->next!=NULL).

和p一〉next=head；。

参考答案：p=p->next

15.在一个链队中，设front和rear分别为队头和队尾指针，则s所指结点(数据

域已赋值)的人队操作为

s->next=NULL；

rear=s；。

参考答案：rear->next=s；

16.字符串4="116甲昭”，a2="he『，a3="heifang”,a4="hefl”中最小的是.

参考答案：a2

17.栈的特点之一是：元素进、出栈的次序是：后进___________.

参考答案：先出

18.在对10个记录的序列(14,30,10,7,22,13,66,85,47,58)进行直接

插人排序时，当把第6个记录13插人到有序表时，为寻找插人位置，元素间需

比较次。(由小到大排列)

参考答案：4

19.18个元素进行冒泡法排序，通常需要进行17趟冒泡，其中第10趟冒泡共需

要进行次元素间的比较。

参考答案：8

20.一棵有15个结点的哈夫曼树，采用链式结构存储，该树结构中有

个叶结点。

参考答案：8

21.广义表的(b,(a,b),d,(c,((e,f),j)))深度是.

参考答案：4

22.序列4,2,7,9,5,3,8,6采用归并排序算法(升序)，经一趟归并后，序

列的结果为.

参考答案：2,4,7,9,3,5,6,8

三、综合题(每小题6分，共30分)

23.(1)已知某二叉树的后序遍历序列是febch,给出该二叉树的根结点？又该二

叉树的中序遍历序列是fbehc,分别给出该二叉树的左、右子树的结点？

(2)画出上述二叉树?若上述二叉树的各个结点的字符分别代表不同的整数(其中

没有相等的)，并恰好使该树成为一棵二叉排序树，试给出h、b、c、f、e的大

小关系。

23.忸h左子加b.f.e右于忖c

<2>

24.设查找表为(1,2,3,4,5,6,7,8,9,10,11)

(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用数值表示)。

(2)说明成功查找到元素5,9各需要经过多少次元素间的比较？

(3)说明查找不到元素4.2,5.5各需要经过多少次元素间的比较？

24.(1)

(2)4次2次

(3)3次4次

四、程序填空题(每空2分，共16分)

25.以下程序是折半插人排序的算法

设待排序的记录序列存放在a[l],…a[n]中，以a[0]作为辅助工作单元,以下程

序是要把a国插人到已经有序的序列a[l],…W一1]中。

voidbinsort(NODEa[],intn)

{intx,i,j,s,k,m；

For(i=2；i<=(l)；i++)

{a0]=a[i]；

x=afi1.key；

s=l；

j=i-l；

while(s<=j)

{m=(2)；

if(x<a[m].key)

(3)；

else

(4)；

)

for(k=i-1；k>=j+l；k—)

(5)=a[k];

a[j+l]==a[0]；

参考答案:

d)n

⑵(s+j)/2；

(3)j=m—1；

(4)s=m+l；

(5)a[k+l]

26.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构

中，左、右指针域分别为left和right,数据域data为字符型，BT指向根结

点)o

void