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

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