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

本試卷為單選題型，填空題，算法閱讀，算法設計等題型。

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

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

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

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

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

3.下列選項中，屬于順序存儲結(jié)構(gòu)優(yōu)點的是(　　)

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

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

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

5.用不帶頭結(jié)點的單鏈表存儲隊列，在進行刪除運算時(　　)

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

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

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

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

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

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

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

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

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

10.若用鄰接矩陣存儲有向圖，矩陣主對角線以下的元素均為零，則關于該圖拓撲排序序列的結(jié)論是(　　)

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

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

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

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

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

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

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

14.線性表采用順序存儲或鏈式存儲，對其進行查找的方法應是(　　)

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

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

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

二、填空題(本大題共10小題，每小題2分，共20分) 請在每小題的空格中填上正確答案。錯填、不填均無分。

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

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

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

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

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

16.一個連通圖的_________是包含圖中所有頂點的極小連通子圖。

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

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

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

110.對箱排序的改進和推廣的排序算法是_________。

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

21.兩個棧共享數(shù)組空間data[m](定義如下),它們的棧底分別設在數(shù)組的兩端(初始化后topl=-1,top2=m).typedef struct{DataType data[m];int top1, top2;}SeqStack; 回答下列問題。(1)編寫判斷棧滿的函數(shù) int stackfull( SeqStack *s);(2)編寫進棧函數(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的前序遍歷序列、中序遍歷序列和后序遍歷序列如下,其中符號____表示未知元素。試寫出①到⑩所代表的正確元素值。前序遍歷序列 A B D ① E F G ②中序遍歷序列 ③ B A ④ C G F ⑤后序遍歷序列 ⑥ ⑦ ⑧ ⑨ H F C ⑩

23.設圖G如題28圖所示 題28圖 回答下列問題。(1)圖G是否是有向無環(huán)圖?(2)給出圖G所有的拓撲排序序列。

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

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

31.已知隊列的基本操作定義如下,請在空白處填寫適當?shù)恼Z句,完成指定的功能。 #define QueueSize 100typedef struct {         //隊列定義         char data[QueueSize];         int front, rear;  } CirQueue;  CirQueue Q;void Init Queue( CirQueue *Q)      //隊列初始化{       Q->front=Q->rear=0;;}  int Queue Empty( CirQueue *Q)        //判隊列是否空{(diào) return ____(1)____;}int Queue Full( CirQueue * Q)          //判隊列是否滿{     return(Q->rear+ 1)% QueueSize==Q->front;  }  char EnQueue( CirQueue *Q, char c)       ///入隊操作{      if (QueueFulk(Q))      return ‘