數(shù)據(jù)結(jié)構(gòu)期中測試-2014級計算機(jī)網(wǎng)絡(luò)技術(shù)用

1、數(shù)據(jù)結(jié)構(gòu)期中測試 -2014 級計算機(jī)網(wǎng)絡(luò)技術(shù)用1-11每小題 3 分，共 33分1. 下面關(guān)于線性表的敘述中， 錯誤 的是哪一個？（ ）A. 線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B. 線性表采用順序存儲，便于進(jìn)行插入和刪除操作C. 線性表采用鏈?zhǔn)酱鎯Γ槐卣加靡黄B續(xù)的存儲單元D. 線性表采用鏈?zhǔn)酱鎯Γ阌诓迦牒蛣h除操作2. 線性表的以下存儲結(jié)構(gòu)中，已知結(jié)點(diǎn)存儲地址，求其前驅(qū)復(fù)雜度最高的的存儲結(jié)構(gòu)是 （）A. 順序表B.雙向鏈表C.單鏈表D.雙向循環(huán)鏈表3. 設(shè)指針變量 p指向單鏈表中的某結(jié)點(diǎn)， q指向其后繼節(jié)點(diǎn)， s指向一個新開辟的結(jié)點(diǎn)，能將 s 所指結(jié)點(diǎn)插入到 p所指結(jié)點(diǎn)后面的

2、操作為 （ ）A. s=p-next; q=s-next;B. s-next=p-next; p-next=s;C. q-next=s; s-next=p;D. p-next=s-next; s-next=q;4. 設(shè)入棧序列為 ABCD ，則以下序列中不可能是出棧序列的為()A.ABCD B.DCBA C.BDAC D.BACD5.為解決計算機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要 輸出的數(shù)據(jù)依次寫入該緩沖區(qū)， 而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。構(gòu)應(yīng)該是（ ）A. 棧 B.隊(duì)列 C.樹6. 對于最大容量為 n的循環(huán)隊(duì)列 Q ，隊(duì)尾指針是()A.(Q.rear+1

3、) % n=Q.frontC.Q.rear+1=Q.front7. 深度為 K 的完全二叉樹至少具有的頂點(diǎn)個數(shù)為K K-1 KA.2 -1 B.2 C.2 +1該緩沖區(qū)的邏輯結(jié)D.圖Q.rear ，隊(duì)頭是 Q.front ，則隊(duì)空的條件是B. Q.rear=Q.frontD.(Q.rear-1) % n=Q.front)K-1D.2 +18. 將樹轉(zhuǎn)換為對應(yīng)的二叉樹，若在二叉樹中結(jié)點(diǎn)可能具有的關(guān)系是（ ）u是 v的父結(jié)點(diǎn)，則在原來的樹中， u和 vA. 只能是兄弟關(guān)系B.只能是父子關(guān)系C. u 既可能是 v 的兄弟，也可能是 v 的父結(jié)點(diǎn)D. v 既可能是 u 的兄弟，也可能是 u 的父結(jié)點(diǎn)9

4、. 一棵二叉樹具有 10個度為 2的結(jié)點(diǎn)， 5 個度為 1的結(jié)點(diǎn)，則度為 0 的結(jié)點(diǎn)個數(shù)是（ ）A.9 B.11 C.15 D. 不確定10. 有 n（ n 1）個葉子的 Huffman 樹，其結(jié)點(diǎn)總數(shù)為（ ）A. 不確定B.2n C.2n+1 D.2n-111. n 個結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為（）A.2n B.n lC.nlD.n12-18 每小題 2 分，共 14 分12. 順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶?。A. 正確 B. 錯誤13. 單鏈表中引入頭結(jié)點(diǎn)有利于簡化結(jié)點(diǎn)插入以及刪除操作的實(shí)現(xiàn)。A. 正確B. 錯誤14. 雙循環(huán)鏈表中，任一個結(jié)點(diǎn)的前驅(qū)指針都

5、不為空。A. 正確B. 錯誤15. 棧采用順序存儲結(jié)構(gòu)，執(zhí)行入棧操作時會引起大量元素的移動。A. 正確B. 錯誤16. 二叉樹的先序遍歷序列與后序遍歷序列不可能相同。A. 正確B. 錯誤17. 樹的先根序遍歷序列等同于它所對應(yīng)二叉樹的先序遍歷序列。A. 正確B. 錯誤18. 二叉樹可以用二叉鏈表存儲，樹與森林無法用二叉鏈表存儲。A. 正確B. 錯誤以下每小問分值，在題后標(biāo)出19. 已知一棵二叉樹先序序列為 ABDEFCGHI ，中序序列為 DBFEAGHCI（1） 試畫出該二叉樹； 6 分（2） 試畫出該二叉樹對應(yīng)的樹或者森林； 6 分答案：（1）2)對應(yīng)的森林為：20. 已知字符 A-F 的

6、出現(xiàn)頻率依次為 2，3， 5，6，11，9，(1) 給出上述字符最優(yōu)編碼對應(yīng)的 Huffman 樹，并在葉子旁標(biāo)注相應(yīng)字符；(2) 計算上述 Huffman 樹的帶權(quán)路徑長度。 3 分8分A(2) 帶權(quán)路徑長度為： 8721. 二叉樹采用二叉鏈表存儲結(jié)構(gòu)，試寫出一遞歸算法計算二叉樹的深度。(1) 寫出二叉鏈表的類型定義，數(shù)據(jù)域要求為整型 5 分(2) 寫出完成問題的算法 10 分參考答案 :(1)typedef struct BiTNode int data;struct BiTNode *lchild,*rchild; BiTNode, * BiTree;(2) 算法描述 :int Tree

7、Depth(BiTree T)int d,d1,d2;if (T=NULL)d=0;else d1=TreeDepth(T-lchild);d2=TreeDepth(T-rchild);d=d1=d2?d1+1:d2+1;return d;22. 設(shè) L 為一個帶頭節(jié)點(diǎn)的單鏈表 L ，表中各個元素取值均不相同，設(shè)計算法將表中元素值 最小的結(jié)點(diǎn)刪除(1) 寫出單鏈表的類型定義，數(shù)據(jù)域要求為整型 5 分(2) 寫出完成問題的算法 10 分參考答案：(1)typedef struct LNode int data;struct LNode *next; LNode, * LinkList;(2) 算法描述 :void DelMin(LinkList L)LNode *p=L-next, *prep=L;LNode *p_min=L-next; p