計算機軟件基礎試題

1、百度文庫軟件技術基礎試題庫課程名稱：軟件技術基礎適用專業(yè)：軟件技術、計算機應用、網(wǎng)絡、信息等計算機相關專業(yè)第一章概述第二章數(shù)據(jù)結(jié)構一、單項選擇題1 .若長度為n的線性表采用順序存儲結(jié)構，刪除它的第i數(shù)據(jù)元素之前，需要先依次向前移動個數(shù)據(jù)元素。()A. n-iB. n+iC. n-i-1D. n-i+1答案：A2 .在單鏈表中，已知q指的結(jié)點是p指的結(jié)點的直接前驅(qū)結(jié)點，若在q和p指的結(jié)點之間插入一個由s指的結(jié)點，則需執(zhí)行。()A. link(s)-link(p)link(p)-sB. link(q)廠Hnk(s)-pC. link(p)-link(s)ink(s)-pD. link(p)廠Hnk

2、(s)-q/答案：B3 .高度為h(h>0)的二叉樹最少有個結(jié)點。()/A. h/B. h-1C. h+1答案：A4 .n個頂點的帶權無向連通圖的最小生成樹包含個頂點。（）2+1/答案：B5 .采用拉鏈法解決沖突的散列表中，查找的平均查找長度（）。A.直接與關鍵字個數(shù)有關'B.直接與裝填因子a有關C.直接與表的容量有關D.直接與散列函數(shù)有關答案：D6 .樹型結(jié)構最適合用來描述（）A.有序的數(shù)據(jù)元素B.無序的數(shù)據(jù)元素C.數(shù)據(jù)元素之間的具有層次關系的數(shù)據(jù)D.數(shù)據(jù)元素之間沒有關系的數(shù)據(jù)答案：C7 .若二叉樹中度為2的結(jié)點有15個，度為1的結(jié)點有10個個葉結(jié)點。（）答案：C8 .若深度為

3、6的完全二叉樹的第6層有3個葉結(jié)點，則該二叉樹一共有個結(jié)點。（）答案：C9 .若某完全二叉樹的深度為h,則該完全二叉樹中至少有個結(jié)點。（）+1./答案：C/10 .在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點的左邊應該（）A.只有左子樹上的所有結(jié)點B.只有左子樹上的部分結(jié)點C.只有右子樹上的所有結(jié)點D.只有右子樹上的部分結(jié)點答案：A11 .下面關于哈夫曼樹的說法，不正確的是（）A.對應于一組權值構造出的哈夫曼樹一般不是唯一的B.哈夫曼樹具有最小帶權路徑長度C.哈夫曼樹中沒有度為1的結(jié)點D.哈夫曼樹中除了度為1的結(jié)點外，還有度為2的結(jié)點和葉結(jié)點答案：D12 .數(shù)據(jù)結(jié)構是一門研究計算機中對象及其關

4、系的學科。（）A.數(shù)值運算B.非數(shù)值運算C.集合D.非集合答案：B13 .數(shù)據(jù)結(jié)構的定義為（K,R）,其中K是的集合。（）A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結(jié)構、答案：B14.算法分析的目的是。（）/A.找出數(shù)據(jù)結(jié)構的合理性/B.研究算法中輸入和輸出的關系/C.分析算法的效率以求改進D.分析算法的易懂性和文檔性答案：C15.數(shù)據(jù)的不可分割的基本單位是。()A.元素B.結(jié)點/C.數(shù)據(jù)類型D.數(shù)據(jù)項答案：D/16 .是具有相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。()A.數(shù)據(jù)符號B.數(shù)據(jù)對象C.數(shù)據(jù)D.數(shù)據(jù)結(jié)構'答案：B17 .數(shù)據(jù)結(jié)構是研究數(shù)據(jù)的及它們之間的相互聯(lián)系。()A.理想結(jié)構、

5、物理結(jié)構B.理想結(jié)構、邏輯結(jié)構C.物理結(jié)構、邏輯結(jié)構D.抽象結(jié)構、邏輯結(jié)構答案：C18 .組成數(shù)據(jù)的基本單位是。()A.數(shù)據(jù)項B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量答案：C19 .數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱為。()A.存儲結(jié)構/B.邏輯結(jié)構/C.順序存儲結(jié)構D.鏈式存儲結(jié)構/答案：C20.算法指的是。()'/A.計算機程序B.解決問題的計算方法C.排序算法D.解決問題的有限運算序列答案：D21.由組成的集合是一個數(shù)據(jù)對象。()A.不同類型的數(shù)據(jù)項/B.不同類型的數(shù)據(jù)元素/C.相同類型的數(shù)據(jù)項D.相同類型的數(shù)據(jù)元素答案：D22 .關于順序存儲的敘述中

6、，哪一條是不正確的。()A.存儲密度大B.邏輯上相鄰的節(jié)點物理上不必鄰接,C.可以通過計算直接確定第i個節(jié)點的位置'D.插入、刪除操作不方便答案：B23 .一個向量第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是。()答案：B24 .已知一個順序存儲的線性表，設每個結(jié)點需要占m個存儲單元，若第一個結(jié)點的地址為da,則第i個結(jié)點的地址為。()+(i-1)*m+i*m*m+(i+1)*m答案：A25.鏈表是一種采用存儲結(jié)構存儲的線性表。()/A.順序/B.鏈式/C.星式D.網(wǎng)狀答案：B/26.線性表若采用鏈式存儲結(jié)構時，要求內(nèi)存中可用存儲單元的地址。()A.必須是連續(xù)

7、的B.部分地址必須是連續(xù)的C. 一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以答案：D27.線性表L在情況下適用于使用鏈式結(jié)構實現(xiàn)。（）A.需經(jīng)常修改L中的結(jié)點值B.需不斷對L進行刪除插入C.L中含有大量的結(jié)點D. L中結(jié)點結(jié)構復雜答案：B28 .在長度為n的順序表的第i（1wiwn+價位置上插入一個元素，元素的移動次數(shù)為。（）+1答案：A29 .線性表是。（）A. 一個有限系列，可以為空B. 一個有限系列，不能為空C.一個無限系列，可以為空D.一個無限系列，不能為空答案：A30 .是線性表。（）A.（孔子，諸葛亮，曹雪芹）B.A,B,C,DC.10,11,12,13,14D.（1,2,3，）答案：A3

8、1 .一是表示線性數(shù)據(jù)結(jié)構的。（）/A.循環(huán)鏈表/B.鄰接多重表/C.孩子鏈表D.單鏈表/答案：D32.將線性表的數(shù)據(jù)元素以結(jié)構存放，查找一個數(shù)據(jù)元素所需時間不依賴于表長。（）A.循環(huán)雙鏈表B.哈希(Hash)表C.一維數(shù)組D.單鏈表/答案：C33 .在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行()>link=p;p->link=s;/、>link=p->link;p->link=s;>link=p->link;p=s;>link=s;s->link=p;答案：34 .在循環(huán)鏈表中first為指向鏈表表頭的指針，

9、current為鏈表當前指針，在循環(huán)鏈表中檢測current是否達到鏈表表尾的語句是。()>link=NULL>link=current=current>link=first答案：35 .從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需平均比較個結(jié)點。()2C.(n-1)/2D.(n+1)/2答案：36 .用鏈表表示線性表的優(yōu)點是。()A.便于隨機存取B.花費的存儲空間比順序表少C.便于插入與刪除D.數(shù)據(jù)元素的物理順序與邏輯順序相同答案：37 .當需要隨機查找線性表的元素時，宜采用作存儲Z構。()/A.雙向鏈表/B.循環(huán)鏈表/C.順序表D.單鏈表

10、9;、/答案：38 .線性表的鏈接實現(xiàn)有利于運算。()A.插入B.讀表元C.查找D.定位/答案：39 .線性表采用鏈式存儲時，其地址。（）A.必須是連續(xù)的/B.部分地址是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以答案：40 .設單鏈表中指針p指著結(jié)點a,若要刪除a之后的結(jié)點（若存在），則需要修改指針的操作為。（）>next=p->next->next=p->next=p->next->next>next=p答案：A41 .向一個有127個元素順序表中插入一個新元素并保存原來順序不變，平均要移動一個元素。（）答案：A42 .向一個有127個元素的順序表中

11、刪除一個元素，平均要移動個元素。（）答案：C43 .又稱為FIFO表。（）A.隊列/B.散列表/C.棧D.哈希表/答案：44 .設依次進入一個棧的元素序列為c,a,b,d,不可得到出棧的元素序列有。（）45 .鏈式棧與順序棧相比，一個比較明顯的優(yōu)點是。()A.插入操作更加方便/B.通常不會出現(xiàn)棧滿的情況/C.不會出現(xiàn)?？盏那闆r/D.刪除操作更加方便答案：46 .在一個順序存儲的循環(huán)隊列中，隊頭指針指向隊頭元素的。()A.前一個位置、B.后一個位置C.隊頭元素位置D.隊尾元素的前一位置答案：47 .若一個棧的輸入序列是1,2,3n,則輸出序列的第一個元素是n,則第i個輸出元素是°()+

12、1答案：48 .棧的數(shù)組表示中，top為棧頂指針，棧空的條件是。()=0=maxSize=maxSize=-1/答案：49 .在數(shù)組表示的循環(huán)隊列中，front、rear分別為隊列的頭、尾指針，maxSize為數(shù)組的最大長度，隊滿的條件是。()/=maxSize、/B.(rear+1)%maxSize=front/=maxSize、-/=front/答案：50 .棧和隊列的共同特點是。()9百度文庫A.都是先進后出B.都是先進先出C.只允許在端點處插入和刪除D.沒有共同點/答案：51 .若非空隊列采用鏈式存儲結(jié)構，front和rear分別為隊頭元素與隊列尾元素的指針，刪除此時隊列的一個元素的操

13、作時依次執(zhí)行pfront,callRET(P)。()link(rear)link(p)/link(front)link(p)答案：52 .由兩個棧共享一個向量空間的好處是。()A.減少存取時間，降低下溢發(fā)生的機率B.節(jié)省存儲空間，降低上溢發(fā)生的機率'C.減少存取時間，降低上溢發(fā)生的機率D.節(jié)省存儲空間，降低下溢發(fā)生的機率答案：53 .數(shù)組datam為循環(huán)隊列的存儲空間，front為隊頭指針，rare為隊尾指針，則執(zhí)行入隊的操作為。()=rare+1二(rare+1)%(m-1)二(rare-1)%m二(rare+1)%m答案：54 .將遞歸算法轉(zhuǎn)換成對應的非遞歸算法時，通常需要使用。(

14、)/A.棧、/B.隊列/C.鏈表D.數(shù)組/答案：55.高度為h(h>0)的二叉樹最少有個結(jié)點。1)答案：56.樹型結(jié)構最適合用來描述。()A.有序的數(shù)據(jù)元素7B.無序的數(shù)據(jù)元素C.數(shù)據(jù)元素之間的具有層次關系的數(shù)據(jù)D.數(shù)據(jù)元素之間沒有關系的數(shù)據(jù)答案：57k有n(n>0)個結(jié)點的完全二叉樹的深度是。()A. log2(n)B. log2(n)+1C. log2(n+1)D. log2(n)+1答案：58.又是一棵滿二叉樹。()A.二叉排序樹B.深度為5有31個結(jié)點的二叉樹C.有15個結(jié)點的完全二叉樹D.哈夫曼(Hufman)樹答案：59 .深度為k的滿二叉樹有個分枝結(jié)點。()+1+1答

15、案：60 .若已知一棵二叉樹先序序列為ABCDEFG,中序序列為CBDAEGF,則其后序序列為。()/答案：A61 .二叉樹第i(i>=1)層上至多有結(jié)點。()A. 2iB. 2i)1- 1C. 2iD. 2i-1/答案：62.在一棵具有5層的滿二叉樹中結(jié)點總數(shù)為。()A. 31B. 32C. 33/D. 16答案：63.一個二叉樹按順序方式存儲在一個維數(shù)組中，如圖01234567891011121314ABCDEFGHIJ則結(jié)點E在二叉樹的第層。()答案：64r在一棵度為3的樹中，度為3的結(jié)點個數(shù)為2,度為2的結(jié)點個數(shù)為1,則度為0的結(jié)點個數(shù)為。()A. 4B. 5/C. 6/D. 7

16、/答案：65.n個頂點的帶權無向連通圖的最小生成樹包含個頂點。()2/+1答案：12百度文庫66 .具有n個頂點的有向完全圖有條弧。()*(n-1)*(n+1)/*n/答案：67 .n個頂點的連通圖至少有條邊。()+1答案：68 .在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的倍。()A. 1/2B. 1C. 2D. 4答案：69.在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為。()A. eB. 2eC. n2eD. n22e答案：D70 .折半查找有序表(6,15,30,37,65,68,70,72,89,99)，若查找元素37,需依次與表中元素進行比較。()/,15,3

17、7,30,37,15,30,15,30,37/答案：71 .對有3600個記錄的索引順序表(分塊表)進行查找，最理想的塊長為。()答案：B72 .折半查找20個記錄的有序表，若查找失敗，比較關鍵字的次數(shù)。()A.最多為6B.最多為5/C.最多為4/D.最多為3/答案：B73 .中序遍歷一棵二叉排序樹所得到的結(jié)點序列是鍵值的序列。()A.遞增或遞減B.遞減C.遞增D.無序答案：74 .散列表中的沖突是指。()A.兩個元素具有相同的序號B.兩個元素的鍵值相同，而其他屬性相同C.不同的鍵值對應相同的存儲地址D.數(shù)據(jù)元素的地址相同答案：75 .用線形探測法查找散列表，可能要探測多個散列地址，這些位置上

18、的鍵值。()A.一定是同義詞B.不一定是同義詞C.一定不是同義詞D.都相同答案：76 .在初始為空的雜湊表中依次插入關鍵字序列(MON,TUE,WED,THU,FRI,SAT,SUN),雜湊函數(shù)為H(k尸iMOD7，其中，i為關鍵字k的第一個字母在英文字母表中的序號，地址值域為0:6,采用線性再散列法處理沖突。插入后的雜湊表應該如所示。()/A. 0123456THUTUEWEDFRISUNSATMONB. 0123456/TUETHUWEDFRISUNSATMON'/C. 0123456TUETHUWEDFRISATSUNMOND. 0123456TUETHUWEDSUNSATFRI

19、MON答案：77 .設有一個含200個表項的散列表，用線性探查法解決沖突，按關鍵碼查詢時找到一個表項的平均探查次數(shù)不超過，則散列存儲空間應能夠至少容納個表項。（設搜索成功的平均搜索長度為Snl=（1+1/（1-a）/2,其中a為裝填因子）（）答案：78 .對長度為10的表作選擇（簡單選擇）排序，共需比較一次關鍵字。（）答案：79 .設有100個數(shù)據(jù)元素，采用折半搜索時，最大比較次數(shù)為（）。A. 6B. 7C. 8D.1080 .對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是。（）A.選擇排序B.直接插入

20、排序,/C.快速排序/D.起泡排序/答案：C81 .對5個不同的數(shù)據(jù)元素進行直接插入排序，最多需要進行次比較。（）A. 8B. 10/C. 15/D. 25答案：82.采用折半查找方法進行查找，數(shù)據(jù)文件應為,且限于。（）A.有序表順序存儲結(jié)構/B.有序表鏈式存儲結(jié)構/C.隨機表順序存儲結(jié)構/D.隨機表鏈式存儲結(jié)構答案：83.從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其存放在已排序序列的合適位置，該排序方法稱為排序法。（）A.插入B.選擇C.希爾D.二路并歸答案：84.就平均查找速度而言，下列幾種查找速度從慢至快的關系是。（）A.順序折半哈西分塊B.順序分塊折半哈西C

21、.分塊折半哈西順序D.順序哈西分塊折半答案：B85 .在下列算法中，算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。（）A.堆排序B.冒泡排序C.插入排序D.快速排序/答案：C86 .堆是一個鍵值序列（Ki,K2,，K）,對I=1,2n/2蹣足。（）< =K2i<=K2i+1/< K2i+1<K2i/< =K2i且Ki<=K2i+1D.Ki<=K2i或Ki<=K2i+1/答案：87.對于關鍵字序列46,58,15,45,90,18,10,62,其快速排序第一趟的結(jié)果是4518151818151018答案：46106245

22、4658454690454662。（）589062905862589020,15,21,25,47,27,68,/15,20,21,25,35,27,47,/15,20,21,25,27,35,47,則所米用的排序方法是一。（）88.用某種排序方法對關鍵字序列（25,序列的變化情況如下：A.選擇排序 B.希爾排序 C.歸并排序 D.快速排序 答案：84,21,47,15,27,68,35,20）進行排序時,35,8468,8468,8489 .下列關鍵字序列中是堆。（）A.16,72,31,23,94,53B.94,23,31,72,16,53C.16,53,23,94,31,72D.16,2

23、3,53,31,94,72答案:90 .目前以比較為基礎的內(nèi)部排序方法中，其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無關的是。（）A.插入排序/B.直接選擇排序/C.快速排序/D.冒泡排序/答案：B91.對n個不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數(shù)為。（）A. n+1B. n/C. n-1'/D. n（n-1）/2答案：二、多項選擇題1.根據(jù)數(shù)據(jù)元素之間的不同特性，通常具有這幾種基本數(shù)據(jù)結(jié)構。（）A.集合/B.線形結(jié)構/C.樹型結(jié)構/D.圖型結(jié)構/答案：ABCD2.數(shù)據(jù)元素之間的關系在計算機中有兩種不同的表示方法。（）A.順序存儲結(jié)構B.二叉樹存儲結(jié)構C.鏈式存儲結(jié)構D.網(wǎng)

24、絡結(jié)構答案：AC3.查找哈希（Hash）表,解決沖突的的方法有。（）A.除留余數(shù)法B.線性探測再散列法C.直接地址法D.鏈地址法答案：BD三、判斷題1 .非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個直接前驅(qū)元素。（）答案：F2 .數(shù)組是一種沒有插入與刪除操作的線性結(jié)構。（）答案：T3 .非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個直接后繼元素。（）答案：F4 .數(shù)據(jù)的存儲結(jié)構不僅有順序存儲結(jié)構和鏈式存儲結(jié)構，還有索引結(jié)構與散列結(jié)構。（）答案：F5 .線性鏈表中各個鏈結(jié)點之間的地址不一定要連續(xù)。（）答案：T6 .若頻繁地對線性表進行插入和刪除操作，該線性表采用順序存儲結(jié)構更合適。（）答案：F7 .若

25、線性表采用順序存儲結(jié)構，每個數(shù)據(jù)元素占用4個存儲單元，第12個數(shù)據(jù)元素的存儲地址為144,則第1個數(shù)據(jù)元素的存儲地址是101。()答案：F/8 .若長度為n的線性表采用順序存儲結(jié)構，刪除表的第i個元素之前需要移動表中n-i+1個元素。()/答案：F9 .符號link(p)出現(xiàn)在表達式中表示p所指的那個結(jié)點的內(nèi)容。()答案：F10 .要將指針p移到它所指的結(jié)點的下一個結(jié)點是執(zhí)行語句plink(p)。()、答案：T11 .在非空線性鏈表中由p所指的結(jié)點后面插入一個由q所指的結(jié)點的過程是依次執(zhí)行語句：link(q)-link(p);link(p)。()答案：T12 .在非空雙向循環(huán)鏈表中由q所指的結(jié)

26、點后面插入一個由p指的結(jié)點的動作依次為：llink(p)-q,rlink(p)-rlink(q),rlink(q)-p,llink(rl(nk(q)-p答案：F13 .若某堆棧的輸入序列為1,2,3,4,則4,3,1,2不可能是堆棧的輸出序列之一。()答案：T14 .刪除非空鏈式存儲結(jié)構的堆棧(設棧頂指針為top)的一個元素的過程是依次執(zhí)行:ptop,toplink(p),callRET(p)。()答案：T15 .若隊列采用鏈式存儲結(jié)構，隊頭指針與指針分別為front和rear,向隊列中插入一個數(shù)據(jù)信息為item的新元素的過程是依次執(zhí)行：callGETNODE(p),data(P廣item,r

27、earp,front()答案：F16 .數(shù)據(jù)結(jié)構概念包括數(shù)據(jù)之間的邏輯結(jié)構，數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運算三個方面。()答案：T17 .非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個直接前驅(qū)元素。()答案：F/18 .在順序表中取出第i個元素所花費的時間與i成正比。()答案：F19 .完全二叉樹就是滿二叉樹。（）答案：F20 .已知一棵二叉樹的前序序列和中序序列可以唯一地構造出該二叉樹。（）答案：T/21 .有向圖是一種非線性結(jié)構。（）答案：T/22 .帶權連通圖的最小生成樹的權值之和一定小于它的其它生成樹的權值之和。（）答案：T23 .對二叉排序樹遍歷的結(jié)果是一個有序序列。（）答案：T24

28、 .折半查找方法適用于按值有序的線性鏈表的查找。（）答案：F25 .非空二叉排序樹的任意一棵子樹也是二叉排序樹。（）答案：T26 .哈希表的查找效率主要取決于所選擇的哈希函數(shù)與處理沖突的方法。（）答案：T四、填空題1 .已知具有n個元素的一維數(shù)組采用順序存儲結(jié)構，每個元素占k個存儲單元，第一個元素的地址為LOC（a1）,那么，LOC（ai尸。答案：LOC（a1）+（n-1）k2 .若一棵二叉樹有10個葉結(jié)點，則該二叉樹中度為2的結(jié)的點個數(shù)為。答案：43 .設SQ為循環(huán)隊列，存儲在數(shù)組dm中，則SQ出隊操作對其隊頭指針front的修改是答案：4 .n（n>0）個結(jié)點二叉樹對應的森林最多包含

29、棵非空樹。5 .深度為n（n>0）的二叉樹最多有個結(jié)點。6 .n(n>0)個結(jié)點、(n-1)條邊的連通無向圖中，頂點度數(shù)最大值為。7 .在一個圖中，所有頂點的度數(shù)之和等于所有邊的數(shù)目的倍。答案：8 .圖的深度優(yōu)先搜索方法類似于二叉樹的遍歷。9 .帶權連通圖G,其中V=v1,v2,v3,v4,v5,E=(v1,v2)7,<V1,V3)6,(V1,V4)9,(V2,V3)8,(V2,V3)8,(V2,V4)4,(V2,V5)4,(V3,V4)6,(V4,V5)2(注：頂點偶對右下角的數(shù)據(jù)為邊上的權值)，G的最小生成樹的權值之和為。答案：10 .將數(shù)據(jù)元素2,4,6,8,10,12

30、,14,16,18,20依次存放于一個一維數(shù)組中，然后采用折半查找方法、查找元素12,被比較過的數(shù)組元素的下標依次為。答案：11 .每趟排序從未排序的子序列中依次取出元素與已經(jīng)排好序的序列中元素進行比較，然后將其放在已經(jīng)排好序的序列的合適位置。這種排序法稱為排序法。答案：12 .從未排序序列中選擇一個元素，該元素將當前參加排序的那些元素分成前后兩個部分，前一部分中所有元素都小于等于所選元素，后一部分中所有元素都大于或等于所選元素，而此時所選元素處在排序的最終位置。這種排序法稱為排序法。答案：13 .對序列(49,38,65,97,76,27,13,50)采用快速排序法進行排序，以序列的第一個元

31、素為基準元素得到的劃分結(jié)果是1。/答案：14 .一個數(shù)據(jù)結(jié)構在計算機中的表示(映象)稱為?。15 .數(shù)據(jù)結(jié)構被形式地定義為(D,R),其中D是的有限集合，R是D上的有限集合。答案：16 .數(shù)據(jù)的邏輯結(jié)構是從邏輯關系上描述數(shù)據(jù)，它與數(shù)據(jù)的無關，是獨立于計算機的。17 .一個算法具有5個特性:、有零個或多個輸入、有一個或多個輸出。答案：18 .線性表中稱為表的長度。19 .設長度為n的線性表順序存貯，若在它的第i-1和第i個元素之間插入一個元素，共需移動個元素（1<iwn）答案：20 .在單鏈表中要在已知結(jié)點*p之前插入一新結(jié)點，需找到。答案：21 .循環(huán)鏈表的主要優(yōu)點是。答案：從任何一個結(jié)

32、點出發(fā)可以遍歷所有結(jié)點22 .在一個單鏈表中刪除p所指結(jié)點的下一個結(jié)點時，應執(zhí)行以下操作：q=p->link;p->link=Deleteq答案：23 .設SQ為循環(huán)隊列，存儲在數(shù)組dm中，則SQ出隊操作對其隊頭指針front的修改是O答案：24 .棧中元素的進出原則為。25 .在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應該是一個結(jié)構，其主要特點是。答案：26 .對于一個以順序?qū)崿F(xiàn)的循環(huán)隊列Q0m-1,隊頭、隊尾指針分別為f、r,其判空的條件是,判滿的條件是。答案：r=f、

33、(r+1)%m=f27 .在具有n個單元的循環(huán)隊列中，隊滿時共有個元素。28 .深度為n(n>0)的二叉樹最多有個結(jié)點。29 .n(n>0)個結(jié)點、(n-1)條邊的連通無向圖中，頂點度數(shù)最大值為。30 .一棵深度為6的滿二叉樹有個非終端結(jié)點。31 .若一棵二叉樹中有8個度為2的結(jié)點，則它有個葉子。32 .樹中結(jié)點A的稱為結(jié)點A的度。33 .一棵深度為4的二叉樹最多有個結(jié)點。34 將轉(zhuǎn)化為二叉樹時，其根結(jié)點的右子樹總是空的。答案：35 .哈夫曼樹是帶權路徑長度的樹，通常權值較大的結(jié)點離根結(jié)點。/答案：36 .具有n個葉子的二叉樹，每個葉子的權值為wi(1&i等剛帶權路徑最小的

34、二叉樹被稱為。/答案：37 .若已知一棵二叉樹的先序序列為-+a*b-cd/ef,中序序列為a+b*c-d-e/f,貝U其后序序歹U為。/答案：38 .已知一棵完全二叉樹中共有768結(jié)點，則該樹中共有個葉子結(jié)點。答案：39 .已知二叉樹有50個葉子結(jié)點，且僅有一個孩子的結(jié)點數(shù)為30,則總結(jié)點數(shù)為。答案：40 .具有10個頂點的無向圖，邊的總數(shù)最多為。41 .在有n個頂點的有向圖中，每個頂點的度最大可達、。答案：42 .有向圖g用鄰接矩陣a口m,1m來存儲，其第i行的所有元素之和等于頂點i的。答案：43 .有n個球隊參加的足球聯(lián)賽按主客場制進行比賽，共需進行場比賽。、答案：44 .帶權連通圖G=

35、<V,E>,其中V=v1,v2,v3,v4,v5,E=(v1,v2)7,(v1,v4)6,(v1,v4)9,(v2,v3)8,(v2,v4)4,(v2,v5)4,(v3,v4)6,(v4,v5)2,(注:頂點偶對右下角的數(shù)據(jù)為邊上的權值),G的最小生成樹的權值之和為。答案：45 .順序查找n個元素的順序表，當使用監(jiān)視哨時，若查找成功，比較關鍵字的次數(shù)至少為一次，最多為一次；若查找失敗，比較關鍵字的次數(shù)為一、次。答案：46 .在單鏈表上難以實現(xiàn)的排序方法有、和。/答案：快速排序、堆排序、希爾排序五、簡答題/問答題/綜述題1 .什么是順序表？順序表的特點是什么？答案：線性表的順序存儲是

36、指在內(nèi)存中用一塊地址連續(xù)的存儲空間順序存放線性表的各元素，用這種形式存儲的線性表稱為順序表。數(shù)據(jù)元素在順序表中物理位置取決于數(shù)據(jù)元素在線性表中的邏輯位置，可得出順序表的特點：邏輯位置相鄰，其物理位置也相鄰。2 .什么樣的圖是連通圖？答案：在無向圖G中，如果從一個頂點Vi到另一個頂點vj(ij)有路徑，則稱頂點vi和頂點Vj是連通的，若圖中任意兩頂點間都是相通的，則稱此圖是連通圖。3 .二叉樹有哪幾種基本形態(tài)？畫圖說明之。答案：六、操作題/綜合能力題原始序列答案：共需5趟7638651397275049第1趟結(jié)果3865137627504997第2趟結(jié)果3813652750497697第3趟結(jié)果

37、1338275049657697第4趟結(jié)果1327384950657697第5趟結(jié)果13273849506576972.若對序列(763865,139727,50,49）采用選擇排序法（按照值的大小從小到大）原始序列763865139727答案：第1趟結(jié)果7638651349275097第2趟結(jié)果5038651349277697第3趟結(jié)果5038271349657697第4趟結(jié)果4938271350657697第5趟結(jié)果1338274950657697第6趟結(jié)果1327384950657697第7趟結(jié)果1327384950657697進行排序，請分別在下表中寫出每一趟的結(jié)果:3.把 1 、50

38、494依次進棧（棧初始為空），任何時刻（只要棧不空），都可以出（退）棧，試寫出所有可能的出棧序列（如 答案：1234 )。1.若對序列（76,38,65,13,97,27,50,49）采用冒泡排序法（按照值的大小從小到大）進行排序，共需幾趟排序？請分別在下表中寫出每一趟的結(jié)果：271度頂4 .若一二叉樹有2度結(jié)點100個，則其葉結(jié)點有多少個？該二叉樹可以有多少個點？答案：5 .已知某非空二叉排序樹采用順序存儲結(jié)構依次將所有結(jié)點的數(shù)據(jù)信息存放于一維數(shù)組ABDIC口EF口口C口口晴分別寫出該二叉樹的前序遍歷序列與中序遍歷序列。答案:6 .二叉樹的順序存儲結(jié)構答案7 .給定30個字符組成的電文DDD

39、DDAAABEEAAFCDAACABBCCCBAADD試為字符A、B、C、D、E、F設計哈夫曼（Hufman）編碼。轉(zhuǎn)換為T2T3棵二叉樹。T4(1)畫出相應的哈夫曼樹；(2)分別列出A、B、C、D、E、F的哈夫曼碼;(3)計算該樹的帶權路徑長度WPL。答案:8 .試將森林 F= T1,T2,T3,T4 ©T1答案:9 .試畫出下列二叉樹的中序線索二叉樹存儲結(jié)構圖。二叉樹答案:10 .試用孩子兄弟(左孩子右兄弟)表示法畫出下列樹的存儲結(jié)構圖。樹答案：11 .已知二叉樹的前序遍歷序列和中序遍歷序列分別是：B,A,C,D,F,E,G和D,C,A,F,G,EB試畫出該二叉樹。答案：12 .

40、試用雙親表示法畫出下列樹T的存儲結(jié)構圖。/X®附T答案：13 .假定后序遍歷二叉樹的結(jié)果是A,C,B(1)試畫出所有可得到這一結(jié)果的不同形態(tài)的二叉樹;(2)分別寫出這些二叉樹的中序遍歷序列。14 .有9個帶權結(jié)點a、b、c、d、e、f、g、h、I,分別帶權4,2,7,12,6,10,5,9,3,試以他們?yōu)槿~子結(jié)點構造一棵哈夫曼樹(請按照左子樹根結(jié)點的權小于等于右子樹根結(jié)點的權的次序構造)。/答案：15 .某二叉樹的結(jié)點數(shù)據(jù)采用順序存儲表示如下：0123456V891011121314151617Z19EAFDHCGIB(1)試畫出此二叉樹的圖形表示。(2)寫出結(jié)點D的雙親結(jié)點及左、右

41、子女。/(3)將此二叉樹看作森林的二叉樹表示，試將它還原為森林。答案：百度文庫16 .圖的鄰接矩陣：及一答案：/17 .有向圖的逆鄰接表/©a/答案：18 .找出卜面網(wǎng)絡的最小生成樹。/二（eVM6募/答案：19.找出卜面網(wǎng)絡的最小生成樹：''JTo（用61-5答案：20 .試回出卜列圖的鄰接表。®-w圖答案：,z21 .對卜面的帶權無向圖米用prim算法從頂點28/開始構造取小生成樹。（與出加入生成樹百度文庫47頂點集合S和選擇邊Edge的順序）Edge:答案:（頂點，頂點，權值）22.對圖所示有向圖，試用Dijkstra算法求出從源點1到其它各頂點的最短

42、路徑，并寫出執(zhí)行算法過程中擴充結(jié)點的每次循環(huán)狀態(tài)。23.已某個不帶權的無向圖采用鄰接矩陣存儲方法依次將頂點的數(shù)據(jù)信息存放于一維數(shù)組ABCDEFGH請寫出從頂點中，邊的信息存放于鄰接矩陣中，鄰接矩陣為A出發(fā)對該圖進行深度有限搜索后得到的頂點序列。01100V答案:10001010010100100101000000110001000010'01V24 .試按表(10,8,9,12,20,5,6,15,19,25)中元素的排列次序,將所有元素插入一棵初始為空的二叉排序樹中，使之仍是一棵二叉排序樹。(1)試畫出插入完成之后的二叉排序樹；(2)若查找元素17,它將依次與二叉排序樹中哪些元素比較

43、大小？(3)假設每個元素的查找概率相等，試計算該樹的平均查找長度ASL。(4)對該樹進行中序遍歷，試寫出中序遍歷序列。答案：25 .已知一關鍵字序列為(40,11,16,31,23,55,13,45,50),試生成一棵平衡的二叉排序樹再從生成的平衡的二叉排序樹中刪除關鍵字45。26 設散列表的長度為13,散列函數(shù)為H(k)=k%13，給頂?shù)年P鍵碼序列為19,14,23,01,68,20,84,27。試畫出用線性探查法解決沖突時所構成的散列表。答案：26 .給出一組關鍵字(19,01,26,92,87,11,43,87,21)進行冒泡排序，試列出每一趟排序后關鍵字的排列次序，并比較每遍排序所進行

44、的關鍵字比較次數(shù)。答案：27 .設待排序序列為10,18,4,3,6,12,1,9,15,8,請給出用希爾排序每一趟的結(jié)果。增量序列取為5,3,2,1。答案：28 .對于給定鍵值：83,40,63,12,35,90,65,畫出堆排序各趟排序的結(jié)果。答案：29 .若對序列(49,38,65,97,76,13,27,50)采用選擇排序法排序，則各趟結(jié)束后序列。答案：第三章操作系統(tǒng)一、單項選擇題1 .操作系統(tǒng)的功能是進行處理機管理、()管理、設備管理和文件管理。A.進程B.存儲器C.硬件D.軟件答案：B2 .在計算機系統(tǒng)中，操作系統(tǒng)是()/A.一般應用軟件B.核心系統(tǒng)軟件C.用戶應用軟件D.用戶應用

45、軟件答案：B3 .如果分時系統(tǒng)的時間片一定，那么（）,則響應時間越長。A.用戶數(shù)越少B.用戶數(shù)越多C.內(nèi)存越少D.內(nèi)存越多答案：B/4 .操作系統(tǒng)中采用多道程序設計技術提高CPU和外部設備的（）。A.利用率B.可靠性C.穩(wěn)定性D.兼容性答案：A）5 .已知，作業(yè)的周轉(zhuǎn)時間=作業(yè)完成時間一作業(yè)的到達時間?，F(xiàn)有三個同時到達的作業(yè)J1,J2和J3,它們的執(zhí)行時間分別是T1,T2和T3,且T1<T2<T3。系統(tǒng)按單道方式運行且采用短作業(yè)優(yōu)先算法，則平均周轉(zhuǎn)時間是（）+ T2+T3/+（2/3）T2 +（1/3）T3答案：C6.任何兩個并發(fā)進程之間（A. 一定存在互斥關系C. 一定彼此獨立無

46、關 答案：DB.（T1 +T2 + T3）/3D. T1 + （1/2）T2+T3）B. 一定存在同步關系D.可能存在同步或互斥關系7 .進程從運行狀態(tài)進入就緒狀態(tài)的原因可能是（）A.被選中占有處理機B.等待某一事件C.等待的事件已發(fā)生D.時間片用完答案：D8 .一作業(yè)8:00到達系統(tǒng)，估計運行時間為1小時，若10:00開始執(zhí)行該作業(yè)，其響應比是（）8.1 答案：A9 .多道程序設計是指（）A.在實時系統(tǒng)中并發(fā)運行多個程序B.在分布系統(tǒng)中同一時刻運行多個程序C.在一臺處理機上同一時刻運行多個程序D.在一臺處理機上并發(fā)運行多個程序答案：D10 .文件系統(tǒng)采用多級目錄結(jié)構后，對于不同用戶的文件，其

47、文件名（）A.應該相同B.應該不同/C.可以相同，也可以不同'D.受系統(tǒng)約束/答案：C11 .在可變式分區(qū)分配方案中，某一作業(yè)完成后，系統(tǒng)收回其主存空間，并與相鄰空閑區(qū)合并，為此需修改空閑區(qū)表，造成空閑區(qū)數(shù)減、1的情況是（）A.無上鄰空閑區(qū)，也無下鄰空閑區(qū)B.有上鄰空閑區(qū)，但無下鄰空閑區(qū)C.有下鄰空閑區(qū)，但無上鄰空閑區(qū)D.有上鄰空閑區(qū)，也有下鄰空閑區(qū)答案：D12、某系統(tǒng)中有3個并發(fā)進程，都需要同類資源4個，試問該系統(tǒng)不會發(fā)生死鎖的最少資源數(shù)是（）。/A.9B.10C.11D.12答案：B13、操作系統(tǒng)的基本職能是（）。A.控制和管理系統(tǒng)內(nèi)各種資源，有效地組織多道程序的運行B.提供用戶界

48、面，方便用戶使用C.提供方便的可視化編輯程序/D.提供功能強大的網(wǎng)絡管理工具答案：A14、如果進程PA對信-號量S執(zhí)行P操作，則信-號量S的值應（A.力口1B.減1C.等于0D.小于0答案：B15、通常，用戶編寫的程序中所使用的地址是（B.物理地址A.邏輯地址C.絕對地址答案：A16、虛擬存儲管理策略可以（A .擴大物理內(nèi)存容量C.擴大邏輯內(nèi)存容量答案：C）。B.擴大物理外存容量D.擴大邏輯外存容量17、1在以下的文件物理存儲組織形式中，（）常用于存放大型的系統(tǒng)文件。A連續(xù)文件B.串連文件C.索引文件D.多重索引文件答案：D18、使用戶所編制的程序與實際使用的物理設備無關，這是由設備管理的（）

49、功能實現(xiàn)的。A.設備獨立性B.設備分配C.緩沖管理D.虛擬設備/答案：A19、引入緩沖技術的主要目的是（）。/A.改善用戶編程環(huán)境B.提高CPU的處理速度C.提高CPU與設備之間的并行程度/D.降低計算機的硬件成本答案：C20、銀行家算法可以實現(xiàn)死鎖的（）。A.預防B.避免C.檢測D.恢復答案：B二、多項選擇題1 .引入多道程序設計的主要目的在于（）A、提高實時響應速度/B、充分利用處理機，減少處理機空閑時間C、有利于代碼共享D、充分利用外圍設備E、減少存儲器碎片答案：BD2 .段式和頁式存儲管理的地址結(jié)構很類似，但是它們之間有實質(zhì)上的不同，表現(xiàn)為（）A、頁式的邏輯地址是連續(xù)的，段式的邏輯地址

50、可以不連續(xù)B、頁式的地址是一維的，段式的地址是二維的C、分頁是操作系統(tǒng)進行的，分段是用戶確定的D、各頁可以分散存放在主存，每段必須占用連續(xù)的主存空間E、頁式采用靜態(tài)重定位方式，段式采用動態(tài)重定位方式答案：ABCD3 .利用記錄的成組與分解操作能（）A、有效地實現(xiàn)信息轉(zhuǎn)儲B、提高存儲介質(zhì)的利用率C、減少操作系統(tǒng)的程序量D、增加啟動外設的次數(shù)E、提高文件的存取速度答案：ABE4 .線程是操作系統(tǒng)的概念，已具有線程管理的操作系統(tǒng)有（）A、WindowsB、OS/2C、WindowsNTD、DOS/E、Mach答案：BCE5 .文件的二級目錄結(jié)構由（）和（）組成。/A.根目錄B.子目錄C.主文件目錄D.用戶文件目錄E.當前目錄答案：CD6 .作業(yè)與進程的主要區(qū)別是（）和（）。A.前者是由用戶提交，后者是由系統(tǒng)自動生成/B.兩者執(zhí)行不同的程序段C.前者以用戶任務為單位，后者是操作系統(tǒng)控制的單位D.前者是批處理的，后者是分時的E.后者可并發(fā)執(zhí)行，前者則不行答案：AC三、判斷題1 .批處理系統(tǒng)的主要優(yōu)點是系統(tǒng)的吞吐量大、資源利用率高、系統(tǒng)的開銷較小。（）答案:T/2 .Windows2000操作系統(tǒng)是支持多任務的操作系統(tǒng)。（）答案：T3 .單級目錄結(jié)構能夠解決文件重名問題。（）答案：F4 .在分頁存儲管理中，頁的大小是可以不相等的。（）答案：F5 .原語是一種不可分