數(shù)據(jù)結(jié)構(gòu)練習(xí)題.doc

一、 單項(xiàng)選擇題1 關(guān)鍵路徑是指AOE(Activity On Edge)網(wǎng)中_。 (a). 最長的回路 (b). 最短的回路(c) 從源點(diǎn)到匯點(diǎn)(結(jié)束頂點(diǎn))的最長路徑 (d). 從源點(diǎn)到匯點(diǎn)(結(jié)束頂點(diǎn))的最短路徑2 以下序列中不符合堆定義的是_。 (a)(102，87，100，79，82，62，84，42，22，12，68) (b)(102，100，87，84，82，79，68，62，42，22，12) (c)(12，22，42，62，68，79，82，84，87，100，102) (d)(102，87，42，79，82，62，68，100，84，12，22)3 一個(gè)具有767個(gè)結(jié)點(diǎn)的完全二叉樹，其葉子結(jié)點(diǎn)個(gè)數(shù)為_。 (a). 383 (b). 384 (c). 385 (d). 3864. 一個(gè)二叉樹的前序遍歷序列為ABCDEFG，它的對(duì)稱序遍歷序列可能是（ ）(a). CABDEFG (b). ABCDEFG (c). DACEFBG (d). EABCDFG5. 高度為h的完全二叉樹（僅含根結(jié)點(diǎn)的二叉樹高度為零）的結(jié)點(diǎn)最少是多少（ ）(a). h1 (b). 2h1 (c). 2h+11 (d). 2h6. 對(duì)包含n個(gè)關(guān)鍵碼的散列表進(jìn)行檢索，平均檢索長度是（ ）(a). O( log2n ) (b). O( n ) (c). O(n log2n ) (d). 不直接依賴于n7. 設(shè)有關(guān)鍵碼初始序列 Q,H,C,Y,P,A,M,S,R,D,F,X，新序列F,H,C,D,P,A,M,Q,R,S,Y,X是采用下列哪種排序方法對(duì)初始序列進(jìn)行第一趟掃描的結(jié)果？(a). 直接插入排序 (b). 二路歸并排序 (c). 以第一元素為樞軸（或分界）元素的快速排序 (c). 基數(shù)排序8. 下列說法中錯(cuò)誤的是 (a). n個(gè)結(jié)點(diǎn)的樹的各結(jié)點(diǎn)度數(shù)之和為n-1 (b). n個(gè)結(jié)點(diǎn)的無向圖最多有n*(n-1)條邊(c). 用相鄰矩陣存儲(chǔ)圖時(shí)所需存儲(chǔ)空間大小與圖的結(jié)點(diǎn)數(shù)有關(guān)，而與邊數(shù)無關(guān)(d). 散列表中碰撞的可能性大小與負(fù)載因子有關(guān)9.堆是一種特殊的數(shù)據(jù)結(jié)構(gòu)，下面哪一個(gè)是堆： (a)19,75,34,26,97,56；(b)97,26,34,75,19,56；(c)19,56,26,97,34,75；(d)19,34,26,97,56,75；10.下面關(guān)于B樹和B+樹的敘述中，不正確的是 (a) B樹和B+樹都是平衡的多分樹； （b）B樹和B+樹都是可用于文件的索引結(jié)構(gòu)； (c) B樹和B+樹都能有效地支持順序檢索；(d) B樹和B+樹都能有效地支持隨機(jī)檢索；11.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成：(a)動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)；(b)緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)；(c)線性結(jié)構(gòu)和非線性結(jié)構(gòu)；(d)內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)；12.若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn, 那么p1=n；pi為：(a)i；(b)n=i；(c)n-i+1；(d)不確定；13.判斷一個(gè)循環(huán)隊(duì)列QU（最多元素m0）為空的條件是：(a)QU-front = = QU-rear；(b) QU-front! = QU-rear；(c) QU-front = = (QU-rear+1)%m0；(d) QU-front ! = (QU-rear+1)%m0；14.表達(dá)式a*(b+c)-d的后綴表達(dá)式是(a)abcd*+-；(b)abc+*d-；(c)abc*+d-；(d)*-a+bc；15.在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行：(a)s-next = p-next; p-next = s；(b)p -next = s-next; s-next = p；(c) q-next =s; s-next = p； (d) p-next =s; s-next = q；16.在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算是：(a) f-next = s；f=s；(b) f-next = s；r=s；(c) s-next = r；r=s；(d) s-next = f；f=s；17.將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用 (a) 棧 (b) 隊(duì)列(c) 鏈表 (d) 樹18.樹最適合用來表示 (a) 有序數(shù)據(jù)元素 (b) 無序數(shù)據(jù)元素(c) 元素之間具有分支層次關(guān)系的數(shù)據(jù)(d) 元素之間相關(guān)聯(lián)的數(shù)據(jù)19.要求一個(gè)線性表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，則可采用的查找方法是：(a) 分塊查找(b) 順序查找(c) 二分查找(d) 散列查找20.A node in a tree that does not have any children is called (a) a leaf； (b) an internal node； (c) a root； (d) an empty node； 21.對(duì)于一棵深度為2（僅含根結(jié)點(diǎn)的二叉樹高度為零）的二叉樹，它的總節(jié)點(diǎn)數(shù)：(a) 至多7個(gè) (b)至多2個(gè) (c) 節(jié)點(diǎn)數(shù)不限 (d) 至多4個(gè) 22.下面的偽碼是對(duì)二叉樹操作算法的片段： print( node ) if( there is a left child ) print( left child ); print data; if( there is a right child ) print( right child ); 這個(gè)算法是：（a）折半查找；（b）前序遍歷；（c）中序遍歷；（d）后序遍歷；23.下面哪個(gè)序列不是折半查找（二分查找）所訪問的數(shù)值序列(a) 10, 20, 30, 40, 50； (b) 50, 40, 30, 20, 10； (c) 10, 20, 30, 15, 18； (d) 30, 35, 40, 45, 4224.遞歸函數(shù)可以調(diào)用自身多少次?(a) 至多1次; (b) 任意次數(shù); (c) 0 次; (d) 至多2次;25.分析下面函數(shù)：int f( int n ) if( n = = 0 ) return 0; if( (n & 1) = = 0 ) return f(n/2); return f(n/2) + 1; 調(diào)用函數(shù)f(10)的返回值是：(a) 1； (b) 3； (c) 5； (d) 2；26.假如n,m=0，那么下面函數(shù)的功能是： int ff( int n, int m ) if( n = 0 ) return m; return ff( n-1, m*n ); (a) 計(jì)算m * (n!)； (b) 計(jì)算最大公約數(shù)； (c)計(jì)算最小公倍數(shù)； (d) 計(jì)算(m + n)!；27.總的來說，哈希方法（hashing，也稱散列方法）的主要問題在于：(a)哈希函數(shù)難以計(jì)算；(b)哈希表的存取速度慢；(c)會(huì)發(fā)生沖突；(d)哈希表占很多內(nèi)存；28.對(duì)于一個(gè)大小為m含有n項(xiàng)的哈希表，它的負(fù)載(load)因子是：(a) m - n； (b) n + m； (c) m/n； (d) n/m ；29.下面對(duì)p的聲明，那一個(gè)是指向整數(shù)的指針：(a) int *p； (b) int p； (c) int &p； (d) int *p；30.假設(shè)Thing是一個(gè)用戶定義的類，B是Thing的一個(gè)實(shí)例，對(duì)于下面的代碼段Thing A = B用到了類Thing中的哪一個(gè)成分：(a)賦值操作符；(b)析構(gòu)函數(shù)；(c)構(gòu)造函數(shù)；(d)復(fù)制構(gòu)造函數(shù)；31.下面對(duì)類的部分描述用于說明一種用戶定義的實(shí)數(shù)實(shí)現(xiàn)： class RealNumber . RealNumber( float x ); RealNumber( float x, float y=0 ); ;這段代碼可能錯(cuò)在哪里?(a)在構(gòu)造函數(shù)中不允許時(shí)有缺省值；(b)沒有錯(cuò)誤；(c)第二個(gè)構(gòu)造函數(shù)與第一個(gè)不一致；(d)用兩個(gè)實(shí)數(shù)參數(shù)無法創(chuàng)建一個(gè)實(shí)數(shù)；32.面向?qū)ο蟮某绦蛟O(shè)計(jì)最適合下面哪一種開發(fā)要求:(a)程序是一個(gè)完整的程序模塊；(b)提供完善的代碼復(fù)用；(c)獲得高效率；(d)對(duì)封裝的需求；33.對(duì)于有n個(gè)節(jié)點(diǎn)e條邊的圖，如果用鄰接表表示，則計(jì)算全部入度的時(shí)間復(fù)雜度是:(a) O(n + e)； (b) O(n2)； (c) O(n3)； (d) O(n * e) ；34.結(jié)定結(jié)點(diǎn)的關(guān)鍵字序列（、），對(duì)它按字母的字典順序進(jìn)行排列， 快速排序的第一趟結(jié)果是：(a)（C、B、D、A、F、E、I、J、G、H）(b)（C、B、D、A、E、F、I、G、J、H） (c)（B、A、D、E、F、G、I、J、H、C）(d)（B、C、D、A、E、F、I、J、G、H）35.計(jì)算機(jī)算法是指(a) 數(shù)值計(jì)算方法(b) 對(duì)抽象數(shù)據(jù)結(jié)構(gòu)的操作方法(c) 非數(shù)值計(jì)算方法(d) 解決問題的有限運(yùn)算序列36、對(duì)于順序存儲(chǔ)的隊(duì)列，存儲(chǔ)空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一個(gè)環(huán)，則隊(duì)列中元素的個(gè)數(shù)為.( ) (a) R-F (b).n+R-F (c).(R-F+1)mod n (d).(n+R-F)mod n37、鏈表不具備的特點(diǎn)是( )。 A可隨機(jī)訪問任何一個(gè)元素 B插入、刪除操作不需要移動(dòng)元素 C無需事先估計(jì)存儲(chǔ)空間大小 D所需存儲(chǔ)空間與線性表長度成正比 38、對(duì)矩陣壓縮存儲(chǔ)的主要目的是( )。 A方便運(yùn)算 B節(jié)省存儲(chǔ)空間 C 降低計(jì)算復(fù)雜度 D提高運(yùn)算速度 39、判斷“鏈?zhǔn)疥?duì)列為空 ”的條件是 ( )（front為頭 指針，rear為尾指針）。Afront=NULL Brear=NULL Cfront=rear Dfront!=rear 40、關(guān)于字符串的判定語句中正確的是( )。 A字符串是一種特殊的線性表B串的長度必須大于零 C字符串不屬于線性表的一種 C空格字符組成的串就是空串 41、有100個(gè)結(jié)點(diǎn)的樹中，其邊的數(shù)目為( )。 A101 B100 C99 D98 42、在程序的執(zhí)行過程中，用 ( )結(jié)構(gòu)可實(shí)現(xiàn)嵌套調(diào)用函數(shù)的正確返回。 A隊(duì)列 B棧 C樹 D圖 43、已知遞歸函數(shù)f(n)的功能是計(jì)算1+ 2+n，且n1，應(yīng)采用的代碼段是( )。Aif n=l then return 1 else return n+f(n-1) Bif n=l then return 1 else return n+f(n+1) Cif n=l then return 0 else return n+f(n-1) Dif n=l then return 0 else return n+f(n+1)44、將一個(gè)三對(duì)角矩陣A l.100，1.100中的元素按行存儲(chǔ)在一維數(shù)組Bl.298中，矩陣A中的元素A66，65在數(shù)組B中的下標(biāo)為 ( )。 A195 B196 C197 D198 45、給定一個(gè)有n個(gè)元素的線性表。若采用順序存儲(chǔ)結(jié)構(gòu)，則在等概率前提下，向其插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)平均為 ( )。An+l Bn/2 C(n+l)/2 D.n 46、( )是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)。 A廣義表 B高維數(shù)組 C雙端隊(duì)列 D二叉樹 47、結(jié)論“( )”是正確的。 A二叉樹的度為2 B樹中結(jié)點(diǎn)的度可以小于2 C二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 D二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2 48、某線性表最常用的運(yùn)算是插入和刪除，插入運(yùn)算是指在表尾插入一個(gè)新元素。刪除運(yùn)算是指刪除表頭第一個(gè)元素，那么采用( )存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 A僅有尾指針的單向循環(huán)鏈表 B僅有頭指針的單向循環(huán)鏈表 C單向鏈表 D雙向鏈表 49、表達(dá)式采用逆波蘭式表示時(shí)可以不用括號(hào)，而且可以用基于( 1 )的求值過程進(jìn)行計(jì)算。與逆波蘭式ab+cd+*對(duì)應(yīng)的中綴表達(dá)式是( 2 )。(1)A棧 B隊(duì)列 C符號(hào)表 D散列表 (2)Aa+b+c*d B(a +b)*c+d C.(a+b)*(c+d) Da+b *c+d50、設(shè)數(shù)組a3.16，5.20的元素以列為主序存放，每個(gè)元素占用兩個(gè)存儲(chǔ)單元，則數(shù)組元素ai,j(3i16，5j20)的地址計(jì)算公式為( )。Aa-118+2i+28j Ba-116+2i+28j Ca-144+2i +28j Da-146+2i+28j51.一個(gè)棧的輸入序列為1，2，3，4，下面哪一個(gè)序列不可能是這個(gè)棧的輸出序列？（ ） A. 1，3，2，4 B. 2，3，4，1 C. 4，3，1，2 D. 3，4，2，152.下列排序方法中，哪一種方法的比較次數(shù)與紀(jì)錄的初始排列狀態(tài)無關(guān)？（ ） A. 直接插入排序 B. 起泡排序 C. 快速排序 D. 直接選擇排序53.對(duì)n個(gè)記錄的文件進(jìn)行二路歸并排序，總的時(shí)間代價(jià)為 A. O（nlog2n） B. O（n2） C. O（log2n） D. O（n）54.若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，則該二叉樹的度為0的結(jié)點(diǎn)個(gè)數(shù)是（ ） A. 9 B. 11 C. 12 D. 不確定55.下面關(guān)于B樹和B+樹的敘述中，不正確的是 A. B樹和B+樹都是平衡的多分樹 B. B樹和B+樹都是可用于文件的索引結(jié)構(gòu)C. B樹和B+樹都能有效地支持順序檢索 D. B樹和B+樹都能有效地支持隨機(jī)檢索56在一棵m階B樹中，若在某結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵字而引起該結(jié)點(diǎn)分裂，則此結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是 。Am Bm 1 Cml Dm257.如果具有n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有( )棵生成樹。 An Bn +l Cn-l D2n 58一棵前序序列為1，2，3，4的二叉樹，其中序序列不可能是 。 A4,1,2,3 B.4,3,2,1 C.2,4,3,1 D.3,4,2,159具有n個(gè)頂點(diǎn)和e條邊的圖的深度優(yōu)先搜索算法的時(shí)間復(fù)雜度為 AO(n) BO(n3) CO(n2) DO(n*e) 60堆排序算法在平均情況下的時(shí)間復(fù)雜度為 A O(n) BO(nlogn) CO(n2) DO(logn) 61在待排序數(shù)據(jù)已基本有序的前提下，下述排序方法中效率最高的是 A 直接插入排序 B直接選擇排序 C快速排序 D歸并排序 62在理想情況下，散列表中查找元素所需的比較次數(shù)為 。An BO Cn2 D163. 在數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)項(xiàng)是有意義的數(shù)據(jù)的（）單位?；咀钚∽畲筇厥?4. 在一個(gè)以 h為頭指針的雙向循環(huán)鏈表中，指針p所指的元素是尾元素的條件是（ ）。A. p=h B. h-rlink=p C. p-llink=h D. p-rlink=h65. 假設(shè)循環(huán)隊(duì)列的最大容量為m的，隊(duì)尾指針是rear，隊(duì)頭指針是front，則隊(duì)列為滿的條件是（ ）。A.(rear+1) % m=front B. rear=front Crear+1=front D. (rear-l) % m=front66. 深度為d(d1)的完全二叉樹至少有 ( )個(gè)結(jié)點(diǎn)。A2d-1+1 B2d-1 C2d-1 D 2d-1-167. 在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是（ ）。Ap-next=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;68. 對(duì)一個(gè)表長為12的有序順序表進(jìn)行二分查找，假定對(duì)表中每個(gè)記錄的查找概率相等,則查找成功的平均查找長度為( )。A. 4 B. 3.1 C. 2.8 D. 1.269. An，n是對(duì)稱矩陣，將下三角（包括對(duì)角線）以行序存儲(chǔ)到一維數(shù)組Tn （n+1）/2中， 則對(duì)任一上三角元素aij對(duì)應(yīng)Tk的下標(biāo)k是（ ）。A. i（i-1）/2+j B. j（j-1）/2+i C. i（i-1）/2+j-1 D. j（j-1）/2+i-1 70. 一個(gè)有兩個(gè)以上結(jié)點(diǎn)的二叉樹的前序遍歷序列與中序遍歷序列正好相反，則該二叉樹（ ）。A. 任一結(jié)點(diǎn)沒有左子樹 B. 任一結(jié)點(diǎn)沒有右子樹C. 任一結(jié)點(diǎn)不能同時(shí)有左子樹和右子樹 D. 不存在71. 計(jì)算機(jī)算法是指數(shù)值計(jì)算方法對(duì)抽象數(shù)據(jù)結(jié)構(gòu)的操作方法非數(shù)值計(jì)算方法解決問題的有限運(yùn)算序列72. 串的長度是（）。串中不同字符的個(gè)數(shù) 串中不同字母的個(gè)數(shù)串中所含字符的個(gè)數(shù)且字符個(gè)數(shù)大于0 串中所含字符的個(gè)數(shù)73. 將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用（）。棧對(duì)列鏈表樹74. 判斷一個(gè)循環(huán)隊(duì)列QU（最多元素m0）為空的條件是（）。QU-front = = QU-rearQU-front! = QU-rearQU-front = = (QU-rear+1)%m0QU-front ! = (QU-rear+1)%m075. 將一個(gè)對(duì)稱矩陣Al.50，1. .50中的元素按行壓縮存儲(chǔ)在一維數(shù)組B中，數(shù)組B的元素總個(gè)數(shù)為（ ）。A2500 B1275 C1225 D150076. 在具有100個(gè)結(jié)點(diǎn)的樹中，其邊的數(shù)目為（）。 10110099D9877. 在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算是：f-next = s；f=s；f-next = s；r=s；s-next = r；r=s；s-next = f；f=s；78. 某線性表最常用的運(yùn)算是插入和刪除，插入運(yùn)算是指在表尾插入一個(gè)新元素。刪除運(yùn)算是指刪除表頭第一個(gè)元素，那么采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。僅有尾指針的單向循環(huán)鏈表 僅有頭指針的單向循環(huán)鏈表單向鏈表 雙向鏈表79. 如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的（）。前序中序后序?qū)又行?0. 下面關(guān)于B樹和B+樹的敘述中，不正確的是（）。B樹和B+樹都是平衡的多分樹 B樹和B+樹都是可用于文件的索引結(jié)構(gòu)B樹和B+樹都能有效地支持順序檢索 B樹和B+樹都能有效地支持隨機(jī)檢索81. 當(dāng)序列中的記錄基本有序或n值較小時(shí)，最佳的排序方法( )。交換排序 堆排序 插入排序 基數(shù)排序82. 深度為5的二叉樹至多有個(gè)結(jié)點(diǎn)（）。1632311083. 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行（ ）。s-next = p-next; p-next = sp -next = s-next; s-next = pq-next =s; s-next = pp-next =s; s-next = q84. 在單向鏈表的第i個(gè)結(jié)點(diǎn)前插入新結(jié)點(diǎn)時(shí)，需預(yù)先保留的結(jié)點(diǎn)指針是 （ ）。指向i結(jié)點(diǎn)的指針指向i結(jié)點(diǎn)的前趨結(jié)點(diǎn)的指針指向i結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針無需保留85. 在數(shù)據(jù)結(jié)構(gòu)中為了敘述的方便和避免產(chǎn)生混淆，通常把數(shù)據(jù)的物理結(jié)構(gòu)統(tǒng)稱為（）。存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)86. 下列屬于隨機(jī)存取結(jié)構(gòu)的是（）。線性鏈表順序表循環(huán)鏈表雙向鏈表87. 下面程序段的時(shí)間復(fù)雜度為（ ）。for（i=0；i=n;+i）for（j=0；j1)個(gè)結(jié)點(diǎn)構(gòu)成的完全二叉樹，其深度為（ ）。 Log2n +1 Log2n -1 log2n+1 Log2n-191. 對(duì)于一棵深度為2的二叉樹，它的總結(jié)點(diǎn)數(shù)：A至多7個(gè) B.至多2個(gè) C. 結(jié)點(diǎn)數(shù)不限 D. 至多4個(gè) 92. 有n個(gè)結(jié)點(diǎn)的完全二叉樹,其最后一個(gè)非終端節(jié)點(diǎn)為（ ）。 n/2 n/2 2n 2n93. 對(duì)于有n個(gè)結(jié)點(diǎn)e條邊的圖，如果用鄰接表表示，則計(jì)算全部結(jié)點(diǎn)入度的時(shí)間復(fù)雜度是:A.O(n + e) B. O(n2) C. O(n3) D. O(n * e) 94. 下面哪個(gè)序列不是折半查找（二分查找）所訪問的數(shù)值序列( )A.10, 20, 30, 40, 50 B. 50, 40, 30, 20, 10 C.13, 26, 30, 45, 68 D. 30, 50, 40, 45, 4295. 給定結(jié)點(diǎn)的關(guān)鍵字序列（、），對(duì)它按字母的字典順序進(jìn)行排列（選F為樞軸），快速排序的第一趟結(jié)果是( )A.（C、B、D、A、F、E、I、J、G、H）B.（C、B、D、A、E、F、I、G、J、H）C.（B、A、D、E、F、G、I、J、H、C）D.（B、C、D、A、E、F、I、J、G、H）96. 總的來說，散列方法（hashing，也稱哈希方法）的主要問題在于( )A.哈希函數(shù)難以計(jì)算B.哈希表的存取速度慢C.會(huì)發(fā)生沖突 D.哈希表占很多內(nèi)存97. 堆是一種特殊的數(shù)據(jù)結(jié)構(gòu)，下面哪一個(gè)是堆( )A.19,75,34,26,97,56 B.97,26,34,75,19,56 C.19,56,26,97,34,75 D.19,34,26,97,56,7598. 一棵具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹的總結(jié)點(diǎn)數(shù)為（ ）。Anl Bn C2n-l D2n 99. 用循環(huán)鏈表表示隊(duì)列，設(shè)隊(duì)列的長度為n，若只設(shè)尾指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別為( )。AO(1)，O(1) B. O(1)，O(n) C. O(n)，O(1) D. O(n)，O(n)100. 設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，則數(shù)據(jù)結(jié)構(gòu)A是（ ）。 A.線性結(jié)構(gòu) B. 樹型結(jié)構(gòu) C.物理結(jié)構(gòu) D.圖型結(jié)構(gòu)101. 設(shè)有n個(gè)待排序的記錄關(guān)鍵字，則在堆排序中需要（ ）個(gè)輔助記錄單元。 A.1B.nC.nlog2nD.n2102. 設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（ ）。 A.n，e B.e，n C.2n，e D.n，2e103. 設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許退棧操作,則不可得到的序列是（ ）。A. cbafed B. abcdef C. cabdef D. fedcba104. 鏈表不具有的特點(diǎn)是 （ ）。 A.隨機(jī)訪問 B.不必事先估計(jì)存儲(chǔ)空間 C.插入刪除不需要移動(dòng)元素 D.所需空間與線性表成正比 105. 設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點(diǎn)，則其判空條件是（ ）。A.head=0 B.head-next=0 C.head-next=head D.head!=0106. 對(duì)矩陣壓縮存儲(chǔ)的主要目的是( )。 A方便運(yùn)算B節(jié)省存儲(chǔ)空間C降低計(jì)算復(fù)雜度D提高運(yùn)算速度 107. 在長度為n(n0)的順序表中插入一個(gè)元素時(shí)（假設(shè)在任何位置上插入或刪除元素概率相等）,平均要移動(dòng)的元素個(gè)數(shù)是( )。n 2n/3 n/2 n/3108. 對(duì)于只在首、尾進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為（ ）。A.順序表 B. 用頭指針表示的單循環(huán)鏈表C.用尾指針表示的單循環(huán)鏈表 D. 單鏈表109. 計(jì)算機(jī)算法是指（ ）。A.數(shù)值計(jì)算方法B.對(duì)抽象數(shù)據(jù)結(jié)構(gòu)的操作方法C.非數(shù)值計(jì)算方法D.解決問題的有限運(yùn)算序列110. 以下關(guān)于廣義表的敘述中,正確的是（ ）。A.廣義表是由0個(gè)或多個(gè)單元素或子表構(gòu)成的有限序列B.廣義表至少有一個(gè)元素是子表C.廣義表不能遞歸定義 D.廣義表不能為空表111. 一棵含18個(gè)結(jié)點(diǎn)的二叉樹的高度至少為（ ）(設(shè)根結(jié)點(diǎn)所在的二叉樹高度為1)。A.3 B.4 C.5 D.6112. 設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為1，則高度為n的二叉樹中所含葉子結(jié)點(diǎn)的個(gè)數(shù)最多為（ ）個(gè)。A.2n B.n C.2n -1 D.2n-1113. 任何一個(gè)無向連通網(wǎng)的最小生成樹（ ）。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在114. 對(duì)一棵二叉搜索樹進(jìn)行（ ）得到的結(jié)點(diǎn)序列是一個(gè)有序序列。A前序遍歷 B. 中序遍歷 C.后序遍歷 D. 層次遍歷115. 在含n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（ ）。 A.e B.2e C.n2-e D.n2-2e 116. 對(duì)矩陣壓縮存儲(chǔ)的主要目的是( )。 A方便運(yùn)算B節(jié)省存儲(chǔ)空間C降低計(jì)算復(fù)雜度D提高運(yùn)算速度 117. 在具有100個(gè)結(jié)點(diǎn)的樹中，其邊的數(shù)目為（ ）。 101 100 99 D98118. 下列屬于隨機(jī)存取結(jié)構(gòu)的是（ ）。A線性鏈表 .順序表 .循環(huán)鏈表 .雙向鏈表119. 所有的操作只能在一端進(jìn)行的數(shù)據(jù)結(jié)構(gòu)是（ ）。 A隊(duì)列 .棧 .棧和隊(duì)列 .循環(huán)隊(duì)列120. 由n(1)個(gè)結(jié)點(diǎn)構(gòu)成的完全二叉樹，其深度為（ ）。 A Log2 (n+1) Log2 (n-1) .log2n+1 .Log2n-1121. 在樹表示中,雙親表示法可以在常量時(shí)間內(nèi)實(shí)現(xiàn)的操作（ ）。A.Parent(T,ax) B.Leftchild(T,x) C.Rightsibling(T,x) D.Deletechild(&T,&p,I)122. 具有n個(gè)頂點(diǎn)的無向完全圖應(yīng)具有的邊數(shù)為（ ）。 A.n .n2-1 .n（n-1）/2 .n（n+1）/2123. （ ）是穩(wěn)定的內(nèi)排序方法。 A.快速排序 .堆排序 .希爾排序 .基數(shù)排序124. 總的來說，哈希方法（hashing，也稱散列方法）的主要問題在于( )。A.哈希函數(shù)難以計(jì)算B.哈希表的存取速度慢C.會(huì)發(fā)生沖突 D.哈希表占很多內(nèi)存125. 堆是一種特殊的數(shù)據(jù)結(jié)構(gòu)，下面（ ）是堆。A.19,75,34,26,97,56 B.97,26,34,75,19,56 C.19,56,26,97,34,75 D.19,34,26,97,56,75126. 下面關(guān)于B樹和B+樹的敘述中，不正確的是（ ）。 A.B樹和B+樹都是平衡的多分樹 B.B樹和B+樹都是可用于文件的索引結(jié)構(gòu)C.B樹和B+樹都能有效地支持順序檢索 D.B樹和B+樹都能有效地支持隨機(jī)檢索127. 以下關(guān)于字符串的判定語句中正確的是( )。 A字符串是一種特殊的線性表 B串的長度必須大于零 C字符串不屬于線性表的一種 D空格字符組成的串就是空串128. 如果具有n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有( )棵生成樹。 An Bn +l Cn-l D2n 129. 一棵前序序列為1，2，3，4的二叉樹，其中序序列不可能是 。 A4,1,2,3 B.4,3,2,1 C.2,4,3,1 D.3,4,2,1130. 具有n個(gè)頂點(diǎn)和e條邊的圖的深度優(yōu)先搜索算法的時(shí)間復(fù)雜度為 AO(n) BO(n3) CO(n2) DO(n*e) 131. 堆排序算法在平均情況下的時(shí)間復(fù)雜度為 B O(n) BO(nlogn) CO(n2) DO(logn) 132. 在待排序數(shù)據(jù)已基本有序的前提下，下述排序方法中效率最高的是 B 直接插入排序 B直接選擇排序 C快速排序 D歸并排序 133. 在理想情況下，散列表中查找元素所需的比較次數(shù)為 。An BO Cn2 D1134. ( )是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)。 A廣義表 B高維數(shù)組 C雙端隊(duì)列 D二叉樹 135. 結(jié)論“( )”是正確的。 A二叉樹的度為2 B樹中結(jié)點(diǎn)的度可以小于2 C二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 D二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2 136. 某線性表最常用的運(yùn)算是插入和刪除，插入運(yùn)算是指在表尾插入一個(gè)新元素。刪除運(yùn)算是指刪除表頭第一個(gè)元素，那么采用( )存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 A僅有尾指針的單向循環(huán)鏈表 B僅有頭指針的單向循環(huán)鏈表 C單向鏈表 D雙向鏈表 137. 表達(dá)式采用逆波蘭式表示時(shí)可以不用括號(hào)，而且可以用基于( 1 )的求值過程進(jìn)行計(jì)算。與逆波蘭式ab+cd+*對(duì)應(yīng)的中綴表達(dá)式是( 2 )。(1)A棧 B隊(duì)列 C符號(hào)表 D散列表 (2)Aa+b+c*d B(a +b)*c+d C.(a+b)*(c+d) Da+b *c+d138. 設(shè)數(shù)組a3.16，5.20的元素以列為主序存放，每個(gè)元素占用兩個(gè)存儲(chǔ)單元，則數(shù)組元素ai,j(3i16，5j20)的地址計(jì)算公式為( )。Aa-118+2i+28j Ba-116+2i+28j Ca-144+2i +28j Da-146+2i+28j139. 一個(gè)棧的輸入序列為1，2，3，4，下面哪一個(gè)序列不可能是這個(gè)棧的輸出序列？（ ） A. 1，3，2，4 B. 2，3，4，1 C. 4，3，1，2 D. 3，4，2，1140. 下列排序方法中，哪一種方法的比較次數(shù)與紀(jì)錄的初始排列狀態(tài)無關(guān)？（ ） A. 直接插入排序 B. 起泡排序 C. 快速排序 D. 直接選擇排序141. 對(duì)n個(gè)記錄的文件進(jìn)行二路歸并排序，總的時(shí)間代價(jià)為 A. O（nlog2n） B. O（n2） C. O（log2n） D. O（n）142. 若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，則該二叉樹的度為0的結(jié)點(diǎn)個(gè)數(shù)是（ ） A. 9 B. 11 C. 12 D. 不確定143. 對(duì)于一個(gè)大小為m含有n項(xiàng)的哈希表，它的負(fù)載(load)因子是：(a) m - n； (b) n + m； (c) m/n； (d) n/m ；144. 下面對(duì)p的聲明，那一個(gè)是指向整數(shù)的指針：(a) int *p； (b) int p； (c) int &p； (d) int *p；145. 假設(shè)Thing是一個(gè)用戶定義的類，B是Thing的一個(gè)實(shí)例，對(duì)于下面的代碼段Thing A = B用到了類Thing中的哪一個(gè)成分：(a)賦值操作符；(b)析構(gòu)函數(shù)；(c)構(gòu)造函數(shù)；(d)復(fù)制構(gòu)造函數(shù)；146. 下面對(duì)類的部分描述用于說明一種用戶定義的實(shí)數(shù)實(shí)現(xiàn)： class RealNumber . RealNumber( float x ); RealNumber( float x, float y=0 ); ;這段代碼可能錯(cuò)在哪里?(a)在構(gòu)造函數(shù)中不允許時(shí)有缺省值；(b)沒有錯(cuò)誤；(c)第二個(gè)構(gòu)造函數(shù)與第一個(gè)不一致；(d)用兩個(gè)實(shí)數(shù)參數(shù)無法創(chuàng)建一個(gè)實(shí)數(shù)；147. 面向?qū)ο蟮某绦蛟O(shè)計(jì)最適合下面哪一種開發(fā)要求:(a)程序是一個(gè)完整的程序模塊；(b)提供完善的代碼復(fù)用；(c)獲得高效率；(d)對(duì)封裝的需求；148. 對(duì)于有n個(gè)節(jié)點(diǎn)e條邊的圖，如果用鄰接表表示，則計(jì)算全部入度的時(shí)間復(fù)雜度是:(a) O(n + e)； (b) O(n2)； (c) O(n3)； (d) O(n * e) ；二、填空題1若一個(gè)具有n個(gè)結(jié)點(diǎn)、k條邊的非連通無向圖是一個(gè)森林(nk)，則該森林中必有（ n - m ）棵樹。 2. 含有3個(gè)2度結(jié)點(diǎn)和4個(gè)葉結(jié)點(diǎn)的二叉樹可含（ 無窮 ）個(gè)1度結(jié)點(diǎn)。3. 含有2的n次方個(gè)結(jié)點(diǎn)的二叉樹高度至少是（ n ），至多是（ 2n - 1 ）（僅含根結(jié)點(diǎn)的二叉樹高度為零）。4. 用起泡法對(duì)n個(gè)關(guān)鍵碼排序，在最好情況下，只需做（ n-1 ）次比較和（ 0 ）次移動(dòng)；在最壞的情況下要做（ n(n-1)/2 ）次比較。5.在用于表示有向圖的鄰接矩陣中, 對(duì)第i行的元素進(jìn)行累加, 可得到第i 個(gè)頂點(diǎn)的（ 出/入 ）度, 而對(duì)第j列的元素進(jìn)行累加, 可得到第j個(gè)頂點(diǎn)的（ 入/出 ）度。 6.一個(gè)連通圖的生成樹是該圖的（ 極小 ）連通子圖。若這個(gè)連通圖有n個(gè)頂點(diǎn), 則它的生成樹有（ n-1 ）條邊。 7.給定序列100, 86, 48, 73, 35, 39, 42, 57, 66, 21, 按堆結(jié)構(gòu)的定義, 則它一定（ 大頂 ）堆。 8.在進(jìn)行直接插入排序時(shí), 其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（ 有 ）關(guān)；而在進(jìn)行直接選擇排序時(shí)，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（ 無 ）關(guān)。 9.利用關(guān)鍵碼分別為10, 20, 30, 40的四個(gè)結(jié)點(diǎn)，能構(gòu)造出（ 48 ）種不同的二叉排序樹。 10在樹結(jié)構(gòu)里，有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū)，稱為根。非根結(jié)點(diǎn)有且僅有一個(gè)（ 前驅(qū) ）,且存在一條從根到該結(jié)點(diǎn)的（ 路徑 ）。11、評(píng)價(jià)數(shù)據(jù)結(jié)構(gòu)的兩條基本標(biāo)準(zhǔn)是：（unkown ）和（ unkown ）。12、對(duì)于順序存儲(chǔ)的棧，因?yàn)闂５目臻g是有限的，在進(jìn)行（ 進(jìn)棧 ）運(yùn)算時(shí)，可能發(fā)生棧的上溢，在進(jìn)行（ 出棧 ）運(yùn)算時(shí)，可能發(fā)生棧的下溢。13、對(duì)于單鏈表形式的隊(duì)列，其空隊(duì)列的F指針和R指針都等于（ NULL ）。14、若S1=linkedst,S2=ring,則S1/S2=（ unkown ）。15、設(shè)根結(jié)點(diǎn)的層數(shù)為0，定義樹的高度為樹中層數(shù)最大的結(jié)點(diǎn)的層數(shù)加1。則高度為k的二叉樹具有的結(jié)點(diǎn)數(shù)目，最少為（ k+1 ）,最多為（ 2(k+1) - 1 ）。16.從邏輯結(jié)構(gòu)看，線性表是典型的（ 線性結(jié)構(gòu) ），樹是典型的（ 非線性結(jié)構(gòu) ） 。17.設(shè)有二維數(shù)組A0.9,0.19，其每個(gè)元素占兩