西安電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題

1、《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)題一、單項(xiàng)選擇題單項(xiàng)選擇題1.按照數(shù)據(jù)邏輯結(jié)構(gòu)的不同，可以將數(shù)據(jù)結(jié)構(gòu)分成。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中正確的是。A.數(shù)組是同類型值的集合B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為復(fù)雜C.樹(shù)是一種線性的數(shù)據(jù)結(jié)構(gòu)D.用一維數(shù)組存儲(chǔ)二叉樹(shù)，總是以先序順序遍歷各結(jié)點(diǎn)3.在計(jì)算機(jī)的存儲(chǔ)器中表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之

2、為A.邏輯結(jié)構(gòu)B.順序存儲(chǔ)結(jié)構(gòu)C.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.以上都不對(duì)4.以下關(guān)于算法特性的描述中，是正確的。（1）算法至少有一個(gè)輸入和一個(gè)輸出（2）算法至少有一個(gè)輸出但是可以沒(méi)有輸入（3）算法可以永遠(yuǎn)運(yùn)行下去A.（1）B.（2）C.（3）D.（2）和（3）5.對(duì)順序存儲(chǔ)的線性表（a1a2…an）進(jìn)行插入操作的時(shí)間復(fù)雜度是。A.O(n)B.O(ni)C.(n2)D.O(n1)6.鏈表不具有的特點(diǎn)是。A.可隨機(jī)訪問(wèn)任一元素B.插入和刪除時(shí)不需要移動(dòng)

3、元素C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與線性表的長(zhǎng)度成正比7.線性鏈表中各鏈結(jié)點(diǎn)之間的地址。A.必須連續(xù)B.部分地址必須連續(xù)C.不一定連續(xù)D.連續(xù)與否無(wú)關(guān)8.以下關(guān)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的敘述中，是不正確的。A.結(jié)點(diǎn)除自身信息外還包括指針域，因此存儲(chǔ)密度小于順序存儲(chǔ)結(jié)構(gòu)第3頁(yè)共9頁(yè)17.若樹(shù)T有a個(gè)度為1的結(jié)點(diǎn)，b個(gè)度為2的結(jié)點(diǎn)，c個(gè)度為3的結(jié)點(diǎn)，則該樹(shù)有個(gè)葉結(jié)點(diǎn)。A.12b3cB.a2b3cC.2b3cD.1b2c18.若一棵二叉樹(shù)有102

4、片葉子結(jié)點(diǎn)，則度二叉樹(shù)度為2的結(jié)點(diǎn)數(shù)是。A.100B.101C.102D.10319.在有n個(gè)葉子結(jié)點(diǎn)的霍夫曼樹(shù)中，其結(jié)點(diǎn)總數(shù)為：。A.nB.2nC.2n1D.2n120.具有12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)有。A.5個(gè)葉子結(jié)點(diǎn)B.5個(gè)度為2的結(jié)點(diǎn)C.7個(gè)分支結(jié)點(diǎn)D.2個(gè)度為1的結(jié)點(diǎn)21.設(shè)結(jié)點(diǎn)x和y是二叉樹(shù)中的任意兩結(jié)點(diǎn)，若在先根序列中x在y之前，而后根序列中x在y之后，則x和y的關(guān)系是。A.x是y的左兄弟B.x是y的右兄弟C.x是y的祖先D.

5、x是y的后代22.先序遍歷序列與中序遍歷序列相同的二叉樹(shù)為。A.根結(jié)點(diǎn)無(wú)左子樹(shù)的二叉樹(shù)B.根結(jié)點(diǎn)無(wú)右子樹(shù)的二叉樹(shù)C.只有根結(jié)點(diǎn)的二叉樹(shù)或非葉子結(jié)點(diǎn)只有左子樹(shù)的二叉樹(shù)D.只有根結(jié)點(diǎn)的二叉樹(shù)或非葉子結(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)23.若二叉樹(shù)T的前序遍歷序列和中序遍歷序列分別是bdcaef和cdeabf，則其后序遍歷序列為。A.ceadfbB.feacdbC.eacdfbD.以上都不對(duì)24.設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有條邊。A.n1B.n(