北大2015年秋季學(xué)期《數(shù)據(jù)結(jié)構(gòu)》課程作業(yè)

1、第１頁共8頁2015年秋季學(xué)期年秋季學(xué)期《數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)》課程作業(yè)課程作業(yè)一.單選題，每空有一個正確選擇，請將正確的選擇填在題號前邊。（每空（每空1分，共分，共3030分）分）1.鼓勵獨(dú)立完成作業(yè)，嚴(yán)懲抄襲！鼓勵獨(dú)立完成作業(yè)，嚴(yán)懲抄襲！數(shù)據(jù)的邏輯結(jié)構(gòu)被形式地定義為B=(KR)其中K是____C__的有限集合，R是K上的___H___的有限集合。（第一章）a存儲b數(shù)據(jù)操作c數(shù)據(jù)元素d操作e邏輯結(jié)構(gòu)f映象g算法h關(guān)系2.以下關(guān)于算法的說法

2、不正確的是____B_________。（第一章）a一個算法應(yīng)包含有限個步驟b算法越簡單越好c算法中的所有操作都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之d算法中的每個步驟都能在有限時間內(nèi)完成3設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，，，，，，，，則數(shù)據(jù)結(jié)構(gòu)A是______B________。（第一章）a線性結(jié)構(gòu)b樹型結(jié)構(gòu)c物理結(jié)構(gòu)d圖型結(jié)構(gòu)4.下面程序段的時

3、間復(fù)雜度為___C___（第一章）intsum=0f(i=0imi)f(j=ijnj)sa.O(mn)b.O(nn)c.O(mn)d.O(mlogn)5.下列有關(guān)線性表的敘述中，正確的是____A____。（第二章）a一個線性表是n個數(shù)據(jù)元素的有限序列b線性表中任何一個元素有且僅有一個直接前驅(qū)c線性表中任何一個元素有且僅有一個直接后繼d以上說法都不正確6.在含有n個結(jié)點(diǎn)的順序存儲的線性表中，在任一位置插入一個結(jié)點(diǎn)所需移動結(jié)點(diǎn)第３頁共8頁

4、a.只允許在端點(diǎn)處插入和刪除元素b.都是先進(jìn)后出c.都是先進(jìn)先出d.沒有共同點(diǎn)15.中綴表達(dá)式(AB)DE(FAD)C的后綴形式是__D____（第四章）aABDEFADCbABDEFADCcABDEFADCdABDEFADC16.如下圖所示的4棵二叉樹，____C_____不是完全二叉樹。（第五章）17.設(shè)某棵二叉樹中有2000個結(jié)點(diǎn)，則該二叉樹的最小高度為_____C_______。（第五章）a9b10c1111d1218.深度為6

5、(根的層次為1)的二叉樹至多有____B___結(jié)點(diǎn)（第五章）a.64b.63c.31d.3219.二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為________D____。（第五章）a.2k1b.2K1c.2K1d.2k120.如果一棵二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是____B___。（第五章）a空或只有一個結(jié)點(diǎn)b高度等于其結(jié)點(diǎn)數(shù)c任一結(jié)點(diǎn)無右孩子d任一結(jié)點(diǎn)無左孩子任一結(jié)點(diǎn)無左孩子21.樹的基本遍歷策略分為先根遍歷和后根

6、遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。結(jié)論_______A__是正確的。（第五章）a.a.樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同b.樹的后根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同c.樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同d.以上都不對22.根據(jù)使用頻率為5個字符設(shè)計的哈夫曼編碼不可能是______B______。（第六章）a111，11