數據結構自考2018年4月真題及答案解析

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

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

1.數據結構不包含的內容是(　　)

A.數據的元素來源
B.數據的邏輯結構
C.數據的存儲結構
D.對數據施加的操作

2.下列選項中，屬于邏輯結構的是(　　)

A.循環隊列
B.二叉樹
C.散列表
D.鄰接表

3.下列選項中，屬于順序存儲結構優點的是(　　)

A.插入運算方便
B.刪除運算方便
C.存儲密度大
D.方便存儲各種邏輯結構

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

A.單鏈表
B.僅有頭指針的單循環鏈表
C.雙向鏈表
D.僅有尾指針的單循環鏈表

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

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

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

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

7.根據二叉樹的定義,3個結點構成的二叉樹的樹型有(　　)

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

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

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

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

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

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

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.若數據元素序列11,13,15,7,8,9,23,2,5是采用下列排序方法之一得到的第二趟排序后的結果,則該排序算法是(　　)

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

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

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

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

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

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

11.在數據結構中,從邏輯上可以把數據結構分為線性結構和_________。

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

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

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

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

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

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

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

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

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

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

21.兩個棧共享數組空間data[m](定義如下),它們的棧底分別設在數組的兩端(初始化后topl=-1,top2=m).typedef struct{DataType data[m];int top1, top2;}SeqStack; 回答下列問題。(1)編寫判斷棧滿的函數 int stackfull( SeqStack *s);(2)編寫進棧函數 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是否是有向無環圖?(2)給出圖G所有的拓撲排序序列。

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

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

31.已知隊列的基本操作定義如下,請在空白處填寫適當的語句,完成指定的功能。 #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)        //判隊列是否空{ return ____(1)____;}int Queue Full( CirQueue * Q)          //判隊列是否滿{     return(Q->rear+ 1)% QueueSize==Q->front;  }  char EnQueue( CirQueue *Q, char c)       ///入隊操作{      if (QueueFulk(Q))      return ‘