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

1、數(shù)據(jù)結(jié)構(gòu)期中測(cè)試 -2014 級(jí)計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)用1-11每小題 3 分，共 33分1. 下面關(guān)于線性表的敘述中， 錯(cuò)誤 的是哪一個(gè)？（ ）A. 線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B. 線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作C. 線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D. 線性表采用鏈?zhǔn)酱鎯?chǔ)，便于插入和刪除操作2. 線性表的以下存儲(chǔ)結(jié)構(gòu)中，已知結(jié)點(diǎn)存儲(chǔ)地址，求其前驅(qū)復(fù)雜度最高的的存儲(chǔ)結(jié)構(gòu)是 （）A. 順序表B.雙向鏈表C.單鏈表D.雙向循環(huán)鏈表3. 設(shè)指針變量 p指向單鏈表中的某結(jié)點(diǎn)， q指向其后繼節(jié)點(diǎn)， s指向一個(gè)新開(kāi)辟的結(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ī)與打印機(jī)之間速度不匹配的問(wèn)題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要 輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)， 而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。構(gòu)應(yīng)該是（ ）A. 棧 B.隊(duì)列 C.樹(shù)6. 對(duì)于最大容量為 n的循環(huán)隊(duì)列 Q ，隊(duì)尾指針是()A.(Q.rear+1

3、) % n=Q.frontC.Q.rear+1=Q.front7. 深度為 K 的完全二叉樹(shù)至少具有的頂點(diǎn)個(gè)數(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. 將樹(shù)轉(zhuǎn)換為對(duì)應(yīng)的二叉樹(shù)，若在二叉樹(shù)中結(jié)點(diǎn)可能具有的關(guān)系是（ ）u是 v的父結(jié)點(diǎn)，則在原來(lái)的樹(shù)中， u和 vA. 只能是兄弟關(guān)系B.只能是父子關(guān)系C. u 既可能是 v 的兄弟，也可能是 v 的父結(jié)點(diǎn)D. v 既可能是 u 的兄弟，也可能是 u 的父結(jié)點(diǎn)9

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

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

6、出現(xiàn)頻率依次為 2，3， 5，6，11，9，(1) 給出上述字符最優(yōu)編碼對(duì)應(yīng)的 Huffman 樹(shù)，并在葉子旁標(biāo)注相應(yīng)字符；(2) 計(jì)算上述 Huffman 樹(shù)的帶權(quán)路徑長(zhǎng)度。 3 分8分A(2) 帶權(quán)路徑長(zhǎng)度為： 8721. 二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，試寫(xiě)出一遞歸算法計(jì)算二叉樹(shù)的深度。(1) 寫(xiě)出二叉鏈表的類型定義，數(shù)據(jù)域要求為整型 5 分(2) 寫(xiě)出完成問(wèn)題的算法 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 為一個(gè)帶頭節(jié)點(diǎn)的單鏈表 L ，表中各個(gè)元素取值均不相同，設(shè)計(jì)算法將表中元素值 最小的結(jié)點(diǎn)刪除(1) 寫(xiě)出單鏈表的類型定義，數(shù)據(jù)域要求為整型 5 分(2) 寫(xiě)出完成問(wèn)題的算法 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