數(shù)據(jù)結(jié)構(gòu)第2階段練習(xí)題答案 2022秋下半年江南大學(xué)限時(shí)機(jī)考考前復(fù)習(xí)資料

第11頁(yè)/共NUMPAGES\*ARABIC11頁(yè)江南大學(xué)網(wǎng)絡(luò)教育第二階段練習(xí)題的參考答案選擇為，在文檔最后考試科目:《數(shù)據(jù)結(jié)構(gòu)》第章至第章（總分100分）__________學(xué)習(xí)中心（教學(xué)點(diǎn)）批次：層次：專(zhuān)業(yè)：學(xué)號(hào)：身份證號(hào)：姓名：得分：一單選題(共10題，總分值20分，下列選項(xiàng)中有且僅有一個(gè)選項(xiàng)符合題目要求，請(qǐng)?jiān)诖痤}卡上正確填涂。)1.設(shè)有向圖G中有五個(gè)頂點(diǎn)，各頂點(diǎn)的度分別為3、2、2、1、2，則G中弧數(shù)為（）。（2分）A.4條B.5條C.6條D.無(wú)法確定2.下列敘述中錯(cuò)誤的是（）。（2分）A.對(duì)數(shù)組一般不做插入和刪除操作B.順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)C.空的廣義表沒(méi)有表頭和表尾D.廣義表的表尾可能是原子也可能是子表3.下列敘述中錯(cuò)誤的是（）。（2分）A.由樹(shù)的先序遍歷序列和后序遍歷序列可以惟一確定一棵樹(shù)B.二叉樹(shù)不同于度為2的有序樹(shù)C.深度為k的二叉樹(shù)上最少有k個(gè)結(jié)點(diǎn)D.在結(jié)點(diǎn)數(shù)目相同的二叉樹(shù)中，最優(yōu)二叉樹(shù)的路徑長(zhǎng)度最短4.一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)有2個(gè)，度為2的結(jié)點(diǎn)有2個(gè)，度為1的結(jié)點(diǎn)有2個(gè)，則度為0的結(jié)點(diǎn)有（）。（2分）A.5個(gè)B.6個(gè)C.7個(gè)D.8個(gè)5.設(shè)有無(wú)向圖G=(V,E)，其中頂點(diǎn)集合V={a,b,c,d,e,f}，邊集合E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}。對(duì)G進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是（）。（2分）A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b6.設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（）條邊。（2分）A.n-1B.n(n-1)/2C.n(n+1)/2D.n27.設(shè)二維數(shù)組A5×8按行優(yōu)先順序存儲(chǔ)，每個(gè)數(shù)據(jù)元素占2個(gè)字節(jié)，首地址即元素A[0][0]的起始地址為S，則元素A[3][6]的起始地址為（）。（2分）A.S+66B.S+60C.S+33D.S+308.已知二叉樹(shù)T的先序序列為abdegcfh，中序序列為dbgeachf，則T的后序序列為（）。（2分）A.gedhfbcaB.dgebhfcaC.abcdefghD.acbfedhg9.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是（）。（2分）A.便于進(jìn)行矩陣運(yùn)算B.便于輸入和輸出C.節(jié)省存儲(chǔ)空間D.降低運(yùn)算的時(shí)間復(fù)雜度10.設(shè)廣義表L=((a,()),b,(c,d,e))，則Head(Tail(Tail(L)))的值為（）。（2分）A.bB.cC.(c)D.(c,d,e)二多選題(共5題，總分值10分，下列選項(xiàng)中至少有2個(gè)或2個(gè)以上選項(xiàng)符合題目要求，請(qǐng)?jiān)诖痤}卡上正確填涂。)11.下列不屬于數(shù)組的主要操作的是（）。（2分）A.存取;B.修改;C.插入;D.刪除;E.查找12.下列說(shuō)法正確的是（）。（2分）A.線性表中數(shù)據(jù)元素之間僅有線性關(guān)系;B.在圖形結(jié)構(gòu)中節(jié)點(diǎn)間的關(guān)系可以是任意的;C.簡(jiǎn)單路徑中序列中頂點(diǎn)可以重復(fù)出現(xiàn);D.鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)13.以下說(shuō)法正確的是（）（2分）A.二叉樹(shù)的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù);B.二叉樹(shù)的子樹(shù)無(wú)左右之分;C.二叉樹(shù)只能進(jìn)行鏈?zhǔn)酱鎯?chǔ);D.樹(shù)的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支14.圖的應(yīng)用算法有（）。（2分）A.克魯斯卡爾算法;B.哈弗曼算法;C.迪杰斯特拉算法;D.拓?fù)渑判蛩惴?5.完全二叉樹(shù)（）。（2分）A.適合于順序結(jié)構(gòu)存儲(chǔ);B.不一定適合順序結(jié)構(gòu)存儲(chǔ);C.葉子結(jié)點(diǎn)可在任一層出現(xiàn);D.某些結(jié)點(diǎn)有右子樹(shù)則必有左子樹(shù)三判斷題(共10題，總分值10分正確的填涂“A”，錯(cuò)誤的填涂“B”。)16.連通圖的生成樹(shù)包含了圖中的所有頂點(diǎn)。（1分）（

）17.用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)。（1分）（

）18.在含有n個(gè)結(jié)點(diǎn)的樹(shù)中，邊數(shù)只能是n-1條。（1分）（

）19.設(shè)深度為d（只有一個(gè)根結(jié)點(diǎn)時(shí)，d為1）的二叉樹(shù)只有度為0和2的結(jié)點(diǎn)，則此類(lèi)二叉樹(shù)的結(jié)點(diǎn)數(shù)至少為2d-1。（1分）（

）20.有向圖的鄰接矩陣一定是不對(duì)稱(chēng)的。（1分）（

）21.二叉樹(shù)通常有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（1分）（

）22.圖的深度優(yōu)先遍歷非遞歸算法通常采用隊(duì)列實(shí)現(xiàn)，廣度優(yōu)先遍歷非遞歸算法通常采用堆棧實(shí)現(xiàn)。（1分）（

）23.對(duì)N（≥2）個(gè)權(quán)值均不相同的字符構(gòu)造哈夫曼樹(shù)，則樹(shù)中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值。（1分）（

）24.某二叉樹(shù)的后序和中序遍歷序列正好一樣，則該二叉樹(shù)中的任何結(jié)點(diǎn)一定都無(wú)右孩子。（（1分）（

）25.AOE圖的關(guān)鍵路徑就是最長(zhǎng)的路徑。（1分）（

）四簡(jiǎn)答題(共2題，總分值20分)26.設(shè)二叉樹(shù)如下，試對(duì)其進(jìn)行先序線索化，畫(huà)出相應(yīng)的先序線索二叉樹(shù)存儲(chǔ)結(jié)構(gòu)示意圖。（10分）27.設(shè)有上三角矩陣(aij)n×n，i=0,1,…,n-1;j==0,1,…,n-1,將其上三角元素逐行存于數(shù)組B[m]中（m充分大），使得B[k]=aij，k≧0,求用i和j表示k的下標(biāo)變換公式。（10分）五綜合題(共3題，總分值40分)28.設(shè)有AOE網(wǎng)如下，要求：(1)求圖中各頂點(diǎn)代表的事件的最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間；(2)求圖中各弧代表的活動(dòng)的最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間；(3)列出各條關(guān)鍵路徑。（14分）29.設(shè)用于通信的電文由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.12、0.31、0.22、0.02、0.03、0.08、0.17、0.05。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼，要求畫(huà)出設(shè)計(jì)過(guò)程中所構(gòu)造的哈夫曼二叉樹(shù)。（13分）30.設(shè)二叉樹(shù)以二叉鏈表存儲(chǔ)，試設(shè)計(jì)算法，實(shí)現(xiàn)二叉樹(shù)的層序遍歷。（13分）

一單選題(共10題，總分值20分，下列選項(xiàng)中有且僅有一個(gè)選項(xiàng)符合題目要求，請(qǐng)?jiān)诖痤}卡上正確填涂。)1.參考答案選擇為：B解析過(guò)程：2.參考答案選擇為：D解析過(guò)程：3.參考答案選擇為：D解析過(guò)程：4.參考答案選擇為：C解析過(guò)程：5.參考答案選擇為：D解析過(guò)程：6.參考答案選擇為：B解析過(guò)程：7.參考答案選擇為：B解析過(guò)程：8.參考答案選擇為：B解析過(guò)程：9.參考答案選擇為：C解析過(guò)程：10.參考答案選擇為：D解析過(guò)程：二多選題(共5題，總分值10分，下列選項(xiàng)中至少有2個(gè)或2個(gè)以上選項(xiàng)符合題目要求，請(qǐng)?jiān)诖痤}卡上正確填涂。)11.參考答案選擇為：C,D解析過(guò)程：12.參考答案選擇為：A,B,D解析過(guò)程：13.參考答案選擇為：A,D解析過(guò)程：14.參考答案選擇為：A,C,D解析過(guò)程：15.參考答案選擇為：A,D解析過(guò)程：三判斷題(共10題，總分值10分正確的填涂“A”，錯(cuò)誤的填涂“B”。)16.參考答案選擇為：T解析過(guò)程：17.參考答案選擇為：F解析過(guò)程：18.參考答案選擇為：T解析過(guò)程：19.參考答案選擇為：T解析過(guò)程：20.參考答案選擇為：F解析過(guò)程：21.參考答案選擇為：T解析過(guò)程：22.參考答案選擇為：F解析過(guò)程：23.參考答案選擇為：T解析過(guò)程：24.參考答案選擇為：T解析過(guò)程：25.參考答案選擇為：T解析過(guò)程：四簡(jiǎn)答題(共2題，總分值20分)26.參考答案選擇為：答：解析過(guò)程：27.參考答案選擇為：答：解析過(guò)程：五綜合題(共3題，總分值40分)28.參考答案選擇為：關(guān)鍵路徑１：v1→v2→v5→v7關(guān)鍵路徑２：v1→v3→v6→v7解析過(guò)程：29.參考答案選擇為：編碼：0.02:001000.03:001010.05:00110.08:0000.12:1000.17:1010.22:010.31:11解析過(guò)程：30.參考答案選擇為：StatusLevelOrderTraverse(BitreeT,Status(*visit)(TElemTypee)){if(!T)returnOK;//空二叉樹(shù)InitQueue(Q);//初始化輔助隊(duì)列if(!visit(T->data))returnERROR;//訪問(wèn)根結(jié)點(diǎn)EnQueue(Q,T);//指向結(jié)點(diǎn)的指針入隊(duì)while(!QueueEmpty(Q)){//若隊(duì)列非空DeQueue(Q,p);//隊(duì)頭指針出隊(duì)if(p->lchild){//先訪問(wèn)p所指結(jié)點(diǎn)的