2020年度自考數(shù)據(jù)結(jié)構(gòu)真題模擬和答案

自考數(shù)據(jù)結(jié)構(gòu)真題和答案

資料僅供參考

10月高等教育自學(xué)考試全國統(tǒng)一命題考試

數(shù)據(jù)結(jié)構(gòu)試卷

（課程代碼02331）

本試卷共7頁，滿分100分，考試時間150分鐘。

考生答題注意事項：

1.本卷所有試題必須在答題卡上作答。答在試卷上無效，

試卷空白處和背面均可作草稿紙。

2.第一部分為選擇題。必須對應(yīng)試卷上的題號使用2B鉛

筆將“答題卡”的相應(yīng)代碼涂黑。

3.第二部分為非選擇題。忠須注明大、小題號，使用0.5

毫米黑色字跡簽字筆作答。

4.合理安排答題空間，超出答題區(qū)域無效。

第一部分選擇題（共30分）

一、單項選擇題（本大題共15小題，每小題2分，共30分）

在每小題列出的四個備選項中只有一個是符合題目要求

的，請將其選出并將“答題

卡”的相應(yīng)代碼涂黑。錯涂、多涂或未涂均無分。

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

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

一個開始結(jié)點

C.結(jié)構(gòu)中只有一個終端結(jié)點D.每個結(jié)點都

僅有一個直接前趨

2.設(shè)17個元素的順序表中，若將第＞個元素e移動到

第/（1勺?，⑼個位置，

資料僅供參考

不改變除e外其它元素之間的相對次序，則需移動的表中

元素個數(shù)是

A.7.MB./-/C.j-f+1D.i-j3.若用一

個大小為7的數(shù)組作為循環(huán)隊列的存儲結(jié)構(gòu)，且當(dāng)前rew

和盤Ont的值分別

為2和4,在此之前的操作是從隊列中刪除了一個元素及加

入兩個元素，請問這3

個操作之前rear和矗Ont的值分別是

A.0和1B.0和3C.3和6

D.4和5

4.已知廣義表LS=(((a)),((b,(c)),(d,(e,f))),0),

LS的長度是

A.2B.3C.4

D.5

5.一棵完全二叉樹T的全部k個葉結(jié)點都在同一層中且每

個分支結(jié)點都有兩個孩子結(jié)點。于中包含的結(jié)點數(shù)是

A.kB.2k-1C.k2

D.2-1

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

為cebda,則該二叉樹的后序

遍歷序列是

A.cedbaB.decbaC.ecdba

D.ecbad

7.一個森林有m棵樹，頂點總數(shù)為n,則森林中含有的總

資料僅供參考

邊數(shù)是

A.mB.n-lC.n-m

D.n+m

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

0101

0011

0100

1000

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

D.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>

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.下列排序算法中，在每一趟都能選出一個元素放到其

最終位置上的是

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é)點時，元素之間的比較次數(shù)是

A.1B.2C.3

D.4

14.下列選項中，既熊捌回事存儲結(jié)構(gòu)也能在鏈?zhǔn)酱鎯Y(jié)

構(gòu)上進(jìn)行查找的方法是

A.散列查找B.順序查

找

C.二分查找D.以上選

資料僅供參考

項均不能

15.在一棵5階B樹中，每個非根結(jié)點中所含關(guān)鍵字的個

數(shù)最少是

A.1B.2C.3

D.4

第二部分非選擇題(共70分)

二、填空題(本大題共10小題，每小題2分，共20分)

16.兩個棧Si和S2共用含100個元素的數(shù)組S[0—99],

為充分利用存儲空間，若S2的

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

_______中。

17.在一個單鏈表中，已知指針變量q所指結(jié)點不是表尾

結(jié)點，若在q所指結(jié)點之后插

入指針變量S所指結(jié)點,則正確的執(zhí)行語句是O

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

素占6個地址單元，則第11

個元素的存儲地址是o

19.二叉樹采用順序存儲方式保存,結(jié)點Z保存在數(shù)組A[7]

中，若X有右孩子結(jié)點L

則Y保存在中。

20.一棵二叉樹中，度數(shù)為1的結(jié)點個數(shù)為ih,度數(shù)為2

的結(jié)點個數(shù)為山，則葉結(jié)點的

個數(shù)為o

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

資料僅供參考

22.在無向圖G的鄰接矩陣A中，入卜“wko

23.已知大根堆中的所有關(guān)鍵字均不相同，最大元素在難

項，第2大元素可能存在的位置有2個，第3大元素

可能存在的位置有個。

24.在有n個元素組成的順序表上進(jìn)行順序查找。若查找

每個元素的概率相等，則查找

成功時平均查找長度是—甘肅自考網(wǎng).cco

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

題。

三、解答題(本大題共4小題，每小題5分，共20分)

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

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

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

題26圖

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

⑴給出圖G的鄰接矩陣；

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

資料僅供參考

8

翅27圖

28.現(xiàn)有5個權(quán)值分別是20、31、16、7和15的葉結(jié)點，

用它們構(gòu)造一棵哈夫曼樹，畫出該樹。

29.對于給定的一組關(guān)鍵字序列序6,18,60,65,45,13,

32),寫出使用直接選擇排序方法將其排成升序序列的

過程。

四、算法閱讀題(本大題共4小題，每小題5分，共20分)

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

為DLNode,定義如下。

typedefintDataType;

typedefstructdlnode

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

structdlnode?prior,?next;"prior指向前趨結(jié)點，next指向后繼結(jié)點

}DLNode;

typedefDLNode?DLinkList;

初始時，L中所有結(jié)點的prior域均為空(NULL),next域

和data域中已經(jīng)正確賦

值。如題30圖a所示。

830圖a

函數(shù)f30完成的功能是：將L中各結(jié)點的prior域正確賦

值，使L成為雙向循環(huán)鏈表。如題30圖b所示。

資料僅供參考

題初圖b

將空白處應(yīng)填寫的內(nèi)容答在答題卡上。

voidf30(DLinkListhead)

(

DLNode?p;

pshead;

while(p->next!■⑴)

(

⑵?p；

pmp->next;

}

(3〉-p;

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

回答問題。

typedefcharDataiy-pe;

typedefstructnode

(

DataTypedata:〃data是數(shù)據(jù)域

structnode?Ichild,?rchild;〃分別指向左、右孩子結(jié)點

JBinTNode;

typedefBinTNode*BinTree;

voidfll(BinTreebt)

(

if(bti-NULL)

(

printf("%c",bt->data);

DI(bt->Ichild);

printf("%c",bt->data);

}

}

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

資料僅供參考

B

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

void02()

(

SeqStack.S;

charx,y;

lnitStack(SX

x-V;

y=*f;

Push(S,x);

Push(S,'c');

x=Pop(S)；

Push(S.xX

Push(S,y);

Push(S,'a');

Push(S,x);

while(!StackEmpty(S))

(

y-Pop(S)；

prints"%c",yX

)

printff-%c\n",'!'X

)

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

intD3(NodeiypeR[],KeyTypek,intn)

(

inti=n-l,count=1;

R[O].key=k;

while(R[i).key!-k)

{

i-；

count++;

)

if(1=0)return-1;

elsereturncount;

}

(1)變量count的含義是什么？

(2)03的功能是什么？

資料僅供參考

五、算法設(shè)計題(本題10分)

34.已知單鏈表類型定義如下：

typedefstructnode

{intdata;

structnode*next;

}ListNode;

typedefListNode*List_ptr;

單鏈表L中結(jié)點數(shù)不少于2o設(shè)計算法判斷L中存儲的全部

n個數(shù)據(jù)是否是斐波那契序列的前n項。如果是，則函數(shù)返

回1,否則返回0。函數(shù)原型如下：

intIsF(List_ptrhead);//判定是否是斐波那契序列

注：斐波那契序列的定義為：力H，6=1，KI+%2仿22)

資料僅供參考

2016年10月高等教育自學(xué)考試全國統(tǒng)一命題考試

數(shù)據(jù)結(jié)構(gòu)試題答案及評分參考

（課程代碼02331）

單項選擇匙（大大數(shù)共15小的，第小疑2分，共討分）

二.填空題（本大題共1。小霆，每小整2分，共"分）

16.SPJ:7s->:iex：-H]->n^xt:qoiicxrf

18.106019.A[16]

20.吁121.；abi

22.I23.6

24.(f225.沖突

三解若題（本大變熬」小題,與小超，分，共2。分）

26.（1）agefbdcagcbfdc12分：）

---..'.-一,

及agcbdc”只及.廷正確給出任您2譽(yù)定可給什，

2;就不汨歷字科agebdef（3分：，

2?.nG的領(lǐng)摟矩陣為—

數(shù)據(jù)帶溝試題答案.至于兮考老第13?共S負(fù)）

資料僅供參考

說羽：萃運笞案不睢。材中任一分支紜點的工右分支苴?可以亙費.只要正確,

同樣沿分.

29.直按選擇排序過程：

初始關(guān)鍵字：26,18,<50.65,45.13,32

一巷排序后：13,18,60.65,45,26.32（】分;

二粒拉泮后；13.18.60.65.45.26.32（1分）

三越排序后：13,18,26.65.45.6C,32門分）

西越排序后：13,18,26,32.45.60.65.（1分）

三越停停后：13,13.26,32,45.60.65C分）

——后:13,18.25.32.4S.60,65

E.算法何談題：本大題共4小磨，每4/5分，共20分

30.CDheadC1分）

p->nev：prior（2分）

（3）head->prior（2分）

3:輪出結(jié)果：ABDDBA（5分）

32.除蟲結(jié)果；csncii!（5今；

數(shù)家褚構(gòu)詞逗答賽電—第2支（共3頁，

資料僅供參考

33..1coin:-5L人奴組蚊之不生就前二，交戲嚀，我—上二比7

次數(shù).（?分）

；2〉63的功級：至敦空中從后向輪港廳,同手安挖，歪向」表示芭投不戌功，

?回一整一裹示三找殘片,，這?住左示迸行的之裳次效.，3號）

￡算法