2018交大數(shù)據(jù)結(jié)構(gòu)期末復習樣卷帶答案

第2頁共4頁上海交通大學繼續(xù)教育學院網(wǎng)絡(luò)教育——期末復習樣卷答案課程名稱：數(shù)據(jù)結(jié)構(gòu)一、單項選擇題（每題2分，共30分）包含64個結(jié)點的完全二叉樹，其深度為（）(根的層次為1)。A、8 B、7 C、6 D、5關(guān)于算法的空間復雜度的理解錯誤的是（）。A.空間復雜度，即為算法的存儲空間需求。B.空間復雜度是指算法在執(zhí)行過程中所需要的最大的存儲空間。C.空間復雜度，包括算法在執(zhí)行過程中指令、常數(shù)、變量、輸入數(shù)據(jù)，以及程序執(zhí)行過程中所需要的輔助空間。D.算法的空間復雜度與算法無關(guān)。數(shù)據(jù)結(jié)構(gòu)包括3個方面的內(nèi)容，它們分別是（）。A、數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項B、數(shù)據(jù)元素、數(shù)據(jù)處理、算法實現(xiàn)C、數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)D、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的操作一個棧的入棧序列是a、b、c、d，則下列序列中不可能是棧的輸出序列的是（）。A、acbd B、dcba C、acdb D、dbac將5個不同的數(shù)據(jù)進行插入排序，至多需要比較（）次。A.8 B.9 C.10 D.25棧和隊列的共同點是（）。A.都是先進先出 B.都是先進后出C.只允許在端點處插入和刪除元素 D.沒有共同點設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準進行一趟快速排序的結(jié)果為（）。A、2,3,5,8,6 B、3,2,5,8,6 C、3,2,5,6,8 D、2,3,6,5,8設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素出線的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)該是（）。A.2 B.3 C.5 D.6設(shè)某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（）。A、n B、e C、2n D、2e

設(shè)無向圖G中有n個頂點e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為（）。A.n，e B.e，n C.2n，e D.n，2e下列關(guān)鍵字序列中，()是堆。A、16,72,31,23,94,53 B、94,23,31,72,16,53C、16,53,23,94，31,72 D、16,23,53,31,94,72以下說法錯誤的是（）。A.一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點越近B.哈夫曼樹中沒有度數(shù)為1的分支結(jié)點C.若初始森林中共有n裸二叉樹，最終求得的哈夫曼樹共有2n-1個結(jié)點D.若初始森林中共有n裸二叉樹，進行2n-1次合并后才能剩下一棵最終的哈夫曼樹設(shè)有序表中有1000個元素，則用二分查找法查找元素X最多需要比較（）次。A、25 B、10 C、7 D、1[log2n]+1二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以（）。A.它不能用順序存儲結(jié)構(gòu)存儲 B.它不能用鏈式存儲結(jié)構(gòu)存儲C.順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都能存儲D.順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都不能使用對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較()次關(guān)鍵字。A、3 B、4 C、5 D、6二、填空題（每空2分，共20分）在線性表中，元素ai(2≤i≤n)被稱為是元素ai-1的后繼。順序棧用data[1..n]存儲數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是__data[++top]=x___。設(shè)有一個空棧，棧頂指針為1000H(十六進制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH后，輸出序列是23，而棧頂指針值是100CHH。設(shè)棧為順序棧，每個元素占4個字節(jié)。一棵深度為6的滿二叉樹有31個分支結(jié)點和32個葉子。為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是構(gòu)造一個好的HASH函數(shù)和確定解決沖突的方法。大多數(shù)排序算法都有兩個基本的操作：比較和移動。三、簡答題（共30分）請解釋名詞：滿二叉樹、拓撲排序答：滿二叉樹：一棵深度為k且有個結(jié)點的二叉樹。拓撲排序：由某個集合上的一個偏序得到該集合上的一個全序，該操作稱為拓撲排序。在各種排序方法中，哪些是穩(wěn)定的？哪些是不穩(wěn)定的？各舉三個即可。答：穩(wěn)定：直接插入排序、折半插入排序、二路插入排序、表插入排序、起泡排序不穩(wěn)定：直接選擇排序、希爾排序、快速排序、堆排序假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個字母設(shè)計哈夫曼編碼。使用0～7的二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。一棵度為2的樹與一棵二叉樹有何區(qū)別？答：度為2的樹從形式上看與二叉樹很相似，但它的子樹是無序的，而二叉樹是有序的。即，在一般樹中若某結(jié)點只有一個孩子，就無需區(qū)分其左右次序，而在二叉樹中即使是一個孩子也有左右之分。給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹，并寫出該二叉樹的后序遍歷序列。后序遍歷序列:B,H,E,C,I,G,F,A,D四、程序設(shè)計題（每題10分，共20分）設(shè)從鍵盤輸入一整數(shù)的序列：a1,a2,a3，…，an,試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當ai≠-1時，將ai進棧；當ai=-1時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況（入棧滿等）給出相應(yīng)的信息。答：#definemaxsize棧空間容量voidInOutS(ints[maxsize]){inttop=0;//top為棧頂指針，定義top=0時為?？?。for(i=1;i<=n;i++)//n個整數(shù)序列作處理。{scanf(“%d”,&x);//從鍵盤讀入整數(shù)序列。if(x!=-1)//讀入的整數(shù)不等于-1時入棧。if(top==maxsize-1){printf(“棧滿\n”);exit(0);}elses[++top]=x;//x入棧。else//讀入的整數(shù)等于-1時退棧。{if(top==0){printf(“?？誠n”);exit(0);}elseprintf(“出棧元素是%d\n”,s[top--])；}}}//算法結(jié)束。試寫一個算法判別讀入的一個以‘@’為結(jié)束符的字符序列是否是“回文”。intPalindrome_Test()//判別輸入的字符串是否回文序列,是則返回1,否則返回0

{

InitStack(S);InitQueue(Q);

while((c=getchar())!='@')

{

Push(S,c);EnQueue(Q,c);//同時使用棧和隊列兩種結(jié)構(gòu)

}

while(!StackEmpty(S))

{

Pop(S,a);DeQueue(Q,b));

if(a!=b)returnERROR;

}

returnOK;

}//Palindrome_Test編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。DLR(liuyu*root)/