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

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

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

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

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

2.下列關(guān)于棧中邏輯上相鄰的兩個(gè)數(shù)據(jù)元素的敘述中，正確的是(　　)

A.順序存儲(chǔ)時(shí)不一定相鄰，鏈?zhǔn)酱鎯?chǔ)時(shí)一定相鄰
B.順序存儲(chǔ)時(shí)不一定相鄰，鏈?zhǔn)酱鎯?chǔ)時(shí)也不一定相鄰
C.順序存儲(chǔ)時(shí)一定相鄰，鏈?zhǔn)酱鎯?chǔ)時(shí)也一定相鄰
D.順序存儲(chǔ)時(shí)一定相鄰，鏈?zhǔn)酱鎯?chǔ)時(shí)不一定相鄰

3.對(duì)帶頭結(jié)點(diǎn)的單循環(huán)鏈表從頭結(jié)點(diǎn)開(kāi)始遍歷(head為頭指針,p=head->next)。若指 針p指向當(dāng)前被遍歷結(jié)點(diǎn)，則判定遍歷過(guò)程結(jié)束的條件是(　　)

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

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

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.數(shù)組A[2][3]按行優(yōu)先順序存放,A的首地址為10。若A中每個(gè)元素占用一個(gè)存儲(chǔ)單元,則元素A[1][2]的存儲(chǔ)地址是(　　)

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

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

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

7.若完全二叉樹(shù)T包含20個(gè)終端結(jié)點(diǎn),則T的結(jié)點(diǎn)數(shù)最多是(　　)

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

8.對(duì)下面的二叉樹(shù)進(jìn)行中序線索化后,結(jié)點(diǎn)f的右指針指向的結(jié)點(diǎn)是(　　)

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

9.若圖G是一個(gè)含有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖,則G的邊數(shù)至少是(　　)

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

10.若從頂點(diǎn)a開(kāi)始對(duì)下圖進(jìn)行廣度優(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.下列排序算法中,比較操作的次數(shù)與待排序序列初始排列狀態(tài)無(wú)關(guān)的是(　　)

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

13.若對(duì)二叉排序樹(shù)進(jìn)行遍歷,則下列遍歷方式中,其遍歷結(jié)果為遞增有序的是(　　)

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

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

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

15.在下面3階B樹(shù)中插入關(guān)鍵字65后,其根結(jié)點(diǎn)內(nèi)的關(guān)鍵字是(　　)

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

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

11.散列方法的基本思想是根據(jù)元素的關(guān)鍵字直接計(jì)算出該元素的________。

12.一個(gè)需要頻繁增刪的線性表宜選擇________存儲(chǔ)結(jié)構(gòu)。

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

14.對(duì)任何一棵二叉樹(shù)T,若其葉子結(jié)點(diǎn)數(shù)為n0, 度數(shù)為2的結(jié)點(diǎn)數(shù)為, 則等于________。

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

16.在給定n個(gè)葉子結(jié)點(diǎn)權(quán)值且不含度數(shù)為1的結(jié)點(diǎn)的所有二叉樹(shù)中,其________最小的二叉樹(shù)稱為哈夫曼樹(shù)。

17.用鄰接表存儲(chǔ)含n個(gè)頂點(diǎn)e條邊的有向無(wú)環(huán)圖G，對(duì)G進(jìn)行拓?fù)渑判?，算法的時(shí)間復(fù)雜度為_(kāi)_______。

18.連通圖G的一個(gè)子圖如果是一棵包含G的所有頂點(diǎn)的樹(shù),則該子圖稱為G的________樹(shù)。

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

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

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

21.對(duì)題26圖所示的帶權(quán)無(wú)向圖G,試回答以下問(wèn)題。(1)畫出G的最小生成樹(shù);(2)若用克魯斯卡爾( Kruskal)算法求最小生成樹(shù),請(qǐng)按被選中的次序?qū)懗鲎钚∩蓸?shù)上各條邊的頂點(diǎn)和權(quán)值。

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

23.試回答下列關(guān)于拓?fù)渑判蛩惴ǖ膯?wèn)題。(1)算法中利用一個(gè)棧保存入度為0的頂點(diǎn),其目的是什么?(2)若在算法中將隊(duì)列改為棧,相應(yīng)地將入、出棧及判?？詹僮鞲臑槿?、出隊(duì)列和判隊(duì)列空操作,其他部分不變,是否依然能夠得到拓?fù)渑判虻恼_結(jié)果?

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

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

31.設(shè)鏈表中結(jié)點(diǎn)類型定義如下,閱讀程序,回答下列問(wèn)題。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},寫出調(diào)用f30(L)的輸出結(jié)果;(2)函數(shù)f30的功能是什么?

32.函數(shù)f31的功能是逆序輸出鏈表中所有結(jié)點(diǎn)的數(shù)據(jù)域值。請(qǐng)?jiān)诳瞻滋幪畛溥m當(dāng)?shù)膬?nèi)容,使其完成指定功能。void f31 LinkList *head){      if( head==NULL ) ___(1)___;      else  {      f31(head->next);          printf("%d",___(2)___);   }}

33.函數(shù)f32的功能是統(tǒng)計(jì)N個(gè)頂點(diǎn)的有向圖中邊的數(shù)量,有向圖用鄰接矩陣A表示。閱讀程序,并在空白處填入適當(dāng)內(nèi)容,使其完成指定功能。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.已知二叉樹(shù)的二叉鏈表類型定義如下:typedef struct node{   char data;    struct node * lchild, *rchild;  } BiTNode;  typedef BiNode BiTree;以下程序?yàn)榍蠖鏄?shù)深度的遞歸算法,請(qǐng)?zhí)羁胀昶罩?。int depth( Bitree *bt)        /*bt為指向根結(jié)點(diǎn)的指針*/  { int h1=0, hr =0;    if(___(1)___) return (0);      h1=depth( bt-> lchild);       hr= depth (bt->rchild);      if(___(2)___) return (h1+1);      else ___(3)___;}

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

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