軟件技術(shù)基礎(chǔ)試題庫.doc
《軟件技術(shù)基礎(chǔ)試題庫.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《軟件技術(shù)基礎(chǔ)試題庫.doc（46頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
《軟件技術(shù)基礎(chǔ)》試題庫 課程名稱：軟件技術(shù)基礎(chǔ) 適用專業(yè)：軟件技術(shù)、計(jì)算機(jī)應(yīng)用、網(wǎng)絡(luò)、信息等計(jì)算機(jī)相關(guān)專業(yè) 第一章 概述 第二章 數(shù)據(jù)結(jié)構(gòu) 一、單項(xiàng)選擇題 1．若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除它的第i數(shù)據(jù)元素之前，需要先依次向前移動(dòng)_______個(gè)數(shù)據(jù)元素。( ) A. n-i B. n+i C. n-i-1 D. n-i+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(h>0) 的二叉樹最少有________個(gè)結(jié)點(diǎn)。（ ） A. h B. h-1 C. h+1 D. 2h 答案：A 4．n個(gè)頂點(diǎn)的帶權(quán)無向連通圖的最小生成樹包含 ________ 個(gè)頂點(diǎn)。（ ） A.n-1 B.n C.n/2 D.n+1 答案：B 5．采用拉鏈法解決沖突的散列表中，查找的平均查找長度( )。 A. 直接與關(guān)鍵字個(gè)數(shù)有關(guān) B. 直接與裝填因子 a 有關(guān) C. 直接與表的容量有關(guān) D. 直接與散列函數(shù)有關(guān) 答案：D 6．樹型結(jié)構(gòu)最適合用來描述( ) A.有序的數(shù)據(jù)元素 B.無序的數(shù)據(jù)元素 C.數(shù)據(jù)元素之間的具有層次關(guān)系的數(shù)據(jù) D.數(shù)據(jù)元素之間沒有關(guān)系的數(shù)據(jù) 答案：C 7．若二叉樹中度為2的結(jié)點(diǎn)有15個(gè)，度為1的結(jié)點(diǎn)有10個(gè)_______個(gè)葉結(jié)點(diǎn)。( ) A.25 B.10 C.16 D.41 答案：C 度0的結(jié)點(diǎn)比度2的結(jié)點(diǎn)多1 8．若深度為6的完全二叉樹的第6層有3個(gè)葉結(jié)點(diǎn)，則該二叉樹一共有______個(gè)結(jié)點(diǎn)。( ) A.32 B.33 C.34 D.25 答案：C 9．若某完全二叉樹的深度為h，則該完全二叉樹中至少有______個(gè)結(jié)點(diǎn)。( ) A.2h B.2h-1 C.2h-2 D.2h-1+1 答案：C 10．在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點(diǎn)的左邊應(yīng)該( ) A.只有左子樹上的所有結(jié)點(diǎn) B.只有左子樹上的部分結(jié)點(diǎn) C.只有右子樹上的所有結(jié)點(diǎn) D.只有右子樹上的部分結(jié)點(diǎn) 答案：A 11．下面關(guān)于哈夫曼樹的說法，不正確的是( ) A.對應(yīng)于一組權(quán)值構(gòu)造出的哈夫曼樹一般不是唯一的 B.哈夫曼樹具有最小帶權(quán)路徑長度 C.哈夫曼樹中沒有度為1的結(jié)點(diǎn) D.哈夫曼樹中除了度為1的結(jié)點(diǎn)外，還有度為2的結(jié)點(diǎn)和葉結(jié)點(diǎn) 答案：D 12．?dāng)?shù)據(jù)結(jié)構(gòu)是一門研究計(jì)算機(jī)中 對象及其關(guān)系的學(xué)科。( ) A. 數(shù)值運(yùn)算 B.非數(shù)值運(yùn)算 C.集合 D.非集合 答案：B 13．?dāng)?shù)據(jù)結(jié)構(gòu)的定義為(K，R)，其中K是 的集合。( ) A.算法 B.數(shù)據(jù)元素 C.數(shù)據(jù)操作 D.邏輯結(jié)構(gòu) 答案：B 14．算法分析的目的是____。( ) A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 B.研究算法中輸入和輸出的關(guān)系 C.分析算法的效率以求改進(jìn) D.分析算法的易懂性和文檔性 答案：C 15．?dāng)?shù)據(jù)的不可分割的基本單位是 。( ) A.元素 B.結(jié)點(diǎn) C.數(shù)據(jù)類型 D.數(shù)據(jù)項(xiàng) 答案：D 16． 是具有相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。( ) A.數(shù)據(jù)符號(hào) B.數(shù)據(jù)對象 C.數(shù)據(jù) D.數(shù)據(jù)結(jié)構(gòu) 答案：B 17．?dāng)?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) 答案：C 18．組成數(shù)據(jù)的基本單位是 。（ ） A.數(shù)據(jù)項(xiàng) B.數(shù)據(jù)類型 C.數(shù)據(jù)元素 D.數(shù)據(jù)變量 答案：C 19．?dāng)?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) 答案：C 20．算法指的是 。（ ） A．計(jì)算機(jī)程序 B．解決問題的計(jì)算方法 C．排序算法 D．解決問題的有限運(yùn)算序列 答案：D 21. 由____組成的集合是一個(gè)數(shù)據(jù)對象。( ) A.不同類型的數(shù)據(jù)項(xiàng) B.不同類型的數(shù)據(jù)元素 C.相同類型的數(shù)據(jù)項(xiàng) D.相同類型的數(shù)據(jù)元素 答案：D 22．關(guān)于順序存儲(chǔ)的敘述中,哪一條是不正確的。( ) A.存儲(chǔ)密度大 B.邏輯上相鄰的節(jié)點(diǎn)物理上不必鄰接 C.可以通過計(jì)算直接確定第i個(gè)節(jié)點(diǎn)的位置 D.插入、刪除操作不方便 答案：B 23．一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是 100 ，每個(gè)元素的長度為 2 ，則第 5 個(gè)元素的地址是 。（ ） A.110 B.108 C.100 D.120 答案：B 24．已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)需要占m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為da，則第i個(gè)結(jié)點(diǎn)的地址為 。（ ） A.da+(i-1)*m B.da+i*m C.da-i*m D.da+(i+1)*m 答案：A 25．鏈表是一種采用 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表。（ ） A.順序 B.鏈?zhǔn)? C.星式 D.網(wǎng)狀 答案：B 26．線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址 。（ ） A.必須是連續(xù)的 B.部分地址必須是連續(xù)的 C.一定是不連續(xù)的 D.連續(xù)或不連續(xù)都可以 答案：D 27．線性表Ｌ在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。 ( ) A.需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值 B.需不斷對Ｌ進(jìn)行刪除插入 C.Ｌ中含有大量的結(jié)點(diǎn) D.Ｌ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜 答案：B 28．在長度為 n 的順序表的第 i (1≤i≤n+1) 個(gè)位置上插入一個(gè)元素，元素的移動(dòng)次數(shù)為 。（ ） A.n-i+1 B.n-i C.i D.i-1 答案：A 29．線性表是 。（ ） A.一個(gè)有限系列，可以為空 B.一個(gè)有限系列，不能為空 C.一個(gè)無限系列，可以為空 D.一個(gè)無限系列，不能為空 答案：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)的。( ) A.循環(huán)鏈表 B.鄰接多重表 C.孩子鏈表 D.單鏈表 答案：D 32. 將線性表的數(shù)據(jù)元素以____結(jié)構(gòu)存放, 查找一個(gè)數(shù)據(jù)元素所需時(shí)間不依賴于表長。( ) A.循環(huán)雙鏈表 B.哈希(Hash)表 C.一維數(shù)組 D.單鏈表 答案：C 33. 在一個(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)鏈表中檢測current是否達(dá)到鏈表表尾的語句是____。( ) A.current->link=NULL B.first->link=current C.first=current D.current->link=first 答案： 35. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較____個(gè)結(jié)點(diǎn)。( ) A.N B.n/2 C.(n-1)/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)。( ) 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->next B.p=p->next C.p= p->next->next D.p->next=p 答案：A 41. 向一個(gè)有127個(gè)元素順序表中插入一個(gè)新元素并保存原來順序不變，平均要移動(dòng) 個(gè)元素。( ) A.64 B.63.5 C.63 D.64.5 答案：A 42. 向一個(gè)有 127 個(gè)元素的順序表中刪除一個(gè)元素，平均要移動(dòng) 個(gè)元素。( ) A.8 B.63.5 C.63 D.7 答案：C 43．____又稱為FIFO表。( ) A.隊(duì)列 B.散列表 C.棧 D.哈希表 答案：A 44．設(shè)依次進(jìn)入一個(gè)棧的元素序列為c,a,b,d,不可得到出棧的元素序列有_____。( ) A.a.b,c,d B.a,d,c,b C.b,a,d,c D.c,d,a,b 答案：D 45. 鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)比較明顯的優(yōu)點(diǎn)是_____。( ) A. 插入操作更加方便 B. 通常不會(huì)出現(xiàn)棧滿的情況 C. 不會(huì)出現(xiàn)棧空的情況 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è)輸出元素是_____。( ) A.n-i B.i C.n-i+1 D.n-i-1 答案：C 48. 棧的數(shù)組表示中，top為棧頂指針，棧空的條件是_____。( ) A.top=0 B.top=maxSize C.top=maxSize D.top=-1 答案：D 49. 在數(shù)組表示的循環(huán)隊(duì)列中，front、rear分別為隊(duì)列的頭、尾指針，maxSize為數(shù)組的最大長度，隊(duì)滿的條件是_____。( ) A.front=maxSize B.(rear+1)%maxSize=front C.rear=maxSize D.rear=front 答案：B 50. 棧和隊(duì)列的共同特點(diǎn)是_____。( ) A.都是先進(jìn)后出 B.都是先進(jìn)先出 C.只允許在端點(diǎn)處插入和刪除 D.沒有共同點(diǎn) 答案：C 51．若非空隊(duì)列采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，front和rear分別為隊(duì)頭元素與隊(duì)列尾元素的指針，刪除此時(shí)隊(duì)列的一個(gè)元素的操作時(shí)依次執(zhí)行p←front，______ ，call RET(P)。( ) A.front←link(rear) B.rear←link(p) C.rear←link(front) D.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．?dāng)?shù)組data[m]為循環(huán)隊(duì)列的存儲(chǔ)空間, front為隊(duì)頭指針, rare為隊(duì)尾指針,則執(zhí)行入隊(duì)的操作為_____。( ) A.rare=rare+1 B.rare=(rare+1)%(m-1) C.rare=(rare-1)%m D.rare=(rare+1)%m 答案：D 54. 將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時(shí)，通常需要使用____。( ) A.棧 B.隊(duì)列 C.鏈表 D.數(shù)組 答案： 55．高度為 h(h>0) 的二叉樹最少有 ________ 個(gè)結(jié)點(diǎn)。( ) A.h B.h-1 C.h+1 D.2h 答案：A 56．樹型結(jié)構(gòu)最適合用來描述____。( ) A.有序的數(shù)據(jù)元素 B.無序的數(shù)據(jù)元素 C.數(shù)據(jù)元素之間的具有層次關(guān)系的數(shù)據(jù) D.數(shù)據(jù)元素之間沒有關(guān)系的數(shù)據(jù) 答案：C 57．有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度是____。( ) A.log2(n) B.log2(n)+1 C.log2(n+1) D.log2(n)+1 答案：BD 58. ___ 又是一棵滿二叉樹。( ) A.二叉排序樹 B.深度為5有31個(gè)結(jié)點(diǎn)的二叉樹 C.有15個(gè)結(jié)點(diǎn)的完全二叉樹 D.哈夫曼(Huffman)樹(沒有度為1的結(jié)點(diǎn)) 答案：C 59. 深度為k的滿二叉樹有____個(gè)分枝結(jié)點(diǎn)。( ) A.2k-1 B.2k-1-1 C.2k+1 D.2k-1+1 答案： 60. 若已知一棵二叉樹先序序列為ABCDEFG，中序序列為CBDAEGF，則其后序序列為____。( ) A.CDBGFEA B.CDBFGEA C.CDBAGFE D.BCDAGFE 答案：A 61. 二叉樹第i(i>=1)層上至多有 結(jié)點(diǎn)。( ) A.２i B.２i C.２i－１ D.２i－１ 答案：C 62. 在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為____。( ) A. 31 B. 32 C. 33 D. 16 答案：A 63. 一個(gè)二叉樹按順序方式存儲(chǔ)在一個(gè)維數(shù)組中，如圖 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 則結(jié)點(diǎn)E在二叉樹的第 層。( ) A.1 B.2 C.3 D.4 答案：C 64．在一棵度為3的樹中,度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2 的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為____。( ) A．4 B．5 C．6 D．7 答案：C 65．n 個(gè)頂點(diǎn)的帶權(quán)無向連通圖的最小生成樹包含 ________ 個(gè)頂點(diǎn)。( ) A.n-1 B.n C.n/2 D.n+1 答案：B 66．具有 n 個(gè)頂點(diǎn)的有向完全圖有 條弧。( ) A.n B.n*(n-1) C.n*(n+1) D.n*n 答案：B 67. n 個(gè)頂點(diǎn)的連通圖至少有 條邊。( ) A.n-1 B.n C.n+1 D.0 答案： 68．在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的 倍。( ) A．1/2 B．1 C．2 D．4 答案： 69．在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中,零元素的個(gè)數(shù)為____。( ) A．e B．2e C．n2－e D．n2－2e 答案：D 70．折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次與表中元素____進(jìn)行比較。( ) A.65,15,37 B.68,30,37 C.65,15,30 D.65,15,30,37 答案：D 71．對有3600個(gè)記錄的索引順序表(分塊表)進(jìn)行查找,最理想的塊長為___。( ) A.1800 B.60 C.1200 D.log2 3600 答案：B 72. 折半查找20個(gè)記錄的有序表,若查找失敗,比較關(guān)鍵字的次數(shù)____。( ) A.最多為6 B.最多為5 C.最多為4 D.最多為3 答案：B 73. 中序遍歷一棵二叉排序樹所得到的結(jié)點(diǎn)序列是鍵值的 序列。( ) A.遞增或遞減 B.遞減 C.遞增 D.無序 答案：C 74．散列表中的沖突是指____。( ) A.兩個(gè)元素具有相同的序號(hào) B.兩個(gè)元素的鍵值相同，而其他屬性相同 C.不同的鍵值對應(yīng)相同的存儲(chǔ)地址 D.數(shù)據(jù)元素的地址相同 答案： 75．用線形探測法查找散列表，可能要探測多個(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)閇0:6]，采用線性再散列法處理沖突。插入后的雜湊表應(yīng)該如________________所示。( ) A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D. 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è)搜索成功的平均搜索長度為Snl=(1+1/(1-a))/2,其中a 為裝填因子）( ) A.400 B.526 C.624 D.676 答案： 78．對長度為10的表作選擇(簡單選擇)排序,共需比較____次關(guān)鍵字。( ) A.45 B.90 C.55 D.110 答案： 79. 設(shè)有100個(gè)數(shù)據(jù)元素，采用折半搜索時(shí)，最大比較次數(shù)為 ( )。 A. 6 B. 7 C. 8 D. 10 答案：A 80. 對待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對兩個(gè)子序列施加同樣的排序操作，直到子序列為空或只剩一個(gè)元素為止。這樣的排序方法是____。( ) A. 選擇排序 B. 直接插入排序 C. 快速排序 D. 起泡排序 答案：C 81. 對5個(gè)不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行 次比較。( ) A. 8 B. 10 C. 15 D. 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) 答案：A 83. 從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其存放在已排序序列的合適位置，該排序方法稱為 排序法。( ) A.插入 B.選擇 C.希爾 D.二路并歸 答案：A 84. 就平均查找速度而言，下列幾種查找速度從慢至快的關(guān)系是 。( ) A.順序 折半 哈西 分塊 B.順序 分塊 折半 哈西 C.分塊 折半 哈西 順序 D.順序 哈西 分塊 折半 答案：B 85. 在下列算法中， 算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。( ) A.堆排序 B.冒泡排序 C.插入排序 D.快速排序 答案：C 86．堆是一個(gè)鍵值序列( K1, K2, …, Kn )，對 I = 1,2…[n/2], 滿足 。( ) A.Ki <= K2i <= K2i+1 B.Ki < K2i+1 < K2i C.Ki <= K2i 且 Ki <=K2i+1 D. Ki <= K2i 或 Ki <= K2i+1 答案： 87．對于關(guān)鍵字序列 {46 ， 58 ， 15 ， 45 ， 90 ， 18 ， 10 ， 62} ，其快速排序第一趟的結(jié)果是 。( ) A.15 45 18 46 10 62 58 90 B.10 15 18 45 46 58 62 90 C.10 18 15 45 46 90 58 62 D.15 10 18 45 46 62 58 90 答案： 88．用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是 。( ) A.選擇排序 B.希爾排序 C.歸并排序 D.快速排序 答案： 89．下列關(guān)鍵字序列中 是堆。( ) A．16，72，31，23，94，53 B．94，23，31，72，16，53 C．16，53，23，94，31，72 D．16，23，53，31，94，72 答案： 90．目前以比較為基礎(chǔ)的內(nèi)部排序方法中，其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無關(guān)的是 。( ) A．插入排序 B．直接選擇排序 C．快速排序 D．冒泡排序 答案：B 91．對n個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為 。( ) A．n+1 B．n C．n-1 D．n(n-1)/2 答案：D 二、多項(xiàng)選擇題 1．根據(jù)數(shù)據(jù)元素之間的不同特性，通常具有 這幾種基本數(shù)據(jù)結(jié)構(gòu)。( ) A. 集合 B. 線形結(jié)構(gòu) C. 樹型結(jié)構(gòu) D. 圖型結(jié)構(gòu) 答案：ABCD 2．?dāng)?shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有 兩種不同的表示方法。( ) A. 順序存儲(chǔ)結(jié)構(gòu) B. 二叉樹存儲(chǔ)結(jié)構(gòu) C. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D. 網(wǎng)絡(luò)結(jié)構(gòu) 答案：AC 3．查找哈希(Hash)表,解決沖突的的方法有___。( ) A.除留余數(shù)法 B.線性探測再散列法 C.直接地址法 D.鏈地址法 答案：BD 三、判斷題 1．非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接前驅(qū)元素。( ) 答案：F 2．?dāng)?shù)組是一種沒有插入與刪除操作的線性結(jié)構(gòu)。( ) 答案：T 3．非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接后繼元素。( ) 答案：F 4．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)不僅有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，還有索引結(jié)構(gòu)與散列結(jié)構(gòu)。( ) 答案：F 5．線性鏈表中各個(gè)鏈結(jié)點(diǎn)之間的地址不一定要連續(xù)。( ) 答案：T 6．若頻繁地對線性表進(jìn)行插入和刪除操作，該線性表采用順序存儲(chǔ)結(jié)構(gòu)更合適。( ) 答案：F 7.若線性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素占用4個(gè)存儲(chǔ)單元，第12個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為144，則第1個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是101。( 100 ) 答案：F 8.若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除表的第i個(gè)元素之前需要移動(dòng)表中n-i+1個(gè)元素。( ) 答案：F 9.符號(hào)link(p)出現(xiàn)在表達(dá)式中表示p所指的那個(gè)結(jié)點(diǎn)的內(nèi)容。( ) 答案：F 10.要將指針p移到它所指的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)是執(zhí)行語句p←link(p)。( ) 答案：T 11.在非空線性鏈表中由p所指的結(jié)點(diǎn)后面插入一個(gè)由q所指的結(jié)點(diǎn)的過程是依次執(zhí)行語句：link(q)←link(p);link(p)←q。( ) 答案：T 12.在非空雙向循環(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。( ) 答案：F 13.若某堆棧的輸入序列為1,2,3,4，則4,3,1,2不可能是堆棧的輸出序列之一。( ) 答案：T 14.刪除非空鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的堆棧(設(shè)棧頂指針為top)的一個(gè)元素的過程是依次執(zhí)行:p←top,top←link(p),call RET(p)。( ) 答案：T 15.若隊(duì)列采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，隊(duì)頭指針與指針分別為front和rear，向隊(duì)列中插入一個(gè)數(shù)據(jù)信息為item的新元素的過程是依次執(zhí)行:call GETNODE(p),data(P)←item,rear←p,front←p。( ) 答案：F 16．?dāng)?shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè)方面。( ) 答案：T 17．非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接前驅(qū)元素。( ) 答案：F 18．在順序表中取出第 i 個(gè)元素所花費(fèi)的時(shí)間與 i 成正比。（ ） 答案：F 19．完全二叉樹就是滿二叉樹。( )滿二叉樹是完全二叉樹 答案：F 20．已知一棵二叉樹的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹。( ) 答案：T 21．有向圖是一種非線性結(jié)構(gòu)。( ) 答案：T 22．帶權(quán)連通圖的最小生成樹的權(quán)值之和一定小于它的其它生成樹的權(quán)值之和。( ) 答案：T 23．對二叉排序樹遍歷的結(jié)果是一個(gè)有序序列。（ ） 答案：T 24．折半查找方法適用于按值有序的線性鏈表的查找。( ) 答案：F 25．非空二叉排序樹的任意一棵子樹也是二叉排序樹。( ) 答案：T 26．哈希表的查找效率主要取決于所選擇的哈希函數(shù)與處理沖突的方法。( ) 答案：T 四、填空題 1．已知具有n個(gè)元素的一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)元素的地址為LOC(a1)，那么，LOC(ai)=___________________。 答案：LOC(a1)+(n-1)k 2．若一棵二叉樹有10個(gè)葉結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)的點(diǎn)個(gè)數(shù)為___________。 答案：4 3．設(shè) SQ 為循環(huán)隊(duì)列，存儲(chǔ)在數(shù)組 d[m] 中，則 SQ 出隊(duì)操作對其隊(duì)頭指針 front 的修改是 _______________ 。 答案： 4．n(n>0) 個(gè)結(jié)點(diǎn)二叉樹對應(yīng)的森林最多包含_______________ 棵非空樹。 答案： 5．深度為 n(n>0) 的二叉樹最多有 _______________ 個(gè)結(jié)點(diǎn)。 答案：2的n次方-1 6．n(n>0) 個(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,下載提示(請認(rèn)真閱讀)
- 1.請仔細(xì)閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
9.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 軟件技術(shù) 基礎(chǔ) 試題庫
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
鏈接地址：http://www.820124.com/p-6591363.html