北京言語大學(xué)20春《數(shù)據(jù)結(jié)構(gòu)》作業(yè)1-復(fù)習(xí)資料答案

1、科目名稱：20春數(shù)據(jù)結(jié)構(gòu)作業(yè)1 一、單選題 (共 20 道試題,共 100 分) 1.用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié) 點(diǎn)，則在進(jìn)行出隊(duì)操作時(shí)_。 A.隊(duì)頭、隊(duì)尾指針都要修改 B.隊(duì)頭、隊(duì)尾指針都可能要修改 C.僅修改隊(duì)尾指針 D.僅修改隊(duì)頭指針 -本題參考答案：B 2.圖 A.D B.C C.B D.A -本題參考答案：C 3.有一個(gè)長度為 12 的有序表 R0.11,按二分查找法對該表進(jìn)行查找,在表內(nèi)各 元素等概率情況下查找成功所需的平均比較次數(shù)為_。 A.43/12 B.39/12 C.37/12 D.35/12 -本題參考答案：C 4.設(shè)哈夫曼樹中的

2、葉子結(jié)點(diǎn)總數(shù)為 m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼 樹中總共有_個(gè)空指針域。 A.4m B.2m-1 C.2m+1 D.2m -本題參考答案：D 5.若有 18 個(gè)元素的有序表存放在一堆數(shù)組 A19中，第一個(gè)元素放 A1中，現(xiàn)進(jìn) 行二分查找，則查找 A3的比較序列的下標(biāo)依次為_。 A.9,5,3 B.9,5,2,3 C.9,4,2,3 D.1,2,3 -本題參考答案：C 6. A.D B.C C.B D.A -本題參考答案：C 7.在一個(gè)具有 n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù) 雜度是_。 A.O（nlog2n） B.O（n2） C.O（n） D.O（1） 提示

3、：本題為必答題，請認(rèn)真閱讀題目后再作答-本題參考答案：C 8.算法指的是_。 A.計(jì)算機(jī)程序 B.解決問題的計(jì)算方法 C.解決問題的有限運(yùn)算序列 D.排序算法 -本題參考答案：C 9.任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對次序_。 A.發(fā)生改變 B.以上都不對 C.不能確定 D.不發(fā)生改變 -本題參考答案：D 10. A.D B.C C.B D.A -本題參考答案：B 11.對于順序存儲(chǔ)的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為_。 A.O（n）O（n） B.O（n）O（1） C.O（1）O（n） D.O（1）O（1） -本題參考答案：D 12.組成數(shù)據(jù)的基本單位是_

4、。 A.數(shù)據(jù)項(xiàng) B.數(shù)據(jù)類型 C.數(shù)據(jù)變量 D.數(shù)據(jù)元素 -本題參考答案：D 13.設(shè)結(jié)點(diǎn) A 有 3 個(gè)兄弟結(jié)點(diǎn)且結(jié)點(diǎn) B 為結(jié)點(diǎn) A 的雙親結(jié)點(diǎn)，則結(jié)點(diǎn) B 的度數(shù)為_。 A.5 B.4 C.3 D.1 -本題參考答案：B 14.對線性表進(jìn)行折半查找時(shí)，要求線性表必須_。 A.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序 B.以順序方式存儲(chǔ) C.以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序 D.以鏈?zhǔn)椒绞酱鎯?chǔ) -本題參考答案：A 15.圖 A.非順序文件 B.索引順序文件 C.索引非順序文件 D.哈希文件 -本題參考答案：B 16.采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的_。 A.按層遍歷

5、B.后序遍歷 C.先序遍歷 D.中序遍歷 -本題參考答案：C 17.串是一種特殊的線性表，其特殊性體現(xiàn)在_。 A.數(shù)據(jù)元素是一個(gè)字符 B.數(shù)據(jù)元素可以是多個(gè)字符 C.可以順序存儲(chǔ) D.可以鏈?zhǔn)酱鎯?chǔ) -本題參考答案：A 18.由權(quán)值分別為 11,8,6,2,5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度 為_。 A.71 B.53 C.48 D.24 -本題參考答案：A 19.設(shè)二維數(shù)組 A610，每個(gè)數(shù)組元素占用 4 個(gè)存儲(chǔ)單元，若按行優(yōu)先順序存 放數(shù)組元素，a00的存儲(chǔ)地址為 860，則 a35的存儲(chǔ)地址是_。 A.860 B.1200 C.1140 D.1000 -本題參考答案：D 20.有一個(gè)有序表1，4，6，10，18，35，42，5