【正文】 《軟件技術(shù)基礎(chǔ)》試題庫 《 軟件技術(shù)基礎(chǔ) 》 試題庫 課程名稱： 軟件技術(shù)基礎(chǔ) 適用專業(yè)：軟件技術(shù) 、計算機(jī)應(yīng)用、網(wǎng)絡(luò)、信息等計算機(jī)相關(guān) 專業(yè) 第一章 概述 第二章 數(shù)據(jù)結(jié)構(gòu) 一、單項選擇題 1．若長度為 n 的線性表采用順序存儲結(jié)構(gòu)，刪除它的第 i 數(shù)據(jù)元素之前，需要先依次向前移動 _______個數(shù)據(jù)元素。 ( ) A. ni B. n+i C. ni1 D. ni+1 答案： A 2．在單鏈表中，已知 q 指的結(jié)點是 p 指的結(jié)點的直接前驅(qū)結(jié)點，若在 q 和 p 指的結(jié)點之間插入一個由 s 指的結(jié)點，則需執(zhí)行 ________。 ( ) A. link(s)←link(p) ， link(p)←s B. link(q)←s ， link(s)←p C. link(p)←link(s) ， link(s)←p D. link(p)←s ， link(s)←q 答案： B 3． 高度為 h(h0) 的二叉樹最少有 ________個結(jié)點 。（ ） A. h B. h1 C. h+1 D. 2h 《軟件技術(shù)基礎(chǔ)》試題庫 答案： A 4． n 個頂點的帶權(quán)無向連通圖的最小生成樹包含 ________ 個頂點 。（ ） +1 答案： B 5． 采用拉鏈法解決沖突的散 列表中，查找的平均查找長度 ( )。 A. 直接與關(guān)鍵字個數(shù)有關(guān) B. 直接與裝填因子 a 有關(guān) C. 直接與表的容量有關(guān) D. 直接與散列函數(shù)有關(guān) 答案： D 6． 樹型結(jié)構(gòu)最適合用來描述 ( ) 答案： C 7． 若二叉樹中度為 2 的結(jié)點有 15 個，度為 1 的結(jié)點有 10 個 _______個葉結(jié)點。 ( ) B. 10 答案： C 8． 若深度為 6 的完全二叉樹的第 6 層 有 3 個葉結(jié)點，則該二叉樹一共有 ______個結(jié)點。 ( ) B. 33 答案： C 9． 若某完全二叉樹的深度為 h，則該完全二叉樹中至少有 ______個結(jié)點。 ( ) 《軟件技術(shù)基礎(chǔ)》試題庫 +1 答案： C 10． 在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點的左邊應(yīng)該 ( ) 答案： A 11． 下面關(guān)于哈夫曼樹的說法， 不正確 的是 ( ) 1 的結(jié)點 1 的結(jié)點外，還有度為 2 的結(jié)點和葉結(jié)點 答案： D 12．?dāng)?shù)據(jù)結(jié)構(gòu)是一門研究計算機(jī)中 對象及其關(guān)系的學(xué)科。 ( ) A. 數(shù)值運算 答案： B 13．?dāng)?shù)據(jù)結(jié)構(gòu)的定義為 (K， R)，其中 K 是 的集合。 ( ) 答案： B 14． 算法分析的目的是 ____。 ( ) 答案： C 《軟件技術(shù)基礎(chǔ)》試題庫 15． 數(shù)據(jù)的不可分割的基本單位是 。 ( ) 答案： D 16． 是具有相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。 ( ) 答案： B 17．?dāng)?shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的 及它們之間的相互聯(lián)系。 （ ） 、 物理結(jié)構(gòu) 、 邏輯結(jié)構(gòu) 、 邏輯結(jié)構(gòu) 、 邏輯結(jié)構(gòu) 答案： C 18． 組成數(shù)據(jù)的基本單位是 。 （ ） 答案： C 19．?dāng)?shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱為 。（ ） 答案： C 20． 算法指的是 。（ ） A．計算機(jī)程序 B．解決問題的計算方法 C．排序算法 《軟件技術(shù)基礎(chǔ)》試題庫 D．解決問題的有限運算序列 答案： D 21. 由 ____組成的集合是一個數(shù)據(jù)對象。 ( ) 答案： D 22．關(guān)于順序存儲的敘述中 ,哪一條是不正確的 。 ( ) i 個節(jié)點的位置 、刪除操作不方便 答案： B 23．一個向量第一個元素的存儲地址是 100 ，每個元素的長度為 2 ，則第 5 個元素的地址是 。（ ） B. 108 答案： B 24．已知一個順序存儲的線性表，設(shè)每個結(jié)點需要占 m 個存儲單元，若第一個結(jié)點的地址為 da，則第 i 個結(jié)點的地址為 。（ ） +(i1)*m B. da+i*m *m +(i+1)*m 答案： A 25．鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表 。（ ） 答案： B 26．線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址 。（ ） 《軟件技術(shù)基礎(chǔ)》試題庫 的 答案： D 27．線性表Ｌ在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)。 ( ) 答案： B 28．在長度為 n 的順序表的第 i (1≤i≤n+1) 個位置上插入一個元素，元素的移動次數(shù)為 。（ ） +1 答案： A 29．線性表是 。（ ） ，可以為空 有限系列，不能為空 ，可以為空 ，不能為空 答案： A 30. ____是線性表。 ( ) A.(孔子 ,諸葛亮 ,曹雪芹 ) B.{A,B,C,D} C.{10,11,12,13,14} D.(1,2,3,...) 答案： A 31. ____ 是表示線性數(shù)據(jù)結(jié)構(gòu)的。 ( ) 答案： D 32. 將線性表的數(shù)據(jù)元素以 ____結(jié)構(gòu)存放 , 查找一個數(shù)據(jù)元素所需時間不依賴于表長。 ( ) 《軟件技術(shù)基礎(chǔ)》試題庫 (Hash)表 答案： C 33. 在一個單鏈表中，若 p 所指結(jié)點不是最后結(jié)點，在 p 之后插入 s 所指結(jié)點，則執(zhí)行 ___。( ) link=p。plink=s。 B. slink=plink。plink=s。 link=plink。p=s。 link=s。slink=p。 答案： 34. 在循環(huán)鏈表中 first 為指向鏈表表頭的指針， current 為鏈表當(dāng)前指針，在循環(huán)鏈表中檢測current 是否達(dá)到鏈表表尾的語句是 ____。 ( ) link=NULL B. firstlink=current =current link=first 答案： 35. 從一個具有 n 個結(jié)點的單鏈表中查找其值等于 x 結(jié)點時，在查找成功的情況下，需平均比較 ____個結(jié)點。 ( ) B. n/2 C.(n1)/2 D.(n+1)/2 答案： 36. 用鏈表表示線性表的優(yōu)點是 ____。 ( ) A. 便于隨機(jī)存取 B. 花費的存儲空間比順序表少 C. 便于插入與刪除 D. 數(shù)據(jù)元素的物理順序與邏輯順序相同 答案： 37. 當(dāng)需要隨機(jī)查找線性表的元素時 ,宜采用 ____作存儲結(jié)構(gòu)。 ( ) 答案： 38. 線性表的鏈接實現(xiàn)有利于 運算。 ( ) 《軟件技術(shù)基礎(chǔ)》試題庫 答案： 39. 線性表采用鏈?zhǔn)酱鎯r，其地址 ____。 ( ) 答案： 40. 設(shè)單鏈表中指針 p 指著結(jié)點 a，若要刪除 a 之后的結(jié)點（若存在），則需要修改指針的操作為 ____。 ( ) next=pnextnext B. p=pnext = pnextnext next=p 答案： A 41. 向一個有 127 個元素順序表中插入一個新元素并保存原來順序不變，平均要移動 個元素。 ( ) 答案： A 42. 向一個有 127 個元素的順序表中刪除一個元素，平均要移動 個元素 。 ( ) 答案： C 43． ____又稱為 FIFO 表。 ( ) 《軟件技術(shù)基礎(chǔ)》試題庫 答案： 44． 設(shè)依次進(jìn)入一個棧的元素序列為 c,a,b,d,不可得到出棧的元素序列有 _____。 ( ) ,c,d ,d,c,b ,a,d,c ,d,a,b 答案： 45. 鏈?zhǔn)綏Ｅc順序棧相比，一個比較明顯的優(yōu)點是 _____。 ( ) A. 插入操作更加方便 B. 通常不會出現(xiàn)棧滿的情況 C. 不會出現(xiàn)?？盏那闆r D. 刪除操作更加方便 答案： 46. 在一個順序存儲的循環(huán)隊列中，隊頭指針指向隊頭元素的 _____。 ( ) A. 前一個位置 B. 后一個位置 C. 隊頭元素位置 D. 隊尾元素的前一位置 答案： 47. 若一個棧的輸入序列是 1， 2， 3……n ，則輸出序列的第一個元素是 n，則第 i 個輸出元素是 _____。 ( ) +1 答案： 48. 棧的數(shù)組表示中， top 為棧頂指針，棧空的條件是 _____。 ( ) =0 B. top=maxSize =maxSize =1 答案： 《軟件技術(shù)基礎(chǔ)》試題庫 49. 在數(shù)組表示的循環(huán)隊列中， front、 rear 分別為隊列的頭、尾指針 ， maxSize 為數(shù)組的最大長度，隊滿的條件是 _____。 ( ) =maxSize B. (rear+1)%maxSize=front =maxSize =front 答案： 50. 棧和隊列的共同特點是 _____。 ( ) 答案： 51．若非空隊列采用鏈?zhǔn)酱鎯Y(jié)構(gòu)， front 和 rear 分別為隊頭元素與隊列尾元素的指針，刪除此時隊列的一個元素的操作時依次執(zhí)行 p←front ， ______ ， call RET(P)。 ( ) ←link(rear) ←link(p) ←link(front) ←link(p) 答案： 52．由兩個棧共享一個向量空間的好處是 _____。 ( ) A．減少存取時間，降低下溢發(fā)生的機(jī)率 B．節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率 C．減少存取時間，降低上溢發(fā)生的機(jī)率 D．節(jié)省存儲空間，降低下溢發(fā)生的機(jī)率 答案： 53． 數(shù)組 data[m]為循環(huán)隊列的存儲空間 , front 為隊頭指針 , rare 為隊尾指針 ,則執(zhí)行入隊 的操作為 _____。 ( ) =rare+1 =(rare+1)%(m1) =(rare1)%m =(rare+1)%m 答案： 54. 將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時，通常需要使用 ____。 ( ) 《軟件技術(shù)基礎(chǔ)》試題庫 答案： 55． 高度為 h(h0) 的二叉樹最少有 ________ 個結(jié)點 。 ( ) +1 答案： 56．樹型結(jié)構(gòu)最適合用來描述 ____。 ( ) 答案： 57． 有 n(n0)個結(jié)點的完全二叉樹的深度是 ____。 ( ) A.?log2(n)? B.?log2(n)+1? C.?log2(n+1)? D.?log2(n)+1? 答案： 58. ___ 又是一棵滿二叉樹。 ( ) 5有 31個結(jié)點的二叉樹 15 個結(jié)點的完全二叉樹 (Huffman)樹 答案： 59. 深度為 k的滿二叉樹有 ____個分枝結(jié)點。 ( ) +1 +1 答案： 《軟件技術(shù)基礎(chǔ)》試題庫 60. 若已知一棵二叉樹先序序列為 ABCDEFG，中序序列為 CBDAEGF，則其后序序列為____。 ( ) 答案： A 61. 二叉樹第 i(i=1)層上至多有 結(jié)點。 ( ) i i i－１ i－１ 答案： 62. 在一棵具有 5 層的滿二叉樹中結(jié)點總數(shù)為 ____。 ( ) A. 31 B. 32 C. 33 D. 16 答案：