2015春北京航空航天大學(xué)算法與數(shù)據(jù)結(jié)構(gòu)在線作業(yè)三及答案

1、2021春北京航空航天大學(xué)算法與數(shù)據(jù)結(jié)構(gòu)?在線作業(yè)三及答案一、單項選擇題共25道試題,共100分.1.在一棵二叉樹中,第4層 上的結(jié)點(diǎn)數(shù)最多為.A. 8B. 15C. 16D. 31選擇：A2. 非空的循環(huán)單鏈表head的尾節(jié)點(diǎn)由p所指向滿足.A. p->next=NULLB. p=NULLC. p->next=headD. p=head選擇：C3. 堆排序在最壞情況下,其時間復(fù)雜性為A. Onlog2nB. On2C. Olog2n2D. Olog2n選擇：A4. 采用分塊查找時,假設(shè)線性表中共有625個元素,查找每個元素的概率 相同,假設(shè)采用順序查找來確定結(jié)點(diǎn)所在的塊時,每塊應(yīng)

2、分個結(jié)點(diǎn) 最正確A. 10B. 25C. 6D. 625選擇：B5. 隊列操作的原那么是().A. 先進(jìn)先出B. 后進(jìn)先出C. 只能進(jìn)行插入D. 只能進(jìn)行刪除選擇：A6. 設(shè)字符串 S1='ABCDEFG', S2='PQRST',貝U運(yùn)算 S=CONCAT (SUB(S1, 2, LENGTH (S2), SUB (S1, LENGTH (S2), 2)后結(jié) 果為().A. BCQR'B. 'BCDEF'C. 'BCDEFG'D. 'BCDEFEF'選擇：D7. 算法的時間復(fù)雜度,都要以通過算法中執(zhí)行頻度

3、最高的語句的執(zhí)行次數(shù)來確定這種觀點(diǎn)A. 完全正確B. 完全錯誤C. 視情況而定D. 以上說法均不正確選擇：B8. 在索引順序表中查找一個元素,可用的且最快的方法是()A. 用順序查找法確定元素所在塊,再用順序查找法在相應(yīng)塊中查找B. 用順序查找法確定元素所在塊,再用二分查找法在相應(yīng)塊中查找C. 用二分查找法確定元素所在塊,再用順序查找法在相應(yīng)塊中查找D. 用二分查找法確定元素所在塊,再用二分查找法在相應(yīng)塊中查找選擇：C9. 對有n個記錄的有序表采用二分查找,其平均查找長度的量級為()A. O(log2n)B. O(nlog2n)C. O(n)D. O(n2)選擇：A10. 以下說法正確的選項是

4、()A. 因鏈棧本身沒有容量限制,故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧 滿情況B. 因順序棧本身沒有容量限制,故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況C. 對于鏈棧而言,在棧滿狀態(tài)下,如果此時再作進(jìn)棧運(yùn)算,那么會發(fā)生“上溢D. 對于順序棧而言在棧滿狀態(tài)下如果此時再作迸棧運(yùn)算,那么會發(fā)生“下溢.選擇：A11. 設(shè)有兩個串S1和S2,求S1在S2中首次出現(xiàn)的位置的運(yùn)算稱 為.A. 連接B. 模式匹配C. 求子串D. 求串長選擇：B12. 設(shè)有向圖有n個頂點(diǎn)和e條邊,采用領(lǐng)接表作為其存儲表示,在 進(jìn)行拓?fù)渑判驎r,總的計算時間為.A. O nlogeB. O n+eC. On*eD. On的平方選擇：B

5、13. 以下列圖的說法中正確的選項是.A. 一個具有n個頂點(diǎn)的無向完全圖的邊數(shù)為 nn-1B. 連通圖的生成樹是該圖的一個極大連通子圖C. 圖的廣度優(yōu)先搜索是一個遞歸過程D. 在非連通圖的遍歷過程中,每調(diào)用一次深度優(yōu)先搜索算法都得到該 圖的一個連通分量選擇：C14. 設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式,以行序為主的 存儲,all為第一個元素,其存儲地址為1,每個元素占1個地址空 間,那么a85的地址為.A. 13B. 18C. 33D. 40-選擇：C15.下述幾種排序方法中,平均查找長度最小的是A. 插入排序B. 選擇排序C. 快速排序D. 歸并排序選擇：C16. 以下說法錯誤的選

6、項是A. 用數(shù)字式計算機(jī)解決問題的實質(zhì)是對數(shù)據(jù)的加工處理B. 程序設(shè)計的實質(zhì)是數(shù)據(jù)處理；數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)的組織形式,根本運(yùn)算規(guī)定了數(shù)據(jù)的根本操作方式C. 運(yùn)算實現(xiàn)是完成運(yùn)算功能的算法,或這些算法的設(shè)計D. 數(shù)據(jù)處理方式總是與數(shù)據(jù)某種相應(yīng)的表示形式相聯(lián)系,反之亦然選擇：B17. 二叉樹上葉結(jié)點(diǎn)數(shù)等于.A. 分支結(jié)點(diǎn)數(shù)加1B. 單分支結(jié)點(diǎn)數(shù)加1C. 雙分支結(jié)點(diǎn)數(shù)加1D. 雙分支結(jié)點(diǎn)數(shù)減1選擇：C18. 順序存儲結(jié)構(gòu)A. 僅適合于靜態(tài)查找表的存儲B. 僅適合于動態(tài)查找表的存儲C. 既適合靜態(tài)又適合動態(tài)查找表的存儲D. 既不適合靜態(tài)又不適合動態(tài)查找表的存儲選擇：C19. 鄰接表是圖的一種.A. 順

7、序存儲結(jié)構(gòu)B. 鏈?zhǔn)酱鎯Y(jié)構(gòu)C. 索引存儲結(jié)構(gòu)D. 列存儲結(jié)構(gòu)選擇：B20. 設(shè)無向圖的頂點(diǎn)個數(shù)為n,那么該圖最多有條邊.A. n-1B. n(n-1)/2C. n(n+1)/2D. 0選擇：B21. 設(shè)有一個無向圖 G= (V, E)和G = (VE')如果G,為G 的生成樹,那么下面不正確的說法是()A. G'為G的子圖B. G'為G的邊通分量C. G'為G的極小連通子圖且 V' =VD. G'為G的一個無環(huán)子圖選擇：B22. 通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性,這意味著A. 數(shù)據(jù)元素具有同一特點(diǎn)B. 不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同,而且對應(yīng)數(shù)據(jù)項的類型要一致C. 每個數(shù)據(jù)元素都一樣D. 數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等選擇：B23. 對于含有n個頂點(diǎn)e條邊的無向連通圖,利用 Prim算法生成最小 代價生成樹其時間復(fù)雜度為().A. O(log2n)B. O(n2)C. O(ne)D. O(elog2e)選擇：B24. 向順序棧中壓入新