本科末考試數(shù)據(jù)結(jié)構(gòu)歷年試題與參考答案

國家開放大學（中央廣播電視大學）2018年秋季學期“開放本科”期末考試

數(shù)據(jù)結(jié)構(gòu)（本）試題2019年1月

一、單項選擇題（每小題3分，共30分）

1.如下圖所示，若從頂點a出發(fā)，按圖的廣度優(yōu)先搜索法進行遍歷，則可能得到

的一種頂點序列為（）。

A.acebdfB.aecbfd

C.aecbdfD.acefdb

參考答案：aecbdf

2.結(jié)構(gòu)中的元素之間存在一對多的關系是（）。

A.集合

B.線性結(jié)構(gòu)

C.樹形結(jié)構(gòu)

D.圖狀結(jié)構(gòu)

參考答案：樹形結(jié)構(gòu)

3.設有一個長度為18的順序表，要在第4個元素之前插入1個元素（也就是插入

元素作為新表的第4個元素），則移動元素個數(shù)為（）。

A.15B.16

C.5D.4

參考答案：15

4.一個不帶頭結(jié)點的單循環(huán)鏈表，尾指針為rear,在鏈表中插人一個s所指向的

新結(jié)點，并作為新的尾結(jié)點，可執(zhí)行（）。

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保存棧頂元素的值，

則執(zhí)行（）。

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,采用壓縮存儲的方式，將其下三角部分以行序

為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），則矩陣中al0.8元素對應于數(shù)

組中第（）號元素。

（矩陣中的第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的結(jié)點存在右孩子，則右孩子的順序編號

為（）o

A.18B.16

C.15D.19

參考答案：19

10.設一棵哈夫曼樹共有15個非葉結(jié)點，則該樹總共有（）個結(jié)點。

A.29B.27

C.31D.28

參考答案:31

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

11.在n個整數(shù)中求最大數(shù)的算法中，其基本操作是.

參考答案：元素間的比較

12.設有一個長度為20的順序表，要刪除第5個元素，則最少要移動元素的個數(shù)

為.

參考答案：15

13.在雙向鏈表中，要刪除p所指的結(jié)點，其中所用的一條語句

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

使P所指結(jié)點的直接前驅(qū)的右指針指向.

參考答案：P所指結(jié)點的直接后繼

14.設有一個頭指針為head的單向鏈表，p指向鏈表中的某結(jié)點，若要使該鏈

表成為單向循環(huán)鏈表，可用語句while(p->next!=NULL).

和p一〉next=head；。

參考答案：p=p->next

15.在一個鏈隊中，設front和rear分別為隊頭和隊尾指針，則s所指結(jié)點(數(shù)據(jù)

域已賦值)的人隊操作為

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個結(jié)點的哈夫曼樹，采用鏈式結(jié)構(gòu)存儲，該樹結(jié)構(gòu)中有

個葉結(jié)點。

參考答案：8

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

參考答案：4

22.序列4,2,7,9,5,3,8,6采用歸并排序算法(升序)，經(jīng)一趟歸并后，序

列的結(jié)果為.

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

三、綜合題(每小題6分，共30分)

23.(1)已知某二叉樹的后序遍歷序列是febch,給出該二叉樹的根結(jié)點？又該二

叉樹的中序遍歷序列是fbehc,分別給出該二叉樹的左、右子樹的結(jié)點？

(2)畫出上述二叉樹?若上述二叉樹的各個結(jié)點的字符分別代表不同的整數(shù)(其中

沒有相等的)，并恰好使該樹成為一棵二叉排序樹，試給出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)畫出對上述查找表進行折半查找所對應的判定樹(樹中結(jié)點用數(shù)值表示)。

(2)說明成功查找到元素5,9各需要經(jīng)過多少次元素間的比較？

(3)說明查找不到元素4.2,5.5各需要經(jīng)過多少次元素間的比較？

24.(1)

(2)4次2次

(3)3次4次

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

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

設待排序的記錄序列存放在a[l],…a[n]中，以a[0]作為輔助工作單元,以下程

序是要把a國插人到已經(jīng)有序的序列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.以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)

中，左、右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)

點)o

void