軟件技術(shù)基礎(chǔ)試題庫(kù).doc

精品文檔軟件技術(shù)基礎(chǔ)試題庫(kù)課程名稱：軟件技術(shù)基礎(chǔ) 適用專業(yè)：軟件技術(shù)、計(jì)算機(jī)應(yīng)用、網(wǎng)絡(luò)、信息等計(jì)算機(jī)相關(guā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(h0) 的二叉樹最少有_個(gè)結(jié)點(diǎn)。（ ）A. hB. h-1 C. h+1D. 2h答案：A4n個(gè)頂點(diǎn)的帶權(quán)無向連通圖的最小生成樹包含 _ 個(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樹型結(jié)構(gòu)最適合用來描述( )A.有序的數(shù)據(jù)元素 B.無序的數(shù)據(jù)元素C.數(shù)據(jù)元素之間的具有層次關(guān)系的數(shù)據(jù)D.數(shù)據(jù)元素之間沒有關(guān)系的數(shù)據(jù)答案：C7若二叉樹中度為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的完全二叉樹的第6層有3個(gè)葉結(jié)點(diǎn)，則該二叉樹一共有_個(gè)結(jié)點(diǎn)。( )A.32 B.33C.34 D.25答案：C9若某完全二叉樹的深度為h，則該完全二叉樹中至少有_個(gè)結(jié)點(diǎn)。( )A.2h B.2h-1C.2h-2D.2h-1+1答案：C10在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點(diǎn)的左邊應(yīng)該( )A.只有左子樹上的所有結(jié)點(diǎn)B.只有左子樹上的部分結(jié)點(diǎn)C.只有右子樹上的所有結(jié)點(diǎn) D.只有右子樹上的部分結(jié)點(diǎn)答案：A11下面關(guān)于哈夫曼樹的說法，不正確的是( )A.對(duì)應(yīng)于一組權(quán)值構(gòu)造出的哈夫曼樹一般不是唯一的B.哈夫曼樹具有最小帶權(quán)路徑長(zhǎng)度C.哈夫曼樹中沒有度為1的結(jié)點(diǎn)D.哈夫曼樹中除了度為1的結(jié)點(diǎn)外，還有度為2的結(jié)點(diǎn)和葉結(jié)點(diǎn)答案：D12數(shù)據(jù)結(jié)構(gòu)是一門研究計(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ù)類型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ù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量答案：C19數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱為 。（ ）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解決問題的計(jì)算方法C排序算法D解決問題的有限運(yùn)算序列答案：D21. 由_組成的集合是一個(gè)數(shù)據(jù)對(duì)象。( )A.不同類型的數(shù)據(jù)項(xiàng)B.不同類型的數(shù)據(jù)元素C.相同類型的數(shù)據(jù)項(xiàng)D.相同類型的數(shù)據(jù)元素答案：D22關(guān)于順序存儲(chǔ)的敘述中,哪一條是不正確的。( )A.存儲(chǔ)密度大B.邏輯上相鄰的節(jié)點(diǎn)物理上不必鄰接C.可以通過計(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è)無限系列，可以為空D.一個(gè)無限系列，不能為空答案：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í)間不依賴于表長(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á)到鏈表表尾的語句是_。( )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)（若存在），則需要修改指針的操作為_。 ( ) A.p-next=p-next-nextB.p=p-nextC.p= p-next-nextD.p-next=p答案：A41. 向一個(gè)有127個(gè)元素順序表中插入一個(gè)新元素并保存原來順序不變，平均要移動(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_又稱為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)棧滿的情況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ì)滿的條件是_。( )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.沒有共同點(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ì)的操作為_。( )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(h0) 的二叉樹最少有 _ 個(gè)結(jié)點(diǎn)。( )A.hB.h-1C.h+1D.2h答案：A56樹型結(jié)構(gòu)最適合用來描述_。( )A.有序的數(shù)據(jù)元素B.無序的數(shù)據(jù)元素C.數(shù)據(jù)元素之間的具有層次關(guān)系的數(shù)據(jù)D.數(shù)據(jù)元素之間沒有關(guān)系的數(shù)據(jù)答案：C57有n(n0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度是_。( )A.log2(n)B.log2(n)+1C.log2(n+1)D.log2(n)+1答案：BD58. _ 又是一棵滿二叉樹。( )A.二叉排序樹B.深度為5有31個(gè)結(jié)點(diǎn)的二叉樹C.有15個(gè)結(jié)點(diǎn)的完全二叉樹D.哈夫曼(Huffman)樹(沒有度為1的結(jié)點(diǎn))答案：C59. 深度為k的滿二叉樹有_個(gè)分枝結(jié)點(diǎn)。( )A.2k-1B.2k-1-1C.2k+1D.2k-1+1答案：60. 若已知一棵二叉樹先序序列為ABCDEFG，中序序列為CBDAEGF，則其后序序列為_。( )A.CDBGFEAB.CDBFGEAC.CDBAGFED.BCDAGFE答案：A61. 二叉樹第i(i=1)層上至多有 結(jié)點(diǎn)。( )A.iB.iC.iD.i答案：C62. 在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為_。( )A. 31B. 32C. 33D. 16答案：A63. 一個(gè)二叉樹按順序方式存儲(chǔ)在一個(gè)維數(shù)組中，如圖0 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEFGHIJ則結(jié)點(diǎn)E在二叉樹的第 層。( )A.1B.2C.3D.4答案：C64在一棵度為3的樹中,度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2 的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為_。( )A4B5C6D7答案：C65n 個(gè)頂點(diǎn)的帶權(quán)無向連通圖的最小生成樹包含 _ 個(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條邊的無向圖的鄰接矩陣中,零元素的個(gè)數(shù)為_。( )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)為_。( )A.1800B.60C.1200D.log2 3600答案：B72. 折半查找20個(gè)記錄的有序表,若查找失敗,比較關(guān)鍵字的次數(shù)_。( )A.最多為6B.最多為5C.最多為4D.最多為3答案：B73. 中序遍歷一棵二叉排序樹所得到的結(jié)點(diǎn)序列是鍵值的 序列。( )A.遞增或遞減B.遞減C.遞增D.無序答案：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)鍵碼查詢時(shí)找到一個(gè)表項(xiàng)的平均探查次數(shù)不超過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)行比較，然后將其存放在已排序序列的合適位置，該排序方法稱為 排序法。( )A.插入B.選擇C.希爾D.二路并歸答案：A84. 就平均查找速度而言，下列幾種查找速度從慢至快的關(guān)系是 。( )A.順序 折半 哈西 分塊B.順序 分塊 折半 哈西C.分塊 折半 哈西 順序D.順序 哈西 分塊 折半答案：B85. 在下列算法中， 算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。( )A.堆排序B.冒泡排序C.插入排序D.快速排序答案：C86堆是一個(gè)鍵值序列( K1, K2, , Kn )，對(duì) I = 1,2n/2, 滿足 。( )A.Ki = K2i = K2i+1B.Ki K2i+1 K2i C.Ki = K2i 且 Ki =K2i+1D. Ki = K2i 或 Ki 0) 個(gè)結(jié)點(diǎn)二叉樹對(duì)應(yīng)的森林最多包含_ 棵非空樹。答案：5深度為 n(n0) 的二叉樹最多有 _ 個(gè)結(jié)點(diǎn)。 答案：2的n次方-16n(n0) 個(gè)結(jié)點(diǎn)、 (n-1) 條邊的連通無向圖中，頂點(diǎn)度數(shù)最大值為 _ 。 答案：2（n-1）7在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊的數(shù)目的_2_倍。答案：8圖的深度優(yōu)先搜索方法類似于二叉樹的_遍歷。答案：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的最小生成樹的權(quán)值之和為_。答案：10.將數(shù)據(jù)元素2,4,6,8,10,12,14,16,18,20依次存放于一個(gè)一維數(shù)組中，然后采用折半查找方法查找元素12，被比較過的數(shù)組元素的下標(biāo)依次為_。答案：11.每趟排序從未排序的子序列中依次取出元素與已經(jīng)排好序的序列中元素進(jìn)行比較，然后將其放在已經(jīng)排好序的序列的合適位置。這種排序法稱為_簡(jiǎn)單選擇_排序法。答案：12.從未排序序列中選擇一個(gè)元素，該元素將當(dāng)前參加排序的那些元素分成前后兩個(gè)部分，前一部分中所有元素都小于等于所選元素，后一部分中所有元素都大于或等于所選元素，而此時(shí)所選元素處在排序的最終位置。這種排序法稱為_快速_排序法。答案：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ī)中的表示(映象)稱為 _。答案：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ù)的_無關(guān)，是獨(dú)立于計(jì)算機(jī)的。答案：17一個(gè)算法具有5個(gè)特性:_、_、_、有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。答案：18線性表中 _ 稱為表的長(zhǎng)度。答案：19設(shè)長(zhǎng)度為n的線性表順序存貯,若在它的第i-1和第i個(gè)元素之間插入一個(gè)元素, 共需移動(dòng) _ 個(gè)元素(1link;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ī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(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ì)尾指針分別為f、r，其判空的條件是f=r ，判滿的條件是 (r+1)%m=f 。答案：r=f、(r+1)%m=f27在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有_個(gè)元素。答案：28深度為 n(n0) 的二叉樹最多有 _ 個(gè)結(jié)點(diǎn)。答案：2的n次方-129n(n0) 個(gè)結(jié)點(diǎn)、 (n-1) 條邊的連通無向圖中，頂點(diǎn)度數(shù)最大值為 _2（n-1）_ 。答案：30一棵深度為6的滿二叉樹有_31_個(gè)非終端結(jié)點(diǎn)。答案：31若一棵二叉樹中有8個(gè)度為2的結(jié)點(diǎn),則它有_9_個(gè)葉子。答案：32樹中結(jié)點(diǎn)A的 _擁有的后件個(gè)數(shù)_ 稱為結(jié)點(diǎn)A的度。答案：33一棵深度為4的二叉樹最多有 _15_ 個(gè)結(jié)點(diǎn)。答案：34將 樹轉(zhuǎn)化為二叉樹時(shí)，其根結(jié)點(diǎn)的右子樹總是空的。答案：35哈夫曼樹是帶權(quán)路徑長(zhǎng)度 最小 的樹，通常權(quán)值較大的結(jié)點(diǎn)離根結(jié)點(diǎn) 近 。答案：36具有n個(gè)葉子的二叉樹，每個(gè)葉子的權(quán)值為wi(1in)其中帶權(quán)路徑最小的二叉樹被稱為 哈夫曼樹（最優(yōu)二叉樹） 。答案：37若已知一棵二叉樹的先序序列為 + a * b c d / e f，中序序列為a + b * c d e / f，則其后序序列為_。答案：38已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有_個(gè)葉子結(jié)點(diǎn)。答案：39已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，且僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為30，則總結(jié)點(diǎn)數(shù)為 129 。答案：50+30+49=12940具有10個(gè)頂點(diǎn)的無向圖,邊的總數(shù)最多為 _ 。答案：41在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá) n-1 。答案：42有向圖g用鄰接矩陣am,1m來存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的。答案：43有n個(gè)球隊(duì)參加的足球聯(lián)賽按主客場(chǎng)制進(jìn)行比賽，共需進(jìn)行 場(chǎng)比賽。答案：44帶權(quán)連通圖G=，其中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的最小生成樹的權(quán)值之和為_ 。答案：45順序查找n個(gè)元素的順序表,當(dāng)使用監(jiān)視哨時(shí),若查找成功,比較關(guān)鍵字的次數(shù)至少為_次, 最多為_次；若查找失敗,比較關(guān)鍵字的次數(shù)為_次。答案：46在單鏈表上難以實(shí)現(xiàn)的排序方法有 、 和 。答案：快速排序、堆排序、希爾排序 五、簡(jiǎn)答題/問答題/綜述題1什么是順序表？順序表的特點(diǎn)是什么？答案：線性表的順序存儲(chǔ)是指在內(nèi)存中用一塊地址連續(xù)的存儲(chǔ)空間順序存放線性表的各元素，用這種形式存儲(chǔ)的線性表稱為順序表。數(shù)據(jù)元素在順序表中物理位置取決于數(shù)據(jù)元素在線性表中的邏輯位置，可得出順序表的特點(diǎn)：邏輯位置相鄰，其物理位置也相鄰。2什么樣的圖是連通圖？答案：在無向圖G中，如果從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(ij)有路徑，則稱頂點(diǎn)vi和頂點(diǎn)vj是連通的，若圖中任意兩頂點(diǎn)間都是相通的，則稱此圖是連通圖。3二叉樹有哪幾種基本形態(tài)? 畫圖說明之。答案：二叉樹，滿二叉樹，完全二叉樹六、操作題/綜合能力題1若對(duì)序列(76，38，65，13，97，27，50，49)采用冒泡排序法(按照值的大小從小到大)進(jìn)行排序，共需幾趟排序？請(qǐng)分別在下表中寫出每一趟的結(jié)果：5分所以應(yīng)該寫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)分別在下表中寫出每一趟的結(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í)刻（只要棧不空），都可以出（退）棧，試寫出所有可能的出棧序列（如 1234 ）。 答案：4若一二叉樹有 2 度結(jié)點(diǎn) 100個(gè)，則其葉結(jié)點(diǎn)有多少個(gè)？該二叉樹可以有多少個(gè) 1 度頂點(diǎn)？答案：葉結(jié)點(diǎn)101個(gè) 1度結(jié)點(diǎn)可以有 101個(gè)5已知某非空二叉排序樹采用順序存儲(chǔ)結(jié)構(gòu)依次將所有結(jié)點(diǎn)的數(shù)據(jù)信息存放于一維數(shù)組ABDICEFCH，請(qǐng)分別寫出該二叉樹的前序遍歷序列與中序遍歷序列。答案：6二叉樹的順序存儲(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)畫出相應(yīng)的哈夫曼樹； (2)分別列出 A、B、C、D、E、F 的哈夫曼碼；(3)計(jì)算該樹的帶權(quán)路徑長(zhǎng)度WPL。答案：8試將森林 F= T1,T2,T3,T4 轉(zhuǎn)換為一棵二叉樹。 T1 T2 T3 T4答案：9試畫出下列二叉樹的中序線索二叉樹存儲(chǔ)結(jié)構(gòu)圖。 二叉樹答案：10試用孩子兄弟(左孩子右兄弟)表示法畫出下列樹的存儲(chǔ)結(jié)構(gòu)圖。 樹答案：11已知二叉樹的前序遍歷序列和中序遍歷序列分別是：B,A,C,D,F,E,G和D,C,A,F,G,E,B, 試畫出該二叉樹。答案：12試用雙親表示法畫出下列樹T的存儲(chǔ)結(jié)構(gòu)圖。答案：13假定后序遍歷二叉樹的結(jié)果是A,C,B(1)試畫出所有可得到這一結(jié)果的不同形態(tài)的二叉樹；(2)分別寫出這些二叉樹的中序遍歷序列。答案：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)造一棵哈夫曼樹（請(qǐng)按照左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造）。答案：15某二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)表示如下：(1) 試畫出此二叉樹的圖形表示。(2) 寫出結(jié)點(diǎn)D的雙親結(jié)點(diǎn)及左、右子女。(3) 將此二叉樹看作森林的二叉樹表示，試將它還原為森林。答案：16圖的鄰接矩陣:答案：17有向圖的逆鄰接表: 答案：18找出下面網(wǎng)絡(luò)的最小生成樹。 答案：19找出下面網(wǎng)絡(luò)的最小生成樹:答案：20試畫出下列圖的鄰接表。 圖答案：21對(duì)下面的帶權(quán)無向圖采用prim算法從頂點(diǎn) 開始構(gòu)造最小生成樹。（寫出加入生成樹頂點(diǎn)集合S和選擇邊Edge的順序）S:頂點(diǎn)號(hào)Edge:(頂點(diǎn)，頂點(diǎn)，權(quán)值)( ， ， )( ， ， ) ( ， ， )( ， ， )( ， ， ) 答案：5462311015410304101522022對(duì)圖所示有向圖，試用Dijkstra算法求出從源點(diǎn)1到其它各頂點(diǎn)的最短路徑，并寫出執(zhí)行算法過程中擴(kuò)充結(jié)點(diǎn)的每次循環(huán)狀態(tài)。答案：23已某個(gè)不帶權(quán)的無向圖采用鄰接矩陣存儲(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)寫出從頂點(diǎn)A出發(fā)對(duì)該圖進(jìn)行深度有限搜索后得到的頂點(diǎn)序列。答案：24試按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 將所有元素插入一棵初始為空的二叉排序樹中, 使之仍是一棵二叉排序樹。 (1)試畫出插入完成之后的二叉排序樹； (2)若查找元素17,它將依次與二叉排序樹中哪些元素比較大小? (3)假設(shè)每個(gè)元素的查找概率相等,試計(jì)算該樹的平均查找長(zhǎng)度ASL。 (4)對(duì)該樹進(jìn)行中序遍歷,試寫出中序遍歷序列。答案：25已知一關(guān)鍵字序列為（40，11，16，31，23，55，13，45，50），試生成一棵平衡的二叉排序樹,再?gòu)纳傻钠胶獾亩媾判驑渲袆h除關(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。試畫出用線性探查法解決沖突時(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，