【MOOC】數(shù)據(jù)結(jié)構(gòu)與算法-大連理工大學 中國大學慕課MOOC答案

【MOOC】數(shù)據(jù)結(jié)構(gòu)與算法-大連理工大學中國大學慕課MOOC答案1.1隨堂測驗1、【單選題】在鏈接存儲結(jié)構(gòu)中，要求。本題答案：【每個結(jié)點占用一片連續(xù)的存儲區(qū)域】2、【單選題】對于數(shù)據(jù)結(jié)構(gòu)的描述，下列說法中不正確的是。本題答案：【相同的邏輯結(jié)構(gòu)對應的存儲結(jié)構(gòu)也必須相同】3、【單選題】以下關(guān)于鏈接存儲結(jié)構(gòu)的敘述中，是不正確的。本題答案：【可以通過計算得到第i個節(jié)點的存儲地址】4、【單選題】可以用、數(shù)據(jù)關(guān)系和基本操作定義一個完整的抽象數(shù)據(jù)類型。本題答案：【數(shù)據(jù)元素】5、【多選題】順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由表示的，鏈接存儲結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系式由表示的。本題答案：【存儲位置#指針】1.2隨堂測驗1、【單選題】算法指得是。本題答案：【對特定問題求解步驟的一種描述，是指令的有限序列?！?、【單選題】下面不是算法所必須具備的特性。本題答案：【高效性】3、【單選題】某算法的時間復雜度是O(n^2)，表明該算法。本題答案：【執(zhí)行時間與n^2成正比】4、【單選題】設(shè)某算法完成對n個元素進行處理，所需的時間是T(n)=100nlgn+200n+500，則該算法的時間復雜度是。本題答案：【O(nlgn)】5、【單選題】算法的時間復雜度屬于一種。本題答案：【事前分析估算的方法】緒論單元作業(yè)緒論單元測驗1、【單選題】在鏈接存儲結(jié)構(gòu)中，要求。本題答案：【每個結(jié)點占用一片連續(xù)的存儲區(qū)域】2、【單選題】對于數(shù)據(jù)結(jié)構(gòu)的描述，下列說法中不正確的是。本題答案：【相同的邏輯結(jié)構(gòu)對應的存儲結(jié)構(gòu)也必須相同】3、【單選題】以下關(guān)于鏈接存儲結(jié)構(gòu)的敘述中，是不正確的。本題答案：【可以通過計算得到第i個節(jié)點的存儲地址】4、【單選題】可以用、數(shù)據(jù)關(guān)系和基本操作定義一個完整的抽象數(shù)據(jù)類型。本題答案：【數(shù)據(jù)元素】5、【單選題】算法指得是。本題答案：【對特定問題求解步驟的一種描述，是指令的有限序列】6、【單選題】下面不是算法所必須具備的特性。本題答案：【高效性】7、【單選題】某算法的時間復雜度是O(n^2)，表明該算法。本題答案：【執(zhí)行時間與n^2成正比】8、【單選題】設(shè)某算法完成對n個元素進行處理，所需的時間是T(n)=100nlgn+200n+500，則該算法的時間復雜度是。本題答案：【O(nlgn)】9、【單選題】算法的時間復雜度屬于一種。本題答案：【事前分析估算的方法】2.1隨堂測驗1、【單選題】將兩個各有n個元素的有序順序表歸并成一個有序順序表，其最少的比較次數(shù)是。本題答案：【n】2、【單選題】在長度為n的線性表中查找值為x的數(shù)據(jù)元素的時間復雜度為。本題答案：【O(n)】3、【單選題】線性表的順序存儲結(jié)構(gòu)是一種的存儲結(jié)構(gòu)。本題答案：【隨機存取】4、【多選題】在一個長度為n的順序表的第i(1≤i≤n+1)個元素之前插入一個元素，需向后移動個元素，刪除第i(1≤i≤n)個元素時，需向前移動個元素。本題答案：【n-i+1#n-i】2.2隨堂測驗1、【單選題】設(shè)線性表中有2n個元素，以下操作中，在單鏈表上實現(xiàn)要比在順序表上實現(xiàn)效率更高。本題答案：【刪除指定的元素】2、【單選題】如果最常用的操作是取第i個節(jié)點及其前驅(qū)，則采用存儲方式最節(jié)省時間。本題答案：【順序表】3、【單選題】與單鏈表相比，雙鏈表的優(yōu)點之一是。本題答案：【訪問前后相鄰結(jié)點更靈活】4、【單選題】帶頭結(jié)點的單鏈表L為空的判定條件是。本題答案：【L-next==NULL】5、【單選題】在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的直接前驅(qū)，若在q和p之間插入s所指結(jié)點，則執(zhí)行操作。本題答案：【q-next=s;s-next=p;】6、【單選題】設(shè)指針rear指向帶頭結(jié)點的循環(huán)單鏈表的尾結(jié)點，若要刪除鏈表的第一個元素結(jié)點，正確的操作是。本題答案：【s=rear-next-next;rear-next-next=s-next;】2.3隨堂測驗1、【單選題】經(jīng)過以下棧運算后，x的值是。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s.x);本題答案：【a】2、【單選題】一個棧的進棧a,b,c,d,e則棧的不可能的輸出序列是。本題答案：【dceab】3、【單選題】已知一個棧的進棧序列是ABC，出棧序列是CBA，經(jīng)過的棧操作是。本題答案：【push,push,push,pop,pop,pop】4、【單選題】判定一個順序棧st為（元素個數(shù)最多為MaxSize）空的條件為。本題答案：【st.top==-1】5、【單選題】鏈棧與順序棧相比有一個明顯的優(yōu)點，即。本題答案：【通常不會出現(xiàn)棧滿的情況】2.5隨堂測驗1、【單選題】設(shè)環(huán)形隊列中數(shù)組的下標是0～N-1，其頭、尾指針分別為f和r，則其元素個數(shù)為。本題答案：【(r-f+N)%N】2、【單選題】對于鏈隊，在進行刪除操作時，。本題答案：【頭、尾指針可能都要修改】2.6隨堂測驗1、【單選題】兩個串相等必有串長度相等且。本題答案：【串中各位置字符均對應相等】2、【單選題】對于含有n個字符的鏈串s，查找元素值為x的算法時間復雜度為。本題答案：【O(n)】3、【單選題】設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作。本題答案：【模式匹配】2.7隨堂測驗1、【單選題】已知t=”abcaabbcabcaabdab”，該模式串的特征數(shù)組值為。本題答案：【-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1】線性表單元作業(yè)線性表單元測驗1、【單選題】將兩個各有n個元素的有序順序表歸并成一個有序順序表，其最少的比較次數(shù)是。本題答案：【n】2、【單選題】在長度為n的線性表中查找值為x的數(shù)據(jù)元素的時間復雜度為。本題答案：【O(n)】3、【單選題】線性表的順序存儲結(jié)構(gòu)是一種的存儲結(jié)構(gòu)。本題答案：【隨機存取】4、【單選題】設(shè)線性表中有2n個元素，以下操作中，在單鏈表上實現(xiàn)要比在順序表上實現(xiàn)效率更高。本題答案：【刪除指定的元素】5、【單選題】如果最常用的操作是取第i個節(jié)點及其前驅(qū)，則采用存儲方式最節(jié)省時間。本題答案：【順序表】6、【單選題】與單鏈表相比，雙鏈表的優(yōu)點之一是。本題答案：【訪問前后相鄰結(jié)點更靈活】7、【單選題】帶頭結(jié)點的單鏈表L為空的判定條件是。本題答案：【L-next==NULL】8、【單選題】在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的直接前驅(qū)，若在q和p之間插入s所指結(jié)點，則執(zhí)行操作。本題答案：【q-next=s;s-next=p;】9、【單選題】設(shè)指針rear指向帶頭結(jié)點的循環(huán)單鏈表的尾結(jié)點，若要刪除鏈表的第一個元素結(jié)點，正確的操作是。本題答案：【s=rear-next-next;rear-next-next=s-next;】10、【單選題】經(jīng)過以下棧運算后，x的值是。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s.x);本題答案：【a】11、【單選題】一個棧的進棧a,b,c,d,e則棧的不可能的輸出序列是。本題答案：【dceab】12、【單選題】已知一個棧的進棧序列是ABC，出棧序列是CBA，經(jīng)過的棧操作是。本題答案：【push,push,push,pop,pop,pop】13、【單選題】判定一個順序棧st為（元素個數(shù)最多為MaxSize）空的條件為。本題答案：【st.top==-1】14、【單選題】鏈棧與順序棧相比有一個明顯的優(yōu)點，即。本題答案：【通常不會出現(xiàn)棧滿的情況】15、【單選題】設(shè)環(huán)形隊列中數(shù)組的下標是0～N-1，其頭、尾指針分別為f和r，則其元素個數(shù)為。本題答案：【(r-f+N)%N】16、【單選題】對于鏈隊，在進行刪除操作時，。本題答案：【頭、尾指針可能都要修改】17、【單選題】對于含有n個字符的鏈串s，查找元素值為x的算法時間復雜度為。本題答案：【O(n)】18、【單選題】已知t=”abcaabbcabcaabdab”，該模式串的特征數(shù)組值為。本題答案：【-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1】3.1隨堂測驗1、【單選題】若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是本題答案：【11】2、【單選題】具有10個葉結(jié)點的二叉樹中有個度為2的結(jié)點。本題答案：【9】3、【單選題】一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是。本題答案：【501】4、【單選題】二叉樹的第I（只有根結(jié)點時的層數(shù)為1）層上最多含有結(jié)點數(shù)為。本題答案：【2^(I-1)】5、【單選題】一個具有1025個結(jié)點的二叉樹的高h（只有根結(jié)點時的高度為1）為本題答案：【11至1025之間】6、【單選題】一棵二叉樹高度為h（只有根結(jié)點時的高度為1）,所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有結(jié)點本題答案：【2h-1】7、【單選題】高度為K（只有根結(jié)點時的高度為1）的二叉樹最大的結(jié)點數(shù)為。本題答案：【2^k-1】8、【單選題】一棵樹高為K（只有根結(jié)點時的高度為1）的完全二叉樹至少有個結(jié)點本題答案：【2^(k-1)】9、【填空題】由3個結(jié)點所構(gòu)成的二叉樹有種形態(tài)。本題答案：【5】3.2隨堂測驗1、【單選題】二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以。本題答案：【順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都能存儲】2、【單選題】對于任意非空二叉樹，要設(shè)計出其后序遍歷的非遞歸算法而不是用堆棧結(jié)構(gòu)，最適合的方法是對該二叉樹采用存儲結(jié)構(gòu)。本題答案：【三叉鏈表】3.4隨堂測驗1、【單選題】一直二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為。本題答案：【DEBFCA】2、【填空題】用一維數(shù)組存放的一棵完全二叉樹ABCDEFGHIJKL，該二叉樹的后序遍歷的訪問結(jié)點序列為。本題答案：【HIDJKEBLFGCA##%_YZPRLFH_%##hidjkeblfgca】3.6隨堂測驗1、【填空題】設(shè)字符A，B，C，D，E，F(xiàn)的在報文中出現(xiàn)的頻率分別為0.25,0.2,0.06,0.14,0.28,0.07。求A的Huffman編碼。本題答案：【01】2、【填空題】（續(xù)）求B的Huffman編碼。本題答案：【00】3、【填空題】（續(xù)）求C的Huffman編碼。本題答案：【1000】4、【填空題】（續(xù)）求D的Huffman編碼。本題答案：【101】5、【填空題】（續(xù)）求E的Huffman編碼。本題答案：【11】6、【填空題】（續(xù)）求F的Huffman編碼。本題答案：【1001】3.7隨堂測驗1、【單選題】有n個葉子的哈夫曼樹的結(jié)點總數(shù)為。本題答案：【2n-1】2、【單選題】下面關(guān)于Huffman樹的說法，不正確的是。本題答案：【Huffman樹中除了度為1的結(jié)點外，還有度為2的結(jié)點和葉結(jié)點】二叉樹單元作業(yè)二叉樹單元測驗1、【單選題】若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是。本題答案：【11】2、【單選題】具有10個葉結(jié)點的二叉樹中有個度為2的結(jié)點。本題答案：【9】3、【單選題】一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是。本題答案：【501】4、【單選題】二叉樹的第I（只有根結(jié)點時的層數(shù)為1）層上最多含有結(jié)點數(shù)為。本題答案：【2^(l-1)】5、【單選題】一個具有1025個結(jié)點的二叉樹的高h（只有根結(jié)點時的高度為1）為本題答案：【11至1025之間】6、【單選題】一棵二叉樹高度為h（只有根結(jié)點時的高度為1）,所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有結(jié)點本題答案：【2h-1】7、【單選題】高度為K（只有根結(jié)點時的高度為1）的二叉樹最大的結(jié)點數(shù)為。本題答案：【2^k-1】8、【單選題】一棵樹高為K（只有根結(jié)點時的高度為1）的完全二叉樹至少有個結(jié)點本題答案：【2^(k-1)】9、【單選題】二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以。本題答案：【順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都能存儲】10、【單選題】對于任意非空二叉樹，要設(shè)計出其后序遍歷的非遞歸算法而不是用堆棧結(jié)構(gòu)，最適合的方法是對該二叉樹采用存儲結(jié)構(gòu)。本題答案：【三叉鏈表】11、【單選題】一直二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為。本題答案：【DEBFCA】12、【單選題】有n個葉子的哈夫曼樹的結(jié)點總數(shù)為。本題答案：【2n-1】13、【單選題】下面關(guān)于Huffman樹的說法，不正確的是。本題答案：【Huffman樹中除了度為1的結(jié)點外，還有度為2的結(jié)點和葉結(jié)點】14、【單選題】二叉樹的先序遍歷的遞歸實現(xiàn)如下：templateclassTvoidBinaryTreeT::PreOrder(BinaryTreeNodeT*root){if(root!=NULL){;}}則中間部分應為：本題答案：【Visit(root-value());PreOrder(root-leftchild());PreOrder(root-rightchild());】15、【單選題】在任何一棵二叉樹中，如果結(jié)點a有左孩子b,右孩子c,則在結(jié)點的先序序列、中序序列、后序序列中，本題答案：【結(jié)點b一定在結(jié)點c的前面】16、【單選題】在二叉樹的前序序列、中序序列和后序序列中，所有葉子結(jié)點的先后順序本題答案：【完全相同】17、【單選題】設(shè)n、m為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，n在m前的條件是本題答案：【n在m左方】18、【單選題】下列序列中，不能唯一地確定一棵二叉樹的是本題答案：【先序序列和后序序列】19、【單選題】設(shè)結(jié)點X和Y是二叉樹中任意的兩個結(jié)點．在該二叉樹的先序遍歷序列中X在Y之前，而在其后序遍歷序列中X在Y之后，則X和Y的關(guān)系是本題答案：【X是Y的祖先】20、【單選題】一棵二叉樹的前序遍歷序列為1234567,它的中序遍歷序列可能是本題答案：【1234567】21、【單選題】在二叉搜索樹的存儲結(jié)構(gòu)中，關(guān)鍵字值最大的結(jié)點（）本題答案：【右指針一定為空】22、【單選題】對于下列關(guān)鍵字序列，不可能構(gòu)成某二叉搜索樹中的一條查找路徑的序列是（）本題答案：【95，22，91，24，94，71】23、【單選題】從空樹開始一次插入元素52，26，14，32，71，60，93，58，24，41后構(gòu)成一個二叉搜索樹。在該樹中查找60要進行比較的次數(shù)是（）本題答案：【3】24、【單選題】對于二叉搜索樹，下面說法正確的是（）本題答案：【用逐點插入法構(gòu)造二叉搜索樹，若先后插入的關(guān)鍵字有序，二叉搜索樹的深度最大】25、【單選題】設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（）個空指針域。?本題答案：【2m】26、【單選題】根據(jù)使用頻率為五個字符設(shè)計的哈夫曼編碼不可能是__。?本題答案：【100，11，10，1，0?】27、【單選題】設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有（????）個。本題答案：【n+1】28、【單選題】設(shè)森林F對應的二叉樹為B，它有m個結(jié)點，B的根為P，P的右子樹結(jié)點個數(shù)為n，森林F中的第一棵樹的結(jié)點個數(shù)是__。?本題答案：【m-n-1】29、【單選題】度為4、高度為h的樹，__。?本題答案：【至少有h+3個結(jié)點】30、【單選題】設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（????）。本題答案：【M2+M3】4.1隨堂測驗1、【單選題】設(shè)圖G有n個結(jié)點，m條邊，且G中每個結(jié)點的度數(shù)不是k，就是k+1，則G中度數(shù)為k的節(jié)點數(shù)是。本題答案：【n(k+1)-2m】2、【單選題】設(shè)無向圖的頂點個數(shù)為n，則該圖最多有條邊。本題答案：【n(n-1)/2】4.2隨堂測驗1、【單選題】下列說法正確的是。本題答案：【用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中結(jié)點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)?！?.3隨堂測驗1、【單選題】下列說法不正確的是。本題答案：【圖的深度遍歷不適用于有向圖】2、【單選題】無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是。本題答案：【a,e,d,f,c,b】3、【單選題】判斷一個有向圖是否存在回路除了可以使用拓撲排序方法外，還可以使用方法。本題答案：【深度優(yōu)先遍歷】4.4隨堂測驗1、【單選題】在用Kruskal算法求解帶權(quán)連通圖的最小生成樹時，通常采用一個輔助結(jié)構(gòu)。本題答案：【并查集】2、【單選題】下列說法正確的是本題答案：【最小生成樹的Kruskal算法是一種貪心算法?！?.5隨堂測驗1、【單選題】下列說法不正確的是。(1).求從指定源點到其余各頂點的Dijkstra最短路徑算法中弧上權(quán)不能為負的原因是在實際應用中無意義；(2).利用Dijkstra求每一對不同頂點之間的最短路徑的算法時間是O(n3)；（圖用鄰接矩陣表示）(3).Floyd求每對不同頂點對的算法中允許弧上的權(quán)為負，但不能有權(quán)和為負的回路。本題答案：【(1),(2),(3)】4.6隨堂測驗1、【單選題】關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中。本題答案：【從源點到匯點的最長路徑】2、【單選題】下面關(guān)于求關(guān)鍵路徑的說法不正確的是。本題答案：【一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差】圖單元作業(yè)圖單元測驗1、【單選題】設(shè)圖G有n個結(jié)點，m條邊，且G中每個結(jié)點的度數(shù)不是k，就是k+1，則G中度數(shù)為k的節(jié)點數(shù)是。本題答案：【n(k+1)-2m】2、【單選題】設(shè)無向圖的頂點個數(shù)為n，則該圖最多有條邊。本題答案：【n(n-1)/2】3、【單選題】下列說法正確的是。本題答案：【用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中結(jié)點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)?！?、【單選題】下列說法不正確的是。本題答案：【圖的深度遍歷不適用于有向圖】5、【單選題】無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是。本題答案：【a,e,d,f,c,b】6、【單選題】判斷一個有向圖是否存在回路除了可以使用拓撲排序方法外，還可以使用方法。本題答案：【深度優(yōu)先遍歷】7、【單選題】在用Kruskal算法求解帶權(quán)連通圖的最小生成樹時，通常采用一個輔助結(jié)構(gòu)。本題答案：【并查集】8、【單選題】下列說法正確的是本題答案：【最小生成樹的Kruskal算法是一種貪心算法】9、【單選題】下列說法不正確的是。(1).求從指定源點到其余各頂點的Dijkstra最短路徑算法中弧上權(quán)不能為負的原因是在實際應用中無意義；(2).利用Dijkstra求每一對不同頂點之間的最短路徑的算法時間是O(n3)；（圖用鄰接矩陣表示）(3).Floyd求每對不同頂點對的算法中允許弧上的權(quán)為負，但不能有權(quán)和為負的回路。本題答案：【(1),(2),(3)】10、【單選題】關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中。本題答案：【從源點到匯點的最長路徑】11、【單選題】下面關(guān)于求關(guān)鍵路徑的說法不正確的是。本題答案：【一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差】12、【單選題】一個有n個頂