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