《數據結構》模擬試題綜合測試題帶答案 (12)

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

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

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

4、等于所有頂點的入度之和的 倍。（ ）（A） 1/2，1 （B） 1，2 （C） 2，1 （D） 1，47、設有一個長度為12的有序表，采用二分查找方法對該表進行查找時，在表內各元素等概率情況下查找成功所需的平均比較次數為。（ ）(A) 35/12 （B） 37/12 （C） 39/12 （D） 43/128、 設有一組記錄的關鍵字是（37，28，56，80，60，14，25，50），用快速排序法以第一個記錄為基準得到的一次劃分結果是（ ）。（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、 文件在外存上的上的組織方式稱為文件的物理結構?；镜奈锢斫Y構有：（ ）(A) 順序結構，鏈接結構，線性結構 (B) 線性結構，鏈接結構，索引結構(C) 順序結構，鏈接結構，線性結構 (D) 順序結構，鏈接結構，索引結構三、分析題（每題6分，共30分）1、 設有一棵二叉樹，其先序遍歷序列是abdgehicf，中序遍歷序列是gdbheiafc，請畫出這棵二叉樹，然后畫出其后序線索化樹。2、 對于下圖中的網，寫出該網的鄰接鏈表；然后寫出其廣度優(yōu)先搜索生成樹（假設從頂點V1出發(fā)）；最后給出按Prime算法從頂點V5出發(fā)得到的最小生

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

7、填空（每空2分，共20分）請在下面各個算法的空白處填上相應的語句，以實現算法功能。每個空白處只能填一個語句。1、 循環(huán)隊列Q的隊首元素出隊操作算法。#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; ; 五、編寫算法（要求給出相應的數據結構說明，14分）將以L為頭結點的單鏈表中值重復的結點刪除，使所得的結果鏈表中所有結點的值均不相同；并對算法進行分析。10數據結構模擬試題12參考答案一、填空題（每小題2分，共18分）1、 線性結構 樹形結構 圖（或網）狀結構2、 時間復雜度 空間復雜度3、 (直接)前驅結點 (直接)后繼結點4、 零個字符組成的串 0 5、 3006、 只有右子樹上的所有結點7、 先序遍歷8、 索引 塊9、 操作系統(tǒng) 數據庫二、單項選擇題（請將答案寫在題目后的括號中。每題2分，共18分）題號123456789答案ABCBDBB

11、CD三、分析題（每題6分，共30分）fabcehidgNULLfabcehidg圖(a) 二叉樹圖(b) 后序線索化樹1、 解：所畫出的二叉樹如圖(a)所示。樹的后序遍歷序列是gdhiebfca，其后序線索化樹如圖(b)所示。2、 解：該網的鄰接鏈表如下圖所示：0123412345293758193441351124174321333532114318從頂點V1出發(fā)的廣度優(yōu)先搜索的頂點序列是12354，相應的生成樹如下：1524389137從頂點V1出發(fā)廣度優(yōu)先搜索生成樹從頂點V5出發(fā)的最小生成樹1524333473、 解：將關鍵字序列（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、 解：根據所給定的散列函數和處理沖突方法，得到的散列表結構如下：0123456789103356 25477117 298 4295 69成功查找的平均查找長度：ASL=(1×8+2×2+3×1)/11=17/115、 解：做非遞減排序時的每一趟結果如下：初始

13、關鍵字：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第四趟歸并完畢，排序結束。四、算法填空（每空2分，共20分）請在下面各個算法的空白處填上相應的語句，以實現算法功能。每個空白處只能填一個語句。1、 循環(huán)隊列Q的隊首元素出隊操作算法。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五、編寫算法（要求給出相應的數據結構說明，14分）解：結點類型定義及算法如下：#define int ElemType typedef struct Lnode ElemType data; /* 數據域，保存結點的值 */struct LNode *next; /* 指針域 */LNode; /* 結點的類型 */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