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

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

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

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

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

）20.有向圖的鄰接矩陣一定是不對稱的。（1分）（

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

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

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

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

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

）四簡答題(共2題，總分值20分)26.設(shè)二叉樹如下，試對其進(jìn)行先序線索化，畫出相應(yīng)的先序線索二叉樹存儲結(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ā)生時間和最晚發(fā)生時間；(2)求圖中各弧代表的活動的最早開始時間和最晚開始時間；(3)列出各條關(guān)鍵路徑。（14分）29.設(shè)用于通信的電文由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.12、0.31、0.22、0.02、0.03、0.08、0.17、0.05。試為這8個字母設(shè)計哈夫曼編碼，要求畫出設(shè)計過程中所構(gòu)造的哈夫曼二叉樹。（13分）30.設(shè)二叉樹以二叉鏈表存儲，試設(shè)計算法，實現(xiàn)二叉樹的層序遍歷。（13分）

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