?數(shù)據(jù)結(jié)構(gòu)自考2016年10月真題

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

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

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

1.下列選項中，不屬于線性結(jié)構(gòu)特征的是(　　)

A.數(shù)據(jù)元素之間存在線性關(guān)系
B.結(jié)構(gòu)中只有一個開始結(jié)點
C.結(jié)構(gòu)中只有一個終端結(jié)點
D.每個結(jié)點都僅有一個直接前驅(qū)

2.設(shè)17個元素的順序表中，若將第i(1≤i

A.j-i-1
B.j-i
C.j-i-+1
D.i-j

3.若用一個大小為7的數(shù)組作為循環(huán)隊列的存儲結(jié)構(gòu)，且當前rear和front的值分別為2和4，在此之前的操作是從隊列中刪除了一個元素及加入兩個元素，請問這3個操作之前rear和front的值分別是(　　)

A.0和1
B.0和3
C.3和6
D.4和5

4.已知廣義表LS=(((a))，((b，(c))，(d，(e，f)))，0)，LS的長度是(　　)

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

5.一棵完全二叉樹T的全部k個葉結(jié)點都在同一層中且每個分支結(jié)點都有兩個孩子結(jié)點。樹中包含的結(jié)點數(shù)是(　　)

A.k
B.2k-1

C.

D.

6.如果某二叉樹的前序遍歷序列為abced，中序遍歷序列為cebda，則該二叉樹的后序遍歷序列是(　　)

A.cedba
B.decba
C.ecdba
D.ecbad

7.一個森林有m棵樹，頂點總數(shù)為n，則森林中含有的總邊數(shù)是(　　)

A.m
B.n-1
C.n-m
D.n+m

8.設(shè)圖的鄰接矩陣A如下所示。各頂點的度依次是(　　)

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

9.若對下列無向圖進行深度優(yōu)先遍歷，得到的正確遍歷序列是(　　)

A.h，c，a，b，d，e，g，f
B.e，a，f，g，b，h，c，d
C.d，b，c，a，h，e，f，g
D.a，b，c，d，h，e，f，g

10.己知有向圖G如下所示，G的拓撲序列是(　　)

A.a，b，e，c，d，f，g
B.a，c，b，f，d，e，g
C.a，C，d，e，b，f，g
D.a，c，d，f，b，e，g

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

A.插入排序
B.希爾排序
C.歸并排序
D.直接選擇排序

12.對一組數(shù)據(jù)(2，12，16，88，5，10)進行排序，若前3趟排序結(jié)果如下：第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88則采用的排序方法是(　　)

A.冒泡排序
B.希爾排序
C.歸并排序
D.基數(shù)排序

13.設(shè)有序表為{9，12，21，32，41，45，52}，當二分查找值為52的結(jié)點時，元素之間的比較次數(shù)是(　　)

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

14.下列選項中，既能在順序存儲結(jié)構(gòu)也能在鏈式存儲結(jié)構(gòu)上進行查找的方法是(　　)

A.散列查找
B.順序查找
C.二分查找
D.以上選項均不能

15.在一棵5階B樹中，每個非根結(jié)點中所含關(guān)鍵字的個數(shù)最少是(　　)

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

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

11.兩個棧S1和S2共用含100個元素的數(shù)組S[0一99]，為充分利用存儲空間，若S2的棧底元素保存在S[99]中，則S1的棧底元素保存在_______中。

12.在一個單鏈表中，已知指針變量q所指結(jié)點不是表尾結(jié)點，若在q所指結(jié)點之后插入指針變量S所指結(jié)點，則正確的執(zhí)行語句是_______。

13.設(shè)順序表第1個元素的存儲地址是1000，每個數(shù)據(jù)元素占6個地址單元，則第11個元素的存儲地址是_______。

14.二叉樹采用順序存儲方式保存，結(jié)點Z保存在數(shù)組A[7]中，若X有右孩子結(jié)點L則Y保存在_______中。

15.一棵二叉樹中，度數(shù)為l的結(jié)點個數(shù)為n1，度數(shù)為2的結(jié)點個數(shù)為n2，則葉結(jié)點的個數(shù)為_______。

16.已知廣義表LS=((a,b)，c，d)，head(LS)是_______。

17.在無向圖G的鄰接矩陣A中，若A[i,j]=1，則A[j,i]=_______。

18. 已知大根堆中的所有關(guān)鍵字均不相同，最大元素在難項，第2大元素可能存在的位置有2個，第3大元素可能存在的位置有_______個。

19.在有n個元素組成的順序表上進行順序查找。若查找每個元素的概率相等，則查找成功時平均查找長度是_______。

110.線性探查法和拉鏈法解決的是散列存儲中的_______問題。

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

21.對題26圖中所給的二叉排序樹T回答下列問題。(1)給出能生成r的2種關(guān)鍵字插入序列;(2)給出r的前序遍歷序列。

22.對題27圖所示的無向帶權(quán)圖G，回答下列問題。(1)給出圖G的鄰接矩陣;(2)給出圖G的一棵最小生成樹。

23.現(xiàn)有5個權(quán)值分別是20、31、16、7和15的葉結(jié)點，用它們構(gòu)造一棵哈夫曼樹，畫出該樹。

24.對于給定的一組關(guān)鍵字序列{26，18，60，65，45，13，32}，寫出使用直接選擇排序方法將其排成升序序列的過程。

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

31.設(shè)非空雙向循環(huán)鏈表L的頭指針為head，表結(jié)點類型為DLNode，定義如下。typedef int DataType;typedef struct dlode{    DataType data;     //data是數(shù)據(jù)域        struct dlnode * prior, *next;       // prior指向前趨結(jié)點,next指向后繼結(jié)點 }DLNode;    typedef DLNode * DLinkList;初始時，L中所有結(jié)點的prior域均為空(NULL)，next域和data域中已經(jīng)正確賦值。如題30圖a所示。函數(shù)f30完成的功能是：將L中各結(jié)點的prior域正確賦值，使L成為雙向循環(huán)鏈表。如題30圖b所示。將空白處應填寫的內(nèi)容答在答題卡上。void f30( DLinkList head)  {     DLNode *p;        p=head;        while(p->next!=____(1)____)      { ____(2)____=p;          p=p->next;     }       ____(3)____=p;}

32.已知二叉樹的二叉鏈表類型定義如下，閱讀程序，并回答問題。typedef char DataType;typedef struct node{       DataType data;       //data是數(shù)據(jù)域        struct node *lchild, *rchild;      //分別指向左、右孩子結(jié)點  }BinTNode;  typedef BinTNode * BinTree;  void f31( BinTree bt){        if (bt!=NULL)     {        printf("%c", bt->data );               f31(bt->lchild;                printf("%c", bt->data );      }}若二叉樹如下所示，寫出調(diào)用f31(T)的輸出結(jié)果。

33.閱讀下列程序，寫出f32的輸出結(jié)果。void f32(){ SeqStack *S;      char x, y;       Initstack(S);       x= 'h';       y= 't';       Push(S, x);       Push(S, 'c'):       x= Pop(S);       Push(S, x);       Push(S, y);       Push(S, 'a');       Push( S, x )      while( !StackEmpty(S))  {     y= Pop(S);      printf(”%c”,y);}       printf ("%c "'!');}

34.閱讀程序，回答下列問題。int f33( NodeType R[], KeyType k, int n){       int i=n-1, count=1;        R[0]. key =k;        while(R[i]. key !=k)       {      i--;             count++;}  if(i-==0) return-1; else return count;}(1)變量 count的含義是什么?(2)f33的功能是什么?

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

41.已知單鏈表類型定義如下：typedef struct node  { int data;     struct node *next;}ListNode;typedef ListNode * List_pt;單鏈表L中結(jié)點數(shù)不少于2。設(shè)計算法判斷L中存儲的全部n個數(shù)據(jù)是否是斐波那契序列的前n項。如果是，則函數(shù)返回1，否則返回0。函數(shù)原型如下：int IsF(List_ptr head);     //判定是否是斐波拉契序列注：斐波拉契序列的定義為：f0=0，f1=，,fn=fn-1+fn-2 (n≥2)