高等教育自學(xué)考試 數(shù)據(jù)結(jié)構(gòu)試題

2016年10月高等教育自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》試題

課程代碼：02331

一、單項(xiàng)選擇題

1.下列選項(xiàng)中，不屬于線性結(jié)構(gòu)特征的是

A.數(shù)據(jù)元素之間存在線性關(guān)系B.結(jié)構(gòu)中只有一個(gè)開始結(jié)點(diǎn)

C.結(jié)構(gòu)中只有一個(gè)終端結(jié)點(diǎn)D.每個(gè)結(jié)點(diǎn)都僅有一個(gè)直接前趨

2.設(shè)n個(gè)元素的順序表中，若將第i(lWi<n)個(gè)元素e移動到第j(l<jWn,i<j)個(gè)位置，

不改變除e外其他元素之間的相對次序，則需移動的表中元素個(gè)數(shù)是

A.j-i-1B.j-iC.j-i+1D.i-j

3.若用一個(gè)大小為7的數(shù)組作為循環(huán)隊(duì)列的存儲結(jié)構(gòu)，且當(dāng)前rear和front的值分別

為2和4,在此之前的操作是從隊(duì)列中刪除了一個(gè)元素及加入兩個(gè)元素，請問這3

個(gè)操作之前real'和front的值分別是

A.0和1B.0和3C.3和6D.4和5

4.已知廣義表LS=(((a)),((b,(c)),(d,(e,f))),()),LS的長度是

A.2B.3C.4D.5

5.?棵完全二叉樹了的全部k個(gè)葉結(jié)點(diǎn)都在同一層中且每個(gè)分支結(jié)點(diǎn)都有兩個(gè)孩子

結(jié)點(diǎn)。了中包含的結(jié)點(diǎn)數(shù)是-

A.kB.2k-1C.k2D.2k-l

6.如果某二叉樹的前序遍歷序列為abced,中序遍歷序列為cebda,則該二叉樹的后序

遍歷序列是

A.cedbaB.decbaC.ecdbaD.ecbad

7.一個(gè)森林有陰棵樹，頂點(diǎn)總數(shù)為，2,則森林中含有的總邊數(shù)是

A.mB.n-1C.n-mD.n+m

8.設(shè)圖的鄰接矩陣A如下所示。各頂點(diǎn)的度依次是

-o1or

0011

A—

0100

1000

A.1,2,1,2B.2,2,1,1C.342,3D.4,4,2,2

9.若對下面無向圖進(jìn)行深度優(yōu)先遍歷，得到的正確遍歷序列是

A.h,c,a,b,d,e,g,fB.e,a,f,g,b,h,c,d

C.d,b,c,a,h,e,f,gD.a,b,c,d,h,e,f,g

10.已知有向圖G如下所示，G的拓?fù)湫蛄惺?/p>

b

A.a,b,e,c,d,f,gB.a,c,b,f,d,e,g

C.a,c,d,e,b,f,gD.a,c,d,f,b,e,g

11.下列排序算法中，在每一趟都能選出一個(gè)元素放到其最終位置上的是

A.插入排序B.希爾排序C.歸并排序D.直接選擇排序

12.對一組數(shù)據(jù)(2,12,16,88,5,10)進(jìn)行排序，若前3趟排序結(jié)果如下：

第一趟：2,12,16,5,10,88

第二趟：2,12,5,10,16,88

第三趟：2,5,10,12,16,88

則采用的排序方法是

A.冒泡排序B.希爾排序C.歸并排序D.基數(shù)排序

13.設(shè)有序表為{9,12,21,32,41,45,52},當(dāng)二分查找值為52的結(jié)點(diǎn)時(shí)，元素之間的比較次數(shù)是

A.1B.2C.3D.4

14.下列選項(xiàng)中，既能在順序存儲結(jié)構(gòu)也能在鏈?zhǔn)酱鎯Y(jié)構(gòu)上進(jìn)行查找的方法是

A.散列查找B.順序查找

C.二分查找D.以上選項(xiàng)均不能

15.在一棵5階B樹中，每個(gè)非根結(jié)點(diǎn)中所含關(guān)鍵字的個(gè)數(shù)最少是

A.1B.2C.3D.4

二、填空題

16.兩個(gè)棧Si和S2共用含100個(gè)元素的數(shù)組S[0..99],為充分利用存儲空間，若S2的棧底元素保存在

S[99]中，則Si的棧底元素保存在中。

17.在一個(gè)單鏈表中，已知指針變量q所指結(jié)點(diǎn)不是表尾結(jié)點(diǎn)，若在q所指結(jié)點(diǎn)之后插入指針變量s

所指結(jié)點(diǎn)，則正確的執(zhí)行語句是。

18.設(shè)順序表第1個(gè)元素的存儲地址是1000,每個(gè)數(shù)據(jù)元素占6個(gè)地址單元，則第11個(gè)元素的存儲

地址是?

19.二叉樹采用順序存儲方式保存，結(jié)點(diǎn)X保存在數(shù)組A[7]中，若X有右孩子結(jié)點(diǎn)Y,則Y保存在_

______中。

20.一棵二叉樹中，度數(shù)為I的結(jié)點(diǎn)個(gè)數(shù)為n”度數(shù)為2的結(jié)點(diǎn)個(gè)數(shù)為m,則葉結(jié)點(diǎn)的個(gè)數(shù)為.

21.已知廣義表LS=((a,b),c,d),head(LS)是。

22.在無向圖G的鄰接矩陣A中，若A[i,j]=l,則A[j,i]=。

23.已知大根堆中的所有關(guān)鍵字均不相同，最大元素在堆頂，第2大元素可能存在的位置有2個(gè)，第

3大元素可能存在的位置有個(gè)。

24.在有n個(gè)元素組成的順序表上進(jìn)行順序查找。若查找每個(gè)元素的概率相等，則查找成功時(shí)平均查

找長度是o

25.線性探查法和拉鏈法解決的是散列存儲中的問題。

三、解答題

26.對題26圖中所給的二叉排序樹T,回答下列問題。

(1)給出能生成了的2種關(guān)鍵字插入序列；

(2)給出了的前序遍歷序列。

27.對題27圖所示的無向帶權(quán)圖G,回答下列問題。

(1)給出圖G的鄰接矩陣；

(2)給出圖G的一棵最小生成樹。

28.現(xiàn)有5個(gè)權(quán)值分別是20、31、16、7和15的葉結(jié)點(diǎn)，用它們構(gòu)造一棵哈夫曼樹，畫出該樹。

29.對于給定的一組關(guān)鍵字序列{26,18,60,65,45,13,32},寫出使用直接選擇排序方法將其排成升序序列

的過程。

四、算法閱讀題

30.設(shè)非空雙向循環(huán)鏈表L的頭指針為head,表結(jié)點(diǎn)類型為DLNode,定義如下。

typedefhatDataType;

typedefstmctdlnode

{DataTypedata;//data是數(shù)據(jù)域

stmctdlnode*prior,*next;//prior指向前趨結(jié)點(diǎn)，next指向后繼結(jié)點(diǎn)

IDLNode;

typedefDLNode*DLinkList;

初始時(shí)，L中所有結(jié)點(diǎn)的prior域均為空(NULL),next域和data域中已經(jīng)正確賦值。如題30圖a所示。

題30圖a

函數(shù)130完成的功能是：將L中各結(jié)點(diǎn)的prior域正確賦值，使L成為雙向循環(huán)鏈表。如題30圖b所

題30圖b

請?jiān)诳瞻滋幪钌线m當(dāng)內(nèi)容將算法補(bǔ)充完整。

voidf30(DLinkListhead)

DLNode*p;

p=head;

while(p->next!=(I))

②_=P；

p=p->next;

(3)=p:

)

31.已知二叉樹的二叉鏈表類型定義如下，閱讀程序，并回答問題。

typedefcharDataType;

typedefstmctnode

DataTypcdata;//data是數(shù)據(jù)域

stmctnode*Ichild,*rchild;//分別指向左、右孩子結(jié)點(diǎn)

(BinTNode;

typedefBinTNode*BinTree;

voidf31(BinTreebt)

(

if(bt!=NULL)

printf("%c'\bt->data);

f31(bt->Ichild);

printf("%c'\bt->data);

若二叉樹了如下所示，寫出調(diào)用f31(T)的輸出結(jié)果。

32.閱讀下列程序，寫出B2的輸出結(jié)果。

voidf32()

(

SeqStack*S;

charx,y;

InitStack(S);

x='h';

y=v；

Push(S,x);

Push(S,'c');

x=Pop(S);

Push(S,x);

Push(S,y);

Push(S,'a');

Push(S,x);

while(IStackEmpty(S))

(

y=Pop(S)；

pfintf("%c",y);

)

pfintf("%c\n'\'!');

)

33.閱讀程序，回答下列問題。

inti33(NodeTypeR[],KeyTypek,intn)

(

inti=n-l,count=l;