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

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

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

1.下列選項中,與數(shù)據(jù)存儲結(jié)構(gòu)直接相關(guān)的是(　　)

A.線性表
B.雙向鏈表
C.二叉樹
D.有向圖

2.將12個數(shù)據(jù)元素保存在順序表中,若第一個元素的存儲地址是100,第二個元素的存儲地址是105,則該順序表最后一個元素的存儲地址是(　　)

A.111
B.144
C.155
D.156

3.設(shè)棧的初始狀態(tài)為空，元素1,2,3,4,5,6依次入棧，棧的容量是3，能夠得到的出棧序列 是(　　)

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

4.設(shè)指針變量head指向非空單循環(huán)鏈表的頭結(jié)點,指針變量p指向終端結(jié)點,next是結(jié)點的指針域,則下列邏輯表達(dá)式中,值為真的是(　　)

A.p->next->next==head
B.p->next==head
C.p->next->next==NULL
D.p->next==NULL

5.已知廣義表LS=(((ab)),((c,(d)),(e,(f))),(g,h)),LS的深度是(　　)

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

6.已知一棵高度為4的完全二叉樹T共有5個葉結(jié)點,則T中結(jié)點個數(shù)最少是(　　)

A.9
B.10
C.11
D.12

7.在一棵非空二叉樹的中序遍歷序列中,所有列在根結(jié)點前面的是(　　)

A.左子樹中的部分結(jié)點
B.左子樹中的全部結(jié)點
C.右子樹中的部分結(jié)點
D.右子樹中的全部結(jié)點

8.用鄰接矩陣表示有n個頂點和e條邊的無向圖，采用壓縮方式存儲，矩陣中零元素的個數(shù)是(　　)

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

9.無向圖G中所有頂點的度數(shù)之和是20,則G中的邊數(shù)是(　　)

A.10
B.20
C.30
D.40

10.設(shè)有向圖G含有n個頂點、e條邊,使用鄰接表存儲。對G進(jìn)行廣度優(yōu)先遍歷的算法的時間復(fù)雜度是(　　)

A.O(n)
B.O(e)
C.O(n+e)
D.O(n×e)

11.對數(shù)據(jù)序列(25,15,7,18,10,0,4)采用直接插入排序進(jìn)行升序排序，兩趟排序后，得到的排序結(jié)果為(　　)

A.0,4,7,18,10,25,15
B.0,4,25,15,7,18,10
C.7,15,10,0,4,18,25
D.7,15,25,18,10,0,4

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

A.希爾排序
B.歸并排序
C.堆排序
D.快速排序

13.一組記錄的關(guān)鍵碼為(45,68,57,13,24,89)，利用堆排序算法進(jìn)行升序排序，建立的初始堆為(　　)

A.68,45,57,13,24,89
B.89,68,57,13,24,45
C.89,68,57,45,24,13
D.89,57,68,24,45,13

14.一棵二叉排序樹中,關(guān)鍵字n所在結(jié)點是關(guān)鍵字m所在結(jié)點的祖先,則(　　)

A.n一定大于m
B.n一定小于m
C.n一定等于m
D.n與m的大小關(guān)系不確定

15.設(shè)散列表長m=14,散列函數(shù)H(key)=key%11，表中已保存4個關(guān)鍵字：addr(15)=4，addr(38)=5，adr(61)=6，addr(84)=7，其余地址均為空。保存關(guān)鍵字49時存在沖突，采用線性探查法來處理。則查找關(guān)鍵字49時的探查次數(shù)是(　　)

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

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

11.數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù),它與數(shù)據(jù)元素的存儲結(jié)構(gòu)_________。

12.指針p和指針q分別指向單鏈表L中的兩個相鄰結(jié)點,即q> nextp,且p所指結(jié)點不是終端結(jié)點。若要刪除p所指結(jié)點,則執(zhí)行的語句是_________。

13.一個直接或間接調(diào)用自己的函數(shù)稱為_________。

14.廣義表(a,(b,c,d),e,f,(g,h))的表尾是_________。

15.二叉樹的前序遍歷序列和后序遍歷序列中,葉結(jié)點之間的相對次序_________。

16.如果圖G存在拓?fù)渑判蛐蛄?則G必為_________。

17.將一棵樹T轉(zhuǎn)換為一棵二叉樹T1,在T1中結(jié)點A是結(jié)點B的父結(jié)點,則在T中,A可能是B的父結(jié)點或_________。

18.對含n個元素的數(shù)據(jù)序列采用快速排序算法進(jìn)行排序,在最壞情況下的時間復(fù)雜度是_________。

19.散列方法中,表示散列表裝滿程度的指標(biāo)a稱為_________。

110.假設(shè)順序存儲的有序表R含有12個關(guān)鍵字,進(jìn)行二分查找時,平均查找長度為_________。

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

21.設(shè)電文字符集是{e1,e2,e3,e4,e5},它們出現(xiàn)的次數(shù)分別為:{50,10,16,8,12}?，F(xiàn)要為該字符集設(shè)計哈夫曼編碼。請回答下列問題。(1)畫出得到的哈夫曼樹。(2)給出各符號的哈夫曼編碼。

22.已知圖G采用鄰接矩陣存儲,鄰接矩陣如題27圖所示。(1)寫出從頂點A開始圖G的3個不同的深度優(yōu)先搜索遍歷序列。(2)寫出從頂點A開始圖G的2個不同的廣度優(yōu)先搜索遍歷序列。

23.有以下數(shù)據(jù)序列(19,14,23,01,68,20,84,27,55,11,10,79,12),使用希爾排序方法將其排成升序序列。請回答下列問題(1)寫出增量為4時對上述數(shù)據(jù)序列進(jìn)行一趟希爾排序的結(jié)果。(2)給出一個可行的希爾排序增量序列。

24.設(shè)有二叉排序樹如題29圖所示。請回答下列問題。(1)假定二叉排序樹初始為空,寫出一個數(shù)據(jù)輸入序列,按序插入時能得到題29圖所示的二叉排序樹。(2)能得到題29圖所示的二叉排序樹的不同的輸入數(shù)據(jù)序列有幾個?

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

31.順序表類型定義如下#define ListSize 100typedef struct{      int data[ListSize];      int length;}SeqLiist;閱讀下列算法,并回答問題。void change(SeqList *SL1, SeqList *SL2){        int minlength;         int k=0, temp;         if(SL1->length< SL2->length) return;        minlength= SL2->length;        while( k< minlength)    {           if (SL1->data[k]< SL2->data[k])      {          temp=SL1->data[k];                 SL1->data[k]=SL2->data[k];                SL2->data[k]=temp;      }           k++;       }         return;    }        void f30( SeqList *SL1, SeqList*SL2)  {   if( SL1->length> SL2->length) change( SL1, SL2 ); else change( SL2, SL1 ); return; } (1)若SL1->data中的數(shù)據(jù)為{25,4,256,9,-38,47,128,256,64},SL2->data中的數(shù)據(jù)為{22,4,-63,15,29,34,42,3},則執(zhí)行算法f30(&SL1,&SL2)后SL1->data和SL2->data中的數(shù)據(jù)各是什么?(2)該算法的功能是什么?

32.二叉樹的存儲結(jié)構(gòu)類型定義如下:typedef char Data Type;typedef struct node{       DataType data;       //data是數(shù)據(jù)域        struct node *lchild, * rchild;        //分別指向左右孩子}BinTNode;typedefBinTNode *BinTree;閱讀下列算法,并回答問題。void A31( BinTree T){      if(T!= NULL)  { printf( "%c", T->data );      A31(T->rchild );      printf("%c",T->data);       A31(T->lchild );     }     return; }(1)設(shè)二叉樹T如題31圖所示,給出執(zhí)行A31(T)的輸出結(jié)果。(2)給出該算法的時間復(fù)雜度。

33.待排序記錄的數(shù)據(jù)類型定義如下:#define maXsize 100typedef int KeyType;typedef struct {       KeyType key;} RecType;typedef RecType SeqList [MAXSIZE];下列算法實現(xiàn)自底向上、自頂向下交替進(jìn)行的雙向掃描冒泡排序,請在空白處填上適當(dāng)內(nèi)容使算法完整。void f32( SeqList R, int n){       int i=0;        RecType t;       int NoSwap=1;     while(NoSwap) {               NoSwap=0;           for(j=n-i-1; ____(1)____)             if(R[j].key t=R[j];              R[i]=R[j-1];              R[j-1]=t;                NoSwap=1;             }         for(____(2)____; j++)       if(Ri]. key>R[j+1].key){              t=R[i];               R[j]=R[j+1];              R[j+1]=t;            NoSwap=1;      }         ___(3)____;         }}

34.二叉樹的存儲結(jié)構(gòu)類型定義如下:typedef int DataType;typedef struct node{ DataType key;       //data是數(shù)據(jù)域  Struct node *lchild, *rchild; //分別指向左右孩子  } BinTNode;typedef BinTNode *BinTree;閱讀下列算法,并回答問題void A33(BinTree root, int k1, int k2, int end)  {      if (root==NULL) return;         A33(root->lchild, k1, k2, end);         if (end) return;        if (root->key>k2){           end=1;          return;         }      if (root->key >=k1) printf( "%d", root->key);        A33(root->rchild, k1, k2, end);}(1)設(shè)二叉排序樹T如題33圖所示,bt是指向根結(jié)點的指針。給出執(zhí)行A33(bt,6,100,0)的輸出結(jié)果。(2)給出該算法的功能。

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

41.已知二叉樹的存儲結(jié)構(gòu)類型定義如下:typedef struct node{      int data;      struct node *lchild, *rchild;  } BinNode;  typedef BinNode *BinTree;編寫遞歸算法,對于給定的一棵二叉樹T,將其修改為鏡像二叉樹。例如,題34圖所示的兩棵二叉樹互為鏡像二叉樹。函數(shù)的原型為:vod f34( BinTree T);