天大17春《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(2)》在線作業(yè)二

1、天大17春計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(2)在線作業(yè)二 2017秋17春天大計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(2)在線作業(yè)二 一、單選題（共 40 道試題，共 100 分。） 1. 判斷一個(gè)順序棧ST（最多元素為mo）為空的條件是（ ）。 A. ST->top<>0 B. ST->top=0 C. st->top<>mo D. st->top=mo 正確答案： 1. 2. 如果T2是由有序樹T轉(zhuǎn)換而來(lái)的二叉樹，則T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的( )。 A. 前序 B. 中序 C. 后序 D. 層次序 正確答案： 1. 3. 對(duì)處理事件有嚴(yán)格時(shí)間限制的系統(tǒng)是( )。 A.

2、 分時(shí)系統(tǒng) B. 實(shí)時(shí)系統(tǒng) C. 分布式操作系統(tǒng) D. 網(wǎng)絡(luò)操作系統(tǒng) 正確答案： 1. 4. 在單處理機(jī)系統(tǒng)中，若同時(shí)存在有10個(gè)進(jìn)程，則處于就緒隊(duì)列中的進(jìn)程最多為( )個(gè)。 A. 0 B. 6 C. 9 D. 10 正確答案： 1. 5. 在所有排序方法中，關(guān)鍵碼（即關(guān)鍵字）比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是 （）。 A. 希爾排序 B. 冒泡排序 C. 直接插入排序 D. 直接選擇排序 正確答案： 1. 6. ( )不屬于多道程序設(shè)計(jì)的概念。 A. 多個(gè)用戶同時(shí)使用一臺(tái)計(jì)算機(jī)的打印設(shè)備 B. 多個(gè)用戶同時(shí)進(jìn)入計(jì)算機(jī)系統(tǒng)，并要求同時(shí)處于運(yùn)行狀態(tài) C. 一個(gè)計(jì)算機(jī)系統(tǒng)從宏觀上進(jìn)行作業(yè)的并行

3、處理，但在微觀上仍在串行操作 D. 多個(gè)作業(yè)同時(shí)存放在主存并處于運(yùn)行狀態(tài) 正確答案： 1. 7. 前序遍歷和中序遍歷結(jié)果相同的二叉樹為 ( ) A. 一般二叉樹 B. 只有根結(jié)點(diǎn)的二叉樹 C. 根結(jié)點(diǎn)無(wú)左孩子的二叉樹 D. 所有結(jié)點(diǎn)只有右孩子的二叉樹 正確答案： 1. 8. 設(shè)待排序的記錄為(20,16,13,14,19)，經(jīng)過(guò)下列過(guò)程將這些記錄排序。 20,16,13,14,19 16,20,13,14,19 13,16,20,14,19 13,14,16,20,19 13,14,16,19,20 所用的排序方法是 （）。 A. 直接插入排序 B. 冒泡排序 C. 希爾排序 D. 堆排序 正

4、確答案： 1. 9. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹。下面結(jié)論正確的是( )。 A. 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同 B. 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同 C. 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同 D. 以上均不對(duì) 正確答案： 1. 10. 下面程序段的時(shí)間復(fù)雜度為（ ）。 i=1; while(i<=n) i=i*2; A. O(1) B. O(n) C. O(n2) D. O(log2n) 正確答案： 1.

5、11. 在一個(gè)長(zhǎng)度為n的順序表中，向第i個(gè)元素之前插入一個(gè)新元素，需向后移動(dòng)（ ）個(gè)元素。 A. n-i B. n-i+1 C. n-i-1 D. i 正確答案： 1. 12. 若已知一個(gè)棧的入棧序列是1,2,3,?,n，其輸出序列為P1,P2,P3,?,Pn，若P1=n，則Pi為 （ ）。 A. i B. n-i C. n-i+1 D. 不確定 正確答案： 1. 13. 一棵有124個(gè)葉結(jié)點(diǎn)的完全二叉樹，最多有 ( )個(gè)結(jié)點(diǎn). A. 247 B. 248 C. 249 D. 251 正確答案： 1. 14. 已知一棵權(quán)集W=2,3,4,7,8,9的哈夫曼樹，其加權(quán)路徑長(zhǎng)度WPL為( )。 A

6、. 20 B. 40 C. 80 D. 160 正確答案： 1. 15. 在下列操作系統(tǒng)中，強(qiáng)調(diào)吞吐能力的是( )。 A. 分時(shí)系統(tǒng) B. 多道批處理系統(tǒng) C. 實(shí)時(shí)系統(tǒng) D. 網(wǎng)絡(luò)操作系統(tǒng) 正確答案： 1. 16. 在文件局部有序或文件長(zhǎng)度較小的情況下，最佳內(nèi)部排序的方法是（ ）。 A. 直接插入排序 B. 冒泡排序 C. 簡(jiǎn)單選擇排序 正確答案： 1. 17. 下面關(guān)于臨界區(qū)的說(shuō)法中，錯(cuò)誤的是( ) 。 A. 進(jìn)程中，訪問(wèn)臨界資源的程序是臨界區(qū) B. 同時(shí)進(jìn)行臨界區(qū)的進(jìn)程必須互斥 C. 進(jìn)入臨界區(qū)內(nèi)的兩個(gè)進(jìn)程訪問(wèn)臨界資源時(shí)必須互斥 D. 在同一時(shí)刻，只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū) 正確答案： 1

7、. 18. 以下結(jié)點(diǎn)序列是堆的為（ ）。 A. 100,90,80,60,85,75,20,25,10,70,65,50 B. 100,70,50,20,90,75,60,25,10,85,65,80 C. 100,80,90,60,85,75,20,25,10,70,65,50 D. 100,90,20,60,85,75,80,25,10,70,65,50 正確答案： 1. 19. 哈希表的地址區(qū)間為0-17，哈希函數(shù)為H(k)=k mod 17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列26,25,72,38,8,18,59依次存儲(chǔ)到哈希表中。那么，元素59存放在哈希表中的地址是 ( )。 A

8、. 8 B. 9 C. 10 D. 11 正確答案： 1. 20. 棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（ ） 。 A. 順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu) B. 散列方式和索引方式 C. 鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組 D. 線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu) 正確答案： 1. 21. 下面關(guān)于進(jìn)程同步的說(shuō)法中，錯(cuò)誤的是( )。 A. 為使進(jìn)程共享資源，又使它們互不沖突，因此必須使這些相關(guān)進(jìn)程同步 B. 系統(tǒng)中有些進(jìn)程必須合作，共同完成一項(xiàng)任務(wù)，因此要求各相關(guān)進(jìn)程同步 C. 進(jìn)程互斥的實(shí)質(zhì)也是同步，它是一種特殊的同步 D. 由于各進(jìn)程之間存在著相互依從關(guān)系，必須要求各進(jìn)程同步工作 正確答案： 1. 22. 設(shè)有如下的單鏈表

9、的按序號(hào)查找的算法，其時(shí)間復(fù)雜度為（ ）。 LinkNode *GetNode(Linklist head, int i) int j; ListNode *p; P = head; j=0; while(p->next && j<i) p = p->next; j+; if(i=j)return(p); else return(NULL); A. O(n2) B. O(2n) C. O(n3 ) D. O(logn 正確答案： 1. 23. 設(shè)有一個(gè)已按各元素的值排好序的線性表，長(zhǎng)度大于2，對(duì)給定的值K，分別用順序查找法和二分查找法查找一個(gè)與K相等的元素，比

10、較的次數(shù)分別為s和b。在查找不成功的情況下，正確的s和b的數(shù)量關(guān)系是( ) 。 A. 總有s=b B. 總有s>b C. 總有s<b D. 與k值大小有關(guān) 正確答案： 1. 24. 某二叉樹前序遍歷結(jié)點(diǎn)的訪問(wèn)順序是ABCDEFG，中序遍歷結(jié)點(diǎn)的訪問(wèn)順序是CBDAFGE，則其后序遍歷結(jié)點(diǎn)的訪問(wèn)順序是 ( )。 A. CDBGFEA B. CDGFEAB C. CDBAGFE D. CDBFAGE 正確答案： 1. 25. 工業(yè)過(guò)程控制系統(tǒng)中，運(yùn)行的操作系統(tǒng)最好是( )。 A. 分時(shí)系統(tǒng) B. 實(shí)時(shí)系統(tǒng) C. 分布式操作系統(tǒng) D. 網(wǎng)絡(luò)操作系統(tǒng) 正確答案： 1. 26. 設(shè)有兩個(gè)串p和

11、q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作( )。 A. 連接 B. 模式匹配 C. 求子串 D. 求串長(zhǎng) 正確答案： 1. 27. 如果只想得到1000個(gè)元素組成的序列中第5個(gè)最小元素之前的部分排序的序列，用（ ）方法最快。 A. 冒泡排序 B. 快速排序 C. 希爾排序 D. 堆排序 正確答案： 1. 28. 下面進(jìn)程狀態(tài)的轉(zhuǎn)換，不能實(shí)現(xiàn)的是( )。 A. 運(yùn)行狀態(tài)轉(zhuǎn)到就緒狀態(tài) B. 就緒狀態(tài)轉(zhuǎn)到運(yùn)行狀態(tài) C. 運(yùn)行狀態(tài)轉(zhuǎn)到阻塞狀態(tài) D. 就緒狀態(tài)轉(zhuǎn)到阻塞狀態(tài) 正確答案： 1. 29. ( )不是引入進(jìn)程的直接目的。 A. 多道程序同時(shí)在主存中運(yùn)行 B. 程序需從頭至尾執(zhí)行 C. 主存中各程序

12、之間存在著相互依賴，相互制約的關(guān)系 D. 程序的狀態(tài)不斷地發(fā)生變化 正確答案： 1. 30. 以下哪一個(gè)不是隊(duì)列的基本運(yùn)算（ ） 。 A. 從隊(duì)尾插入一個(gè)新元素 B. 從隊(duì)列中刪除第i個(gè)元素 C. 判斷一個(gè)隊(duì)列是否為空 D. 讀取隊(duì)頭元素的值 正確答案： 1. 31. 分時(shí)操作系統(tǒng)是指( )。 A. 多個(gè)用戶分時(shí)使用同一臺(tái)計(jì)算機(jī)的某一個(gè)終端 B. 多道程序分時(shí)共享計(jì)算機(jī)的軟、硬件資源 C. 多道程序進(jìn)入系統(tǒng)后的批量處理 D. 多用戶的計(jì)算機(jī)系統(tǒng) 正確答案： 1. 32. 對(duì)下圖所示的二叉表，按先根次序遍歷得到的結(jié)點(diǎn)序列為( )。 A. ABCDHEIFG B. ABDHIECFG C. HDI

13、BRAFCG D. HIDBEFGAC 正確答案： 1. 33. 假定有K個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這K個(gè)關(guān)鍵字存入散列表中，至少要 進(jìn)行( )次探測(cè)。 A. K-1次 B. K次 C. K+1次 D. K(K+1)/2次 正確答案： 1. 34. 操作系統(tǒng)中，當(dāng)( )時(shí)，進(jìn)程從執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)。 A. 進(jìn)程被進(jìn)程調(diào)度程序選中 B. 時(shí)間片到 C. 等待某一事件 D. 等待的事件發(fā)生 正確答案： 1. 35. 對(duì)于一個(gè)棧，給出輸入項(xiàng)A,B,C。如果輸入項(xiàng)序列由A,B,C所組成，則不可能產(chǎn)生的輸出序列是（ ）。 A. CAB B. CBA C. ABC D. ACB 正確答案： 1. 36. 常對(duì)數(shù)組進(jìn)行的兩種基本操作是( ) 。 A. 建立和刪除 B. 索引和修改 C. 查找和修改 D. 索引和查找 正確答案： 1. 37. 設(shè)有1000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用( )排序法。 A. 冒泡排序 B. 快速排序 C. 堆排序 D. 希爾排序 正確答案： 1. 38. 稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即( )