?數據結構自考2017年4月真題

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

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

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

1.下列敘述中，不正確的是(　　)

A.算法解決的只能是數值計算問題
B.同一問題可以有多種不同算法
C.算法的每一步操作都必須明確無歧義
D.算法必須在執(zhí)行有限步后結束

2.下列關于棧中邏輯上相鄰的兩個數據元素的敘述中，正確的是(　　)

A.順序存儲時不一定相鄰，鏈式存儲時一定相鄰
B.順序存儲時不一定相鄰，鏈式存儲時也不一定相鄰
C.順序存儲時一定相鄰，鏈式存儲時也一定相鄰
D.順序存儲時一定相鄰，鏈式存儲時不一定相鄰

3.對帶頭結點的單循環(huán)鏈表從頭結點開始遍歷(head為頭指針,p=head->next)。若指 針p指向當前被遍歷結點，則判定遍歷過程結束的條件是(　　)

A.p==NULL
B.head==NULL
C.p==head
D.head !=p

4.設棧的入棧序列為1,2,3,4,5,經過入、出棧操作后,可能得到的出棧序列是(　　)

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

5.數組A[2][3]按行優(yōu)先順序存放,A的首地址為10。若A中每個元素占用一個存儲單元,則元素A[1][2]的存儲地址是(　　)

A.10
B.12
C.14
D.15

6.廣義表((a,b),(c,d))的表尾是(　　)

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

7.若完全二叉樹T包含20個終端結點,則T的結點數最多是(　　)

A.38
B.39
C.40
D.41

8.對下面的二叉樹進行中序線索化后,結點f的右指針指向的結點是(　　)

A.a
B.b
C.c
D.e

9.若圖G是一個含有n個頂點的強連通有向圖,則G的邊數至少是(　　)

A.n-1
B.n
C.n*(n+1)/2
D.n*(n+1)

10.若從頂點a開始對下圖進行廣度優(yōu)先遍歷,則不可能得到的遍歷序列是(　　)

A.a,b,c,e,f,d
B.a,c,b,e,f,d
C.a,c,e,b,d,f
D.a,e,b,c,f,d

11.下列排序算法中,穩(wěn)定的是(　　)

A.堆排序
B.直接選擇排序
C.冒泡排序
D.希爾排序

12.下列排序算法中,比較操作的次數與待排序序列初始排列狀態(tài)無關的是(　　)

A.快速排序
B.直接選擇排序
C.冒泡排序
D.直接插入排序

13.若對二叉排序樹進行遍歷,則下列遍歷方式中,其遍歷結果為遞增有序的是(　　)

A.前序遍歷
B.中序遍歷
C.后序遍歷
D.按層遍歷

14.設一組記錄的關鍵字為{12,22,10,20,88,27,54,11},散列函數為H(key)=key%11,用拉鏈法解決沖突,則散列地址為0的鏈中結點數是(　　)

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

15.在下面3階B樹中插入關鍵字65后,其根結點內的關鍵字是(　　)

A.53 90
B.53
C.90
D.65

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

11.散列方法的基本思想是根據元素的關鍵字直接計算出該元素的________。

12.一個需要頻繁增刪的線性表宜選擇________存儲結構。

13.若中綴表達式為9+(6-2)*8,則相應的后綴表達式是________。

14.對任何一棵二叉樹T,若其葉子結點數為n0, 度數為2的結點數為, 則等于________。

15.若某二叉樹T的前序遍歷序列是A,B,C,D,中序遍歷序列是B,A,D,C,則T的后序遍歷序列是________。

16.在給定n個葉子結點權值且不含度數為1的結點的所有二叉樹中,其________最小的二叉樹稱為哈夫曼樹。

17.用鄰接表存儲含n個頂點e條邊的有向無環(huán)圖G，對G進行拓撲排序，算法的時間復雜度為________。

18.連通圖G的一個子圖如果是一棵包含G的所有頂點的樹,則該子圖稱為G的________樹。

19.二分查找的速度快效率高,但是它要求表按關鍵字有序并且________。

110.除了問題的規(guī)模和分量個數之外,還有________是影響基數排序時間復雜度的主要因素。

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

21.對題26圖所示的帶權無向圖G,試回答以下問題。(1)畫出G的最小生成樹;(2)若用克魯斯卡爾( Kruskal)算法求最小生成樹,請按被選中的次序寫出最小生成樹上各條邊的頂點和權值。

22.已知散列表的長度為11,散列函數為H(key)=key%11,散列表的當前狀態(tài)如下:現要插入關鍵字38,回答下列問題(1)若用線性探查法解決沖突,則38所在位置的下標是什么?(2)若用二次探查法解決沖突,則38所在位置的下標是什么?(3)以上兩種方法中,各需要多少次擦查次數?

23.試回答下列關于拓撲排序算法的問題。(1)算法中利用一個棧保存入度為0的頂點,其目的是什么?(2)若在算法中將隊列改為棧,相應地將入、出棧及判棧空操作改為入、出隊列和判隊列空操作,其他部分不變,是否依然能夠得到拓撲排序的正確結果?

24.考慮用快速排序、堆排序和歸并排序3種排序方法對數據序列進行排序,針對下列不同情況,宜分別選擇哪種排序方法?(1)使用盡量少的存儲空間;(2)要求排序結果是穩(wěn)定的;(3)快速找出數據序列中關鍵字值較大的若干項。

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

31.設鏈表中結點類型定義如下,閱讀程序,回答下列問題。typedef int DataType;typedef struct node{       DataType data;        struct node *next;} RecType, LinkList;    int f30( LinkList *head)  {       if( head ==NULL ) return 0;       else return max(head-> data,f30(head->next);    //max(ab)返回ab中的較大者}(1)若鏈表L={2,12,16,88,5,10},寫出調用f30(L)的輸出結果;(2)函數f30的功能是什么?

32.函數f31的功能是逆序輸出鏈表中所有結點的數據域值。請在空白處填充適當的內容,使其完成指定功能。void f31 LinkList *head){      if( head==NULL ) ___(1)___;      else  {      f31(head->next);          printf("%d",___(2)___);   }}

33.函數f32的功能是統(tǒng)計N個頂點的有向圖中邊的數量,有向圖用鄰接矩陣A表示。閱讀程序,并在空白處填入適當內容,使其完成指定功能。int f32(intAIN)      {    int i, j;          int sum=0;          for(i=0; i<N;  (3) )          for( ___(2)___ ; j <N;j++)          if( ___(3)___ ) sum++;         return sun;}

34.已知二叉樹的二叉鏈表類型定義如下:typedef struct node{   char data;    struct node * lchild, *rchild;  } BiTNode;  typedef BiNode BiTree;以下程序為求二叉樹深度的遞歸算法,請?zhí)羁胀昶罩?。int depth( Bitree *bt)        /*bt為指向根結點的指針*/  { int h1=0, hr =0;    if(___(1)___) return (0);      h1=depth( bt-> lchild);       hr= depth (bt->rchild);      if(___(2)___) return (h1+1);      else ___(3)___;}

五、算法設計題(本大題共1小題，共10分)

41.已知二叉樹的結點類型定義如下:typedef struct node{     int data;       struct node *lchild, *rchild;}BinTNode;typedef BinTNode BinTree;請編寫函數 SearchXNum,計算任意二叉樹T中其數據域的值大于或等于x的結點的個數并返回該值。函數原型如下: int SearchXNum( Bintree *T, int x);//返回二叉樹T中數據域的值大于或等于x的結點的個數