【MOOC期末】《數據結構》(南京郵電大學)期末中國大學慕課答案

有些題目順序不一致，下載后按鍵盤ctrl+F進行搜索數據結構在線期末試卷客觀卷1.單選題：一棵二叉樹中，若度為1的結點個數為47，度為2的結點的個數為38，則葉結點的個數為_______。

選項：

A、37

B、38

C、39

D、40

答案：【39】2.單選題：將7×8的二維數組A按照行優先順序存儲到一維數組B中，則B[37]中存儲的二維數組元素是_______。

選項：

A、A[4][4]

B、A[4][5]

C、A[4][6]

D、A[4][7]

答案：【A[4][5]】3.單選題：一個待散列存儲的元素序列（25，63，50，42，32，90）中，若選用h(key)=key%9作為散列函數，則元素18的同義詞共有（）個。

選項：

A、1

B、2

C、3

D、4

答案：【2】4.單選題：采用某種排序算法對序列(4,7,5,3,2,9)進行排序，對其進行第二趟排序后得到的序列為(4,5,7,3,2,9)，則該算法最可能是（）。

選項：

A、直接插入排序

B、堆排序

C、冒泡排序

D、合并排序

答案：【直接插入排序】5.單選題：對稀疏矩陣采用三元組方式存儲的最主要目的是（）。

選項：

A、使表達變得簡單

B、使矩陣元素的存取變得簡單

C、壓縮存儲空間

D、去掉矩陣中的多余元素

答案：【壓縮存儲空間】6.單選題：下面二叉樹中一定是完全二叉樹的是（）。

選項：

A、擴充二叉樹

B、滿二叉樹

C、哈夫曼樹

D、二叉搜索樹

答案：【滿二叉樹】7.單選題：二叉樹的先序遍歷為EFHIGJK，中序遍歷序列為HFIEJKG。該二叉樹根結點的左子樹的根是（）。

選項：

A、E

B、G

C、F

D、H

答案：【F】8.單選題：設一個棧輸入序列是1、2、3、4、5，則下列序列中不可能是棧的輸出序列是（）。

選項：

A、32541

B、15432

C、14523

D、23145

答案：【14523】9.單選題：若從無向圖的任意一個頂點出發進行深度優先遍歷可以訪問圖中所有的頂點，則該圖一定是（）。

選項：

A、非連通圖

B、連通圖

C、強連通圖

D、有向非強連通圖

答案：【連通圖】[vk-content]10.單選題：二叉搜索樹中，最大元素的左子樹（），它的右子樹（）。

選項：

A、一定為空，不一定為空

B、不一定為空，一定不為空

C、一定不為空，不一定為空

D、不一定為空，一定為空

答案：【不一定為空，一定為空】11.單選題：不帶表頭結點的單鏈表中，first為頭指針，當（）時，單鏈表為空。

選項：

A、first==NULL

B、first->link==NULL

C、first->link==first

D、first!=NULL

答案：【first==NULL】12.單選題：在有序表9,11,27,41,49,53,62,89,94,99上查找元素79，若執行對半搜索，需要比較_____次查找失敗

選項：

A、2

B、3

C、4

D、5

答案：【4】13.單選題：序列11,23,54,48,52,59是最小堆

選項：

A、正確

B、錯誤

答案：【正確】14.單選題：一棵完全二叉樹具有100個結點，則該樹葉子結點個數是50。

選項：

A、正確

B、錯誤

答案：【正確】15.單選題：一個表示工程的AOE網中的關鍵路徑可以有多條。

選項：

A、正確

B、錯誤

答案：【正確】16.單選題：序列95,72,60,28,84,94是最大堆

選項：

A、正確

B、錯誤

答案：【錯誤】17.單選題：已知先序遍歷和后序遍歷序列能唯一確定一棵二叉樹。

選項：

A、正確

B、錯誤

答案：【錯誤】18.單選題：數組A[20]實現循環隊列，已知front=18，rear=4，則隊列中隊列元素個數為6個

選項：

A、正確

B、錯誤

答案：【正確】19.已知一棵二叉樹結點的后序遍歷序列為：C,B,F,D,A,E,中序遍歷序列為B,C,A,F,D,E,請給出該樹的先序遍歷序列：___________。（請用半角逗號作為分隔符，不要有空格，例如A,B,C,D,E,F）

答案：【E,A,B,C,D,F】20.已知一棵二叉樹結點的先序遍歷序列為：D,A,B,C,F,E,中序遍歷序列為B,A,D,C,E,F,請給出該樹的后序遍歷序列：___________。（請用半角逗號作為分隔符，不要有空格，例如A,B,C,D,E,F）

答案：【B,A,E,F,C,D】21.將7×8的二維數組A按照行優先順序存儲到一維數組B中，則B[39]中存儲的二維數組元素是A[4][__]。

答案：【7】22.對有11個元素的有序表進行對半搜索，搜索成功的平均搜索長度為_______

答案：【3】23.已知哈夫曼樹結點總數是99個，則該哈夫曼樹對_________個信號進行了哈夫曼編碼。

答案：【50】24.在有10個頂點的無向圖G的鄰接矩陣A中，若A[2][6]等于1，則A[6][2]等于。

答案：【1】25.堆的存儲結構是存儲結構

答案：【順序】26.設有8×8的數組A，其每個元素占3個字節，已知A[6][1]在內存中的地址是162，按列優先順序存儲，A[7][2]的地址是_________。

答案：【189】27.已知一棵二叉搜索樹的層次遍歷序列為5,3,6,2,4,1，則在這棵二叉搜索樹上搜索元素1需要進行______次比較。

答案：【4】28.高度為6（根的層次為1）的完全二叉樹至少有個結點。

答案：【32】29.對于一個具有n個結點的單鏈表，在給定值為x的結點后插入一個新結點的平均時間復雜度為O（_______）。

答案：【n】數據結構在線期末考試主觀卷1.友情提醒：提交答案時，如果不方便使用文字時，請直接提交圖片（請不要使用附件），謝謝！已知英文字母集合{A,B,C,D,E,F}及其權值集合{2,6,10,14,4,1}，請給出以上英文字母的哈夫曼編碼，要求該編碼對應的哈夫曼樹上左分支編碼為0，右分支編碼為1，且任意結點的左孩子權值不大于右孩子權值。A:____________B:____________C:____________D:____________E:____________F:____________WPL=____________

答案：【一個編碼3分字符與編碼的對應關系如下：A:11101B:110C:10D:0E:1111F:11100WPL2分WPL=83】2.給定一棵二叉樹，請完成下列算法交換左右子樹。voidExchange(BTreebt){（1）;}voidExchange(BTNode*t){if(!t)return;BTNode*temp=t->LChild;（2）;t->RChild=temp;（3）;（4）;}

答案：【(1)Exchange(bt.Root)(2)t->LChild=t->RChild(3)Exchange(t->LChild)或Exchange(t->RChild)(4)Exchange(t->RChild)或Exchange(t->LChild)評分標準：一空5分】3.將整型數據元素存儲在List類型的線性表中，List類型定義如下：typedefstructlist{intn;intD[MaxSize];}List;請完成直接插入排序算法。voidInsertSort(List*list){inti,j;//i為待插入元素下標intitem;//每一趟待插入元素for(i=1;in;i++){(1);for(j=i-1;j>=0;j--){if((2))(3);elsebreak;}(4);//待插入元素有序存放至有序序列中}}

答案：【(1)item=list->D[i](2)item<list->D[j](3)list->D[j+1]=list->D[j](4)list->D[j+1]=item評分標準：一空5分】4.請從空樹開始構造二叉平衡樹，依次插入關鍵字40,28,6,72,98，畫出相應的二叉平衡樹。

答案：【】5.已知森林轉換后的二叉樹如圖所示，請畫出對應森林。

答案：【一棵樹5分】6.使用普里姆算法以0為源點構建該圖的最小代價生成樹，并計算該生成樹的代價。

答案：【(16分)生成樹的代價是36（4分）】7.給定一個長度為13的散列表ht如下所示，采用二次探查法解決沖突，散列函數為h(key)=key%13，請向散列表依次插入關鍵字為20,64,37,26,35的集合元素，給出插入完成后的散列表。

答案：【錯一個扣4分】8.根據下圖的鄰接表，從頂點2出發，請給出深度優先遍歷的遍歷序列。

答案：【深度優先遍歷序列：2，4，5，0，1，3】9.請對序列(4,5,16,2,3,1,3,6,8)進行快速排序，寫出前2趟的排序結果，按照如下答題格式進行答題，答題時注意不要漏掉下劃線。答題格式：第1趟：____________________________第2趟：____________________________

答案：【第1趟：3,3,1,2,4,16,5,6,8第2趟：1,2,3,3,4,16,5,6,8評分要點：每趟10分】10.請編寫算法計算鄰接表表示的圖中任意頂點v的出度。邊結點和鄰接表的結構C語言定義如下：typedefstructeNode{intadjVex;structeNode*nextArc;}ENode;typedefstructgraph{int