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

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

2、是 。8、 在查找時(shí)，若采用折半查找，要求線性表 ，而哈希表的查找，要求線性表 。9、對(duì)于文件，按物理結(jié)構(gòu)劃分，可分為順序文件、 文件、 文件和多關(guān)鍵字文件。二、單項(xiàng)選擇題（請(qǐng)將答案寫在題目后的括號(hào)中。每題2分，共18分）1、有如下遞歸函數(shù)fact(n)，其時(shí)間復(fù)雜度是（ ）。Fact(int n) if (nnext=NULL； （B） p=NULL；（C） p-next=head； （D） p=head； 3、設(shè)有一個(gè)棧頂指針為top的順序棧S，top為0時(shí)表示?？?，則從S中取出一個(gè)元素保存在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)的長(zhǎng)度是 ，深度是 。（ ）（A） 6，3 （B） 5，3 （C） 6，4 （D） 6，25、 當(dāng)一棵有n個(gè)結(jié)點(diǎn)的二叉樹按層次從上到下，同層次從左到右將(結(jié)點(diǎn))數(shù)據(jù)存儲(chǔ)在一維數(shù)組A1n中時(shí)，數(shù)組中第i個(gè)結(jié)點(diǎn)的左子結(jié)點(diǎn)是 。（ ）（A） A2i(2in) （B） A2i+1(2i+1n) （C） Ai/2 （D） 條件不充分，無(wú)法確定6、設(shè)有一棵二叉樹，其先序遍歷序列是acdgehibfkj，中序遍歷序列是dgcheiabkfj，則該二叉樹的后序遍歷序列是 。（ ）（A） gdehickjfba （B

4、） gdhiecfkjba （C） dghieckjfba （D） gdhieckjfba7、 在一個(gè)有向圖中，所有頂點(diǎn)的出度之和等于所有頂點(diǎn)的入度之和的 倍，所有頂點(diǎn)的度之和等于所有頂點(diǎn)的出度之和的 倍。（ ）（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的鏈表中有 個(gè)記錄。（ ）(A) 4 （B） 2 （C） 3 （D） 19、 用直接插入法對(duì)下列四個(gè)序列按非遞減方式排序，元素比較次數(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é)點(diǎn)的權(quán)值，請(qǐng)構(gòu)造對(duì)應(yīng)的Huffman樹，然后求出其帶權(quán)路徑長(zhǎng)度WPL。2、 對(duì)于下圖中的網(wǎng)，寫出該網(wǎng)的鄰接鏈表；然后寫出其廣度優(yōu)先搜索生成樹（假設(shè)從頂點(diǎn)V1出發(fā)）；最后給出按Kruskal算法得到的最小生成樹。1524368113341073、 將關(guān)鍵字序列（15，21，13，7

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

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

8、進(jìn)行編號(hào)建立鏈?zhǔn)蕉鏄?。?duì)每個(gè)結(jié)點(diǎn)，輸入結(jié)點(diǎn)i、結(jié)點(diǎn)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 ; /*以編號(hào)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é)點(diǎn)編號(hào) */ if ( ) sj-Lchild=p ; else ; return(T) ; 3、 圖的鄰接鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下圖所示。下面算法是從頂點(diǎn)v出發(fā)，遞歸地深度優(yōu)先搜索圖G。adjvex info nextarc表結(jié)點(diǎn)data firstarc頂點(diǎn)結(jié)點(diǎn)#define MAX_VEX_NUM 30 /* 最大頂點(diǎn)數(shù) */BOOLEAN VisitedMAX_VEX_NUM ;void DFS(ALGraph *G , int v)

10、 LinkNode *p ; Visitedv=TRUE ; Visitv ; /* 置訪問(wèn)標(biāo)志，訪問(wèn)頂點(diǎn)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)說(shuō)明，14分）設(shè)T是指向二叉樹根結(jié)點(diǎn)的指針變量，用非遞歸方法統(tǒng)計(jì)樹中度為1和度為0的結(jié)點(diǎn)個(gè)數(shù)。11數(shù)據(jù)結(jié)構(gòu)模擬試題14參考答案一、填空題（每小題2分，共18分）1、 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖（或網(wǎng)）狀結(jié)構(gòu)2、 時(shí)間復(fù)雜度 空間復(fù)雜度3、 物理上的相鄰 指針4、 操作受限 后進(jìn)先出（先進(jìn)后出） 5、 13406、左子樹 右子樹7、 頂點(diǎn)數(shù) 對(duì)稱矩陣8、 順序存儲(chǔ)且有序 散列存儲(chǔ)9、索引 散列二、單項(xiàng)選擇題（請(qǐng)將答案寫在題目后的括號(hào)中。每題2分，共18分）題號(hào)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從頂點(diǎn)V1出發(fā)的廣度優(yōu)先搜索的頂點(diǎn)序列是12453，相應(yīng)的生成樹如下：按Kruskal算法得到的最小生成樹152436334從頂點(diǎn)V1出發(fā)廣度優(yōu)先搜索生成樹1524368473、 解：將關(guān)鍵字序列（15，21，13，7，4，9，25，19，2

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

14、排序時(shí)的每一趟結(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分）請(qǐng)?jiān)谙旅娓魉惴ǖ目瞻滋幪钌舷鄳?yīng)語(yǔ)句實(shí)現(xiàn)算法功能。每個(gè)空白處只能填一個(gè)語(yǔ)句。1、頭插入法創(chuàng)建單鏈表，以整數(shù)的最大值(32767)作為輸入結(jié)束，鏈表的頭結(jié)點(diǎn)head作為返回值。P= (LNode *)mall

15、oc(sizeof(LNode)pnext= headnext2、按滿二叉樹的方式對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)建立鏈?zhǔn)蕉鏄?。?duì)每個(gè)結(jié)點(diǎn)，輸入結(jié)點(diǎn)i、結(jié)點(diǎn)ch。pLchild=pRchild=NULL i%2=0sj-Rchild=p3、從頂點(diǎn)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)說(shuō)明，14分）解：結(jié)點(diǎn)類型定義及算法如下：#define Max_Node_Num 50Typedef struct BTNode ElemType data ; /* 數(shù)據(jù)域，保存結(jié)點(diǎn)的值 */struct BTNode *Lchild , *Rchild ; /* 指針域 */BTNode ; /* 結(jié)點(diǎn)的類型 */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