數(shù)據(jù)結(jié)構(gòu)學(xué)位考試試題

1、數(shù)據(jù)結(jié)構(gòu)課程學(xué)位考試試題(參考答案在題后)；錯(cuò)，在題號(hào)后填入“X判斷題：判斷下列各小題敘述的正誤。對(duì)，在題號(hào)后的括號(hào)內(nèi)填入“V1、 數(shù)據(jù)的最小單位是數(shù)據(jù)項(xiàng)。 .(V)2、 多重表文件中主索引為非稠密索引，次索引為稠密索引。.(V ) 3、通常數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中有四種不同的表示方法分為順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)、文件存儲(chǔ)。.(X )4、 算法具有輸入、輸出、可行性、穩(wěn)定性、有窮性五個(gè)特性。.(X )5、 數(shù)據(jù)的基本單位是數(shù)據(jù)項(xiàng)。 .(X )6、 算法的復(fù)雜度分為時(shí)間復(fù)雜度和效率復(fù)雜度。 .(X )7、 性質(zhì)相同的數(shù)據(jù)元素的集合成為數(shù)據(jù)對(duì)象。 ( V )8、所有結(jié)點(diǎn)按 1 對(duì) 1 的鄰接

2、關(guān)系構(gòu)成的整體就是集合結(jié)構(gòu)。 ( X )9、 散列文件不能順序存取、只能按關(guān)鍵字隨機(jī)存取。 .(V )10、 數(shù)據(jù)的基本單位是數(shù)據(jù)元素。 .(V )11、 扌樹中的K個(gè)孩子的結(jié)點(diǎn)必有 K個(gè)關(guān)鍵字。.(V)12、 B+樹中的K個(gè)孩子的結(jié)點(diǎn)必有 K個(gè)關(guān)鍵字。.(V )13、 倒排表的索引項(xiàng)中沒有頭指針和鏈表長(zhǎng)度項(xiàng)。 .(V )14、 磁帶是順序存取的外存儲(chǔ)設(shè)備。 ( X )15、 索引文件只能是磁盤文件。 (V )16、 順序文件只適宜于順序存取。 ( X )17、 磁帶是順序存取的外存儲(chǔ)設(shè)備。 .(X )18、 線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲(chǔ)，也可以鏈接存儲(chǔ)。 .(V)19、 倒排表的索引項(xiàng)中沒有頭

3、指針和鏈表長(zhǎng)度項(xiàng)。 .(V)20、 散列文件不能順序存取、只能按關(guān)鍵字隨機(jī)存取。.( V )21、 棧和隊(duì)列都是順序存取的的線性表，但它們對(duì)存取位置的限制不同。(V)22、 循環(huán)鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn) ( V )23、單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。.(X )24、 線性表采用順序存儲(chǔ)表示時(shí)，必須占用一片連續(xù)的存儲(chǔ)單元。(V )25、 循環(huán)鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。 ( V )26、 設(shè)串S的長(zhǎng)度為n,則S的子串個(gè)數(shù)為n(n+1)/2 .( X )27、 線性表采用鏈接存儲(chǔ)表示時(shí)，必須占用一片連續(xù)的存儲(chǔ)單元。( X )28、 鏈接表上做刪除和

4、插入運(yùn)算時(shí)的平均時(shí)間復(fù)雜度都是O(n) ( X)29、 線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。 ( V )30、 順序表上做刪除和插入運(yùn)算時(shí)的平均時(shí)間復(fù)雜度都是O(n) ( V )31、 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為匚2log2 nj +1 ( X )則有32、在只有度為 0 和度為 2 的結(jié)點(diǎn)的二叉樹中，設(shè)度為 0 的結(jié)點(diǎn)有 n0 個(gè)，度為 2 的結(jié)點(diǎn)有 n2 個(gè)，n0=n2+1 (V )33、 循環(huán)隊(duì)列判斷隊(duì)列為滿的條件是sq->front+1= =sq->rear 。 (X )34、 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。( V )

5、35、若二叉樹中各結(jié)點(diǎn)的值均不相同，則由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均 能惟一地確定一棵二叉樹。 ( V )36、有n個(gè)結(jié)點(diǎn)的不同的二叉樹有 n!棵。( X )37、 一般樹和二叉樹的結(jié)點(diǎn)數(shù)目都可以為0。 (V )38、 循環(huán)隊(duì)列判斷隊(duì)列為空的條件是sq->front= =sq->rear。 (V )39、 設(shè)有一順序棧 S,元素s1,s 2,s 3,s 4,s 5,s 6依次進(jìn)棧，如果 6個(gè)元素出線的順序是 s2,s 3,s 4, s 6 , s 5,s 1,則 棧的容量至少應(yīng)該是3。.( V)40、在只有度為0和度為k的結(jié)點(diǎn)的k叉樹中，設(shè)度為0的結(jié)點(diǎn)有n

6、0個(gè)，度為k的結(jié)點(diǎn)有nk個(gè)，則有n0=nk+1 .( x )41、 一個(gè)連通圖的生成樹，是含該連通圖的全部頂點(diǎn)的一個(gè)極小連通子圖.(V )42、 在二叉樹的第i層上至多有2-個(gè)結(jié)點(diǎn).(V )43、 先根遍歷樹和先根遍歷與該樹對(duì)應(yīng)的二叉樹，其結(jié)果不一樣。(X )44、 由樹轉(zhuǎn)化成二叉樹，其根的右子女指針總是空的.(V )45、 網(wǎng)絡(luò)的最小代價(jià)生成樹是唯一的 .(X )46、 深度優(yōu)先搜索遍歷類似于樹的先根遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是隊(duì)列。(X )47、在一棵二叉樹中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒有右子女，對(duì)它分別進(jìn)行中序遍歷和后序遍歷，則具有相同的結(jié)果。(V)48、對(duì)于一棵具有n個(gè)結(jié)點(diǎn)，其高度為h的

7、二叉樹，進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度為 O(n)。 .( V )49、 圖的深度優(yōu)先搜索類似于樹的先根次序遍歷 .(V)50、 在無向圖中定義頂點(diǎn)V i與V之間的路徑為從 V i到達(dá)V的一個(gè)頂點(diǎn)序列(V )51、 設(shè)無向連通圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有n(n-1)/2 條邊.(V )52、 圖的廣度優(yōu)先遍歷是樹的按中根遍歷推廣。(X )53、 設(shè)圖 G=(V,E) , V=1,2,3,4, E=<1,2>,<1,3>,<2,4>,<3,4>，從頂點(diǎn) 1 出發(fā)，對(duì)圖G進(jìn)行廣度優(yōu)先搜索的序列有2種( V )54、 用鄰接表作為有向圖G的存儲(chǔ)結(jié)構(gòu)。

8、設(shè)有 n個(gè)頂點(diǎn)、e條弧，則拓?fù)渑判虻臅r(shí)間復(fù)雜度為O(n*e) .( x )55、 查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合(V)56、存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān) . .(V )57、 圖的深度和廣度遍歷兩種操作的時(shí)間復(fù)雜度都為O (n*e )。 .(x n)158、 只有無向圖，頂點(diǎn)數(shù)n、邊數(shù)e和度數(shù)之間有如下關(guān)系：e=DXv)59、 裝載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的裝滿程度。(V) i 160、 閉散列法通常比開散列法時(shí)間效率更高。(X )61、 進(jìn)行折半搜索的表必須是順序存儲(chǔ)的有序表。(V )62、 索引順序查找的

9、過程也是一個(gè)“縮小區(qū)間”的查找過程(V)63、 設(shè)有100個(gè)數(shù)據(jù)元素，采用折半搜索時(shí)，最大比較次數(shù)為7. ( X)64、在順序表中進(jìn)行順序搜索時(shí)，若各元素的搜索概率不等，則各元素應(yīng)按照搜索概率的降序排列存放，則可得到最小的平均搜索長(zhǎng)度。.(X )65、在二叉搜索樹中，若各結(jié)點(diǎn)的搜索概率不等，使得搜索概率越小的結(jié)點(diǎn)離樹根越近，則得到的是最優(yōu)二叉搜索樹。(V)66、閉散列法通常比開散列法時(shí)間效率更高。( X )67、 折半搜索只適用與有序表，包括有序的順序表和有序的鏈表。(V )68、 起泡選擇排序是一種不穩(wěn)定的排序方法。(X )69、 折半搜索只適用與有序表，包括有序的順序表和有序的鏈表。.(X

10、 )70、 除留余法選擇一個(gè)適當(dāng)?shù)恼麛?shù)p,以p除健值以所得的余數(shù)作為散列地址。(V )71、 選擇排序是一種不穩(wěn)定的排序方法。(V )72、 直接選擇排序是不穩(wěn)定的，其時(shí)間復(fù)雜性為)O(1)。 .( X )73、 快速排序是一種不穩(wěn)定的排序方法。(V )74、 對(duì)于有n個(gè)對(duì)象的待排序序列進(jìn)行歸并排序，所需平均時(shí)間為O (nIog2n )。(V)75、 直接選擇排序是一種不穩(wěn)定的排序方法。.(V )76、 直接插入排序是一種穩(wěn)定的排序方法。(V )77、 歸并排序是一種不穩(wěn)定的排序方法。(X )78、 選擇排序是一種不穩(wěn)定的排序方法。(V )79、 歸并排序是一種不穩(wěn)定的排序方法。(X )80

11、、 堆排序是一種不穩(wěn)定的排序方法。(V ) 二、單選題：從選擇的答案中選出正確的答案，將其字母編號(hào)填入下列敘述中的括號(hào)內(nèi)。1、 以下說法錯(cuò)誤的是( B )A. 數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式B. 算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的C. 對(duì)鏈表進(jìn)行插人和刪除操作時(shí)，不必移動(dòng)結(jié)點(diǎn)D. 雙鏈表中至多只有一個(gè)結(jié)點(diǎn)的后繼指針為空2、 下列有關(guān)散列文件的說法中不正確的是(C )A. 散列文件具有隨機(jī)存放的優(yōu)點(diǎn)B.散列文件只能按關(guān)鍵字存取C.散列文件需要索引區(qū)D.散列文件的記錄不需要進(jìn)行排序3、有一個(gè)算法由 3個(gè)部分的代碼嵌套連接組成，每部分的時(shí)間復(fù)雜度分別為 O(1)、 O(

12、n2)、 O( n3 ) 該算法的時(shí)間復(fù)雜度為 (D )A. O (1) + ( n2 ) + ( n3 ) B. O (n2)C. ( n3 )D.( n5 )4、 下列有關(guān)散列文件的說法中不正確的是(C )A. 散列文件具有隨機(jī)存放的優(yōu)點(diǎn)B.散列文件只能按關(guān)鍵字存取C.散列文件需要索引區(qū)D.散列文件的記錄不需要進(jìn)行排序5、 設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data ,next )。已知指針 q 所指結(jié)點(diǎn)是指針 p 所指結(jié)事業(yè)的直接前驅(qū)，若在*q與*p之間插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作？(B )。A. s->next=p->next;p->next=sB q->next

13、=s ;s->next=pC.p->next=s->next;s->next=pD.p->next=s ;s->next=q6、 對(duì)順序表上的插入、刪除算法的時(shí)間復(fù)雜性分析來說，通常以(B )為標(biāo)準(zhǔn)操作A. 條件判斷B.結(jié)點(diǎn)移動(dòng)C.算術(shù)表達(dá)式D.賦值語句7、 在循環(huán)鏈表中，將頭指針改設(shè)為尾指針(rear )后，其頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的存儲(chǔ)位置分別是( B )A. reaI 和 rear->next->nextB. rear->next和 reaIC. rear->next->next和 rearD. rear 和 rear->n

14、ext8、有一個(gè)算法由 3個(gè)部分的線性代碼連接組成， 每部分的時(shí)間復(fù)雜度分別為 O(1)、 O(n2)、 O( n3 ) 該算法的時(shí)間復(fù)雜度為 (C)A. O ( 1 ) +( n2 ) +( n3 ) B. O( n2)C. ( n3 )D.( n5 )9、以下說法錯(cuò)誤的是( A )A. 對(duì)循環(huán)鏈表來說，從表中任一結(jié)點(diǎn)出發(fā)都能通過前后操作而掃描整個(gè)循環(huán)鏈表B. 對(duì)單鏈表來說，只有從頭結(jié)點(diǎn)開始才能掃描表中全部結(jié)點(diǎn)C. 雙鏈表的特點(diǎn)是找結(jié)點(diǎn)的前趨和后繼都很容易D. 對(duì)雙鏈表來說，結(jié)點(diǎn)*P的存儲(chǔ)位置既存放在其前趨結(jié)點(diǎn)的后繼指針域中，也存放在它的后繼結(jié)點(diǎn)的前趨指針域中。10、在串的基本運(yùn)算中，屬于加

15、工型運(yùn)算的有A. EQAL（S,T） B.LENGTH（S）C.CONCA T（S,T）D.REPLACE（S,T,R）11、線性鏈表不具有的特點(diǎn)是（ A ）。A. 隨機(jī)訪問B不必事先估計(jì)所需存儲(chǔ)空間大小C.插入與刪除時(shí)不必移動(dòng)元素D 所需空間與線性表長(zhǎng)度成正比12、以下說法正確的是（ C）A. 在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因?yàn)榭梢詮念^結(jié)點(diǎn)進(jìn)行查找任何一個(gè)B. 在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)C. 順序存儲(chǔ)結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)屬于動(dòng)態(tài)結(jié)構(gòu)D順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)13、線性表是一個(gè)具有 n個(gè)（C）的有

16、限序列。A. 表元素B .字符 C .數(shù)據(jù)元素D .數(shù)據(jù)項(xiàng)14、 對(duì)于順序表，以下說法錯(cuò)誤的是（ A ）A. 順序表是用一維數(shù)組實(shí)現(xiàn)的線性表，數(shù)組的下標(biāo)可以看成是元素的絕對(duì)地址B. 順序表的所有存儲(chǔ)結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列C. 順序表的特點(diǎn)是 : 邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰D. 順序表的特點(diǎn)是 :邏輯上相鄰的元素，存儲(chǔ)在物理位置也相鄰的單元中2D. O(n 2)15、一個(gè)長(zhǎng)度為 n 的順序表的表尾插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（C）。A. O(n)B. O(n/2)C. O(1)16、單鏈表的一個(gè)存儲(chǔ)結(jié)點(diǎn)包含（ D ）A. 數(shù)據(jù)域或指針域B.指針域或鏈域C

17、. 指針域和鏈域D.數(shù)據(jù)域和鏈域精選17、在串的基本運(yùn)算中，屬于引用型運(yùn)算的有（ B ）A.ASSIGN(S,T) B.INSERT(S1,i,S2)A )。C.DELETE(S,i,j) D.SUBSTR(S,i,j)18、一個(gè)長(zhǎng)度為 n 的順序表的任一位置插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為(2A. O(n)B. O(n/2)C. O(1)D. O(n 2)19、 向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)(A )。A. 先移動(dòng)棧頂指針，再存入元素B .先存入元素，再移動(dòng)棧頂指針 C. 先后次序無關(guān)緊要D .同時(shí)進(jìn)行20、 順序隊(duì)列的人隊(duì)操作應(yīng)為( A )A. sq.rear=sq.rear+1;sq.da

18、tasq.rear=xB. sq.datasq.rear=x;sq.rear=sq.rear+1C. sq.rear=(sq.rear+1)% maxsize;sq.datasq.rear=xD. sq.datasqrear=x;sq.rear=(sq.rear+1)% maxsize21、 頭結(jié)點(diǎn)的單鏈表first 為空的判定條件是： (B)A. first = NULL;B. first->next= NULL;C. first->next = first;D. first != NULL;22、如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則入棧操作時(shí)（A）A、必須判別棧是否滿B 、必須判別棧

19、元素的類型C、必須判別棧是否空D、對(duì)棧不作任何判別23、 設(shè)有一個(gè)n n的對(duì)稱矩陣A,將其下三角部分按行存放在一個(gè)一維數(shù)組B中，A00存放于B0中, 那么第i行的對(duì)角元素 Aii 存放于B中(A )處。A. (i+3)*i/2 B. (i+1)*i/2C. (2n-i+1)*i/2D. (2n-i-1)*i/224、 一個(gè)棧的入棧序列是a,b,c,d,e, 則棧的不可能的輸出序列是( A )A. d c e a b B.d e c b aC. e d c b a D.a b c d e25、 假定一個(gè)鏈?zhǔn)疥?duì)列的隊(duì)頭和隊(duì)尾指針分別為front 和 rear ，則判斷隊(duì)空的條件為 ( A ) 。A

20、. front = rearB. front != NULLC. rear != NULLD. front = NULL26、當(dāng)利用大小為 n 的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為( B )。A. n-2 B. n-1 C. n D. n+127、循環(huán)鏈表主要優(yōu)點(diǎn)是( D )A. 不再需要頭指針了B. 已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨C. 在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好地保證鏈表不斷開D. 從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表28、稀疏矩陣一般采用 (C ) 方法壓縮存儲(chǔ)。A. 三維數(shù)組B. 單鏈表C. 三元組表D. 散列表29、鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)比較明顯的優(yōu)點(diǎn)是(

21、B)A 插入操作更加方便 B 通常不會(huì)出現(xiàn)棧滿的情況C 不會(huì)出現(xiàn)?？盏那闆r D 刪除操作更加方便30、設(shè)有一順序棧 S,元素S1,S2,s3,s4,S5,S 6依次進(jìn)棧，如果 6個(gè)元素出線的順序是S2,S3,s4,S6,S5,s1,則棧的容量至少應(yīng)該是( B )A.2B. 331、設(shè)有 50 行60列的二維數(shù)組 A5060 元素 A1825A3700C3900設(shè) C 語言數(shù)組C. 5D.6，其元素長(zhǎng)度為 4 字節(jié)，按行優(yōu)先順序存儲(chǔ)，基地址為200，則32、的存儲(chǔ)地址為( A)。B4376D4620DATAm+1作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為對(duì)頭指針 rear 為對(duì)尾指針，則執(zhí)行出33

22、、34、35、隊(duì)操作的語句為( D)A.front=front+1B.front=(front+1)%mD. .front=(front+1)%(m+1)(C)C.rear=(rear+1)%m循環(huán)隊(duì)列的隊(duì)滿條件為A. (Sq.rear+1) % mazSize =(Sq.front+1) % maxSize;B. (Sq.rear+1 % maxSize =Sq.front+1C. Sq.(rear+1) % maxSize =Sq.frontD. Sq.rear =Sq.front在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加(A. 2B. 1C. 0具有65個(gè)結(jié)點(diǎn)的完全二叉樹的高

23、度為(B)o (根的層次號(hào)為A )。D. 10)A 8B 7 C6D 5DBFEAC則后序遍歷的結(jié)果為36、對(duì)某二叉樹進(jìn)行前序遍歷的結(jié)果為ABDEFC中序遍歷的結(jié)果為A DBFEACB DFEBCAC. BDFECA D . BDEFAC37、 循環(huán)隊(duì)列的出隊(duì)操作為（A ）A. sq.fr on t=（sq.ft on t+1）% maxsizeB. sq.fr on t=sq.fr on t+1C. sq.rear=（sq.rear+）% maxsizeD. sq.rear=sq.rear+138、 設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非葉結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有 （

24、C ） 個(gè)。A. n-1 B. n C . n+1 D . n+239、 設(shè)二叉樹結(jié)點(diǎn)的先根序列、中根序列和后根序列中，所有葉子結(jié)點(diǎn)的先后順序（B ）A.都不相同B.完全相同C.先序和中序相同，而與后序不同D.中序和后序相同，而與先序不同40、 對(duì)于順序存儲(chǔ)的隊(duì)列，存儲(chǔ)空間大小為n,頭指針為F,尾指針為R。若在邏輯上看一個(gè)環(huán)，則隊(duì)列中 元素的個(gè)數(shù)為（B ）A.R-FB. （n+R-F）mod nC.（R-F+1）mod nD. n+R-F41、 以下說法錯(cuò)誤的是（A ）A. 樹形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前趨B. 線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼C. 樹形結(jié)構(gòu)可以表達(dá)（組織）更

25、復(fù)雜的數(shù)據(jù)D.樹（及一切樹形結(jié)構(gòu)）是一種”分支層次”結(jié)構(gòu)42、以下說法錯(cuò)誤的是（B ）。A. 二叉樹可以是空集B. 二叉樹的任一結(jié)點(diǎn)都有兩棵子樹C. 二叉樹與樹具有相同的樹形結(jié)構(gòu)D. 二叉樹中任一結(jié)點(diǎn)的兩棵子樹有次序之分43、 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于（C ）A. n B . n-1 C . n+1D. 2*n44、下列說法中正確的是（ A ）oA. 一棵二叉樹的度可以小于2 B.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2C. 二叉樹的度為2D.任何一棵二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為245、在一棵具有5層的滿二叉樹中結(jié)點(diǎn)數(shù)為（ A ）A 31 B 32 C 33 D 1646、

26、一個(gè)二叉樹按順序方式存儲(chǔ)在一個(gè)維數(shù)組中，如圖0123 456 78 9 10 11 12 13 14ABCDEFGHIJ則結(jié)點(diǎn)E在二叉樹的第（C ）層。A.1B.2C.3D.447、在圖的鄰接表存儲(chǔ)結(jié)構(gòu)上執(zhí)行廣度優(yōu)先搜索遍歷類似于二叉樹上的（D）A.先根遍歷B.中根遍歷C.后根遍歷 D.按層次遍歷48、任何一棵二叉樹的葉結(jié)點(diǎn)在其先根、中根、后跟遍歷序列中的相對(duì)位置（C ）A.肯定發(fā)生變化C.肯定不發(fā)生變化49、在一棵高度為h+1A. 2B.有時(shí)發(fā)生變化D.無法確定h（假定樹根結(jié)點(diǎn)的層號(hào)為B. 2h-1 C. 20）的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于h-1D. 2 h(B)。50、樹若用雙親鏈表

27、表示，則 (A)A. 可容易地實(shí)現(xiàn)求雙親及子孫的運(yùn)算B. 求雙親及子孫的運(yùn)算均較困難C可容易地實(shí)現(xiàn)求雙親運(yùn)算，但求子孫運(yùn)算較困難D.可容易地實(shí)現(xiàn)求子孫運(yùn)算，但求雙親運(yùn)算較困難51、任何一個(gè)帶權(quán)的無向連通圖的最小生成樹( B)A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在52、設(shè)有向圖有 n 個(gè)頂點(diǎn)和 e 條邊，采用領(lǐng)接表作為其存儲(chǔ)表示，在進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為 ( B )。O(n+e)O(n2)A O(nlog2e )BC O(ne)D53、以下說法正確的是( A )A. 連通圖的生成樹，是該連通圖的一個(gè)極小連通子圖。B. 無向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)

28、稱的。C. 任何一個(gè)有向圖，其全部頂點(diǎn)可以排成一個(gè)拓?fù)湫蛄?。D. 有回路的圖不能進(jìn)行拓?fù)渑判颉?4、以下說法錯(cuò)誤的是 ( D )A. 一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近B哈夫曼樹中沒有度數(shù)為 1的分支結(jié)點(diǎn)C .若初始森林中共有 n 裸二叉樹，最終求得的哈夫曼樹共有 2n-1 個(gè)結(jié)點(diǎn)D. 若初始森林中共有 n裸二叉樹，進(jìn)行2n-1次合并后才能剩下一棵最終的哈夫曼樹55、如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則 該圖一定是 ( B )A.完全圖B.連通圖C.有回路D.一棵樹56、 將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，則對(duì)編號(hào)為25的結(jié)點(diǎn)x，該結(jié)點(diǎn)(B )A.

29、 無左、右孩子B. 有左孩子，無右孩子C. 有右孩子，無左孩子D. 有左、右孩子57、深度為 6的二叉樹最多有 (B ) 個(gè)結(jié)點(diǎn)A.64B.63C.32D.3158、一個(gè)有序順表有 255 個(gè)對(duì)象，采用順序搜索法查表，搜索長(zhǎng)度為( A )。A、 128 B 、 127 C 、 126 D 、 25559、 在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的(C )。A. 入度B.出度C. 入度與出度之和D. 入度與出度之差60、具有 n 個(gè)頂點(diǎn)的有向無環(huán)圖最多可包含 ( D ) 條有向邊。A n-1 B n C n(n-1)/2 D n(n-1)61、 用鄰接表作為有向圖G的存儲(chǔ)結(jié)構(gòu)。設(shè)有 n個(gè)頂點(diǎn)、e條弧，

30、則拓?fù)渑判虻臅r(shí)間復(fù)雜度為(B )A. O(n)B. O(n+e)C. O(e)D. O(n*e)62、一個(gè)有序順表有 255 個(gè)對(duì)象，采用順序搜索法查表，搜索長(zhǎng)度為( A)。A、 128B、 127 C、 126 D、 25563、 在有向圖中，所有頂點(diǎn)的入度之和是所有頂點(diǎn)出度之和的(B)倍。A.0.5B. 1C. 2D.464、以下說法錯(cuò)誤的是( B)A. 用相鄰矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。B. 鄰接表法只能用于有向圖的存儲(chǔ)，而相鄰矩陣法對(duì)于有向圖和無向圖的存儲(chǔ)都適用。C. 存儲(chǔ)無向圖的相鄰矩陣是對(duì)稱的，因此只要存

31、儲(chǔ)相鄰矩陣的下（或上）三角部分就可以了D. 用相鄰矩陣 A 表示圖，判定任意兩個(gè)結(jié)點(diǎn) Vi 和 Vj 之間是否有長(zhǎng)度為 m 的路徑相連，則只要檢查 A 的第i行第j列的元素是否為0即可。65、 在圖的鄰接表存儲(chǔ)結(jié)構(gòu)上執(zhí)行深度優(yōu)先搜索遍歷類似于二叉樹上的（A ）A. 先根遍歷B. 中根遍歷C. 后根遍歷 D 按層次遍歷66、 在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（B ）倍。A 3 B 2 C 1 D 1/267、 在無向圖中，所有頂點(diǎn)的度數(shù)之和是所有邊數(shù)的（C ）倍。A.0.5B.1C.2D.468、設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（B）條邊能確保是一個(gè)連通圖。A. 5 B. 6C

32、. 7D. 869、以下說法正確的是（D ）A. 連通分量是無向圖中的極小連通子圖。B. 強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖。C. 在一個(gè)有向圖的拓?fù)湫蛄兄校繇旤c(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧 <a,b>。D. 對(duì)有向圖G如果從任意頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個(gè)頂點(diǎn)，則該圖一定是完全圖。R14 進(jìn)行折半搜索，搜索到R3 的關(guān)鍵碼等于給定值，此時(shí)元素比較順70、對(duì)有 14 個(gè)數(shù)據(jù)元素的有序表 序依次為（C ）。R0 ， R13 ， R2 ， R3R6 ， R4 ， R2 ， R3A R0 ， R1 ， R2 ， R3BC R6 ， R2 ， R4 ， R3D

33、71、設(shè)有序表的關(guān)鍵字序列為1 ， 4， 6， 10， 18，35， 42， 53， 67， 71， 78， 84， 92， 99 ，當(dāng)用二分查找法查找健值為 99 的結(jié)點(diǎn)時(shí)，經(jīng)（C ）次比較后查找成功。A.2B. 3C.4C. 1272、 設(shè)有 100 個(gè)數(shù)據(jù)元素，采用折半搜索時(shí)，最大比較次數(shù)為（B）A 6 B 7 C 8D 1073、對(duì)長(zhǎng)度為 n 的有序單鏈表，若搜索每個(gè)元素的概率相等，則順序搜索到表中任一元素的平均搜索長(zhǎng)度 為（ B）A. n/2 B . （n+1）/2 C . （n - 1）/2 D. n/474、 對(duì)采用二分查找法進(jìn)行查找運(yùn)算的查找表，要求按（C）方式進(jìn)行存儲(chǔ)。鏈?zhǔn)酱?/p>

34、儲(chǔ)A 順序存儲(chǔ)C 順序存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序D 鏈?zhǔn)酱鎯?chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序75、二分查找法適用于存儲(chǔ)結(jié)構(gòu)為（A）的，且按關(guān)鍵字排序的線性表A. 順序存儲(chǔ) B. 鏈接存儲(chǔ) C. 順序存儲(chǔ)或鏈接存儲(chǔ) D. 索引存儲(chǔ)76、在一個(gè)長(zhǎng)度為 n 的順序表的任一位置插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（B ）A. O（n）B. O（n/2）C. O（1）D. O（n2）77、在對(duì)查找表的查找過程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。這種方式主 要適合于 （C ）A. 靜態(tài)查找表B.動(dòng)態(tài)查找表C. 靜態(tài)查找表與動(dòng)態(tài)查找表 D. 兩種表都不適合78、在一個(gè)長(zhǎng)度為 n 的順序表的表尾插入一個(gè)新元素

35、的漸進(jìn)時(shí)間復(fù)雜度為（B ）279、設(shè)有序表的關(guān)鍵字序列為AO （n）BO （1）C O （n2 ） DO （log 2 n）1 ， 4， 6， 10， 18， 35， 42， 53， 67， 71， 78， 84， 92， 99 ，當(dāng)用二分查找A2法查找健值為 84 的結(jié)點(diǎn)時(shí)，經(jīng)（ C）次比較后查找成功。B 3C 4D 1280、靜態(tài)查找表與動(dòng)態(tài)查找表兩者的根本差別在于（C ）A邏輯結(jié)構(gòu)不同B 存儲(chǔ)實(shí)現(xiàn)不同C 施加的操作不同81、以下時(shí)間復(fù)雜性不是D 數(shù)據(jù)元素的類型不同0（n2）的排序方法是A. 直接插入排序B. 二路歸并排序 C. 冒泡排序 D. 直接選擇排序82、 一個(gè)對(duì)象序列的排序碼為4

36、6，79，56，38，40，84 ，采用快速排序以位于最左位置的對(duì)象為基準(zhǔn)而得到的第一次劃分結(jié)果為（C）。A 38 ， 46， 79， 56， 40， 84B38 ，79，56，46，40，84C40 ，38，46，56，79，84D38 ，46，56，79，40，8483、 用順序查找法對(duì)具有n 個(gè)結(jié)點(diǎn)的線性表查找的時(shí)間復(fù)雜性量級(jí)為（C）A.O（n2）B. O（nlog 2n）C. O（n）D O（log 2n）84、 用某種排序方法對(duì)序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序，記錄序列的變化情況如 下：2584214715276835201520212547276

37、83584152021253527476884152021252735476884則采取的排序方法是( C)A.直接選擇排序B.冒泡排序C.快速排序D.二路歸并排序85、 一個(gè)對(duì)象序列的排序碼為46，79，56，38，40，84 ，采用快速排序以位于最左位置的對(duì)象為基準(zhǔn)而 得到的第一次劃分結(jié)果為（ C ）。A38 ，46，79，56，40，84B38，79，56，46，40，84C40 ，38，46，56，79，84D38，46，56，79，40，8486、 順序查找法適合于（D ）存儲(chǔ)結(jié)構(gòu)的查找表。A.壓縮B.散列C.索引D.順序或鏈?zhǔn)?7、以下說法錯(cuò)誤的是（C ）A. 直接插入排序的空間復(fù)

38、雜度為0（1）。B. 快速排序附加存儲(chǔ)開銷為O（log 2n）。C. 堆排序的空間復(fù)雜度為 0（n） 。D. 二路歸并排序的空間復(fù)雜度為0（n）,需要附加兩倍的存儲(chǔ)開銷。88、 對(duì)于大文件的排序要研究在外設(shè)上的排序技術(shù)，即（C）A.快速排序法B.內(nèi)排序法C.外排序法D.交叉排序法89、對(duì)于長(zhǎng)度為 9 的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長(zhǎng)度為（C ）的值除以 9。A. 20 B. 18 C. 25 D. 2290、 具有 24 個(gè)記錄的序列，采用冒泡排序至少的比較次數(shù)是（ B ）A.1B.23C. 24D. 52991、 當(dāng)初始序列已按健值有序時(shí)，用直接插入算法進(jìn)行排

39、序，需要比較的次數(shù)為（A）A.n-1B.log 2nC. 2log2nD.n292、 排序的目的是為了以后對(duì)已排序的數(shù)據(jù)元數(shù)進(jìn)行（D）操作。A.打印輸出B.分類C.合并D.查找93、 以下穩(wěn)定的排序方法是（ B）A.快速排序B.冒泡排序C.直接選擇排序D.堆排序94、（ B ）方法是從未排序序列中依次取出元素與已排序序列中的元素作比較，將其放入已排序序列的正 確位置上。A. 歸并排序B. 插入排序C快速排序D. 選擇排序95、在文件局部有序或文件長(zhǎng)度較小的情況下，最佳的排序方法是（ A）A. 直接插入排序 B. 冒泡排序 C. 直接選擇排序 D. 歸并排序96、如果只想得到 1024個(gè)元素組成

40、的序列中的前 5 個(gè)最小元素，那么用（ C ）方法最快。A.起泡排序 B 快速排序 C 堆排序 D 直接選擇排序97、對(duì)一個(gè)由 n 個(gè)整數(shù)組成的序列，借助排序過程找出其中的最大值，希望比較次數(shù)和移動(dòng)次數(shù)最少，應(yīng) 選用（ C ）方法。A. 歸并排序B.直接插入排序C. 直接選擇排序 D. 快速排序98、對(duì)待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對(duì)兩個(gè)子序列施加同樣的排序操作，直到子序列為空或只剩一個(gè)元素為止。這樣的排序方法是（C ）A 直接選擇排序 B 直接插入排序 C 快速排序 D 起泡排序99、 以下不穩(wěn)定的排序方法是（ C ）A. 直接插入排序 B. 冒泡排序 C. 直接選擇

41、排序 D. 二路歸并排100、在一個(gè)長(zhǎng)度為 n 的順序表的任一位置插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（ B ）A. O（n）B. O（n/2）C. O（1）D. O（n2）O（n）、O（n2）、O（ n 4 ）O（n）、 O（ n2）、 O（ n4 ）（ 事后測(cè)試 ） 。三、填空題1、有一個(gè)算法由 3 個(gè)部分的線性代碼連接組成，每部分的時(shí)間復(fù)雜度分別為 該算法的時(shí)間復(fù)雜度為 （O（ n 4 ） ） 。2、數(shù)據(jù)的基本單位是 （數(shù)據(jù)元素 ） 。它必須具備輸入、輸出、可行性、 （確定性）和（有3、計(jì)算機(jī)中的算法指的是解決某一問題的有限運(yùn)算序列， 窮性 ）等 5個(gè)特征4、所有結(jié)點(diǎn)按 1對(duì) 1的鄰接關(guān)系構(gòu)

42、成的整體就是 （線性） 結(jié)構(gòu)5、 數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系”稱為（ 邏輯） 關(guān)系。6、有一個(gè)算法由 3 個(gè)部分的代碼嵌套連接組成，每部分的時(shí)間復(fù)雜度分別為 該算法的時(shí)間復(fù)雜度為 （ O（ n7 ） ） 。7、 數(shù)據(jù)元素之間邏輯關(guān)系的整體稱為（邏輯結(jié)構(gòu) ） 。8、對(duì)一個(gè)算法要作出全面的分析可分成兩用人才個(gè)階段進(jìn)行，即事先分析和 9、算法的復(fù)雜度分為 （ 時(shí)間復(fù)雜度 ） 和（ 空間復(fù)雜度 ） 兩種。10、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示（機(jī)內(nèi)表示）稱為數(shù)據(jù)的（ 存儲(chǔ)結(jié)構(gòu) ）11、文件的檢索有順序存取、直接存取和（ 按關(guān)鍵字存取 ） 三種方式。12、文件的檢索有順序存取、直接存取和（ 按關(guān)鍵字存

43、取 ） 三種方式。13、在順序表中插入或刪除一個(gè)元素， 需要平均移動(dòng) （n+1）/2） 元素，具體移動(dòng)的元素個(gè)數(shù)與 （） 有關(guān)。14、 VSAM文件結(jié)構(gòu)由三部分組成：索引集、（順序集）和數(shù)據(jù)集。15、 ISAM文件是由多級(jí)主索引、柱面索引、磁道索引和（主文件索引）組成。16、 已知： s1=I 'm a teacher ， s2= teacher ， s3= student ，則 REPLACE（s1,s2, s3） 等于 （I 'm a teacher ） 。17、 如果文件中的每個(gè)記錄都有一個(gè)索引項(xiàng)，則這樣的索引稱為（稠密索引 ） 。18、 如果文件中多個(gè)記錄只有一個(gè)索引項(xiàng)

44、，則這樣的索引稱為（非稠密索引 ）。19、 在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向（ 前驅(qū) ） ， 另一個(gè)指向 （ 后繼 ） 。20、當(dāng)且僅當(dāng)兩個(gè)串的 （長(zhǎng)度 ）相等并且各個(gè)對(duì)應(yīng)位置上的字符都相同時(shí)，這兩個(gè)串相等。一個(gè)串中任意個(gè)連續(xù)字符組成的序列稱為該串的 （ 子串 ） 串。21、 VSAM文件結(jié)構(gòu)由三部分組成：索引集、（順序集）和數(shù)據(jù)集。22、 串的順序存儲(chǔ)有兩種方法：一種是每個(gè)單元只存一個(gè)字符，稱為（ 非緊縮格式 ） 格式，另一種是每個(gè)單 元存放多個(gè)字符，稱為 （ 緊縮格式 ） 格式。23、 線性表的常見鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有單鏈表、（雙向鏈表 ）和（循環(huán)鏈表 ）。24、 線性表典型的基本運(yùn)算

45、包括初始化、（ 插入）、 （刪除） 、查找定位、求長(zhǎng)度、存取等六種。25、已知： s1=I'm a teacher ，s2=teacher ，s3= student ，則 SUBSTR（s1,7,7） 等于 （student） 。26、 已知： s1=I 'm a teacher ， s2= teacher ， s3= student ，則 DELETE（s1,4,10） 等于 （ I'm） 。27、 已知： s1=I'm a teacher ， s2= teacher ， s3=student ，則 EQUAL（s1,s2） 等于（0 ）。28、 順序表中邏輯

46、上相鄰的元素的物理位置（必須）緊鄰。單鏈表中邏輯上相鄰的元素的物理位置 （不需要 ） 緊鄰。29、 四維數(shù)組是一種非線性結(jié)構(gòu)，其中的每一個(gè)數(shù)組元素最多有（4） 個(gè)直 接前驅(qū)（或直接后繼）30、 一般地，棧和線性表類似有兩種實(shí)現(xiàn)方法，即（ 順序 ） 實(shí)現(xiàn)和 （ 鏈接 ） 實(shí)現(xiàn)。31、 含零個(gè)字符的串稱為（空串）串，用（）表示。32、 棧是一種限定在表的一端進(jìn)行插入和刪除的線性表，又被稱為（后進(jìn)先出 ）線性表。33、 在棧的順序?qū)崿F(xiàn)中，設(shè)棧頂指針為top ，?？盏臈l件為 （top=0） 。34、 若已知一個(gè)棧的入棧序列是1, 2, 3, 4，n，其輸出序列是 P1, P2, P3,，Pn,若P仁n

47、,則 Pi 為（n-i+1 ）。35、對(duì)于順序存儲(chǔ)的棧, 因?yàn)闂５目臻g是有限的, 在進(jìn)行（后進(jìn)）運(yùn)算時(shí), 可能發(fā)生棧的上溢, 在進(jìn)行（先出） 運(yùn)算時(shí),可能發(fā)生棧的下溢。36、（棧）可以作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。37、 對(duì)任何二叉樹，若度為2的節(jié)點(diǎn)數(shù)為n2,則葉子數(shù)n0=（ n2+1 ）38、 隊(duì)列中允許進(jìn)行刪除的一端稱為（對(duì)頭）。39、一般地,一個(gè) n 維數(shù)組可視為其數(shù)據(jù)元素為 （ n ） 基本運(yùn)算。40、二叉樹有不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),其中最常用的是41、 以下運(yùn)算實(shí)現(xiàn)在順序棧上的進(jìn)棧,請(qǐng)?jiān)冢ǎ㊣nt Push（SqStackTp *sq,DataType x） if（sp->t

48、op=sqstack_maxsize-1error（ else（ sq->top+）:（sq->datasq->top）=x;return（1）;維數(shù)組的線性表。數(shù)組通常只有 （刪除）和（插入）兩種（ 二叉鏈表 ） 與（ 三叉鏈表 ） 。處用適當(dāng)?shù)恼Z句予以填充?！皸M” ）;return（0）;42、深度為 90 的滿二叉樹上,第 11 層有（210）個(gè)結(jié)點(diǎn)。43、已知一棵度為 3的樹有 2個(gè)度為 1的結(jié)點(diǎn), 3個(gè)度過為 2的結(jié)點(diǎn), 1個(gè)度為 3 的結(jié)點(diǎn),則該樹中有 （6） 個(gè)葉子結(jié)點(diǎn)。44、 深度優(yōu)先搜索遍歷類似于樹的（先根）遍歷,它所用到的數(shù)據(jù)結(jié)構(gòu)是 （棧）。45、具有

49、n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 （log2n 1 ）。46、（樹 ） 中結(jié)點(diǎn)的最大度數(shù)允許大于 2,而 （ 二叉樹 ） 中結(jié)點(diǎn)的最大度數(shù)不允許大于 247、一棵樹按照左子女 -右兄弟表示法轉(zhuǎn)換成對(duì)應(yīng)的二叉樹,則該二叉樹中樹根結(jié)點(diǎn)肯定沒有（右）子女。48、深度為 k（k>=1） 的二叉樹至多有 （2k-1 ）個(gè)結(jié)點(diǎn)。49、有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其結(jié)點(diǎn)總數(shù)為 （2m-1 ）。50、在一棵樹中， （ 根） 結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)。51、對(duì)無向圖，其鄰接矩陣是一個(gè)關(guān)于（對(duì)角線 ） 對(duì)稱的矩陣。52、 n （n > 0）個(gè)頂點(diǎn)的有向連通圖最多有 （n（n-1）條邊，最少有（n-1）條邊53、設(shè)

50、無向連通圖 G的頂點(diǎn)數(shù)為n,貝U G最少有（n-1 ）條邊。54、遍歷圖的基本方法有 （深度）優(yōu)先搜索和 （ 廣度 ） 優(yōu)先搜索兩種。55、 在集合這種邏輯結(jié)構(gòu)中,任何結(jié)點(diǎn)之間都不存在（ 邏輯 ） 關(guān)系,這是集合這種邏輯結(jié)構(gòu)的基本特點(diǎn)。56、 一個(gè)有向圖 G中若有弧，<Vi,Vj>、<Vj,Vk>和<Vi,Vk>則在圖G的拓?fù)湫蛄兄?，頂點(diǎn)V、Vj和Vk的相對(duì) 位置為 （省略 ）。57、 廣度優(yōu)先搜索遍歷類似于樹的（層次）遍歷,它所用到的數(shù)據(jù)結(jié)構(gòu)是 （隊(duì)列）。58、由 （ 樹） 轉(zhuǎn)換成二叉樹時(shí),其根結(jié)點(diǎn)的右子樹總是空的。59、設(shè)圖 G=（V,E） , V=1,

51、2,3,4,E=<1,2>,<1,3>,<2,4>,<3,4> ，從頂點(diǎn) 1 出發(fā)，對(duì)圖 G進(jìn)行廣度優(yōu)先搜索的序列有種 （ 2 ）。60、 任何連通圖的連通分量只有一個(gè),即（本身）。61、 向一棵二叉搜索樹中插入一個(gè)元素時(shí),若元素的值小于根結(jié)點(diǎn)的值, 貝應(yīng)把它插入到根結(jié)點(diǎn)的 （左子樹 ） 上。62、對(duì)有序表 （25, 30, 32, 38, 47, 54, 62, 68, 90, 95）用二分查找法查找 32,貝所需的比較次數(shù)為 （ 3）。63、靜態(tài)查找表包括 （建表）、 （查找）、 （讀元素 ）三種基本運(yùn)算。64、 動(dòng)態(tài)查找表包括建表、查找、讀

52、元素、（ 插入 ） 、 （ 刪除 ） 五種基本運(yùn)算。65、 根據(jù)一組記錄（56, 42, 50, 64, 48）依次插入結(jié)點(diǎn)生成一棵AVL樹（高度平衡的二叉搜索樹）時(shí)， 當(dāng)插入到值為 （50） 的結(jié)點(diǎn)時(shí)需要進(jìn)行旋轉(zhuǎn)調(diào)整。66、 平衡二叉排序樹上任一結(jié)點(diǎn)的平衡因子只可能是（0） 、 （1）或（-1） 。（空）變?yōu)?（指向該結(jié)點(diǎn) ）即樹高度之差的絕對(duì)值不超（ 1 ）。（ 選擇排序 ） 、 （ 交換排序 ） 、67、在二叉排序樹上插入新結(jié)點(diǎn)時(shí),不必移動(dòng)其它結(jié)點(diǎn),僅需使某結(jié)點(diǎn)的指針域由 可。68、在一棵AVL樹（高度平衡的二叉搜索樹）中，每個(gè)結(jié)點(diǎn)的左子樹高度與右子過（ 1 ） 。69、在具有 24 個(gè)

53、元素的有序表上進(jìn)行二分查找,貝比較一次查找成功的結(jié)點(diǎn)數(shù)為70、 快速排序是不穩(wěn)定的,其時(shí)間復(fù)雜性為（ O（ nlog2n） ）71、 直接選擇排序是不穩(wěn)定的,其時(shí)間復(fù)雜性為（O（ n2） ）。72、 按排序過程中依據(jù)的不同原貝對(duì)內(nèi)部排序方法進(jìn)行分類,主要有： 插入排序、 歸并排序等四類73、 歸并排序的空間復(fù)雜度為（O（1） 。74、 二叉排序樹是一種特殊的、增加了限制條件的二叉樹,其限制條件是任一結(jié)點(diǎn)的鍵值（大 ） 于其左孩子 （及其子孫）的鍵值且 （?。┯谄溆液⒆樱捌渥訉O）的鍵值。75、 歸并排序的時(shí)間復(fù)雜度是（O（nlog2n ） ）。276、 簡(jiǎn)單排序的時(shí)間復(fù)雜性為（ O（n2） ） ,空間復(fù)雜度為 （ O（1） ） 。77、二叉樹第 i （ i>=1 ）層至多有 （2 i-1 ） 個(gè)節(jié)點(diǎn)。278、 直接插入排序是穩(wěn)定的,它的時(shí)間復(fù)雜性為（O（n2） ,空間復(fù)雜度為 （O（1） 。79、 歸并排序要求待排序列由若干個(gè)（有序）的子序列組成。80、 按照排序過程涉及的存儲(chǔ)設(shè)備的不同,排序可分為（內(nèi)）排序和（外 ）排序。四、計(jì)算題1、設(shè)二維數(shù)組 A8*9 的每個(gè)元素占 4 個(gè)字節(jié),已知 Loc（a00） =1000, A 共占多少個(gè)字節(jié)？ A