《數(shù)據(jù)結(jié)構(gòu)》模擬試題綜合測試題帶答案 (12)

1、數(shù)據(jù)結(jié)構(gòu)模擬試題12一、填空題（每小題2分，共18分）1、 數(shù)據(jù)的邏輯結(jié)構(gòu)包括 ， 和 三種結(jié)構(gòu)。2、 算法分析的兩個(gè)主要方面是 和 。3、 在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向 ，另一個(gè)指向 。4、 空串是 ，其長度等于 。5、 有一個(gè)10階對稱矩陣A，采用壓縮存儲方式，以行為主存儲下三角形到一個(gè)一維數(shù)組中，若A00的地址是200（每個(gè)元素占2個(gè)基本存儲單元），則A95的地址是 。6、 在非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊 。7、 采用鄰接鏈表存儲圖，則圖的深度優(yōu)先搜索算法類似于二叉樹的 。8、 在分塊查找方法中，首先查找 ，然后再查找相應(yīng)的 。9、 對于文件，按其記錄的類型可

2、將文件分為 文件、 文件。二、單項(xiàng)選擇題（請將答案寫在題目后的括號中。每題2分，共18分）1、有如下遞歸函數(shù)fact(n)，其時(shí)間復(fù)雜度是（ ）。Fact(int n) if (n<=1) return 1; else return(n*fact(n-1) ;（A） O(n) （B） O(n2) （C） O(2n) （D） O(n2n)2、 設(shè)有一個(gè)棧頂指針為top的順序棧S，top為0時(shí)表示?？?，則向S中壓入一個(gè)元素P執(zhí)行的操作是（ ）。（A） Stop+=p； （B） S+top=p；(C) S-top=p； （D） Stop-=p； 3、 稀疏矩陣一般的壓縮存儲方法有主要有（ ）兩

3、種。（A） 二維數(shù)組和三維數(shù)組 （B） 三元組和散列（C） 三元組和十字鏈表 （D） 散列和十字鏈表4、 一般樹的存儲結(jié)構(gòu)主要有（ ）。（A） 雙親表示法，孩子表示法，鏈表表示法（B） 雙親表示法，孩子表示法，孩子兄弟表示法（C） 雙親表示法，孩子兄弟表示法，鏈表表示法（D） 雙親表示法，孩子兄弟表示法，鏈表表示法5、 一棵有n(n0)個(gè)結(jié)點(diǎn)的滿二叉樹的葉子結(jié)點(diǎn)的數(shù)目是 ，非葉子結(jié)點(diǎn)的數(shù)目是 。（ ）（A） 22n 22n （B） 22n-1 22n （C） 22n-1 22n-1 （D） 22n 22n-16、 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍，所有頂點(diǎn)的度之和

4、等于所有頂點(diǎn)的入度之和的 倍。（ ）（A） 1/2，1 （B） 1，2 （C） 2，1 （D） 1，47、設(shè)有一個(gè)長度為12的有序表，采用二分查找方法對該表進(jìn)行查找時(shí)，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為。（ ）(A) 35/12 （B） 37/12 （C） 39/12 （D） 43/128、 設(shè)有一組記錄的關(guān)鍵字是（37，28，56，80，60，14，25，50），用快速排序法以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果是（ ）。（A） 25，28，37，14，56，80，60，50 （B） 25，28，37，14，60，80，56，50 （C） 25，28，14，37，60，80，

5、56，50 （D） 25，28，14，37，60，56，80，509、 文件在外存上的上的組織方式稱為文件的物理結(jié)構(gòu)?；镜奈锢斫Y(jié)構(gòu)有：（ ）(A) 順序結(jié)構(gòu)，鏈接結(jié)構(gòu)，線性結(jié)構(gòu) (B) 線性結(jié)構(gòu)，鏈接結(jié)構(gòu)，索引結(jié)構(gòu)(C) 順序結(jié)構(gòu)，鏈接結(jié)構(gòu)，線性結(jié)構(gòu) (D) 順序結(jié)構(gòu)，鏈接結(jié)構(gòu)，索引結(jié)構(gòu)三、分析題（每題6分，共30分）1、 設(shè)有一棵二叉樹，其先序遍歷序列是abdgehicf，中序遍歷序列是gdbheiafc，請畫出這棵二叉樹，然后畫出其后序線索化樹。2、 對于下圖中的網(wǎng)，寫出該網(wǎng)的鄰接鏈表；然后寫出其廣度優(yōu)先搜索生成樹（假設(shè)從頂點(diǎn)V1出發(fā)）；最后給出按Prime算法從頂點(diǎn)V5出發(fā)得到的最小生

6、成樹。1524389113341373、 將關(guān)鍵字序列（14，9，18，7，4，13，25，19，6）依此插入到初態(tài)為空的二叉排序樹中，請畫出所得到的樹T；然后畫出刪除18之后的二叉排序樹T1；最后再畫出插入18之后的二叉排序樹T2。4、 線性表的關(guān)鍵字集合71，25，8，29，42，69，95，33，17，56，47，共有11個(gè)元素，已知散列函數(shù)為：H（k） = k MOD 11，采用鏈地址處理沖突，請給出對應(yīng)的散列表結(jié)構(gòu)，并計(jì)算該表成功查找的平均查找長度。5、 已知序列35，29，52，60，17，9，38，27，13，45，請給出采用歸并排序法對該序列做非遞減排序時(shí)的每一趟結(jié)果。四、算法

7、填空（每空2分，共20分）請?jiān)谙旅娓鱾€(gè)算法的空白處填上相應(yīng)的語句，以實(shí)現(xiàn)算法功能。每個(gè)空白處只能填一個(gè)語句。1、 循環(huán)隊(duì)列Q的隊(duì)首元素出隊(duì)操作算法。#define Max_Queue_Size 100ElemType Delete_CirQueue(SqQueue Q) ElemType x ; if ( ) printf(“The Circular Queue is Null!”) ;else x=Q.Queue_arrayQ.front ; ; 2、 二叉樹中序遍歷的非遞歸算法。#define Max_Node_Num 50Void InorderTraverse( BTNode *T)

8、BTNode *StackMax_Node_Num ,*p=T ; int top=0 , bool=1 ; if (T=NULL) printf(“The Binary Tree is Empty!n”) ; else do while (p!=NULL) stack+top=p ; p=p->Lchild ; if (top=0) bool=0 ; else ; visit( p->data ) ; ; while ( ) ; 3、 折半查找算法。int Bin_Search(SSTable ST , KeyType key) int Low=1，High=ST.length,

9、 Mid ; while (Low<High) ; if (ST. elemMid.key=key) return(Mid) ; else if (ST. elemMid.key<key) Low=Mid+1 ;else High=Mid-1 ; ; 4、 簡單選擇排序算法。void simple_selection_sort(Sqlist *L) int m, n , k;for (m=1;m<L->length;m+) k=m ; for (n=m+1;n<=L->length;n+) if ( ) k=n ; if ( ) L->R0=L->

10、;Rm; L->Rm=L->Rk; ; 五、編寫算法（要求給出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)說明，14分）將以L為頭結(jié)點(diǎn)的單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果鏈表中所有結(jié)點(diǎn)的值均不相同；并對算法進(jìn)行分析。10數(shù)據(jù)結(jié)構(gòu)模擬試題12參考答案一、填空題（每小題2分，共18分）1、 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖（或網(wǎng)）狀結(jié)構(gòu)2、 時(shí)間復(fù)雜度 空間復(fù)雜度3、 (直接)前驅(qū)結(jié)點(diǎn) (直接)后繼結(jié)點(diǎn)4、 零個(gè)字符組成的串 0 5、 3006、 只有右子樹上的所有結(jié)點(diǎn)7、 先序遍歷8、 索引 塊9、 操作系統(tǒng) 數(shù)據(jù)庫二、單項(xiàng)選擇題（請將答案寫在題目后的括號中。每題2分，共18分）題號123456789答案ABCBDBB

11、CD三、分析題（每題6分，共30分）fabcehidgNULLfabcehidg圖(a) 二叉樹圖(b) 后序線索化樹1、 解：所畫出的二叉樹如圖(a)所示。樹的后序遍歷序列是gdhiebfca，其后序線索化樹如圖(b)所示。2、 解：該網(wǎng)的鄰接鏈表如下圖所示：0123412345293758193441351124174321333532114318從頂點(diǎn)V1出發(fā)的廣度優(yōu)先搜索的頂點(diǎn)序列是12354，相應(yīng)的生成樹如下：1524389137從頂點(diǎn)V1出發(fā)廣度優(yōu)先搜索生成樹從頂點(diǎn)V5出發(fā)的最小生成樹1524333473、 解：將關(guān)鍵字序列（14，9，18，7，4，13，25，19，6）依此插入到

12、初態(tài)為空的二叉排序樹中所得到的二叉排序樹T如圖(a)所示；刪除18之后的二叉排序樹T1如圖(b)所示；最后再插入18之后的二叉排序樹T2。149197134256圖(b) 刪除18的二叉排序樹14918713419256圖(a) 生成的二叉排序樹14919713418256圖(c) 插入18后的二叉排序樹4、 解：根據(jù)所給定的散列函數(shù)和處理沖突方法，得到的散列表結(jié)構(gòu)如下：0123456789103356 25477117 298 4295 69成功查找的平均查找長度：ASL=(1×8+2×2+3×1)/11=17/115、 解：做非遞減排序時(shí)的每一趟結(jié)果如下：初始

13、關(guān)鍵字：35，29，52，60，17，9，38，27，13，45第一趟： 29，35 52，60 9，17 27，38 13，45第二趟： 29，35，52，60 9，17，27，38 13，45第三趟： 29，35，52，60 9，13，17，27，38，45第四趟： 9，13，17，27，29，35，38，45，52，60第四趟歸并完畢，排序結(jié)束。四、算法填空（每空2分，共20分）請?jiān)谙旅娓鱾€(gè)算法的空白處填上相應(yīng)的語句，以實(shí)現(xiàn)算法功能。每個(gè)空白處只能填一個(gè)語句。1、 循環(huán)隊(duì)列Q的隊(duì)首元素出隊(duì)操作算法。Q.front=Q.rearQ.front=(Q.front+1)%Max_Queue_S

14、ize ;2、 二叉樹中序遍歷的非遞歸算法。p=stacktop-p=p->Rchildbool!=0 3、 折半查找算法。Mid=(Low+High)/2return(0)4、 簡單選擇排序算法。L->Rn.key<L->Rk.keyk!=mL->Rk=L->R0五、編寫算法（要求給出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)說明，14分）解：結(jié)點(diǎn)類型定義及算法如下：#define int ElemType typedef struct Lnode ElemType data; /* 數(shù)據(jù)域，保存結(jié)點(diǎn)的值 */struct LNode *next; /* 指針域 */LNode; /* 結(jié)點(diǎn)的類型 */void Delete_LinkList_Value(LNode *L) LNode *p=L->next, *q, *ptr ;ElemType k ;while ( p->next!=NULL) k=p->data ; ptr=p ; q=ptr->next ;while (q!=NULL) if (q->data=k) ptr->next=q->next