2020年度自考數據結構真題模擬和答案

自考數據結構真題和答案

資料僅供參考

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

數據結構試卷

（課程代碼02331）

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

考生答題注意事項：

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

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

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

筆將“答題卡”的相應代碼涂黑。

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

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

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

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

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

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

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

卡”的相應代碼涂黑。錯涂、多涂或未涂均無分。

1.下列選項中，不屬于線性結構特征的是

A.數據元素之間存在線性關系B.結構中只有

一個開始結點

C.結構中只有一個終端結點D.每個結點都

僅有一個直接前趨

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

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

資料僅供參考

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

元素個數是

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

個大小為7的數組作為循環(huán)隊列的存儲結構，且當前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個葉結點都在同一層中且每

個分支結點都有兩個孩子結點。于中包含的結點數是

A.kB.2k-1C.k2

D.2-1

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

為cebda,則該二叉樹的后序

遍歷序列是

A.cedbaB.decbaC.ecdba

D.ecbad

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

資料僅供參考

邊數是

A.mB.n-lC.n-m

D.n+m

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

0101

0011

0100

1000

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

D.4,4,2,2

9.若對下廈無向圖進行深度優(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的拓撲序列是

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.對一組數據(2,12,16,88,5,10)進行排序，若前3

趟排序結果如下：

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

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

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

則采用的排序方法是

A.冒泡排序B.希爾排序C.歸并排

序D.基數排序

13.設有序表為｛9,12,21,32,41,45,52),當二分查

找值為52的結點時，元素之間的比較次數是

A.1B.2C.3

D.4

14.下列選項中，既熊捌回事存儲結構也能在鏈式存儲結

構上進行查找的方法是

A.散列查找B.順序查

找

C.二分查找D.以上選

資料僅供參考

項均不能

15.在一棵5階B樹中，每個非根結點中所含關鍵字的個

數最少是

A.1B.2C.3

D.4

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

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

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

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

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

_______中。

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

結點，若在q所指結點之后插

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

18.設順序表第1個元素的存儲地址是1000,每個數據元

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

個元素的存儲地址是o

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

中，若X有右孩子結點L

則Y保存在中。

20.一棵二叉樹中，度數為1的結點個數為ih,度數為2

的結點個數為山，則葉結點的

個數為o

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

資料僅供參考

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

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

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

可能存在的位置有個。

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

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

成功時平均查找長度是—甘肅自考網.cco

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

題。

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

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

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

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

題26圖

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

⑴給出圖G的鄰接矩陣；

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

資料僅供參考

8

翅27圖

28.現有5個權值分別是20、31、16、7和15的葉結點，

用它們構造一棵哈夫曼樹，畫出該樹。

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

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

過程。

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

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

為DLNode,定義如下。

typedefintDataType;

typedefstructdlnode

{DataTypedata;//data是數據域

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

}DLNode;

typedefDLNode?DLinkList;

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

和data域中已經正確賦

值。如題30圖a所示。

830圖a

函數f30完成的功能是：將L中各結點的prior域正確賦

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

資料僅供參考

題初圖b

將空白處應填寫的內容答在答題卡上。

voidf30(DLinkListhead)

(

DLNode?p;

pshead;

while(p->next!■⑴)

(

⑵?p；

pmp->next;

}

(3〉-p;

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

回答問題。

typedefcharDataiy-pe;

typedefstructnode

(

DataTypedata:〃data是數據域

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

JBinTNode;

typedefBinTNode*BinTree;

voidfll(BinTreebt)

(

if(bti-NULL)

(

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

DI(bt->Ichild);

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

}

}

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

資料僅供參考

B

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

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的功能是什么？

資料僅供參考

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

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

typedefstructnode

{intdata;

structnode*next;

}ListNode;

typedefListNode*List_ptr;

單鏈表L中結點數不少于2o設計算法判斷L中存儲的全部

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

回1,否則返回0。函數原型如下：

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

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

資料僅供參考

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

數據結構試題答案及評分參考

（課程代碼02331）

單項選擇匙（大大數共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譽定可給什，

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

2?.nG的領摟矩陣為—

數據帶溝試題答案.至于兮考老第13?共S負）

資料僅供參考

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

同樣沿分.

29.直按選擇排序過程：

初始關鍵字：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:輪出結果：ABDDBA（5分）

32.除蟲結果；csncii!（5今；

數家褚構詞逗答賽電—第2支（共3頁，

資料僅供參考

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

次數.（?分）

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

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

￡算法