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

自考責(zé)任編輯：彭雅倩 2019-06-26

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

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

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

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

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

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

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

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é)點(diǎn),指針變量p指向終端結(jié)點(diǎn),next是結(jié)點(diǎn)的指針域,則下列邏輯表達(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個(gè)葉結(jié)點(diǎn),則T中結(jié)點(diǎn)個(gè)數(shù)最少是(　　)

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

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

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

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

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

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

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

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

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

11.對(duì)數(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é)點(diǎn)是關(guān)鍵字m所在結(jié)點(diǎn)的祖先,則(　　)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、算法閱讀題(本大題共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.二叉樹的存儲(chǔ)結(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)給出該算法的時(shí)間復(fù)雜度。

33.待排序記錄的數(shù)據(jù)類型定義如下:#define maXsize 100typedef int KeyType;typedef struct { KeyType key;} RecType;typedef RecType SeqList [MAXSIZE];下列算法實(shí)現(xiàn)自底向上、自頂向下交替進(jìn)行的雙向掃描冒泡排序,請(qǐng)?jiān)诳瞻滋幪钌线m當(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.二叉樹的存儲(chǔ)結(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é)點(diǎn)的指針。給出執(zhí)行A33(bt,6,100,0)的輸出結(jié)果。(2)給出該算法的功能。

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

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