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

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

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

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

4、須占用一片連續(xù)的存儲(chǔ)單元。.(× )28、鏈接表上做刪除和插入運(yùn)算時(shí)的平均時(shí)間復(fù)雜度都是O(n) .( × )29、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。 .( )30、順序表上做刪除和插入運(yùn)算時(shí)的平均時(shí)間復(fù)雜度都是O(n) .( )31、具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的高度為2log2 n+1 .(× )32、在只有度為 0 和度為2 的結(jié)點(diǎn)的二叉樹中，設(shè)度為0的結(jié)點(diǎn)有n0 個(gè)，度為2 的結(jié)點(diǎn)有n2 個(gè)，則有n0=n2+1 .( )33、循環(huán)隊(duì)列判斷隊(duì)列為滿的條件是sq->front+1= =sq->rear。(× )34、數(shù)組是一種

5、復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。.( )35、若二叉樹中各結(jié)點(diǎn)的值均不相同，則由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均能惟一地確定一棵二叉樹。. ( )36、有 n 個(gè)結(jié)點(diǎn)的不同的二叉樹有n！棵。 . .( ×)37、一般樹和二叉樹的結(jié)點(diǎn)數(shù)目都可以為0。 .( )38、循環(huán)隊(duì)列判斷隊(duì)列為空的條件是sq->front= =sq->rear。 ( )39、設(shè)有一順序棧 S，元素 s1,s 2,s 3,s4,s 5,s 6 依次進(jìn)棧，如果6 個(gè)元素出線的順序是s2,s 3,s 4, s 6 , s 5,s 1, 則棧的容量至少應(yīng)該是

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

7、、在一棵二叉樹中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒有右子女，對(duì)它分別進(jìn)行中序遍歷和后序遍歷，則具有相同的結(jié)果。( )48 、 對(duì) 于 一 棵具 有 n 個(gè)結(jié) 點(diǎn) ， 其 高 度 為 h 的 二叉 樹 ， 進(jìn) 行 任一 種次 序遍 歷 的 時(shí) 間 復(fù)雜 度為 O （n）。 . .( )49、圖的深度優(yōu)先搜索類似于樹的先根次序遍歷.( )50、在無向圖中定義頂點(diǎn)V與 V 之間的路徑為從V到達(dá) V 的一個(gè)頂點(diǎn)序列（ ）ijij51、設(shè)無向連通圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有n(n-1)/2條邊 .( )52、圖的廣度優(yōu)先遍歷是樹的按中根遍歷推廣。( × )53、設(shè)圖 G=(V,E) ，V=1,2,

8、3,4, E=<1,2>,<1,3>,<2,4>,<3,4>，從頂點(diǎn) 1出發(fā)，對(duì)圖 G進(jìn)行廣度優(yōu)先搜索的序列有2 種. ( )54 、用鄰接表作為有向圖G 的存儲(chǔ)結(jié)構(gòu)。設(shè)有n 個(gè)頂點(diǎn)、 e條弧，則拓?fù)渑判虻臅r(shí)間復(fù)雜度為O(n*e) .( × )55、查找表是由同一類型的數(shù)據(jù)元素( 或記錄 ) 構(gòu)成的集合 ( )56、存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān) . . . . . .( )57、圖的深度和廣度遍歷兩種操作的時(shí)間復(fù)雜度都為O（ n*e ）。 .( × )58、只有無向圖，頂點(diǎn)數(shù)n

9、、邊數(shù) e 和度數(shù)之間有如下關(guān)系：e=1n D(×(v i)59、裝載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的裝滿程度。2 i1（）60、閉散列法通常比開散列法時(shí)間效率更高。（ × ）61、進(jìn)行折半搜索的表必須是順序存儲(chǔ)的有序表。（ ）62、索引順序查找的過程也是一個(gè)“縮小區(qū)間”的查找過程( )63、設(shè)有 100 個(gè)數(shù)據(jù)元素，采用折半搜索時(shí)，最大比較次數(shù)為7. (×)64、在順序表中進(jìn)行順序搜索時(shí)，若各元素的搜索概率不等，則各元素應(yīng)按照搜索概率的降序排列存放，則可得到最小的平均搜索長(zhǎng)度。.(×)65、在二叉搜索樹中，若各結(jié)點(diǎn)的搜索概率不等，使得搜索概

10、率越小的結(jié)點(diǎn)離樹根越近，則得到的是最優(yōu)二叉搜索樹。( )66、閉散列法通常比開散列法時(shí)間效率更高。（× ）67、折半搜索只適用與有序表，包括有序的順序表和有序的鏈表。()68、起泡選擇排序是一種不穩(wěn)定的排序方法。( × )69、折半搜索只適用與有序表，包括有序的順序表和有序的鏈表。. .(70、除留余法選擇一個(gè)適當(dāng)?shù)恼麛?shù)p, 以 p 除健值以所得的余數(shù)作為散列地址。×)（ ）71、選擇排序是一種不穩(wěn)定的排序方法。( )72、直接選擇排序是不穩(wěn)定的，其時(shí)間復(fù)雜性為）O(1) 。.(× )73、快速排序是一種不穩(wěn)定的排序方法。( )74、對(duì)于有n 個(gè)對(duì)象的

11、待排序序列進(jìn)行歸并排序，所需平均時(shí)間為O（nlog2n ）。（）75、直接選擇排序是一種不穩(wěn)定的排序方法。 . . . . . ()76、直接插入排序是一種穩(wěn)定的排序方法。( )77、歸并排序是一種不穩(wěn)定的排序方法。( ×)78、選擇排序是一種不穩(wěn)定的排序方法。( )79、歸并排序是一種不穩(wěn)定的排序方法。(×)80、堆排序是一種不穩(wěn)定的排序方法。( )二、單選題：從選擇的答案中選出正確的答案，將其字母編號(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ì)鏈表

12、進(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（ 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.散列文件需

13、要索引區(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=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.賦值

14、語句7、在循環(huán)鏈表中，將頭指針改設(shè)為尾指針（rear ）后，其頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的存儲(chǔ)位置分別是（ B ）A.real 和 rear->next->nextB.rear->next和 realC.rear->next->next和 rearD.rear 和 rear->nextO（ 1）、O（n2）、O（ n 38、有一個(gè)算法由 3 個(gè)部分的線性代碼連接組成，每部分的時(shí)間復(fù)雜度分別為）,該算法的時(shí)間復(fù)雜度為 ( C)A. O （ 1） +（ n2 ）+（ n3 ）B. O（n2）C. （ n3 ）D.（ n5）9、以下說法錯(cuò)誤的是（ A）A. 對(duì)循環(huán)鏈表來說，從

15、表中任一結(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)算中，屬于加工型運(yùn)算的有（D）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è)元

16、素的存儲(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）的有限序列。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)是

17、:邏輯上相鄰的元素，存儲(chǔ)在物理位置也相鄰的單元中15、一個(gè)長(zhǎng)度為 n 的順序表的表尾插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（C）。A. O(n)B. O(n/2)C. O(1)D. O(n2)16、單鏈表的一個(gè)存儲(chǔ)結(jié)點(diǎn)包含（A.數(shù)據(jù)域或指針域B.D ）指針域或鏈域C. 指針域和鏈域D.數(shù)據(jù)域和鏈域17、在串的基本運(yùn)算中，屬于引用型運(yùn)算的有（ B）A.ASSIGN(S,T)B.INSERT(S1,i,S2)C.DELETE(S,i,j)D.SUBSTR(S,i,j)18、一個(gè)長(zhǎng)度為n 的順序表的任一位置插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（A ）。A. O(n)B. O(n/2)C. O(1)D. O(n

18、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 )21、頭結(jié)點(diǎn)的單鏈表firstA. first = NULL;C. first->next = first;為空的判定條件是：( B )B. first->next= NULL;D. first != NULL;22、如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則入棧操作時(shí)（A ）A、必須判別棧是否滿B、必須判別棧元素的類型C、必須判別棧是否空D、對(duì)棧不作任何判別23、設(shè)有一個(gè)n n 的對(duì)稱矩陣那么第 i 行的對(duì)角元素

19、AiiA，將其下三角部分按行存放在一個(gè)一維數(shù)組存放于 B 中（A）處。B 中， A00存放于B0中，A. (i+3)*i/2B. (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 bB.d e c b aC. e d c b aD.a b c d e25、假定一個(gè)鏈?zhǔn)疥?duì)列的隊(duì)頭和隊(duì)尾指針分別為front和 rear，則判斷隊(duì)空的條件為( A)。A. front = rearB. front != NULLC. rear != NULLD. front = NULL26、當(dāng)

20、利用大小為n 的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為（B ）。A. n-2B. n-1C. nD. 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. 三元組表29、鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)比較明顯的優(yōu)點(diǎn)是（B）A插入操作更加方便B通常不會(huì)出現(xiàn)棧滿的情況D. 散列表C不會(huì)出現(xiàn)棧空的情況D刪除操作更加方便30、設(shè)有一順序棧S，元素 s1,s 2,s 3,s

21、4,s 5,s 6 依次進(jìn)棧，如果的容量至少應(yīng)該是（B）6 個(gè)元素出線的順序是s2,s3,s4,s6,s5,s1, 則棧A.2B. 3C. 5D.631、設(shè)有 50 行 60 元素 A1825 A 3700列的二維數(shù)組A5060的存儲(chǔ)地址為（A ）。B4376，其元素長(zhǎng)度為4 字節(jié)，按行優(yōu)先順序存儲(chǔ)，基地址為200，則C 3900D462032、設(shè) C 語言數(shù)組DATAm+1作為循環(huán)隊(duì)列隊(duì)操作的語句為（D ）SQ的存儲(chǔ)空間，front為對(duì)頭指針rear為對(duì)尾指針， 則執(zhí)行出A.front=front+1B.front=(front+1)%mC.rear=(rear+1)%mD. .front=

22、(front+1)%(m+1)33、循環(huán)隊(duì)列的隊(duì)滿條件為(C)A.(sq.rear+1) % mazsize =(sq.front+1) % maxsize;B.(sq.rear+1 % maxsize =sq.front+1C.sq.(rear+1) % maxsize =sq.front34、在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（A）。A. 2B. 1C. 0D. 135、具有A 865 個(gè)結(jié)點(diǎn)的完全二叉樹的高度為（B7C6B）。（根的層次號(hào)為D 50）36、對(duì)某二叉樹進(jìn)行前序遍歷的結(jié)果為A DBFEACB DFEBCAABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍

23、歷的結(jié)果為（B）C BDFECAD BDEFAC37、循環(huán)隊(duì)列的出隊(duì)操作為(A )38、設(shè) F 是一個(gè)森林， B 是由 F 轉(zhuǎn)換得到的二叉樹， F 中有 n 個(gè)非葉結(jié)點(diǎn)，則 B 中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（ C ）個(gè)。A n-1B nCn+1D 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)m

24、od 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á) ( 組織 ) 更復(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 nBn-1C n+1D 2*n44、下列說法中正確的是（A）。A. 一棵二叉樹的度可以小

25、于2B. 二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2C. 二叉樹的度為2D. 任何一棵二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為245、在一棵具有5 層的滿二叉樹中結(jié)點(diǎn)數(shù)為（A）A 31B 32C 33D 1646、一個(gè)二叉樹按順序方式存儲(chǔ)在一個(gè)維數(shù)組中，如圖01234567891011 121314ABCDEFGHIJ則結(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ā)生變化B.有時(shí)發(fā)生變化C.肯定不發(fā)

26、生變化D.無法確定49、在一棵高度為h( 假定樹根結(jié)點(diǎn)的層號(hào)為0) 的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于( B)。A. 2h+1B. 2h-1C. 2h-1D. 2h50、樹若用雙親鏈表表示，則(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）。A O（nlog2e C O(n

27、e)）DB O（n+e） O(n2)53、以下說法正確的是（ A ）A. 連通圖的生成樹，是該連通圖的一個(gè)極小連通子圖。B. 無向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)稱的。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)先

28、搜索即可訪問所有頂點(diǎn)，則該圖一定是 (B )A. 完全圖B. 連通圖C.有回路D.一棵樹56、將一棵有50 個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，則對(duì)編號(hào)為A.無左、右孩子B.有左孩子，無右孩子C. 有右孩子，無左孩子D. 有左、右孩子25 的結(jié)點(diǎn)x，該結(jié)點(diǎn)( B )57、深度為6 的二叉樹最多有(B )個(gè)結(jié)點(diǎn)A.64B.63C.32D.3158、一個(gè)有序順表有A、128 B 、127 C255 個(gè)對(duì)象，采用順序搜索法查表，搜索長(zhǎng)度為（、126 D 、 255A）。59、在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的（A.入度B.出度C. 入度與出度之和D.入度與出度之差C ）。60、具有 n 個(gè)頂點(diǎn)的有向無環(huán)圖最

29、多可包含(A n-1B nCn(n-1)/261、用鄰接表作為有向圖G的存儲(chǔ)結(jié)構(gòu)。設(shè)有D) 條有向邊。D n(n-1)n 個(gè)頂點(diǎn)、 e 條弧，則拓?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、 127C、 126D、 25563、在有向圖中，所有頂點(diǎn)的入度之和是所有頂點(diǎn)出度之和的（B）倍。B. 1C. 2D.464、以下說法錯(cuò)誤的是（B）A. 用相鄰矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。

30、B. 鄰接表法只能用于有向圖的存儲(chǔ)，而相鄰矩陣法對(duì)于有向圖和無向圖的存儲(chǔ)都適用。C.存儲(chǔ)無向圖的相鄰矩陣是對(duì)稱的，因此只要存儲(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 3B 2C1D 1/267、在無向圖中，所有頂點(diǎn)的度數(shù)之和是所有邊數(shù)的（C）倍。A.0.5

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

32、0 ， R13 ， R2 ，R3C R6 ，R2， R4， R3D R6 ， R4 ， R2 ，R371、設(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 6B 7C 8D 1073、對(duì)長(zhǎng)度為n 的有序單鏈表，若搜索每個(gè)元素的概率相等，則順序搜索到表中任一元素的平均搜索長(zhǎng)度為（ B）A n/2B(n+1)/2C (n 1)/2Dn/474、對(duì)采用二分查找法進(jìn)行查

33、找運(yùn)算的查找表，要求按（C）方式進(jìn)行存儲(chǔ)。A 順序存儲(chǔ)B鏈?zhǔn)酱鎯?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)2D. O(n )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)

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

35、2、一個(gè)對(duì)象序列的排序碼為46 ， 79， 56， 38，40， 84 ，采用快速排序以位于最左位置的對(duì)象為基準(zhǔn)而得到的第一次劃分結(jié)果為（C）。A 38 ， 46， 79， 56， 40， 84B 38 ， 79，56， 46，40， 84C 40 ， 38， 46， 56，79， 84D 38 ， 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 2 n)84、用某種排序方法對(duì)序列（25， 84， 21， 47， 15， 27， 68， 35， 20）進(jìn)行排序，記錄序

36、列的變化情況如下：258421471527683520152021254727683584152021253527476884152021252735476884則采取的排序方法是（ C ）A. 直接選擇排序B.冒泡排序C.快速排序D. 二路歸并排序85、一個(gè)對(duì)象序列的排序碼為 46 ， 79， 56， 38，40， 84 ，采用快速排序以位于最左位置的對(duì)象為基準(zhǔn)而得到的第一次劃分結(jié)果為（ C ）。A 38 ， 46， 79， 56， 40， 84B 38 ， 79， 56， 46， 40， 84C 40 ， 38， 46， 56， 79， 84D 38 ， 46， 56， 79， 40， 8

37、486、順序查找法適合于（D）存儲(chǔ)結(jié)構(gòu)的查找表。A. 壓縮B. 散列C.索引D.順序或鏈?zhǔn)?7、以下說法錯(cuò)誤的是（C ）A. 直接插入排序的空間復(fù)雜度為O(1) 。B. 快速排序附加存儲(chǔ)開銷為O(log 2n) 。C. 堆排序的空間復(fù)雜度為O(n) 。D. 二路歸并排序的空間復(fù)雜度為O(n),需要附加兩倍的存儲(chǔ)開銷。88、對(duì)于大文件的排序要研究在外設(shè)上的排序技術(shù)，即（C）A. 快速排序法B. 內(nèi)排序法C.外排序法D. 交叉排序法89、對(duì)于長(zhǎng)度為 9 的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長(zhǎng)度為（C ）的值除以 9。A. 20B. 18C. 25D. 2290、具有 24

38、 個(gè)記錄的序列，采用冒泡排序至少的比較次數(shù)是（ B ）A.1B.23C. 24D. 52991、當(dāng)初始序列已按健值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為（A ）A.n-1B.log 2nC. 2log2nD.n 292、排序的目的是為了以后對(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、在文件局部有序或文件

39、長(zhǎng)度較小的情況下，最佳的排序方法是（ A）A. 直接插入排序B.冒泡排序C.直接選擇排序D.歸并排序96、如果只想得到1024 個(gè)元素組成的序列中的前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 快

40、速排序 D 起泡排序99、以下不穩(wěn)定的排序方法是（ C ）A. 直接插入排序B.冒泡排序C. 直接選擇排序D. 二路歸并排100、在一個(gè)長(zhǎng)度為 n 的順序表的任一位置插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（B ）A. O(n)B. O(n/2)C. O(1)D. O(n 2)三、填空題1、有一個(gè)算法由3 個(gè)部分的線性代碼連接組成，每部分的時(shí)間復(fù)雜度分別為O（n）、 O（ n2）、 O（ n 4） ,該算法的時(shí)間復(fù)雜度為(O（ n 4 ） ) 。2、數(shù)據(jù)的基本單位是(數(shù)據(jù)元素 ) 。3、計(jì)算機(jī)中的算法指的是解決某一問題的有限運(yùn)算序列，它必須具備輸入、 輸出、 可行性、 ( 確定性 ) 和( 有窮性 )

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

42、存取和(按關(guān)鍵字存取) 三種方式。12、文件的檢索有順序存取、直接存取和( 按關(guān)鍵字存取 ) 三種方式。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 ，則等于 (I m a teacher) 。REPLACE(s1,s2, s3)17、如果文件中的每個(gè)記錄都有一個(gè)索引項(xiàng)，則這樣的索引稱為( 稠密索引 ) 。18、如果文件中多個(gè)記錄只有一個(gè)索引項(xiàng)，則這樣的索引稱為( 非稠密索引 ) 。19、在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向( 前驅(qū) ) ，另一個(gè)指向 ( 后繼 ) 。20、當(dāng)且僅當(dāng)兩個(gè)