違法信息舉報 客服熱線:400-118-7898
廣告
?
專接本欄目測試廣告

?數(shù)據(jù)結構自考2017年4月真題

自考 責任編輯:彭雅倩 2019-06-26

摘要:本試卷為單選題型,填空題,算法閱讀,算法設計等題型。

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

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

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

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

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

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

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,經(jīng)過入、出棧操作后,可能得到的出棧序列是(  )

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中每個元素占用一個存儲單元,則元素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的結點數(shù)最多是(  )

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

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

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

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

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.下列排序算法中,比較操作的次數(shù)與待排序序列初始排列狀態(tài)無關的是(  )

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

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

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

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

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.散列方法的基本思想是根據(jù)元素的關鍵字直接計算出該元素的________。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、算法閱讀題(本大題共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)函數(shù)f30的功能是什么?

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

33.函數(shù)f32的功能是統(tǒng)計N個頂點的有向圖中邊的數(shù)量,有向圖用鄰接矩陣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í)羁胀昶罩nt 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;請編寫函數(shù) SearchXNum,計算任意二叉樹T中其數(shù)據(jù)域的值大于或等于x的結點的個數(shù)并返回該值。函數(shù)原型如下: int SearchXNum( Bintree *T, int x);//返回二叉樹T中數(shù)據(jù)域的值大于或等于x的結點的個數(shù)

更多資料

00149《國際貿(mào)易理論與實務》【知識集錦】

00159《高級財務會計》【知識集錦】

00184《市場營銷策劃》【知識集錦】

溫馨提示:因考試政策、內容不斷變化與調整,本網(wǎng)站提供的以上信息僅供參考,如有異議,請考生以權威部門公布的內容為準!

自考備考資料免費領取

去領取