軟件技術(shù)基礎(chǔ)試題庫(kù)課程名稱(chēng)：軟件技術(shù)基礎(chǔ) 適用專(zhuān)業(yè)：軟件技術(shù)、計(jì)算機(jī)應(yīng)用、網(wǎng)絡(luò)、信息等計(jì)算機(jī)相關(guān)專(zhuān)業(yè)第一章 概述第二章 數(shù)據(jù)結(jié)構(gòu)一、單項(xiàng)選擇題1若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除它的第i數(shù)據(jù)元素之前，需要先依次向前移動(dòng)_個(gè)數(shù)據(jù)元素。( )A. n-iB. n+iC. n-i-1D. n-i+1答案：A2在單鏈表中，已知q指的結(jié)點(diǎn)是p指的結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若在q和p指的結(jié)點(diǎn)之間插入一個(gè)由s指的結(jié)點(diǎn)，則需執(zhí)行_。( )A. link(s)link(p)，link(p)sB. link(q)s，link(s)pC. link(p)link(s)，link(s)pD. link(p)s，link(s)q答案：B3高度為h(h>0) 的二叉樹(shù)最少有_個(gè)結(jié)點(diǎn)。（ ）A. hB. h-1 C. h+1D. 2h答案：A4n個(gè)頂點(diǎn)的帶權(quán)無(wú)向連通圖的最小生成樹(shù)包含 _ 個(gè)頂點(diǎn)。（）A.n-1 B.n C.n/2 D.n+1答案：B5采用拉鏈法解決沖突的散列表中，查找的平均查找長(zhǎng)度( )。A. 直接與關(guān)鍵字個(gè)數(shù)有關(guān) B. 直接與裝填因子 a 有關(guān) C. 直接與表的容量有關(guān) D. 直接與散列函數(shù)有關(guān)答案：D6樹(shù)型結(jié)構(gòu)最適合用來(lái)描述( )A.有序的數(shù)據(jù)元素 B.無(wú)序的數(shù)據(jù)元素C.數(shù)據(jù)元素之間的具有層次關(guān)系的數(shù)據(jù)D.數(shù)據(jù)元素之間沒(méi)有關(guān)系的數(shù)據(jù)答案：C7若二叉樹(shù)中度為2的結(jié)點(diǎn)有15個(gè)，度為1的結(jié)點(diǎn)有10個(gè)_個(gè)葉結(jié)點(diǎn)。( )A.25 B.10C.16 D.41答案：C 度0的結(jié)點(diǎn)比度2的結(jié)點(diǎn)多18若深度為6的完全二叉樹(shù)的第6層有3個(gè)葉結(jié)點(diǎn)，則該二叉樹(shù)一共有_個(gè)結(jié)點(diǎn)。( )A.32 B.33C.34 D.25答案：C9若某完全二叉樹(shù)的深度為h，則該完全二叉樹(shù)中至少有_個(gè)結(jié)點(diǎn)。( )A.2h B.2h-1C.2h-2D.2h-1+1答案：C10在非空二叉樹(shù)的中序遍歷序列中，二叉樹(shù)的根結(jié)點(diǎn)的左邊應(yīng)該( )A.只有左子樹(shù)上的所有結(jié)點(diǎn)B.只有左子樹(shù)上的部分結(jié)點(diǎn)C.只有右子樹(shù)上的所有結(jié)點(diǎn) D.只有右子樹(shù)上的部分結(jié)點(diǎn)答案：A11下面關(guān)于哈夫曼樹(shù)的說(shuō)法，不正確的是( )A.對(duì)應(yīng)于一組權(quán)值構(gòu)造出的哈夫曼樹(shù)一般不是唯一的B.哈夫曼樹(shù)具有最小帶權(quán)路徑長(zhǎng)度C.哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)D.哈夫曼樹(shù)中除了度為1的結(jié)點(diǎn)外，還有度為2的結(jié)點(diǎn)和葉結(jié)點(diǎn)答案：D12數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究計(jì)算機(jī)中 對(duì)象及其關(guān)系的學(xué)科。( )A. 數(shù)值運(yùn)算B.非數(shù)值運(yùn)算C.集合D.非集合答案：B13數(shù)據(jù)結(jié)構(gòu)的定義為(K，R)，其中K是 的集合。( )A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結(jié)構(gòu)答案：B14算法分析的目的是_。( )A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性答案：C15數(shù)據(jù)的不可分割的基本單位是 。( )A.元素B.結(jié)點(diǎn)C.數(shù)據(jù)類(lèi)型D.數(shù)據(jù)項(xiàng)答案：D16 是具有相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。( )A.數(shù)據(jù)符號(hào)B.數(shù)據(jù)對(duì)象C.數(shù)據(jù)D.數(shù)據(jù)結(jié)構(gòu)答案：B17數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的 及它們之間的相互聯(lián)系。（ ）A.理想結(jié)構(gòu)、物理結(jié)構(gòu)B.理想結(jié)構(gòu)、邏輯結(jié)構(gòu)C.物理結(jié)構(gòu)、邏輯結(jié)構(gòu)D.抽象結(jié)構(gòu)、邏輯結(jié)構(gòu)答案：C18組成數(shù)據(jù)的基本單位是 。（ ）A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)類(lèi)型C.數(shù)據(jù)元素D.數(shù)據(jù)變量答案：C19數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱(chēng)為 。（ ）A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)答案：C20算法指的是 。（ ）A計(jì)算機(jī)程序B解決問(wèn)題的計(jì)算方法C排序算法D解決問(wèn)題的有限運(yùn)算序列答案：D21. 由_組成的集合是一個(gè)數(shù)據(jù)對(duì)象。( )A.不同類(lèi)型的數(shù)據(jù)項(xiàng)B.不同類(lèi)型的數(shù)據(jù)元素C.相同類(lèi)型的數(shù)據(jù)項(xiàng)D.相同類(lèi)型的數(shù)據(jù)元素答案：D22關(guān)于順序存儲(chǔ)的敘述中,哪一條是不正確的。( )A.存儲(chǔ)密度大B.邏輯上相鄰的節(jié)點(diǎn)物理上不必鄰接C.可以通過(guò)計(jì)算直接確定第i個(gè)節(jié)點(diǎn)的位置D.插入、刪除操作不方便答案：B23一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是 100 ，每個(gè)元素的長(zhǎng)度為 2 ，則第 5 個(gè)元素的地址是 。（ ）A.110B.108C.100D.120 答案：B24已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)需要占m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為da，則第i個(gè)結(jié)點(diǎn)的地址為 。（ ）A.da+(i-1)*mB.da+i*mC.da-i*mD.da+(i+1)*m答案：A25鏈表是一種采用 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表。（ ） A.順序B.鏈?zhǔn)紺.星式D.網(wǎng)狀答案：B26線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址 。（ ）A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以答案：D27線性表在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。 ( )A.需經(jīng)常修改中的結(jié)點(diǎn)值B.需不斷對(duì)進(jìn)行刪除插入C.中含有大量的結(jié)點(diǎn)D.中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜答案：B28在長(zhǎng)度為 n 的順序表的第 i (1in+1) 個(gè)位置上插入一個(gè)元素，元素的移動(dòng)次數(shù)為 。（ ）A.n-i+1B.n-iC.iD.i-1答案：A29線性表是 。（ ）A.一個(gè)有限系列，可以為空B.一個(gè)有限系列，不能為空C.一個(gè)無(wú)限系列，可以為空D.一個(gè)無(wú)限系列，不能為空答案：A30. _是線性表。( )A.(孔子,諸葛亮,曹雪芹)B.A,B,C,DC.10,11,12,13,14D.(1,2,3,.)答案：A31. _ 是表示線性數(shù)據(jù)結(jié)構(gòu)的。( )A.循環(huán)鏈表B.鄰接多重表C.孩子鏈表D.單鏈表答案：D32. 將線性表的數(shù)據(jù)元素以_結(jié)構(gòu)存放, 查找一個(gè)數(shù)據(jù)元素所需時(shí)間不依賴(lài)于表長(zhǎng)。( )A.循環(huán)雙鏈表B.哈希(Hash)表C.一維數(shù)組D.單鏈表答案：C33. 在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行_。( )A.s->link=p;p->link=s;B.s->link=p->link;p->link=s;C.s->link=p->link;p=s;D.p->link=s;s->link=p;答案：34. 在循環(huán)鏈表中first為指向鏈表表頭的指針，current為鏈表當(dāng)前指針，在循環(huán)鏈表中檢測(cè)current是否達(dá)到鏈表表尾的語(yǔ)句是_。( )A.current->link=NULLB.first->link=currentC.first=currentD.current->link=first答案：35. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較_個(gè)結(jié)點(diǎn)。( )A.NB.n/2C.(n-1)/2D.(n+1)/2答案：36. 用鏈表表示線性表的優(yōu)點(diǎn)是_。 ( ) A. 便于隨機(jī)存取B. 花費(fèi)的存儲(chǔ)空間比順序表少C. 便于插入與刪除D. 數(shù)據(jù)元素的物理順序與邏輯順序相同答案：37. 當(dāng)需要隨機(jī)查找線性表的元素時(shí),宜采用_作存儲(chǔ)結(jié)構(gòu)。( )A.雙向鏈表B.循環(huán)鏈表C.順序表D.單鏈表答案：38. 線性表的鏈接實(shí)現(xiàn)有利于 運(yùn)算。( )A.插入B.讀表元C.查找D.定位答案：39. 線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址_。 ( ) A.必須是連續(xù)的B.部分地址是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以答案：40. 設(shè)單鏈表中指針p指著結(jié)點(diǎn)a，若要?jiǎng)h除a之后的結(jié)點(diǎn)（若存在），則需要修改指針的操作為_(kāi)。 ( ) A.p->next=p->next->nextB.p=p->nextC.p= p->next->nextD.p->next=p答案：A41. 向一個(gè)有127個(gè)元素順序表中插入一個(gè)新元素并保存原來(lái)順序不變，平均要移動(dòng) 個(gè)元素。( )A.64B.63.5C.63D.64.5答案：A42. 向一個(gè)有 127 個(gè)元素的順序表中刪除一個(gè)元素，平均要移動(dòng) 個(gè)元素。( )A.8B.63.5C.63D.7答案：C43_又稱(chēng)為FIFO表。( )A.隊(duì)列B.散列表C.棧D.哈希表答案：A44設(shè)依次進(jìn)入一個(gè)棧的元素序列為c,a,b,d,不可得到出棧的元素序列有_。( )A.a.b,c,dB.a,d,c,bC.b,a,d,cD.c,d,a,b答案：D45. 鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)比較明顯的優(yōu)點(diǎn)是_。( )A. 插入操作更加方便B. 通常不會(huì)出現(xiàn)棧滿(mǎn)的情況C. 不會(huì)出現(xiàn)?？盏那闆rD. 刪除操作更加方便答案：46. 在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的_。( )A. 前一個(gè)位置B. 后一個(gè)位置C. 隊(duì)頭元素位置D. 隊(duì)尾元素的前一位置答案：47. 若一個(gè)棧的輸入序列是1，2，3n，則輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是_。( )A.n-iB.iC.n-i+1D.n-i-1答案：C48. 棧的數(shù)組表示中，top為棧頂指針，?？盏臈l件是_。( )A.top=0B.top=maxSizeC.top=maxSizeD.top=-1答案：D49. 在數(shù)組表示的循環(huán)隊(duì)列中，front、rear分別為隊(duì)列的頭、尾指針，maxSize為數(shù)組的最大長(zhǎng)度，隊(duì)滿(mǎn)的條件是_。( )A.front=maxSizeB.(rear+1)%maxSize=frontC.rear=maxSizeD.rear=front答案：B50. 棧和隊(duì)列的共同特點(diǎn)是_。( )A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除D.沒(méi)有共同點(diǎn)答案：C51若非空隊(duì)列采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，front和rear分別為隊(duì)頭元素與隊(duì)列尾元素的指針，刪除此時(shí)隊(duì)列的一個(gè)元素的操作時(shí)依次執(zhí)行pfront，_ ，call RET(P)。( )A.frontlink(rear)B.rearlink(p)C.rearlink(front)D.frontlink(p)答案：52由兩個(gè)棧共享一個(gè)向量空間的好處是_。( )A減少存取時(shí)間，降低下溢發(fā)生的機(jī)率B節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率C減少存取時(shí)間，降低上溢發(fā)生的機(jī)率D節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率答案：53數(shù)組datam為循環(huán)隊(duì)列的存儲(chǔ)空間, front為隊(duì)頭指針, rare為隊(duì)尾指針,則執(zhí)行入隊(duì)的操作為_(kāi)。( )A.rare=rare+1B.rare=(rare+1)%(m-1)C.rare=(rare-1)%mD.rare=(rare+1)%m答案：D54. 將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用_。( )A.棧B.隊(duì)列C.鏈表D.數(shù)組答案：55高度為 h(h>0) 的二叉樹(shù)最少有 _ 個(gè)結(jié)點(diǎn)。( )A.hB.h-1C.h+1D.2h答案：A56樹(shù)型結(jié)構(gòu)最適合用來(lái)描述_。( )A.有序的數(shù)據(jù)元素B.無(wú)序的數(shù)據(jù)元素C.數(shù)據(jù)元素之間的具有層次關(guān)系的數(shù)據(jù)D.數(shù)據(jù)元素之間沒(méi)有關(guān)系的數(shù)據(jù)答案：C57有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是_。( )A.log2(n)B.log2(n)+1C.log2(n+1)D.log2(n)+1答案：BD58. _ 又是一棵滿(mǎn)二叉樹(shù)。( )A.二叉排序樹(shù)B.深度為5有31個(gè)結(jié)點(diǎn)的二叉樹(shù)C.有15個(gè)結(jié)點(diǎn)的完全二叉樹(shù)D.哈夫曼(Huffman)樹(shù)(沒(méi)有度為1的結(jié)點(diǎn))答案：C59. 深度為k的滿(mǎn)二叉樹(shù)有_個(gè)分枝結(jié)點(diǎn)。( )A.2k-1B.2k-1-1C.2k+1D.2k-1+1答案：60. 若已知一棵二叉樹(shù)先序序列為ABCDEFG，中序序列為CBDAEGF，則其后序序列為_(kāi)。( )A.CDBGFEAB.CDBFGEAC.CDBAGFED.BCDAGFE答案：A61. 二叉樹(shù)第i(i>=1)層上至多有 結(jié)點(diǎn)。( )A.iB.iC.iD.i答案：C62. 在一棵具有5層的滿(mǎn)二叉樹(shù)中結(jié)點(diǎn)總數(shù)為_(kāi)。( )A. 31B. 32C. 33D. 16答案：A63. 一個(gè)二叉樹(shù)按順序方式存儲(chǔ)在一個(gè)維數(shù)組中，如圖0 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEFGHIJ則結(jié)點(diǎn)E在二叉樹(shù)的第 層。( )A.1B.2C.3D.4答案：C64在一棵度為3的樹(shù)中,度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2 的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為_(kāi)。( )A4B5C6D7答案：C65n 個(gè)頂點(diǎn)的帶權(quán)無(wú)向連通圖的最小生成樹(shù)包含 _ 個(gè)頂點(diǎn)。( )A.n-1B.nC.n/2D.n+1答案：B66具有 n 個(gè)頂點(diǎn)的有向完全圖有 條弧。( )A.nB.n*(n-1)C.n*(n+1)D.n*n答案：B67. n 個(gè)頂點(diǎn)的連通圖至少有 條邊。( )A.n-1 B.n C.n+1 D.0答案：68在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的 倍。( )A1/2B1C2D4答案：69在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中,零元素的個(gè)數(shù)為_(kāi)。( )AeB2eCn2eDn22e答案：D70折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次與表中元素_進(jìn)行比較。( )A.65,15,37B.68,30,37C.65,15,30D.65,15,30,37答案：D71對(duì)有3600個(gè)記錄的索引順序表(分塊表)進(jìn)行查找,最理想的塊長(zhǎng)為_(kāi)。( )A.1800B.60C.1200D.log2 3600答案：B72. 折半查找20個(gè)記錄的有序表,若查找失敗,比較關(guān)鍵字的次數(shù)_。( )A.最多為6B.最多為5C.最多為4D.最多為3答案：B73. 中序遍歷一棵二叉排序樹(shù)所得到的結(jié)點(diǎn)序列是鍵值的 序列。( )A.遞增或遞減B.遞減C.遞增D.無(wú)序答案：C74散列表中的沖突是指_。( )A.兩個(gè)元素具有相同的序號(hào)B.兩個(gè)元素的鍵值相同，而其他屬性相同C.不同的鍵值對(duì)應(yīng)相同的存儲(chǔ)地址D.數(shù)據(jù)元素的地址相同答案：75用線形探測(cè)法查找散列表，可能要探測(cè)多個(gè)散列地址，這些位置上的鍵值_。( )A.一定是同義詞B.不一定是同義詞C.一定不是同義詞D.都相同答案：76在初始為空的雜湊表中依次插入關(guān)鍵字序列(MON，TUE，WED，THU，F(xiàn)RI，SAT，SUN), 雜湊函數(shù)為H(k)=i MOD 7，其中，i為關(guān)鍵字k的第一個(gè)字母在英文字母表中的序號(hào)，地址值域?yàn)?:6，采用線性再散列法處理沖突。插入后的雜湊表應(yīng)該如_所示。( )A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MONB. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MONC. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MOND. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON答案：77設(shè)有一個(gè)含200個(gè)表項(xiàng)的散列表，用線性探查法解決沖突，按關(guān)鍵碼查詢(xún)時(shí)找到一個(gè)表項(xiàng)的平均探查次數(shù)不超過(guò)1.5，則散列存儲(chǔ)空間應(yīng)能夠至少容納 個(gè)表項(xiàng)。（設(shè)搜索成功的平均搜索長(zhǎng)度為Snl=(1+1/(1-a)/2,其中a 為裝填因子）( )A.400B.526C.624D.676答案：78對(duì)長(zhǎng)度為10的表作選擇(簡(jiǎn)單選擇)排序,共需比較_次關(guān)鍵字。( )A.45B.90C.55D.110答案：79. 設(shè)有100個(gè)數(shù)據(jù)元素，采用折半搜索時(shí)，最大比較次數(shù)為 ( )。A. 6B. 7C. 8D. 10答案：A80. 對(duì)待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對(duì)兩個(gè)子序列施加同樣的排序操作，直到子序列為空或只剩一個(gè)元素為止。這樣的排序方法是_。( )A. 選擇排序B. 直接插入排序C. 快速排序D. 起泡排序答案：C81. 對(duì)5個(gè)不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行 次比較。( )A. 8B. 10C. 15D. 25答案：82. 采用折半查找方法進(jìn)行查找，數(shù)據(jù)文件應(yīng)為 ，且限于 。( )A.有序表 順序存儲(chǔ)結(jié)構(gòu)B.有序表 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.隨機(jī)表 順序存儲(chǔ)結(jié)構(gòu)D.隨機(jī)表 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)答案：A83. 從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其存放在已排序序列的合適位置，該排序方法稱(chēng)為 排序法。( )A.插入B.選擇C.希爾D.二路并歸答案：A84. 就平均查找速度而言，下列幾種查找速度從慢至快的關(guān)系是 。( )A.順序 折半 哈西 分塊B.順序 分塊 折半 哈西C.分塊 折半 哈西 順序D.順序 哈西 分塊 折半答案：B85. 在下列算法中， 算法可能出現(xiàn)下列情況：在最后一趟開(kāi)始之前，所有的元素都不在其最終的位置上。( )A.堆排序B.冒泡排序C.插入排序D.快速排序答案：C86堆是一個(gè)鍵值序列( K1, K2, , Kn )，對(duì) I = 1,2n/2, 滿(mǎn)足 。( )A.Ki <= K2i <= K2i+1B.Ki < K2i+1 < K2i C.Ki <= K2i 且 Ki <=K2i+1D. Ki <= K2i 或 Ki <= K2i+1答案：87對(duì)于關(guān)鍵字序列 46 ， 58 ， 15 ， 45 ， 90 ， 18 ， 10 ， 62 ，其快速排序第一趟的結(jié)果是 。( )A.15 45 18 46 10 62 58 90B.10 15 18 45 46 58 62 90C.10 18 15 45 46 90 58 62D.15 10 18 45 46 62 58 90答案：88用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84則所采用的排序方法是 。( )A.選擇排序B.希爾排序C.歸并排序D.快速排序答案：89下列關(guān)鍵字序列中 是堆。( )A16，72，31，23，94，53B94，23，31，72，16，53C16，53，23，94，31，72D16，23，53，31，94，72答案：90目前以比較為基礎(chǔ)的內(nèi)部排序方法中，其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無(wú)關(guān)的是 。( )A插入排序B直接選擇排序C快速排序D冒泡排序答案：B91對(duì)n個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為 。( )An+1BnCn-1Dn(n-1)/2答案：D二、多項(xiàng)選擇題1根據(jù)數(shù)據(jù)元素之間的不同特性，通常具有 這幾種基本數(shù)據(jù)結(jié)構(gòu)。( )A. 集合B. 線形結(jié)構(gòu)C. 樹(shù)型結(jié)構(gòu)D. 圖型結(jié)構(gòu)答案：ABCD2數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有 兩種不同的表示方法。( )A. 順序存儲(chǔ)結(jié)構(gòu)B. 二叉樹(shù)存儲(chǔ)結(jié)構(gòu)C. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D. 網(wǎng)絡(luò)結(jié)構(gòu)答案：AC3查找哈希(Hash)表,解決沖突的的方法有_。( )A.除留余數(shù)法B.線性探測(cè)再散列法C.直接地址法D.鏈地址法答案：BD三、判斷題1非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接前驅(qū)元素。( )答案：F2數(shù)組是一種沒(méi)有插入與刪除操作的線性結(jié)構(gòu)。( )答案：T3非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接后繼元素。( )答案：F4數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)不僅有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，還有索引結(jié)構(gòu)與散列結(jié)構(gòu)。( )答案：F5線性鏈表中各個(gè)鏈結(jié)點(diǎn)之間的地址不一定要連續(xù)。( )答案：T6若頻繁地對(duì)線性表進(jìn)行插入和刪除操作，該線性表采用順序存儲(chǔ)結(jié)構(gòu)更合適。( )答案：F7.若線性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素占用4個(gè)存儲(chǔ)單元，第12個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為144，則第1個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是101。( 100 )答案：F8.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除表的第i個(gè)元素之前需要移動(dòng)表中n-i+1個(gè)元素。( )答案：F9.符號(hào)link(p)出現(xiàn)在表達(dá)式中表示p所指的那個(gè)結(jié)點(diǎn)的內(nèi)容。( )答案：F10.要將指針p移到它所指的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)是執(zhí)行語(yǔ)句plink(p)。( )答案：T11.在非空線性鏈表中由p所指的結(jié)點(diǎn)后面插入一個(gè)由q所指的結(jié)點(diǎn)的過(guò)程是依次執(zhí)行語(yǔ)句：link(q)link(p);link(p)q。( )答案：T12.在非空雙向循環(huán)鏈表中由q所指的結(jié)點(diǎn)后面插入一個(gè)由p指的結(jié)點(diǎn)的動(dòng)作依次為：llink(p)q,rlink(p)rlink(q),rlink(q)p,llink(rlink(q)p。( )答案：F13.若某堆棧的輸入序列為1,2,3,4，則4,3,1,2不可能是堆棧的輸出序列之一。( )答案：T14.刪除非空鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的堆棧(設(shè)棧頂指針為top)的一個(gè)元素的過(guò)程是依次執(zhí)行:ptop,toplink(p),call RET(p)。( )答案：T15.若隊(duì)列采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，隊(duì)頭指針與指針?lè)謩e為front和rear，向隊(duì)列中插入一個(gè)數(shù)據(jù)信息為item的新元素的過(guò)程是依次執(zhí)行:call GETNODE(p),data(P)item,rearp,frontp。( )答案：F16數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè)方面。( )答案：T17非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接前驅(qū)元素。( )答案：F18在順序表中取出第 i 個(gè)元素所花費(fèi)的時(shí)間與 i 成正比。（ ）答案：F19完全二叉樹(shù)就是滿(mǎn)二叉樹(shù)。( )滿(mǎn)二叉樹(shù)是完全二叉樹(shù)答案：F20已知一棵二叉樹(shù)的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹(shù)。( )答案：T21有向圖是一種非線性結(jié)構(gòu)。( )答案：T22帶權(quán)連通圖的最小生成樹(shù)的權(quán)值之和一定小于它的其它生成樹(shù)的權(quán)值之和。( )答案：T23對(duì)二叉排序樹(shù)遍歷的結(jié)果是一個(gè)有序序列。（ ）答案：T24折半查找方法適用于按值有序的線性鏈表的查找。( )答案：F25非空二叉排序樹(shù)的任意一棵子樹(shù)也是二叉排序樹(shù)。( )答案：T26哈希表的查找效率主要取決于所選擇的哈希函數(shù)與處理沖突的方法。( )答案：T四、填空題1已知具有n個(gè)元素的一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)元素的地址為L(zhǎng)OC(a1)，那么，LOC(ai)=_。答案：LOC(a1)+(n-1)k2若一棵二叉樹(shù)有10個(gè)葉結(jié)點(diǎn)，則該二叉樹(shù)中度為2的結(jié)的點(diǎn)個(gè)數(shù)為_(kāi)。答案：43設(shè) SQ 為循環(huán)隊(duì)列，存儲(chǔ)在數(shù)組 dm 中，則 SQ 出隊(duì)操作對(duì)其隊(duì)頭指針 front 的修改是 _ 。答案：4n(n>0) 個(gè)結(jié)點(diǎn)二叉樹(shù)對(duì)應(yīng)的森林最多包含_ 棵非空樹(shù)。答案：5深度為 n(n>0) 的二叉樹(shù)最多有 _ 個(gè)結(jié)點(diǎn)。 答案：2的n次方-16n(n>0) 個(gè)結(jié)點(diǎn)、 (n-1) 條邊的連通無(wú)向圖中，頂點(diǎn)度數(shù)最大值為 _ 。 答案：2（n-1）7在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊的數(shù)目的_2_倍。答案：8圖的深度優(yōu)先搜索方法類(lèi)似于二叉樹(shù)的_遍歷。答案：9帶權(quán)連通圖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（注：頂點(diǎn)偶對(duì)右下角的數(shù)據(jù)為邊上的權(quán)值），G的最小生成樹(shù)的權(quán)值之和為_(kāi)。答案：10.將數(shù)據(jù)元素2,4,6,8,10,12,14,16,18,20依次存放于一個(gè)一維數(shù)組中，然后采用折半查找方法查找元素12，被比較過(guò)的數(shù)組元素的下標(biāo)依次為_(kāi)。答案：11.每趟排序從未排序的子序列中依次取出元素與已經(jīng)排好序的序列中元素進(jìn)行比較，然后將其放在已經(jīng)排好序的序列的合適位置。這種排序法稱(chēng)為_(kāi)簡(jiǎn)單選擇_排序法。答案：12.從未排序序列中選擇一個(gè)元素，該元素將當(dāng)前參加排序的那些元素分成前后兩個(gè)部分，前一部分中所有元素都小于等于所選元素，后一部分中所有元素都大于或等于所選元素，而此時(shí)所選元素處在排序的最終位置。這種排序法稱(chēng)為_(kāi)快速_排序法。答案：13.對(duì)序列(49,38,65,97,76,27,13,50)采用快速排序法進(jìn)行排序，以序列的第一個(gè)元素為基準(zhǔn)元素得到的劃分結(jié)果是_。答案：38 27 13 49 65 97 76 50 14一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(映象)稱(chēng)為 _。答案：15數(shù)據(jù)結(jié)構(gòu)被形式地定義為（ D, R ），其中 D 是 數(shù)據(jù)元素 的有限集合， R 是 D 上的 有限集合。 答案：16數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的_無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。答案：17一個(gè)算法具有5個(gè)特性:_、_、_、有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。答案：18線性表中 _ 稱(chēng)為表的長(zhǎng)度。答案：19設(shè)長(zhǎng)度為n的線性表順序存貯,若在它的第i-1和第i個(gè)元素之間插入一個(gè)元素, 共需移動(dòng) _ 個(gè)元素(1<in)。答案：20在單鏈表中要在已知結(jié)點(diǎn)*p之前插入一新結(jié)點(diǎn)，需找到 。答案：21循環(huán)鏈表的主要優(yōu)點(diǎn)是 。答案：從任何一個(gè)結(jié)點(diǎn)出發(fā)可以遍歷所有結(jié)點(diǎn)22在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：q=p->link;p->link=_ _Delete q答案：23設(shè) SQ 為循環(huán)隊(duì)列，存儲(chǔ)在數(shù)組 dm 中，則 SQ 出隊(duì)操作對(duì)其隊(duì)頭指針 front 的修改是 _ 。答案：24棧中元素的進(jìn)出原則為 _先進(jìn)后出_ 。答案：25在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個(gè) 結(jié)構(gòu)，其主要特點(diǎn)是 。答案：26對(duì)于一個(gè)以順序?qū)崿F(xiàn)的循環(huán)隊(duì)列Q0m-1，隊(duì)頭、隊(duì)尾指針?lè)謩e為f、r，其判空的條件是f=r ，判滿(mǎn)的條件是 (r+1)%m=f 。答案：r=f、(r+1)%m=f27在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿(mǎn)時(shí)共有_個(gè)元素。答案：28深度為 n(n>0) 的二叉樹(shù)最多有 _ 個(gè)結(jié)點(diǎn)。答案：2的n次方-129n(n>0) 個(gè)結(jié)點(diǎn)、 (n-1) 條邊的連通無(wú)向圖中，頂點(diǎn)度數(shù)最大值為 _2（n-1）_ 。答案：30一棵深度為6的滿(mǎn)二叉樹(shù)有_31_個(gè)非終端結(jié)點(diǎn)。答案：31若一棵二叉樹(shù)中有8個(gè)度為2的結(jié)點(diǎn),則它有_9_個(gè)葉子。答案：32樹(shù)中結(jié)點(diǎn)A的 _擁有的后件個(gè)數(shù)_ 稱(chēng)為結(jié)點(diǎn)A的度。答案：33一棵深度為4的二叉樹(shù)最多有 _15_ 個(gè)結(jié)點(diǎn)。答案：34將 樹(shù)轉(zhuǎn)化為二叉樹(shù)時(shí)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。答案：35哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度 最小 的樹(shù)，通常權(quán)值較大的結(jié)點(diǎn)離根結(jié)點(diǎn) 近 。答案：36具有n個(gè)葉子的二叉樹(shù)，每個(gè)葉子的權(quán)值為wi(1in)其中帶權(quán)路徑最小的二叉樹(shù)被稱(chēng)為 哈夫曼樹(shù)（最優(yōu)二叉樹(shù)） 。答案：37若已知一棵二叉樹(shù)的先序序列為 + a * b c d / e f，中序序列為a + b * c d e / f，則其后序序列為_(kāi)。答案：38已知一棵完全二叉樹(shù)中共有768結(jié)點(diǎn)，則該樹(shù)中共有_個(gè)葉子結(jié)點(diǎn)。答案：39已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，且僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為30，則總結(jié)點(diǎn)數(shù)為 129 。答案：50+30+49=12940具有10個(gè)頂點(diǎn)的無(wú)向圖,邊的總數(shù)最多為 _ 。答案：41在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá) n-1 。答案：42有向圖g用鄰接矩陣am,1m來(lái)存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的。答案：43有n個(gè)球隊(duì)參加的足球聯(lián)賽按主客場(chǎng)制進(jìn)行比賽，共需進(jìn)行 場(chǎng)比賽。答案：44帶權(quán)連通圖G=<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，(注：頂點(diǎn)偶對(duì)右下角的數(shù)據(jù)為邊上的權(quán)值)，G的最小生成樹(shù)的權(quán)值之和為_(kāi) 。答案：45順序查找n個(gè)元素的順序表,當(dāng)使用監(jiān)視哨時(shí),若查找成功,比較關(guān)鍵字的次數(shù)至少為_(kāi)次, 最多為_(kāi)次；若查找失敗,比較關(guān)鍵字的次數(shù)為_(kāi)次。答案：46在單鏈表上難以實(shí)現(xiàn)的排序方法有 、 和 。答案：快速排序、堆排序、希爾排序 五、簡(jiǎn)答題/問(wèn)答題/綜述題1什么是順序表？順序表的特點(diǎn)是什么？答案：線性表的順序存儲(chǔ)是指在內(nèi)存中用一塊地址連續(xù)的存儲(chǔ)空間順序存放線性表的各元素，用這種形式存儲(chǔ)的線性表稱(chēng)為順序表。數(shù)據(jù)元素在順序表中物理位置取決于數(shù)據(jù)元素在線性表中的邏輯位置，可得出順序表的特點(diǎn)：邏輯位置相鄰，其物理位置也相鄰。2什么樣的圖是連通圖？答案：在無(wú)向圖G中，如果從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(ij)有路徑，則稱(chēng)頂點(diǎn)vi和頂點(diǎn)vj是連通的，若圖中任意兩頂點(diǎn)間都是相通的，則稱(chēng)此圖是連通圖。3二叉樹(shù)有哪幾種基本形態(tài)? 畫(huà)圖說(shuō)明之。答案：二叉樹(shù)，滿(mǎn)二叉樹(shù)，完全二叉樹(shù)六、操作題/綜合能力題1若對(duì)序列(76，38，65，13，97，27，50，49)采用冒泡排序法(按照值的大小從小到大)進(jìn)行排序，共需幾趟排序？請(qǐng)分別在下表中寫(xiě)出每一趟的結(jié)果：5分所以應(yīng)該寫(xiě)5趟原始序列 76 38 65 13 97 27 50 49答案：共需5趟第1趟結(jié)果3865137627504997第2趟結(jié)果3813652750497697第3趟結(jié)果1338275049657697第4趟結(jié)果1327384950657697第5趟結(jié)果13273849506576972若對(duì)序列(76，38，65，13，97，27，50，49)采用選擇排序法(按照值的大小從小到大)進(jìn)行排序，請(qǐng)分別在下表中寫(xiě)出每一趟的結(jié)果：原始序列 76 38 65 13 97 27 50 49答案：第1趟結(jié)果7638651349275097第2趟結(jié)果5038651349277697第3趟結(jié)果5038271349657697第4趟結(jié)果4938271350657697第5趟結(jié)果1338274950657697第6趟結(jié)果1327384950657697第7趟結(jié)果13273849506576973把 1 、 2 、 3 、 4依次進(jìn)棧（棧初始為空），任何時(shí)刻（只要棧不空），都可以出（退）棧，試寫(xiě)出所有可能的出棧序列（如 1234 ）。 答案：4若一二叉樹(shù)有 2 度結(jié)點(diǎn) 100個(gè)，則其葉結(jié)點(diǎn)有多少個(gè)？該二叉樹(shù)可以有多少個(gè) 1 度頂點(diǎn)？答案：葉結(jié)點(diǎn)101個(gè) 1度結(jié)點(diǎn)可以有 101個(gè)5已知某非空二叉排序樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)依次將所有結(jié)點(diǎn)的數(shù)據(jù)信息存放于一維數(shù)組ABDICEFCH，請(qǐng)分別寫(xiě)出該二叉樹(shù)的前序遍歷序列與中序遍歷序列。答案：6二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu):答案：7給定30個(gè)字符組成的電文:D D D D D A A A B E E A A F C D A A C A B B C C C B A A D D試為字符 A、B、C、D、E、F 設(shè)計(jì)哈夫曼(Huffman)編碼。 (1)畫(huà)出相應(yīng)的哈夫曼樹(shù)； (2)分別列出 A、B、C、D、E、F 的哈夫曼碼；(3)計(jì)算該樹(shù)的帶權(quán)路徑長(zhǎng)度WPL。答案：8試將森林 F= T1,T2,T3,T4 轉(zhuǎn)換為一棵二叉樹(shù)。 T1 T2 T3 T4答案：9試畫(huà)出下列二叉樹(shù)的中序線索二叉樹(shù)存儲(chǔ)結(jié)構(gòu)圖。 二叉樹(shù)答案：10試用孩子兄弟(左孩子右兄弟)表示法畫(huà)出下列樹(shù)的存儲(chǔ)結(jié)構(gòu)圖。 樹(shù)答案：11已知二叉樹(shù)的前序遍歷序列和中序遍歷序列分別是：B,A,C,D,F,E,G和D,C,A,F,G,E,B, 試畫(huà)出該二叉樹(shù)。答案：12試用雙親表示法畫(huà)出下列樹(shù)T的存儲(chǔ)結(jié)構(gòu)圖。答案：13假定后序遍歷二叉樹(shù)的結(jié)果是A,C,B(1)試畫(huà)出所有可得到這一結(jié)果的不同形態(tài)的二叉樹(shù)；(2)分別寫(xiě)出這些二叉樹(shù)的中序遍歷序列。答案：14有9個(gè)帶權(quán)結(jié)點(diǎn) a、b、c、d、e、f、g、h、I，分別帶權(quán) 4，2，7，12，6，10，5，9，3，試以他們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)（請(qǐng)按照左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)造）。答案：15某二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)表示如下：(1) 試畫(huà)出此二叉樹(shù)的圖形表示。(2) 寫(xiě)出結(jié)點(diǎn)D的雙親結(jié)點(diǎn)及左、右子女。(3) 將此二叉樹(shù)看作森林的二叉樹(shù)表示，試將它還原為森林。答案：16圖的鄰接矩陣:答案：17有向圖的逆鄰接表: 答案：18找出下面網(wǎng)絡(luò)的最小生成樹(shù)。 答案：19找出下面網(wǎng)絡(luò)的最小生成樹(shù):答案：20試畫(huà)出下列圖的鄰接表。 圖答案：21對(duì)下面的帶權(quán)無(wú)向圖采用prim算法從頂點(diǎn) 開(kāi)始構(gòu)造最小生成樹(shù)。（寫(xiě)出加入生成樹(shù)頂點(diǎn)集合S和選擇邊Edge的順序）S:頂點(diǎn)號(hào)Edge:(頂點(diǎn)，頂點(diǎn)，權(quán)值)( ， ， )( ， ， ) ( ， ， )( ， ， )( ， ， ) 答案：5462311015410304101522022對(duì)圖所示有向圖，試用Dijkstra算法求出從源點(diǎn)1到其它各頂點(diǎn)的最短路徑，并寫(xiě)出執(zhí)行算法過(guò)程中擴(kuò)充結(jié)點(diǎn)的每次循環(huán)狀態(tài)。答案：23已某個(gè)不帶權(quán)的無(wú)向圖采用鄰接矩陣存儲(chǔ)方法依次將頂點(diǎn)的數(shù)據(jù)信息存放于一維數(shù)組ABCDEFGH中，邊的信息存放于鄰接矩陣中，鄰接矩陣為0 1 1 0 0 0 0 01 0 0 0 1 0 1 11 0 0 1 0 1 0 00 0 1 0 0 1 0 00 1 0 0 0 0 0 10 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 請(qǐng)寫(xiě)出從頂點(diǎn)A出發(fā)對(duì)該圖進(jìn)行深度有限搜索后得到的頂點(diǎn)序列。答案：24試按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 將所有元素插入一棵初始為空的二叉排序樹(shù)中, 使之仍是一棵二叉排序樹(shù)。 (1)試畫(huà)出插入完成之后的二叉排序樹(shù)； (2)若查找元素17,它將依次與二叉排序樹(shù)中哪些元素比較大小? (3)假設(shè)每個(gè)元素的查找概率相等,試計(jì)算該樹(shù)的平均查找長(zhǎng)度ASL。 (4)對(duì)該樹(shù)進(jìn)行中序遍歷,試寫(xiě)出中序遍歷序列。答案：25已知一關(guān)鍵字序列為（40，11，16，31，23，55，13，45，50），試生成一棵平衡的二叉排序樹(shù),再?gòu)纳傻钠胶獾亩媾判驑?shù)中刪除關(guān)鍵字45。3設(shè)散列表的長(zhǎng)度為13，散列函數(shù)為H(k) = k % 13，給頂?shù)年P(guān)鍵碼序列為19, 14, 23, 01, 68, 20, 84, 27。試畫(huà)出用線性探查法解決沖突時(shí)所構(gòu)成的散列表。答案：26給出一組關(guān)鍵字（19，01，26，92，87，11，43，87，21）進(jìn)行冒泡排序，試列出每一趟排序后關(guān)鍵字的排列次序，并比較每遍排序所進(jìn)行的關(guān)鍵字比較次數(shù)。答案：27設(shè)待排序序列為 10, 18, 4, 3, 6, 12, 1, 9, 15, 8，請(qǐng)給出用希爾排序每一趟的結(jié)果。增量序列取為5, 3, 2, 1。答案：28對(duì)于給定鍵值： 83， 40， 63， 12， 35， 90， 65, 畫(huà)出堆排序各趟排序的結(jié)果。答案：29若對(duì)序列(49，38，65，97，76，13，27，50)采用選擇排序法排序，則各趟結(jié)束后序列。答案：第三章 操作系統(tǒng)一、單項(xiàng)選擇題1. 操作系統(tǒng)的功能是進(jìn)行處理機(jī)管理、（ ）管理、設(shè)備管理和文件管理。A. 進(jìn)程 B. 存儲(chǔ)器 C.硬件 D.軟件答案：B2. 在計(jì)算機(jī)系統(tǒng)中，操作系統(tǒng)是（ ）A.一般應(yīng)用軟件 B.核心系統(tǒng)軟件 C.用戶(hù)應(yīng)用軟件 D.用戶(hù)應(yīng)用軟件答案：B3. 如果分時(shí)系統(tǒng)的時(shí)間片一定，那么（ ），則響應(yīng)時(shí)間越長(zhǎng)。A.用戶(hù)數(shù)越少 B.用戶(hù)數(shù)越多C.內(nèi)存越少 D.內(nèi)存越多答案：B4. 操作系統(tǒng)中采用多道程序設(shè)計(jì)技術(shù)提高CPU和外部設(shè)備的（ ）。A.利用率 B.可靠性 C.穩(wěn)定性 D.兼容性答案：A5.已知，作業(yè)的周轉(zhuǎn)時(shí)間=作業(yè)完成時(shí)間作業(yè)的到達(dá)時(shí)間?，F(xiàn)有三個(gè)同時(shí)到達(dá)的作業(yè)J1，J2和J3，它們的執(zhí)行時(shí)間分別是T1，T2和T3，且T1<T2<T3。系統(tǒng)按單道方式運(yùn)行且采用短作業(yè)優(yōu)先算法，則平均周轉(zhuǎn)時(shí)間是()A.T1T2T3 B.(T1T2T3)/3C.T1(2/3)T2(1/3)T3D.T1(1/2)T2T3答案：C6.任何兩個(gè)并發(fā)進(jìn)程之間()A.一定存在互斥關(guān)系B.一定存在同步關(guān)系C.一定彼此獨(dú)立無(wú)關(guān)D.可能存在同步或互斥關(guān)系答案：D7.進(jìn)程從運(yùn)行狀態(tài)進(jìn)入就緒狀態(tài)的原因可能是()A.被選中占有處理機(jī) B.等待某一事件C.等待的事件已發(fā)生 D.時(shí)間片用完答案：D8.一作業(yè)8：00到達(dá)系統(tǒng)，估計(jì)運(yùn)行時(shí)間為1小時(shí)，若10：00開(kāi)始執(zhí)行該作業(yè)，其響應(yīng)比是()A.2 B.1 C.3 D.0.5答案：A9.多道程序設(shè)計(jì)是指()A.在實(shí)時(shí)系統(tǒng)中并發(fā)運(yùn)行多個(gè)程序B.在分布系統(tǒng)中同一時(shí)刻運(yùn)行多個(gè)程序C.在一臺(tái)處理機(jī)上同一時(shí)刻運(yùn)行多個(gè)程序D.在一臺(tái)處理機(jī)上并發(fā)運(yùn)行多個(gè)程序答案：D10.文件系統(tǒng)采用多級(jí)目錄結(jié)構(gòu)后，對(duì)于不同用戶(hù)的文件，其文件名()A.應(yīng)該相同 B.應(yīng)該不同C.可以相同，也可以不同 D.受系統(tǒng)約束答案：C11.在可變式分區(qū)分配方案中，某一作業(yè)完成后，系統(tǒng)收回其主存空間，并與相鄰空閑區(qū)合并，為此需修改空閑區(qū)表，造成空閑區(qū)數(shù)減1的情況是()A. 無(wú)上鄰空閑區(qū)，也無(wú)下鄰空閑區(qū)B. 有上鄰空閑區(qū)，但無(wú)下鄰空閑區(qū)C. 有下鄰空閑區(qū)，但無(wú)上鄰空閑區(qū)D.有上鄰空閑區(qū)， 也有下鄰空閑區(qū)答案：D12、某系統(tǒng)中有3個(gè)并發(fā)進(jìn)程，都需要同類(lèi)資源4個(gè)，試問(wèn)該系統(tǒng)不會(huì)發(fā)生死鎖的最少資源數(shù)是（ ）。A9 B10 C11 D12答案：B13、操作系統(tǒng)的基本職能是（ ）。A控制和管理系統(tǒng)內(nèi)各種資源，有效地組織多道程序的運(yùn)行 B提供用戶(hù)界面，方便用戶(hù)使用 C提供方便的可視化編輯程序D提供功能強(qiáng)大的網(wǎng)絡(luò)管理工具答案：A14、如果進(jìn)程PA對(duì)信號(hào)量S執(zhí)行P操作，則信號(hào)量S的值應(yīng)（ ）。A加1 B減1 C等于0 D小于0答案：B15、通常，用戶(hù)編寫(xiě)的程序中所使用的地址是（ ）。A邏輯地址 B物理地址 C絕對(duì)地址 D內(nèi)存地址答案：A16、虛擬存儲(chǔ)管理策略可以（ ）。A擴(kuò)大物理內(nèi)存容量 B擴(kuò)大物理外存容量 C擴(kuò)大邏輯內(nèi)存容量