?數(shù)據(jù)結(jié)構(gòu)自考2018年4月真題

數(shù)據(jù)結(jié)構(gòu)自考2018年4月真題及答案解析

本試卷為單選題型，填空題，算法閱讀，算法設(shè)計(jì)等題型。

一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。

1.數(shù)據(jù)結(jié)構(gòu)不包含的內(nèi)容是(　　)

A.數(shù)據(jù)的元素來源
B.數(shù)據(jù)的邏輯結(jié)構(gòu)
C.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
D.對(duì)數(shù)據(jù)施加的操作

2.下列選項(xiàng)中，屬于邏輯結(jié)構(gòu)的是(　　)

A.循環(huán)隊(duì)列
B.二叉樹
C.散列表
D.鄰接表

3.下列選項(xiàng)中，屬于順序存儲(chǔ)結(jié)構(gòu)優(yōu)點(diǎn)的是(　　)

A.插入運(yùn)算方便
B.刪除運(yùn)算方便
C.存儲(chǔ)密度大
D.方便存儲(chǔ)各種邏輯結(jié)構(gòu)

4.某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則下列存儲(chǔ)結(jié)構(gòu)中，最節(jié)省運(yùn)算時(shí)間的是(　　)

A.單鏈表
B.僅有頭指針的單循環(huán)鏈表
C.雙向鏈表
D.僅有尾指針的單循環(huán)鏈表

5.用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)(　　)

A.僅修改頭指針
B.僅修改尾指針
C.頭、尾指針一定都要修改
D.頭、尾指針可能都要修改

6.二維數(shù)組M,行下標(biāo)取值范圍為0~8,列下標(biāo)取值范圍為1~10,若按行優(yōu)先存儲(chǔ)時(shí),元素M[8][5]的存儲(chǔ)地址為ar,則按列優(yōu)先存儲(chǔ)時(shí)，地址ar存儲(chǔ)的數(shù)組元素應(yīng)(　　)

A.M[8]5]
B.M[5]8]
C.M[3]10]
D.M[0]9]

7.根據(jù)二叉樹的定義,3個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹的樹型有(　　)

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

8.一棵有序樹可轉(zhuǎn)換為一棵二叉樹,樹的后序遍歷對(duì)應(yīng)二叉樹的(　　)

A.前序遍歷
B.中序遍歷
C.后序遍歷
D.以上都不對(duì)

9.若圖G的鄰接表中有奇數(shù)個(gè)表結(jié)點(diǎn),則G是(　　)

A.含奇數(shù)個(gè)頂點(diǎn)的圖
B.無向圖
C.含偶數(shù)個(gè)頂點(diǎn)的圖
D.有向圖

10.若用鄰接矩陣存儲(chǔ)有向圖，矩陣主對(duì)角線以下的元素均為零，則關(guān)于該圖拓?fù)渑判蛐蛄械慕Y(jié)論是(　　)

A.存在,且唯一
B.存在,且不唯
C.存在,可能不唯一
D.無法確定是否存在

11.如果無向圖G的最小生成樹T中含有邊(a,b)和(a,c),則下列選項(xiàng)中，一定不在T中的邊是(　　)           題11圖 

A.(b,c)
B.(b,d)
C.(c,d)
D.(c,e)

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

A.插入排序
B.希爾排序
C.歸并排序
D.堆

13.若數(shù)據(jù)元素序列11,13,15,7,8,9,23,2,5是采用下列排序方法之一得到的第二趟排序后的結(jié)果,則該排序算法是(　　)

A.冒泡排序
B.插入排序
C.選擇排序
D.歸并排序

14.線性表采用順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，對(duì)其進(jìn)行查找的方法應(yīng)是(　　)

A.順序查找
B.二分查找
C.散列查找
D.索引查找

15.設(shè)有序表為(1,3,9,12,32,41,45,62,75,77,82),采用二分查找法查找關(guān)鍵字75,查找過程中關(guān)鍵字之間的比較次數(shù)是(　　)

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

二、填空題(本大題共10小題，每小題2分，共20分) 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。

11.在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和_________。

12.為便于實(shí)現(xiàn)單鏈表的插入及刪除運(yùn)算，需要在單鏈表中增加一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)稱為_________。

13.在二維數(shù)組A[10][8]中,每個(gè)數(shù)組元素占用4個(gè)存儲(chǔ)單元,則數(shù)組A需要的存儲(chǔ)單元個(gè)數(shù)是_________。

14.對(duì)長度為1的廣義表A,若有 Head(A)=Tail(A),則A=_________。

15.設(shè)高為h的二又樹T中只有度為0和2的結(jié)點(diǎn),則T包含的結(jié)點(diǎn)數(shù)最多為_________。

16.一個(gè)連通圖的_________是包含圖中所有頂點(diǎn)的極小連通子圖。

17.無向圖G中含7個(gè)頂點(diǎn),頂點(diǎn)間的邊是隨機(jī)設(shè)置的,為保證圖G在任何情況下都是連通的,則需要的邊數(shù)最少是_________。

18.求單源最短路徑的迪杰斯特拉( Dijkstra)算法是按照路徑_________不減的次序求出各條路徑的。

19.一組記錄的關(guān)鍵字為(45,53,18,49,36,76,13,97,36,32),利用快速排序方法對(duì)其進(jìn)行排序，選擇45為基準(zhǔn)，一次性劃分后的結(jié)果為_________。

110.對(duì)箱排序的改進(jìn)和推廣的排序算法是_________。

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

21.兩個(gè)棧共享數(shù)組空間data[m](定義如下),它們的棧底分別設(shè)在數(shù)組的兩端(初始化后topl=-1,top2=m).typedef struct{DataType data[m];int top1, top2;}SeqStack; 回答下列問題。(1)編寫判斷棧滿的函數(shù) int stackfull( SeqStack *s);(2)編寫進(jìn)棧函數(shù) void push( SeqStack *s, int si, DataType x); 其中,si取值為0、1,分別表示棧底為0或m-1的棧。

22.已知二叉樹T中含有元素A,B,C,D,E,F,G,H,T的前序遍歷序列、中序遍歷序列和后序遍歷序列如下,其中符號(hào)____表示未知元素。試寫出①到⑩所代表的正確元素值。前序遍歷序列 A B D ① E F G ②中序遍歷序列 ③ B A ④ C G F ⑤后序遍歷序列 ⑥ ⑦ ⑧ ⑨ H F C ⑩

23.設(shè)圖G如題28圖所示 題28圖 回答下列問題。(1)圖G是否是有向無環(huán)圖?(2)給出圖G所有的拓?fù)渑判蛐蛄小?/p>

24.設(shè)關(guān)鍵字序列為:53,15,72,52,48,67,63,23。已知散列表地址空間為0~11,散列函數(shù)為H(k)=kmod11,采用線性探查再散列法解決沖突。(1)將所給關(guān)鍵字?jǐn)?shù)據(jù)依次填入該散列表中;(2)計(jì)算等概率下查找成功的平均查找長度。

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

31.已知隊(duì)列的基本操作定義如下,請(qǐng)?jiān)诳瞻滋幪顚戇m當(dāng)?shù)恼Z句,完成指定的功能。 #define QueueSize 100typedef struct {         //隊(duì)列定義         char data[QueueSize];         int front, rear;  } CirQueue;  CirQueue Q;void Init Queue( CirQueue *Q)      //隊(duì)列初始化{       Q->front=Q->rear=0;;}  int Queue Empty( CirQueue *Q)        //判隊(duì)列是否空{(diào) return ____(1)____;}int Queue Full( CirQueue * Q)          //判隊(duì)列是否滿{     return(Q->rear+ 1)% QueueSize==Q->front;  }  char EnQueue( CirQueue *Q, char c)       ///入隊(duì)操作{      if (QueueFulk(Q))      return ‘