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

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

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

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

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

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

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

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

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

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

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

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

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

A.k
B.2k-1

C.

D.

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

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

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

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

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

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

9.若對(duì)下列無(wú)向圖進(jìn)行深度優(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的拓?fù)湫蛄惺?　　)

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.下列排序算法中，在每一趟都能選出一個(gè)元素放到其最終位置上的是(　　)

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

12.對(duì)一組數(shù)據(jù)(2，12，16，88，5，10)進(jìn)行排序，若前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}，當(dāng)二分查找值為52的結(jié)點(diǎn)時(shí)，元素之間的比較次數(shù)是(　　)

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

14.下列選項(xiàng)中，既能在順序存儲(chǔ)結(jié)構(gòu)也能在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上進(jìn)行查找的方法是(　　)

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

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

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

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

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

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

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

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

15.一棵二叉樹(shù)中，度數(shù)為l的結(jié)點(diǎn)個(gè)數(shù)為n1，度數(shù)為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則葉結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)______。

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

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

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

19.在有n個(gè)元素組成的順序表上進(jìn)行順序查找。若查找每個(gè)元素的概率相等，則查找成功時(shí)平均查找長(zhǎng)度是_______。

110.線性探查法和拉鏈法解決的是散列存儲(chǔ)中的_______問(wèn)題。

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

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

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

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

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

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

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

32.已知二叉樹(shù)的二叉鏈表類型定義如下，閱讀程序，并回答問(wèn)題。typedef char DataType;typedef struct node{       DataType data;       //data是數(shù)據(jù)域        struct node *lchild, *rchild;      //分別指向左、右孩子結(jié)點(diǎn)  }BinTNode;  typedef BinTNode * BinTree;  void f31( BinTree bt){        if (bt!=NULL)     {        printf("%c", bt->data );               f31(bt->lchild;                printf("%c", bt->data );      }}若二叉樹(shù)如下所示，寫出調(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.閱讀程序，回答下列問(wèn)題。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è)計(jì)題(本大題共1小題，共10分)

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