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

1、數(shù)據(jù)結(jié)構(gòu)模擬試題14一、填空題（每小題2分，共18分）1、 對于給定的n個元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有集合, ， 和 四種。2、 數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是 和 。3、 順序存儲結(jié)構(gòu)是通過 表示數(shù)據(jù)元素之間的(邏輯)關(guān)系；鏈式存儲結(jié)構(gòu)是通過 表示數(shù)據(jù)元素之間的(邏輯)關(guān)系。4、 棧是 的線性表，其操作數(shù)據(jù)的基本原則是 。5、 設(shè)有一個二維數(shù)組A0909，若每個元素占5個基本存儲單元，A00的地址是1000，若按行優(yōu)先（以行為主）順序存儲，則A68的存儲地址是 。6、 二叉樹由根結(jié)點， 和 三個基本單元組成。7、 若采用鄰接矩陣存儲一個圖所需要的存儲單元取決于圖的 ；無向圖的鄰接矩陣一定

2、是 。8、 在查找時，若采用折半查找，要求線性表 ，而哈希表的查找，要求線性表 。9、對于文件，按物理結(jié)構(gòu)劃分，可分為順序文件、 文件、 文件和多關(guān)鍵字文件。二、單項選擇題（請將答案寫在題目后的括號中。每題2分，共18分）1、有如下遞歸函數(shù)fact(n)，其時間復(fù)雜度是（ ）。Fact(int n) if (nnext=NULL； （B） p=NULL；（C） p-next=head； （D） p=head； 3、設(shè)有一個棧頂指針為top的順序棧S，top為0時表示棧空，則從S中取出一個元素保存在P中執(zhí)行的操作是（ ）。（A） p=Stop+； （B） p=S+top；（C） p=S-top；

3、 （D） p=Stop-； 4、 廣義表(a, (a, b), d, e, (i, j), k)的長度是 ，深度是 。（ ）（A） 6，3 （B） 5，3 （C） 6，4 （D） 6，25、 當(dāng)一棵有n個結(jié)點的二叉樹按層次從上到下，同層次從左到右將(結(jié)點)數(shù)據(jù)存儲在一維數(shù)組A1n中時，數(shù)組中第i個結(jié)點的左子結(jié)點是 。（ ）（A） A2i(2in) （B） A2i+1(2i+1n) （C） Ai/2 （D） 條件不充分，無法確定6、設(shè)有一棵二叉樹，其先序遍歷序列是acdgehibfkj，中序遍歷序列是dgcheiabkfj，則該二叉樹的后序遍歷序列是 。（ ）（A） gdehickjfba （B

4、） gdhiecfkjba （C） dghieckjfba （D） gdhieckjfba7、 在一個有向圖中，所有頂點的出度之和等于所有頂點的入度之和的 倍，所有頂點的度之和等于所有頂點的出度之和的 倍。（ ）（A） 1/2，1 （B） 1，2 （C） 2，1 （D） 1，48、設(shè)有一組記錄的關(guān)鍵字為19, 14, 23, 1, 68, 20, 84, 27，用鏈地址法構(gòu)造哈希表，哈希函數(shù)為H(key)=key MOD 13，哈希地址為1的鏈表中有 個記錄。（ ）(A) 4 （B） 2 （C） 3 （D） 19、 用直接插入法對下列四個序列按非遞減方式排序，元素比較次數(shù)最少的是（ ）。（A）

5、 21，32，46，40，80，69，90，94 （B） 94，32，40，90，80，46，21，69 （C） 32，40，21，46，69，94，90，80 （D） 90，69，80，46，21，32，94，40三、分析題（每題6分，共30分）1、 若以7, 19, 2, 6, 32, 3, 21, 10作為葉子結(jié)點的權(quán)值，請構(gòu)造對應(yīng)的Huffman樹，然后求出其帶權(quán)路徑長度WPL。2、 對于下圖中的網(wǎng)，寫出該網(wǎng)的鄰接鏈表；然后寫出其廣度優(yōu)先搜索生成樹（假設(shè)從頂點V1出發(fā)）；最后給出按Kruskal算法得到的最小生成樹。1524368113341073、 將關(guān)鍵字序列（15，21，13，7

6、，4，9，25，19，23）插入到初態(tài)為空的二叉排序樹中，請畫出建立二叉排序樹T的過程；然后畫出刪除13之后的二叉排序樹T1。4、 線性表的關(guān)鍵字集合71，25，8，29，42，69，95，33，17，56，47，共有11個元素，已知散列函數(shù)為：H（k） = k MOD 11，采用鏈地址處理沖突，請給出對應(yīng)的散列表結(jié)構(gòu)，并計算該表成功查找的平均查找長度。5、 已知序列15，29，13，40，17，9，38，27，52，45，請給出采用增量序列為5, 3, 1的希爾排序法，對該序列做非遞減排序時的每一趟結(jié)果。四、算法填空（每空2分，共20分）請在下面各算法的空白處填上相應(yīng)語句以實現(xiàn)算法功能。每個

7、空白只能填一個語句。1、頭插入法創(chuàng)建單鏈表，以整數(shù)的最大值(32767)作為輸入結(jié)束，鏈表的頭結(jié)點head作為返回值。LNode *create_LinkList(void) int data; LNode *head, *p ; head= (LNode *)malloc(sizeof(LNode) ; head-next=NULL; /*創(chuàng)建鏈表的表頭結(jié)點head*/ while (1) scanf(“%d”,& data) ; if (data=32767) break ; ； pdata=data; ； headnext=p ; return (head); 2、按滿二叉樹的方式對結(jié)點

8、進行編號建立鏈式二叉樹。對每個結(jié)點，輸入結(jié)點i、結(jié)點ch。#define Max_Node_Num 50Typedef struct BTNode char data ; struct BTNode *Lchild , *Rchild ; BTNode ;BTNode *Create_BTree() BTNode *T , *p , *sMax_Node_Num ; char ch ; int i , j ; while (1) scanf(“%d”,&i) ; if (i=0) break ; /*以編號0作為輸入結(jié)束*/ else ch=getchar() ; p=(BTNode *)ma

9、lloc(sizeof(BTNode) ; pdata=ch ; ; si=p ; if (i=1) T=p ; else j=i/2 ; /* j是i的雙親結(jié)點編號 */ if ( ) sj-Lchild=p ; else ; return(T) ; 3、 圖的鄰接鏈表的結(jié)點結(jié)構(gòu)如下圖所示。下面算法是從頂點v出發(fā)，遞歸地深度優(yōu)先搜索圖G。adjvex info nextarc表結(jié)點data firstarc頂點結(jié)點#define MAX_VEX_NUM 30 /* 最大頂點數(shù) */BOOLEAN VisitedMAX_VEX_NUM ;void DFS(ALGraph *G , int v)

10、 LinkNode *p ; Visitedv=TRUE ; Visitv ; /* 置訪問標志，訪問頂點v */ ; while (p!=NULL) if (!Visitedp-adjvex) ; ; 4、 冒泡排序算法。#define FALSE 0#define TRUE 1Void Bubble_Sort(Sqlist *L) int j ,k ,flag ; for (j=0; jlength; j+) /* 共有n-1趟排序 */ flag=TRUE ; for (k=1; klength-j; k+) /* 一趟排序 */ if ( ) flag=FALSE ; L-R0=L-R

11、k ; L-Rk=L-Rk+1 ; L-Rk+1=L-R0 ; if ( ) break ; 五、編寫算法（要求給出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)說明，14分）設(shè)T是指向二叉樹根結(jié)點的指針變量，用非遞歸方法統(tǒng)計樹中度為1和度為0的結(jié)點個數(shù)。11數(shù)據(jù)結(jié)構(gòu)模擬試題14參考答案一、填空題（每小題2分，共18分）1、 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖（或網(wǎng)）狀結(jié)構(gòu)2、 時間復(fù)雜度 空間復(fù)雜度3、 物理上的相鄰 指針4、 操作受限 后進先出（先進后出） 5、 13406、左子樹 右子樹7、 頂點數(shù) 對稱矩陣8、 順序存儲且有序 散列存儲9、索引 散列二、單項選擇題（請將答案寫在題目后的括號中。每題2分，共18分）題號123456

12、789答案ACDBDDBCA10019402125311671710286032三、分析題（每題6分，共30分）1、 解：所構(gòu)造的Huffman樹如下圖所示。WPL=(19+21+32)2+(6+7+10)4+(2+3)5=2612、 解：該網(wǎng)的鄰接鏈表如下圖所示：1234518374608243104111433110230743111330601234從頂點V1出發(fā)的廣度優(yōu)先搜索的頂點序列是12453，相應(yīng)的生成樹如下：按Kruskal算法得到的最小生成樹152436334從頂點V1出發(fā)廣度優(yōu)先搜索生成樹1524368473、 解：將關(guān)鍵字序列（15，21，13，7，4，9，25，19，2

13、3）生成二叉排序樹T的過程如圖(a)所示；刪除13之后的二叉排序樹T1如圖(b)所示。15211513211571321154713211594713211525947132115圖(a) 生成的二叉排序樹T的過程2325199471321152519947132115圖(b) 刪除13后的二叉排序樹25231947921154、 解：根據(jù)所給定的散列函數(shù)和處理沖突方法，得到的散列表結(jié)構(gòu)如下：0123456789103356 25477117 298 4295 69成功查找的平均查找長度：ASL=(18+22+31)/11=17/115、 解：采用增量序列為5, 3, 1的希爾排序法，做非遞減

14、排序時的每一趟結(jié)果如下：初始關(guān)鍵字：15， 29， 13， 40， 52， 9，3 8， 27， 17， 45第一趟： 9， 29， 13， 17， 45， 15， 38， 27， 40， 52第二趟： 9， 27， 13， 17， 29， 15， 38， 45， 40， 52第三趟： 9， 13， 15， 17， 27， 29， 38， 40， 45， 52四、算法填空（每空2分，共20分）請在下面各算法的空白處填上相應(yīng)語句實現(xiàn)算法功能。每個空白處只能填一個語句。1、頭插入法創(chuàng)建單鏈表，以整數(shù)的最大值(32767)作為輸入結(jié)束，鏈表的頭結(jié)點head作為返回值。P= (LNode *)mall

15、oc(sizeof(LNode)pnext= headnext2、按滿二叉樹的方式對結(jié)點進行編號建立鏈式二叉樹。對每個結(jié)點，輸入結(jié)點i、結(jié)點ch。pLchild=pRchild=NULL i%2=0sj-Rchild=p3、從頂點v出發(fā)，遞歸地深度優(yōu)先搜索圖G。p=G-AdjListv.firstarc DFS(G, p-adjvex) p=p-nextarc 4、 冒泡排序算法。L-Rk.keyL-Rk+1.key flag=TRUE五、編寫算法（要求給出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)說明，14分）解：結(jié)點類型定義及算法如下：#define Max_Node_Num 50Typedef struct BTNode ElemType data ; /* 數(shù)據(jù)域，保存結(jié)點的值 */struct BTNode *Lchild , *Rchild ; /* 指針域 */BTNode ; /* 結(jié)點的類型 */Void count_node_num( BTNode *T) BTNode *StackMax_Node_Num ,*p=T, *q ;int top=0 , leaf_num=0 , num1=0 ;if (T=NULL) printf(“The Binary Tree is Empty!n”) ;else do if