計(jì)算機(jī)軟件技術(shù)基礎(chǔ)復(fù)習(xí)題和答案

1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ)試題2. 線性表是具有n個(gè)_C的有限序列。A. 表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)E.信息項(xiàng)1.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比優(yōu)點(diǎn)是CDA. 所有的操作算法實(shí)現(xiàn)簡單B.便于隨機(jī)存取C.便于插入和刪除D.便于利用零散的存儲(chǔ)器空間3. 若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)， 在其第I個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為 C。( K I n+1)A. 0(0)B. 0(1)2C. 0(n)D. 0(n )4. 設(shè)A是一個(gè)線性表(ai,a2,a n)，采用順序存儲(chǔ)結(jié)構(gòu)，則在等概率的前提下，平均每插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為_B，平均每刪除一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為;

2、若元素插在a與ai+i之間(0 I n ext=p+1; p-n ext=s;B. (*p). next=s; (*s). next=(*p). next;C. s-n ext=p-n ext; p-n ext=s-n ext;D. s-n ext=p-n ext; p-n ext=s;13. 用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的A位置。A. 鏈頭B.鏈尾C.鏈中14. 若用單鏈表表示隊(duì)列，則應(yīng)該選用_B。A. 帶尾指針的非循環(huán)鏈表B.帶尾指針的循環(huán)鏈表C.帶頭指針的非循環(huán)鏈表D.帶頭指針的循環(huán)鏈表15. 在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主 機(jī)將要輸出

3、的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印，先放入打印緩沖區(qū)的數(shù)據(jù)先被打印。該緩沖區(qū)應(yīng)該是一個(gè)B結(jié)構(gòu)。A. 堆棧B.隊(duì)列C.數(shù)組D.線性表16. 若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)兀素,再加入兩個(gè)兀素后，rear 禾口 front的值分別為BA. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 117.設(shè)棧的輸入序列為1,2 ,10 ,輸出序列為a1,a 2,a 10,若a5=10,則a?為 A. 4B. 8C.不確定D.718.設(shè)棧的輸入序列是1,2,3,4，貝UD不可能是其出棧序列。A.1243B.

4、 2134C.1432D. 431219.以下D是C語言中abed3 21ABCD 的子串。A.abedB. 321ABC.“ abeABCD. “ 21AB20.右串 S- software”，其子串的數(shù)目是C。A. 8B. 37C. 36D. 9C21將一個(gè) A1:100,1:100的三對(duì)角矩陣，按行優(yōu)先存入一維數(shù)組A66,65（即該元素的下標(biāo)）在B數(shù)組中位置k為BA. 198B.195C.197B1:298中，A中元素22.設(shè)咼為h的二叉樹只有度為0和2的結(jié)點(diǎn)，則此類二叉樹的結(jié)點(diǎn)數(shù)至少為B至多為F。高為h的完芫全二叉樹的結(jié)點(diǎn)數(shù)至少為E，至多為FA. 2hB. 2h-1C.2h+1D.h+

5、1h-1hG.h+1hE. 2F. 2 -12 -1H. 2 +123. 一棵有124個(gè)葉結(jié)點(diǎn)的完全二一叉樹，最多有B個(gè)結(jié)點(diǎn)。A. 247B. 248C.249D. 251OD. 19624.若從二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉 樹是 C。A. 滿二叉樹B.哈夫曼樹C.堆D.二叉查找樹25.前序遍歷和中序遍歷結(jié)果相同的二叉樹為F:前序遍歷和后序遍歷結(jié)果相同的二叉樹為B。A. 一般二叉樹B.只有根結(jié)點(diǎn)的二叉樹C.根結(jié)點(diǎn)無左孩子的二叉樹D.根結(jié)點(diǎn)無右孩子的二叉樹E.所有結(jié)點(diǎn)只有左孩子的二叉樹F.所有結(jié)點(diǎn)只有右孩子的二叉樹27. 若在線性表中采用折半查找法查找

6、元素，該線性表應(yīng)該C。A. 元素按值有序B.采用順序存儲(chǔ)結(jié)構(gòu)C.元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)D.元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)28. 在分塊檢索中，對(duì) 256個(gè)元素的線性表分成16塊最好，每塊的最佳長度是16;若每塊的長度為 8，其平均檢索長度為21。29.假定有K個(gè)關(guān)鍵字互為同義詞，若用線性探測法把這K個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行_D次探測。A. K-1 次B. K 次C. K+1 次D. K(K+1)/2次30.在n個(gè)記錄的有序順序表中進(jìn)行折半查找，最大的比較次數(shù)是log 2 n 1。31. Hash技術(shù)廣泛應(yīng)用于查找過程，選擇Hash函數(shù)的標(biāo)準(zhǔn)是處理沖突的技術(shù)有優(yōu)有劣，其共同標(biāo)

7、準(zhǔn)是 32. 在下述排序算法中，所需輔助存儲(chǔ)空間最多的是的是 C，平均速度最快的是AA.快速排序B.歸并排序C.33. 在文件局部有序或文件長度較小的情況下，最佳部排序的方法是A.直接插入排序B.冒泡排序C.34. 快速排序在最壞情況下時(shí)間復(fù)雜度是0(n2)，比AA.堆排序B.冒泡排序35. 若需在O(nlogn)的時(shí)間完成對(duì)數(shù)組的排序，是 C，所需輔助存儲(chǔ)空間最小堆排序A簡單選擇排序 一的性能差。C.簡單選擇排序且要求排序是穩(wěn)定的，則可選擇的排序方法A.快速排序B.C.歸并排序D.36. 如果只想得到1000個(gè)元素組成的序列中第B方法最快。A.冒泡排序C.希爾排序37. 以下結(jié)點(diǎn)序列是堆的為

8、 _A。A. 100,90,80,60,85,75,20,25,10,70,65,50B. 100,70,50,20,90,75,60,25,10,85,65,8038. 若要盡可能快地完成對(duì)實(shí)數(shù)數(shù)組的排序，且要求排序是穩(wěn)定的，則應(yīng)選A.快速排序B.堆排序C. 歸并排序D.希爾排序39. 從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為A排序法。A.插入排序B.交換排序C.選擇排序D.歸并排序40. 直接插入排序在最好情況下的時(shí)間復(fù)雜度為BA. O(log n)B. O(n)2C. O(nlogn)D. O(n )41. 表是一種

9、數(shù)據(jù)結(jié)構(gòu)，鏈表是一種(1)。隊(duì)列和棧都是線性表，棧的操作特性是 (2)，隊(duì)列的操作特性是(3)。今有一空棧 S,對(duì)下列待進(jìn)棧的數(shù)據(jù)元素序列a,b,c,d,e,f依次進(jìn)棧、進(jìn)棧、出棧、進(jìn)棧、進(jìn)棧、出棧的操作，則此操作完成后，棧S的棧頂元素為 (4)，棧底元素為 _(5)供選答案：(1):A.非順序存儲(chǔ)線性表C.順序存儲(chǔ)線性表堆排序希爾排序5個(gè)最小元素之前的部分排序的序列，用B.D.快速排序堆排序E.簡單選擇排序B.非順序存儲(chǔ)非線性表D.順序存儲(chǔ)非線性表(2):A.隨機(jī)進(jìn)出B.先進(jìn)后出C.先進(jìn)先出D.出優(yōu)于進(jìn)：A.隨機(jī)進(jìn)出B.先進(jìn)后出C.后進(jìn)后出D.進(jìn)優(yōu)于出：A. fB.cC. aD.b：A. b

10、B.cC. aD.d答案：ABCBC42.操作系統(tǒng)主要是對(duì)計(jì)算機(jī)系統(tǒng)全部進(jìn)行管理，以方便用戶、提高計(jì)算機(jī)使用效率的一種系統(tǒng)軟件。它的主要功能有：處理機(jī)管理、存儲(chǔ)管理、文件管理、 管 理和設(shè)備管理等。Windows和Unix是最常用的兩類操作系統(tǒng)。前者是一個(gè)具有圖形界面的窗口式的 (3)系統(tǒng)軟件，后者是一個(gè)基本上采用(4)語言編制而成的的系統(tǒng)軟件。在 (5)操作系統(tǒng)控制下，計(jì)算機(jī)能及時(shí)處理由過程控制反饋的信息并作出響應(yīng)。供選答案：(1):A.應(yīng)用軟件B.系統(tǒng)軟硬件C.資源D.設(shè)備(2):A.數(shù)據(jù)B.作業(yè)C.中斷D.I/O(3):A.分時(shí)B.多任務(wù)C.多用戶D.實(shí)時(shí)(4):A.PASCALB.宏C

11、.匯編D.C(5):A.網(wǎng)絡(luò)B.分時(shí)C.批處理D.實(shí)時(shí)答案：CBBDD44.計(jì)算機(jī)數(shù)據(jù)處理的對(duì)象是具有不同結(jié)構(gòu)的各種數(shù)據(jù)，可以訪問的最小數(shù)據(jù)信息單位是 ，可以引用的最小命名數(shù)據(jù)單位是(2)。線性表是最簡單的一種數(shù)據(jù)結(jié)構(gòu)，有順序和兩種存儲(chǔ)方式。線性表按方式存儲(chǔ)時(shí)，每個(gè)結(jié)點(diǎn)的包括(3)兩部分。線性表的查找有(4)和 (5)兩種，但 (5)只能用于順序存儲(chǔ)的情況。供選答案：(1):A.C.數(shù)字?jǐn)?shù)據(jù)元素B.D.字符數(shù)據(jù)項(xiàng)：A.結(jié)點(diǎn)B.記錄C.數(shù)據(jù)兀素D.數(shù)據(jù)項(xiàng)：A.數(shù)據(jù)值與符號(hào)B.數(shù)據(jù)與指針C.數(shù)據(jù)與表名D.頭地址與尾地址：A.隨機(jī)查找B.順序查找C.二分法查找D.瀏覽：A.隨機(jī)查找B.順序查找C.二

12、分法查找D.瀏覽答案：CDBBCC.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.部結(jié)構(gòu)和外部結(jié)構(gòu)46. 從未排序的序列中， 依次取出元素，與已排序序列的元素比較后，放入已排序序列中的恰當(dāng)位置上，這是 排序。從未排序的序列中，挑選出元素，放在已排序序列的某一端位置，這是 (2)排序。逐次將待排序的序列中的相鄰元素兩兩比較，是逆序則進(jìn)行交換，這是(3)排序。如果整個(gè)排序過程都在存中進(jìn)行，稱為(4)排序。排序算法的復(fù)雜性與排序算法的(5)有關(guān)。供選答案:(1):A.C.選擇 比較B.D.插入歸并：A.選擇B.插入C.比較D.歸并：A.冒泡B.交換C.比較D.散列：A.外部B.部C.外存D.存：A.運(yùn)算量大小與占用存儲(chǔ)多

13、少B.運(yùn)算量大小與處理的數(shù)據(jù)量大小C.并行處理能力和占用存儲(chǔ)多少D.占用存儲(chǔ)多少和處理的數(shù)據(jù)量大小答案：BAABA47. 操作系統(tǒng)是對(duì)計(jì)算機(jī)資源進(jìn)行的系統(tǒng)軟件，是(2)的接口。在處理機(jī)管理中，進(jìn)程是一個(gè)重要的概念，它由程序塊、(3)和數(shù)據(jù)塊三部分組成，它有3種基本狀態(tài)，不可能發(fā)生的狀態(tài)轉(zhuǎn)換是(4)。虛擬存儲(chǔ)器的作用是允許程序直接訪問比存更大的地址空間，它通常使用 作為它的一個(gè)主要組成部分。 供選答案：(1)：A.輸入和輸出C.管理和控制B.鍵盤操作D.匯編和執(zhí)行(2)：A.軟件和硬件B.主機(jī)和外設(shè)C.咼級(jí)語言和機(jī)器語言D.用戶和計(jì)算機(jī)(3)：A.進(jìn)程控制塊B.作業(yè)控制塊C.文件控制塊D.設(shè)備控

14、制塊(4)：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)換為運(yùn)行態(tài)(5)：A.軟盤B.硬盤C. CDROMD.寄存器答案：CDADB48. _A是信息的載體，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。A. 數(shù)據(jù)B.數(shù)據(jù)元素C.結(jié)點(diǎn)D.數(shù)據(jù)項(xiàng)A以及它們之52. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中，計(jì)算機(jī)的 間的關(guān)系和運(yùn)算等的學(xué)科。A. 操作對(duì)象B.計(jì)算方法C.邏輯存儲(chǔ)D.數(shù)據(jù)映象53. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成C。A. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)54. 算法分析的目的是A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性B. 研究算法中輸入和輸出的關(guān)系

15、C. 分析算法的效率以求改進(jìn)D. 分析算法的易懂性和文檔性55. 算法分析的兩個(gè)主要方面是（4）A. 間復(fù)雜性和時(shí)間復(fù)雜性C.可讀性和文檔性B. 正確性和簡明性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性56. 一個(gè)線性順序表第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為 2，則第5個(gè)元素的地址為 B。A. 110B. 108C.100D.12057. 若已知一個(gè)棧的入棧序列是1,2,3,n，其輸出序列為R,P2,P3,Pn,若R=n，則P為 C。A. iB. n-iC. n-i+1D.不確定58. 對(duì)于一個(gè)棧，給出輸入項(xiàng)A,B,C。如果輸入項(xiàng)序列由A,B,C所組成，則不可能產(chǎn)生的輸出序列是_A。A. CABB

16、. CBAC. ABCD. ACB61. 以下哪一個(gè)不是隊(duì)列的基本運(yùn)算C。A.從隊(duì)尾插入一個(gè)新元素B.從隊(duì)列中刪除第i個(gè)元素C. 判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值62. 在一個(gè)長度為n的順序表中，向第i個(gè)元素之前插入一個(gè)新元素，需向后移動(dòng) B 個(gè)A. n-iB. n-i+1C. n-i-1D. i63. 從一個(gè)長度為n的順序表中刪除第i個(gè)元素時(shí)，需向前移動(dòng) _A個(gè)元素。A. n-iB. n-i+1C. n-i-1D. i64. 在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中， 假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件是 _B。A. fron t=rear+1B. fro

17、n t=rearC. fron t+1=rearD. fron t=065. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較 D個(gè)結(jié)點(diǎn)。A. nB. n/2C. (n -1)/2D. (n+1)/266. 一個(gè)棧的入棧序列是 a,b,c,d,e ，則棧不可能的輸出序列是C。A. edcbaB. decbaC. dceabD. abcde67. 棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是A.順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)C.鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組68. 判斷一個(gè)順序棧ST （最多元素為mA. ST-top0B. ST-top=0A。B. 散列方式和索引方式D. 線性存儲(chǔ)結(jié)構(gòu)和非線

18、性存儲(chǔ)結(jié)構(gòu) 為空的條件是 B。C. st-topmoD. st-top=mo69. 不帶頭結(jié)點(diǎn)的單鏈表 head為空表的判定條件是AA. head=NILLB. head-next=NULL C. head-next=head D. head != NULL70. 在一個(gè)單鏈表中，已知 q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在p和q之間插入s結(jié)點(diǎn)，則應(yīng)執(zhí)行_C。A. s-n ext = p-n ext; p-n ext=s;B. p-next = s-n ext; s-n ext=p;C. q-n ext = s; s-n ext=p;D. p-n ext = s; s-n ext=q;72.

19、串是一種特殊的線性表，其特殊性體現(xiàn)在B。A. 可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C. 可以存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符73. 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作BA. 連接B.模式匹配 C.求子串D.求串長74. 設(shè)串 s1 = ” ABCDEFG , s2=” PQRST，函數(shù) con(x,y)返回 x 和 y 串的連接串，subs(s,l,j)返回串s的從序號(hào)i的字符開始的con (sub(s1,2,le n( s2),sub(s1,le n(s2),2)個(gè)字符組成的子串，len(s)返回串s的長度，則 的結(jié)果是 D。D. BCDEFEFA. BCDEFB. BCDEF

20、GC. BCPQRST75. 常對(duì)數(shù)組進(jìn)行的兩種基本操作是C。A.建立和刪除B.索引和修改C.查找和修改76.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即CA.二維數(shù)組和三維數(shù)組B.三元組和散列C.二兀組和十字鏈表D.散列和十字鏈表D.索引和查找77.對(duì)下圖所示的二叉表，按先根次序遍歷得到的結(jié)點(diǎn)序列為_BA. ABCDHEIFGB. ABDHIECFGC. HDIBRAFCGD. HIDBEFGAC78. 在一棵二叉樹上，度為 0的結(jié)點(diǎn)個(gè)數(shù)為no,度為2的結(jié)點(diǎn)數(shù)為n2,貝U n0= A。A. n 2+1B. n 2-1C. n 2D. n 2/279. 某二叉樹前序遍歷結(jié)點(diǎn)的訪問順序是ABCDEFG中

21、序遍歷結(jié)點(diǎn)的訪問順序是CBDAFG,則其后序遍歷結(jié)點(diǎn)的訪問順序是A。A. CDBGFEAB. CDGFEABC. CDBAGFED. CDBFAGE80.在下列存儲(chǔ)形式中,D不是樹的存儲(chǔ)形式。A.雙親表示法B. 孩子鏈表表示法C.孩子兄弟表示法D. 順序存儲(chǔ)表示法81.已知一棵二叉樹的中序序列為cbedahgijf ，后序序列為 cedbhjigfa ，則該二叉樹為82.已知一棵權(quán)集 W=2,3,4,7,8,9的哈夫曼樹，其加權(quán)路徑長度WPL為A. 20B. 40C. 80D. 16087.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,則其前序遍歷序列為83. 已知一棵度為

22、 m的樹中有m個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，nm個(gè)度為m的結(jié)點(diǎn)，問這棵樹中葉子結(jié)點(diǎn)為 C 。A. 1+n i(I-1)B. 1+n i (1+1) C. n 1+n2+nmD. m nm84. 如下圖所示的4棵二叉樹中，C不是完全二叉樹。85. 設(shè)高度為h的二叉樹上只有度為 0或度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為 B。D. h+1D. defbagcA. 2hB. 2h-1C. 2h+186. 如下圖所示的二叉樹的中序遍歷序列是 CA. abcdgefB. dfebagcC. dbaefcgo樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同 樹的先根遍歷序列與其對(duì)應(yīng)的二叉

23、樹的后序遍歷序列相同 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同 以上均不對(duì)A.只有右子樹的所有結(jié)點(diǎn)C.只有左子樹的部分結(jié)點(diǎn)92. 樹最適合用來表示_A.有序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)B.D.B.D.只有右子樹的部分只有左子樹的所有結(jié)點(diǎn)無序數(shù)據(jù)元素元素之間無聯(lián)系的數(shù)據(jù)A. acbedB.decabC.deabcD.cedba88. 如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，則T中結(jié)點(diǎn)的前序就是 T2中結(jié)點(diǎn)的A 。A. 前序B.中序C.后序D.層次序89. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得

24、到的二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹。下面結(jié)論正確的是 AA.B.C.D.90. 深度為5的二叉樹至多有C個(gè)結(jié)點(diǎn)。D. 10A. 16B. 32C. 3191. 在一非空二叉樹的中序遍序序列中，根結(jié)點(diǎn)的右邊93. 設(shè)n, m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是CA. n在m的右方B. n是m的祖先C. n在m的左方D. n 是m的子94. 對(duì)一個(gè)滿二叉樹，m個(gè)樹葉,n個(gè)結(jié)點(diǎn)，深度為h，則 DA. n=h+mB. h+m=2 nC. m=h-1D. n=2 h-195. 如果某二叉樹的前序?yàn)閟tuwv，中序?yàn)閡wtvs，則該二叉樹后序?yàn)锳. uwvtsB. vwutsC. wuv

25、tsD. wutsv96. 設(shè)待排序的記錄為(20,16,13,14,19)，經(jīng)過下列過程將這些記錄排序。20.16.13.14.1916.20.13.14.1913.16.20.14.1913.14.16.20.1913.14.16.19.20所用的排序方法是 A。A.直接插入排序B.冒泡排序C.希爾排序D.堆排序97. 對(duì)下列4個(gè)序列用快速排序的方法進(jìn)行排序，以序列的第一個(gè)元素為基礎(chǔ)進(jìn)行劃分，在第一趟劃分過程中，元素移動(dòng)次數(shù)最多的是A序列。A. 70,75,82,90,23,16,10,68B. 70,75,68,23,10,16,90,82C. 82,75,70,16,10,90,68,

26、23D. 23,10,16,70,82,75,68,9098. 用快速排序的方法對(duì)包含幾個(gè)關(guān)鍵字的序列進(jìn)行排序，最壞情況下，執(zhí)行的時(shí)間為2A. 0(n)B. O(log 2n)C.0(nlog 2n)D. O(n )99. 在所有排序方法中，關(guān)鍵碼(即關(guān)鍵字)比較的次數(shù)與記錄的初始排列次序無關(guān)的是DA.希爾排序B.冒泡排序C.直接插入排序D.直接選擇排序100.在歸并排序過程中，需歸并的趟數(shù)為C。A. nB. , nC. n log 2 nD. log 2 n101. 一組記錄的排序代碼為46,79,56,38,40,84，則利用堆排序的方法建立的初始堆為B。A. 79,46,56,38,40

27、,80B. 84,79,56,38,40,46C. 84,79,56,46,40,38D. 84,56,79,40,46,38102. 一組記錄的排序代碼為46,79,56,38,40,84，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為C 。A. 38,40,46,56,79,84B. 40,38,46,79,56,84C. 40,38,46,56,79,84D. 40,38,46,84,56,79103. 每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中元素的排序碼均小于等于基準(zhǔn)元素的排序碼，右區(qū)間中元素的排序碼均大于等于基準(zhǔn)元素的排序碼，此種排序方法叫做 _B。A.堆

28、排序B.快速排序C.冒泡排序D.希爾排序104. 一組記錄的排序碼為一個(gè)字母序列Q,D,F,X,A,P,N,B,Y,M,C,W，按歸并排序方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為_D。A. D,F,Q,X,A,B,N,P,C,M,W,YB. D,F,Q,A,P,X,B,N,Y,C,M,WC. D,Q,F,X,A,P,N,B,Y,M,C,WD. D,Q,F,X,A,P,B,N,M,Y,C,W105. 一組記錄的排序碼為25,48,16,35,79,82,23,40,36,72 ，其中，含有5個(gè)長度為2的有序表，按歸并排序方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為A。A. 16,25,35,48,23,40,7

29、9,82,36,72B. 16.25,35,48,79,82,23,36,40,72C. 16,25,48,35,79,82,23,36,40,72D. 16,25,35,48,79,23,36,40,72,82106. 設(shè)有1000個(gè)無序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用C排序法。A.冒泡排序B.快速排序C.堆排序D.希爾排序107. 在待排序的兀素序列基本有序的前提下，效率最高的排序方法是A。A.插入排序B.選擇排序C.快速排序D.歸并排序108. 用某種排序方法對(duì)線性表25,84,21,47,15,27,68,35,20進(jìn)行排序時(shí)，元素序列的變化情況如下：(1

30、) 25,84,21,47,15,27,68,35,20 20,15,21,25,47,27,68,35,84(3) 15,20,21,25,35,27,47,68,84(4) 15,20,21,25,27,35,47,68,84則所采用的排序方法是D。A.選擇排序B.希爾排序C.歸并排序D.快速排序109. 快速排序方法在C情況下最不利于發(fā)揮其長處。A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)中含有多個(gè)相同值C.要排序的數(shù)據(jù)已基本有序D.要排序的數(shù)據(jù)個(gè)數(shù)為整數(shù)110. 設(shè)有一個(gè)已按各元素的值排好序的線性表，長度大于2,對(duì)給定的值K,分別用順序查找法和二分查找法查找一個(gè)與 K相等的元素，比較的次數(shù)分

31、別為 s和b。在查找不成功的情 況下，正確的s和b的數(shù)量關(guān)系是 _B。A.總有s=bB.總有sbC.總有sbD.與k值大小有關(guān)111. 如果要求一個(gè)線性表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，則可采用的方法是A。A.分塊法B.順序法C.二分法D.哈希法112. 哈希表的地址區(qū)間為 0-17，哈希函數(shù)為 H(k)=k mod 17。采用線性探測法處理沖突，并將關(guān)鍵字序列26,25,72,38,8,18,59依次存儲(chǔ)到哈希表中。那么，元素59存放在哈希表中的地址是 D。A. 8B. 9C. 10D. 11113. 哈希表的地址區(qū)間為 0-17，哈希函數(shù)為 H(k)=k mod 17。采用線性探測

32、法處理沖突，并將關(guān)鍵字序列26,25,72,38,8,18,59依次存儲(chǔ)到哈希表中。如果要訪問元素59,則需要的搜索次數(shù)是C 。A. 2B. 3D. 5C. 4114. 在計(jì)算機(jī)系統(tǒng)中，允許多個(gè)程序同時(shí)進(jìn)入存并運(yùn)行，這種方法稱為DA. Spodli ng 技術(shù)B.C.緩沖技術(shù)D.115. 分時(shí)系統(tǒng)追求的目標(biāo)是 _C。A.高吞吐率B.C.快速響應(yīng)D.116. 引入多道程序的目的是D。A.提高實(shí)時(shí)響應(yīng)速度B.C.為了充分利用主存儲(chǔ)器D.117. 若把操作系統(tǒng)看作計(jì)算機(jī)系統(tǒng)資源的管理者,虛擬存儲(chǔ)技術(shù)多道程序設(shè)計(jì)技術(shù)充分利用存減少系統(tǒng)開銷增強(qiáng)系統(tǒng)交互能力充分利用CPU減少CPU等待時(shí)間下列 D不屬于操

33、作系統(tǒng)所管理的資源。B.存A.程序C. CPUD. 中斷118. _A不屬于多道程序設(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è)的并行處理，但在微觀上仍在串行操作D. 多個(gè)作業(yè)同時(shí)存放在主存并處于運(yùn)行狀態(tài)119. 操作系統(tǒng)的CPU管理主要是解決C。A.單道程序?qū)?CPU的占用B.多道程序?qū)PU的占用C.多道程序?qū)PU的分配D.多道程序或單道程序?qū)?CPU的爭奪120. 分時(shí)操作系統(tǒng)是指_B。A. 多個(gè)用戶分時(shí)使用同一臺(tái)計(jì)算機(jī)的某一個(gè)終端B. 多道程序分時(shí)共享計(jì)算機(jī)的軟、硬件資源C. 多道程

34、序進(jìn)入系統(tǒng)后的批量處理D. 多用戶的計(jì)算機(jī)系統(tǒng)121. _A不是實(shí)時(shí)系統(tǒng)的特征。A.很強(qiáng)的交互性B.具有對(duì)用戶信息的及時(shí)響應(yīng)性C.具有很強(qiáng)的可靠性D.有一定的交互性122.工業(yè)過程控制系統(tǒng)中，運(yùn)行的操作系統(tǒng)最好是B。A.分時(shí)系統(tǒng)B.實(shí)時(shí)系統(tǒng)C.分布式操作系統(tǒng)D.網(wǎng)絡(luò)操作系統(tǒng)123.對(duì)處理事件有嚴(yán)格時(shí)間限制的系統(tǒng)是B。A.分時(shí)系統(tǒng)B.實(shí)時(shí)系統(tǒng)C.分布式操作系統(tǒng)D.網(wǎng)絡(luò)操作系統(tǒng)124.在下列操作系統(tǒng)中，強(qiáng)調(diào)吞吐能力的是B。A.分時(shí)系統(tǒng)B.多道批處理系統(tǒng)C.實(shí)時(shí)系統(tǒng)D.網(wǎng)絡(luò)操作系統(tǒng)125.操作系統(tǒng)中，當(dāng)B時(shí)，進(jìn)程從執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)。A.進(jìn)程被進(jìn)程調(diào)度程序選中B.時(shí)間片到C.等待某一事件D.等待

35、的事件發(fā)生.進(jìn)程和程序的根本區(qū)別在于D。A.是否具有就緒、運(yùn)行和等待狀態(tài)B.是否被調(diào)入存中C.是否占有處理機(jī)D.靜態(tài)與動(dòng)態(tài)特點(diǎn)127.在單處理機(jī)系統(tǒng)中，右冋時(shí)存在有10個(gè)進(jìn)程，則處于就緒隊(duì)列中的進(jìn)程最多為C個(gè)。A. 0B.6C. 9D.10128.下列不屬于臨界資源的是A。A. CPUB.公共變量C.公用數(shù)據(jù)D.輸入輸出設(shè)備129.下面關(guān)于進(jìn)程同步的說法中，錯(cuò)誤的是D。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)系，必

36、須要求各進(jìn)程同步工作130. 若S是P、V操作的信號(hào)量，當(dāng) S0,則繼續(xù)執(zhí)行；若 S0則_C。A. 將進(jìn)程阻塞，插入等待隊(duì)列B. 將隊(duì)列中的一個(gè)進(jìn)程移出，使之處于運(yùn)行狀態(tài)C. 將隊(duì)列中的一個(gè)進(jìn)程移出，使之處于就緒狀態(tài)D. 將進(jìn)程變?yōu)閽炱馉顟B(tài)142. 在進(jìn)程的調(diào)度算法中，_D是動(dòng)態(tài)優(yōu)先數(shù)的確定算法。A.按進(jìn)程使用的資源進(jìn)行調(diào)度B.按進(jìn)程在隊(duì)列中等待的時(shí)間進(jìn)行調(diào)度C.按時(shí)間片輪轉(zhuǎn)調(diào)度D非剝奪方式優(yōu)先數(shù)調(diào)度143作業(yè)控制塊 JCB的容不包括C。A.作業(yè)的狀態(tài)B.作業(yè)進(jìn)入系統(tǒng)的時(shí)間C.作業(yè)對(duì)進(jìn)程的要求D. 作業(yè)對(duì)資源的要求144.設(shè)有一組作業(yè)，它們的提交時(shí)刻及運(yùn)行時(shí)間如下表所示:A. 1,3,4,2C

37、. 4,1,2,3145.有如下三個(gè)作業(yè)：A1以計(jì)算為主,B. 4,3,2,1D. 1,4,3,2A2以輸入/輸出為主，A3是計(jì)算和輸入在作業(yè)調(diào)度中，若采用優(yōu)先級(jí)調(diào)度算法,為盡可能使處理器和外部設(shè)備并行工作,/輸出兼顧， 則它們的作業(yè)號(hào)提交時(shí)刻運(yùn)行時(shí)間（分鐘）19:007029:403039:5010410:105則在單道方式下，采用短作業(yè)優(yōu)先調(diào)度算法，作業(yè)的執(zhí)行順序?yàn)镈優(yōu)先級(jí)從高到低的排列順序是CB. A2, A3, A1A. A1, A2, A3C. A3, A2, A1D. A2, A1, A3146. 下面幾個(gè)選項(xiàng)中，作業(yè)里肯定沒有的是_D。A.程序B.初始數(shù)據(jù)C.作業(yè)說明書D.通道程

38、序147. 作業(yè)調(diào)度程序不能無故或無限地拖延一個(gè)作業(yè)的執(zhí)行，這是作業(yè)調(diào)度的A.公平性原則B.平衡資源使用原則C.極大的流量原則D.必要條件148. 作業(yè)調(diào)度是A。A. 從輸入進(jìn)挑選作業(yè)進(jìn)入主存B. 從讀卡機(jī)挑選作業(yè)進(jìn)輸入井C. 從主存中挑選作業(yè)進(jìn)程處理器D. 從等待設(shè)備的隊(duì)列中選取一個(gè)作業(yè)進(jìn)程149.用戶通過D直接在終端控制作業(yè)的執(zhí)行。A. C語言B.匯編語言C.操作控制命令D.作業(yè)控制語言150.在作業(yè)調(diào)度算法中，C兼顧了短作業(yè)與長作業(yè)。A.先來先服務(wù)B.計(jì)算時(shí)間最短優(yōu)先C.均衡調(diào)度D.最高響應(yīng)比優(yōu)先151.某作業(yè)的任務(wù)是某緊急事務(wù)處理，應(yīng)選擇C算法較為合適。A.先來先服務(wù)B.短作業(yè)優(yōu)先C.

39、優(yōu)先數(shù)調(diào)度D.響應(yīng)比高者優(yōu)先152.現(xiàn)有三個(gè)同時(shí)到達(dá)的作業(yè)J1、J2和J3，它們的執(zhí)行時(shí)間分別為系統(tǒng)按單道方式運(yùn)行且采用短作業(yè)優(yōu)先算法，則其平均周轉(zhuǎn)時(shí)間為A. T1+T2+T3B. (T1+T2+T3)/3C. T1+2*T2/3+T3/3D. T1/3+2*T2/3+T3154. 在頁式存儲(chǔ)管理系統(tǒng)中，整個(gè)系統(tǒng)的頁表個(gè)數(shù)是CA. 1個(gè)B. 2個(gè)C.和裝入主存的作業(yè)個(gè)數(shù)相同D.不確定155. 虛擬存儲(chǔ)器是DA.B.C.D.T1、T2和 T3,且 T1T2T3,CO可提高計(jì)算機(jī)執(zhí)行指令速度的外圍設(shè)備容量擴(kuò)大了的磁盤存儲(chǔ)器 實(shí)際上不存在的存儲(chǔ)器可以容納總和超過主存容量的、多個(gè)作業(yè)同時(shí)運(yùn)行的一個(gè)地址

40、空間156. 存儲(chǔ)管理的目的是實(shí)現(xiàn) A.提高計(jì)算機(jī)資源的利用率 C.有效使用和分配外存空間157. 在虛擬頁式存儲(chǔ)管理中，A.程序性中斷 C.硬件中斷158. 一進(jìn)程剛獲得三132,1,2,1,5,1,2,3 A. 4C. 6159. 存共享的目的是OB.擴(kuò)充主存容量，并提高主存利用效率 D.提高CPU的執(zhí)行效率由于所需頁面不在存，而引發(fā)的缺頁中斷屬于_B. I/O 中斷D.時(shí)鐘中斷個(gè)存儲(chǔ)塊的使用權(quán)，當(dāng)采用先進(jìn)先出調(diào)度算法時(shí)，B. 5D. 7若該進(jìn)程訪問頁面的次序是發(fā)生缺頁的次數(shù)是 C次。A.B.擴(kuò)大存空間，提高存空間的利用效率節(jié)省存空間，實(shí)現(xiàn)進(jìn)程間通信，提高存空間的利用效率 共享存中的程序和

41、數(shù)據(jù) 以上說法均不對(duì)C.D.160. 以下主存管理方案中，不采用動(dòng)態(tài)重定位的是A.頁式管理B.C.可變分區(qū)D.161. 最易形成很多小碎片的可變分區(qū)分配算法是A.最先適應(yīng)算法B.C.最壞適應(yīng)算法162. 頁式存儲(chǔ)管理中，頁表的大小由A.作業(yè)所占頁的多少B.操作系統(tǒng)C.計(jì)算機(jī)編址圍D.系統(tǒng)統(tǒng)一指定.在提供虛擬存儲(chǔ)的系統(tǒng)中，用戶的邏輯地址空間主要受A.主存的大小C.計(jì)算機(jī)編址圍164.在分段管理中，A.以段為單位分配，D.AC每段固定分區(qū)段式管理B最優(yōu)適應(yīng)算法以上都不對(duì)決定。CB.輔存的大小D.主存中用戶區(qū)域的大小的限制。1. 從工作的角度看操作系統(tǒng)，可以分為單用戶系統(tǒng)、批處理系統(tǒng)、A.單機(jī)操作系

42、統(tǒng)B.分時(shí)操作系統(tǒng)C.面向過程的操作系統(tǒng)D.網(wǎng)絡(luò)操作系統(tǒng)2. 在下列系統(tǒng)中，_B_ A.計(jì)算機(jī)激光照排系C.辦公自動(dòng)化系統(tǒng)3. 操作系統(tǒng)是一種_B_A.應(yīng)用軟件C.通用軟件4. 引入多道程序的目的在于是實(shí)時(shí)系統(tǒng)。B.航空定票系統(tǒng)D.計(jì)算機(jī)輔助設(shè)計(jì)系統(tǒng)和實(shí)時(shí)系統(tǒng)。B.系統(tǒng)軟件D.工具軟件A.先進(jìn)先出調(diào)度算法B.短執(zhí)行優(yōu)先調(diào)度A. 充分利用CPU減少CPU等待時(shí)間B. 提高實(shí)時(shí)響應(yīng)速度C. 有利于代碼共享，減少主、輔存信息交換量D. 充分利用存儲(chǔ)器以外的所有運(yùn)行所需資源的進(jìn)程處于就緒狀態(tài)。B.打印機(jī)D.存空間B5. 已經(jīng)獲得除CA. 存儲(chǔ)器C. CPU，二是恰當(dāng)?shù)剡M(jìn)行代碼轉(zhuǎn)換。B.調(diào)度算法D.存空

43、間6. 進(jìn)程調(diào)度的關(guān)鍵問題：一是選擇合理的A. 時(shí)間片間隔C. CPU速度7. 采用輪轉(zhuǎn)法調(diào)度是為了A. 多個(gè)終端都能得到系統(tǒng)的及時(shí)響應(yīng)B. 先來先服務(wù)C. 優(yōu)先級(jí)較高的進(jìn)程得到及時(shí)調(diào)度D. 需CPU最短的進(jìn)程優(yōu)先8. 在一段時(shí)間只允許一個(gè)進(jìn)程訪問的資源，稱為CA. 共享資源B.臨界區(qū)C.臨界資源D.共享區(qū)9. 并發(fā)性是指若干事件在B發(fā)生。A. 同一時(shí)刻B.同一時(shí)間間隔C.不同時(shí)刻D.不同時(shí)間間隔10. 在單一處理器上，將執(zhí)行時(shí)間有重疊的幾個(gè)程序稱為_CB.多道程序D.并行程序只有程序本身能改變系統(tǒng)資源狀態(tài)， 這是指BB.程序順序執(zhí)行的封閉性D.并發(fā)程序失去再現(xiàn)性CA. 順序程序C.并發(fā)程序1

44、1. 程序運(yùn)行時(shí)，獨(dú)占系統(tǒng)資源，A. 程序順序執(zhí)行的再現(xiàn)性C.并發(fā)程序失去封閉性12. 引入多道程序技術(shù)后，處理器的利用率A. 降低了B.有所改善C.大大提高D.沒有變化，只是程序的執(zhí)行方便了13. 在單一處理器上執(zhí)行程序，多道程序的執(zhí)行是在B進(jìn)行的。A. 同一時(shí)刻B.同一時(shí)間間隔C.某一固定時(shí)刻D.某一固定時(shí)間間隔14. 在進(jìn)程通信中，常C通過變量、數(shù)組形式來實(shí)現(xiàn)。A.高級(jí)通信B.消息通信C.低級(jí)通信D.管道通信15.管道通信是以B進(jìn)行寫入和讀出。A.消息為單位B.自然字符流C.文件D.報(bào)文16.現(xiàn)代操作系統(tǒng)的兩個(gè)基本特征是C和資源共享。A.多道程序設(shè)計(jì)B.中斷處理C.程序的并發(fā)執(zhí)行D.實(shí)現(xiàn)分時(shí)與實(shí)時(shí)處理17.為了描述進(jìn)程的動(dòng)態(tài)變化過程，采用了一個(gè)與進(jìn)程相聯(lián)系的C來感知進(jìn)程的存在。A.進(jìn)程狀態(tài)字B.進(jìn)程優(yōu)先數(shù)C.進(jìn)程控制塊D.進(jìn)程起始地址18.順序執(zhí)行和并發(fā)程序的執(zhí)行相比，C。A.基本相同B.有點(diǎn)不同C.并發(fā)程序執(zhí)行總體上執(zhí)行時(shí)間快D.順序程序執(zhí)行總體上執(zhí)行時(shí)間快19.進(jìn)程是B。A.與程序等效的概念B.執(zhí)行中的程序C.