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

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

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

{

InitStack(S);InitQueue(Q);

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

{

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

}

while(!StackEmpty(S))

{

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

if(a!=b)returnERROR;

}

returnOK;

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