數(shù)據(jù)結(jié)構(gòu)期末考試_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)期末考試_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)期末考試_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)期末考試_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)期末考試_第5頁(yè)
免費(fèi)預(yù)覽已結(jié)束,剩余7頁(yè)可下載查看

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、數(shù)據(jù)結(jié)構(gòu)期末考試作者:日期:12數(shù)據(jù)結(jié)構(gòu)課后練習(xí)題一、填空題(第二章)1、順序表中邏輯上相鄰元素的物理位置世范,單鏈表中邏輯上相鄰的元素物理位置可以相鄰,也可以不相鄰。一2、在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素,平均要移動(dòng) n-i個(gè)元素,如果在第i個(gè)元素之前插入一個(gè)元素,平均要移動(dòng) n-i+1個(gè)元素。3、在一個(gè)單鏈表中,若 p所指的結(jié)點(diǎn)不是最后結(jié)點(diǎn),在p之后插入s結(jié)點(diǎn),則執(zhí)行s->next=p->next;p->next=s。4、在一個(gè)長(zhǎng)度為n的順序表的表尾插入一個(gè)新元素的時(shí)間負(fù)責(zé)度為O。5、非空的單循環(huán)鏈表head的尾結(jié)點(diǎn)(由指針 P所指)滿足p->next=hea

2、d。(第三章)1 .棧和隊(duì)列都是線性結(jié)構(gòu),對(duì)于棧來(lái)說(shuō),它的插入和刪除操作智能在棧頂進(jìn)行,而隊(duì)列的插入操作是在隊(duì)星進(jìn)行,刪除元素的操作是在隊(duì)首進(jìn)行。2 .設(shè)有一順序棧s,元素s1,s2,s3,s4,s5,s6吃入棧,如果六個(gè)元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)該是3。3 .在具有n個(gè)單元的循環(huán)隊(duì)列中,隊(duì)滿時(shí)共有n-1個(gè)元素。4 .從棧頂指針為T(mén)op的鏈棧中刪除一個(gè)結(jié)點(diǎn),并將結(jié)點(diǎn)值保存在X中,進(jìn)行的操作是x=Top->data;Top=Top->next。5 .中綴表達(dá)式(A+B ) *D+E/(F+A*D)對(duì)應(yīng)的后綴表達(dá)式為 AB+D*EFAD*+/+

3、6 .在操作序歹U push (1); push (2) ;pop (2);push (3); push (4); push (5); push (6); push (7); pop 之后棧頂元素和棧底元素分別是6和1。7 .在操作序歹U Qinsert(1);Qinsert(2);Qdelete(1);Qdelete(2);Qinsert(3);Qinsert(4);Qinsert (5); Qinsert(6);Qinsert(7);Qdelete(3);Qdelete(4);Qinsert(8);Qinsert(9);之后隊(duì)頭元素和隊(duì)尾元素分別是 5_和9。(第四章)1 .串是由0個(gè)或多

4、個(gè)字符組成的序列。2 .不包含任何字符串 稱為空串:由一個(gè)或多個(gè)空格組成的串 稱為空格串。3 .子用的定位運(yùn)算 稱為串的模式匹配;被匹配的主串稱為目標(biāo)串,子串稱為模式。(第五章)1 .廣義表的深度是等于括號(hào)嵌套的最大層數(shù)。2 .在廣義表的存儲(chǔ)結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)均包含3個(gè)域。3 .一個(gè)廣義表的深度等于 括號(hào)!嵌套的最大層數(shù)。4 .對(duì)矩陣壓縮是為了 節(jié)省存儲(chǔ)空間。5 .當(dāng)廣義表中的每個(gè)元素都是原子時(shí),廣義表便成了線性表。6 .廣義表的表尾是指除第一個(gè)元素之外,其余元素組成的表。7 .廣義表的 深必定義為廣義表中括弧的重?cái)?shù)。8 .設(shè)廣義表L=(), (),則hesd (L)是 ();tail (L)是

5、();L的長(zhǎng)度是2;深度是2。9 .廣義表(a, (a,b) ,d,e,(i,j),k)的長(zhǎng)度是5,深度是3。(第六章)1 .對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù),該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為nzlo2 .一顆二棵深度為5的滿二叉樹(shù)中的結(jié)點(diǎn)樹(shù)為31個(gè)。3 .假定一棵樹(shù)的廣義表表示為A (B(C,D(E,F,G),H(I,J),則樹(shù)種所含的結(jié)點(diǎn)數(shù)為 10個(gè),樹(shù)的深度為四個(gè),樹(shù)的度為3.4 .假定一棵樹(shù)的廣義表表示為A ( B(C,D(E,F,G),H(I,J),則度為3, 2, 1, 0的結(jié)點(diǎn)樹(shù)分別為 2、1、1和§個(gè)。5 .假定一棵樹(shù)的廣義表表示為A ( B(C,D(E,F,G),H(I,J),則

6、結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為 B,孩子結(jié)點(diǎn)為I和J。6 .在哈夫曼編碼中,若編碼長(zhǎng)度只允許小于等于4,則除了已對(duì)兩個(gè)字符編碼為0和10外,還可以最多對(duì)4個(gè)字符編碼。7 .對(duì)于一棵二叉樹(shù),若一個(gè)結(jié)點(diǎn)的編碼為i,則它的左孩子結(jié)點(diǎn)的編號(hào)為2i,右孩子結(jié)點(diǎn)的編號(hào)為2i+1,雙親結(jié)點(diǎn)編號(hào)為i/2 o8 .在一棵二叉樹(shù)中,第 5層上的結(jié)點(diǎn)數(shù)最多為 16。9 .假定一棵二叉樹(shù)的結(jié)點(diǎn)樹(shù)為18,則它的最小深度為 5,最大深度為18。10 .假定一棵二叉樹(shù)順序存儲(chǔ)在一維數(shù)組a中,則ai元素的左孩子元素為a2i,右孩子元素為 a2i+1,雙親元素(i-1)為ai/2。11 .假定一棵二叉樹(shù)順序存儲(chǔ)在一維數(shù)組a中,但讓編號(hào)為1

7、的結(jié)點(diǎn)存入a0元素中,讓編號(hào)為 2的結(jié)點(diǎn)存入a1元素中,其余類推,則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)對(duì)應(yīng)的存儲(chǔ)位置為2i-1。12 .對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù),對(duì)應(yīng)二叉鏈接表中指針總數(shù)為2n個(gè),其中n-1個(gè)用于指向孩子結(jié)點(diǎn),n+1個(gè)指向空閑著。13 .一棵二叉樹(shù)廣義表表示為a(b(d(h),c(e,f(g,i(k),該樹(shù)的結(jié)點(diǎn)數(shù)為10個(gè),深度為5O14 .假定一棵二叉樹(shù)廣義表表示為a (b(c),d(e,f),則對(duì)它進(jìn)行的先序遍歷結(jié)果為a b c d e f,中序遍歷結(jié)果為c b a e d f,后續(xù)序遍歷結(jié)果為 c b e f d a。(第七章)1 .有向圖G用鄰接矩陣存儲(chǔ),其第i行的所有元素之

8、和等于頂點(diǎn)i的出度。2 .圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)之適用于有向圖。3 .圖的深度優(yōu)先遍歷序列 不是唯一的。4 .圖的BFS生成樹(shù)的樹(shù)高比 DFS生成樹(shù)的樹(shù)高 矮或相當(dāng)。5 .拓?fù)渑判蜉敵龅捻旤c(diǎn)數(shù)小于有向圖的頂點(diǎn)數(shù),則該圖一定存在 如。6 .若要求一個(gè)稀疏圖 G的最小生成樹(shù),最好用 Kruskal算法來(lái)求解。1 .關(guān)鍵字是數(shù)據(jù)元素(或記錄)中某個(gè)屬性,用它的標(biāo)識(shí)(或識(shí)別)一個(gè)查找表中的 數(shù)據(jù)元素(或記錄)。并且,在一個(gè)查找表中,能夠唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素(或記錄)的關(guān)鍵字稱為主關(guān)鍵字。2 .查找又稱為(檢索),它是根據(jù)給定的某個(gè)值,在查找表中確定是否有元素或記錄的關(guān)鍵字等于給定值的操作。若操作之后確定

9、表中存在這樣的記錄,則稱為查找是成功的,否則稱為不成功(或失敗)。3 .平均查找長(zhǎng)度是指為確定所查找的記錄在查找表中的位置,需要與給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的平均伯(或期望值)。4 .采用順序查找法查找長(zhǎng)度為n大的線性表時(shí),假設(shè)查找成功與查找不成功的概率對(duì)等,對(duì)每個(gè)記錄的查找概率也相等,則平均查找長(zhǎng)度為3 (n+1) /4。5 .折半查找又稱為 二分杳找,其查找思路是:每次將給定值與查找表中所要查找區(qū)域中間位置的關(guān)鍵字進(jìn)行比較,而不是查找表中的第一條或最后一條。6 .在各種查找方法中,平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是哈希表杳找法。7 .哈希表的查找小綠主要取決于哈希表建表時(shí)選擇的哈希函

10、數(shù) 和裝埴因子。8 .構(gòu)造哈希函數(shù)的方法有 直接岸址法、數(shù)字分析法、平方取中法、折疊法和除留余數(shù)法。9 .假定有K個(gè)關(guān)鍵字互為同義詞,若用線性探測(cè)法把這K個(gè)關(guān)鍵字存入哈希表中,至少要進(jìn)行(K/1 )82_次探測(cè)。10 .二叉排序樹(shù)又稱為 二叉杳找樹(shù),它或者是一棵空樹(shù),或者是具有下列性質(zhì)的一棵二叉樹(shù);(1)若左子樹(shù)不空,則左子樹(shù)上所有結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值。(2)若右子樹(shù)不空,則左子樹(shù)上所有結(jié)點(diǎn)的值大干根結(jié)點(diǎn)的俏。(3)左、右子樹(shù)又分別是一棵二叉排序樹(shù)。11 .平衡二叉樹(shù)是有 Abelson-Velskil和Landis提出的一種附加一定限制條件的二叉樹(shù)。又稱為AVL樹(shù)。平衡二叉樹(shù)定義為:它或者

11、是一棵空樹(shù);或者是具有這樣性質(zhì)的二叉樹(shù);它的左子樹(shù)和右子樹(shù)都是一棵平衡二叉樹(shù),且左子樹(shù)和右子樹(shù)的深度之差絕對(duì)值不大于112.在向哈希表中存儲(chǔ)關(guān)鍵字的時(shí)候,有時(shí)會(huì)出現(xiàn)一個(gè)待插入關(guān)鍵字的記錄已經(jīng)被占用的情況,這種對(duì)不同關(guān)鍵字得到同一地址的現(xiàn)象稱為沖突(或碰撞),相應(yīng)的把這些具有相同哈希函數(shù)值得關(guān)鍵字稱為同義而。 13.構(gòu)造哈希函數(shù)應(yīng)當(dāng)盡量減少?zèng)_突,但是還是無(wú)法避免沖突的發(fā)生,一旦沖突發(fā)生了,就必須訊企鵝合適的方法來(lái)解決沖突。常用開(kāi)放地址法和鏈地址法兩種方法來(lái)解決沖突。 14.對(duì)長(zhǎng)度n=50的有序表進(jìn)行折半查找,則對(duì)應(yīng)的判定樹(shù)高度為6,判定樹(shù)前5層的結(jié)點(diǎn)樹(shù)是31,最后一層的結(jié)點(diǎn)樹(shù)為9。二、單選題(第

12、二章)1、線性表L= ( ai,a2,,a,a),下列說(shuō)法正確的是( D) A、每個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼 B、線性表中至少有一個(gè)元素C、表中諸元素的排列順序必須是從小到大或由大到小D、除第一個(gè)元素和最后一個(gè)元素外,其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。2、對(duì)于順序表,以下說(shuō)法錯(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ǔ)在物理位置也相鄰的單元中 3、對(duì)順序表上的插入、

13、刪除、算法的時(shí)間復(fù)雜度分析來(lái)說(shuō),通常以( B)對(duì)標(biāo)準(zhǔn)操作。 A、條件判斷 B、結(jié)點(diǎn)移動(dòng)C、算術(shù)表達(dá)式D、賦值語(yǔ)句4、對(duì)于順序表的優(yōu)、缺點(diǎn),以下說(shuō)法錯(cuò)誤的是( C) A、無(wú)須為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間 B、可以方便的隨機(jī)存儲(chǔ)表中任一結(jié)點(diǎn) C、插入和刪除操作較方便D、由于順序表要求占用連續(xù)的空間,存儲(chǔ)分配只能預(yù)先進(jìn)行(靜態(tài)分配)5、在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中,在任一結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)所需移動(dòng)的點(diǎn)的平均次數(shù)為(B)A、nB、n/2C、(n-1)/2D、(n+1)/26、在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中,刪除一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為(C)A、nB、n/2C、(n-1)

14、/2D、(n+1)/27、帶頭結(jié)點(diǎn)的單鏈表head為空的條件是(B)A、head=NULL B、head->next=NULL C、head->next=head D、head!=NULL8、非空循環(huán)單鏈表 head的尾結(jié)點(diǎn)*p滿足(C)A、p->next=NULLB、p=NULL C、p->next=head D、p=head9、在循環(huán)雙鏈表的*p結(jié)點(diǎn)之后插入*s滿足(D)A、p->next=s;s->prior=p;p->next->prior=s;s->next=p->next; B、p->next=s;p->nex

15、t->prior=s;s->prior=p;s->next=p->next; C、s->prior=p;s->next=p->next;p->next=s;p->next->prior=s; D、s->prior=p;s->next=p->next;p->next->prior=s;p->next=s; 10、在線性表的下列存儲(chǔ)結(jié)構(gòu)中,讀取元素花費(fèi)時(shí)間最少的是( D) A、單鏈表 B、雙鏈表C、循環(huán)列表D、順序表(第三章)1.有一棧的輸入序列是a、b、c,則通過(guò)入棧、出棧操作可能得到a、b、c的不同

16、排列個(gè)數(shù)為(B)。A. 42 .和順序棧相比,鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是(A通常不會(huì)出現(xiàn)棧滿的情況C插入操作更容易實(shí)現(xiàn)3 .若一個(gè)棧的輸入序列是1、2、A不確定 B n-i4 .一個(gè)棧的入棧序列是a、b、c、A e、d、c、b、a B d、e、c、5 .一個(gè)隊(duì)列的入隊(duì)列是1、2、3、A. 4、3、2、1B. 1、2、6 .順序列隊(duì)的出隊(duì)操作為(B)A sq.front=(sq.front+1)%maxsizeCsq.rear=(sq.rear+1)maxsize7 .循環(huán)隊(duì)列q的出隊(duì)操作為(A)A q,front=(q.front+1)%maxsizeC q.rear=(q.rear+1)%m

17、axisize8 .循環(huán)隊(duì)列用數(shù)組A0 則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是A.(rear-front+m)%mC.read-front-19 .在一個(gè)鏈隊(duì)中,假設(shè)A)。B通常不會(huì)出現(xiàn)??盏那闆rD刪除操作更容易實(shí)現(xiàn)3、4、n,輸出序列第一個(gè)元素是C n-i+1D n-i-1d、e,則棧的不可能輸出序列是( b、a C d、c、e、a、b D a、4,則隊(duì)列的可能輸出序列是(B)4C.1、4、3、2B sq.front=sq.front+1D sq.rear=sq.rear+1B q.front=q.front+1Dq.rear=q.rear+13、n,則第i個(gè)輸出元素是(C)。C)b、 c、 d、 eD

18、.3、2、4、1m-1存放其元素值,已知其頭、尾指針?lè)謩e是(A)。B read-front+1D.read-frontf和r分別為隊(duì)首和隊(duì)尾指針,則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算是(front 和 rear,C)。A,r=f->next B.r=r->next(第四章)1 .串是(D)A. 一些符號(hào)構(gòu)成的序列C. 一個(gè)以上的字符構(gòu)成的序列C.f=f->next D f=r->nextB.一些字母構(gòu)成的序列D.任意有限個(gè)字符構(gòu)成的序列2.S1= " abcd "S2= " cd,” 貝U S2 在 S1 中的位置是(C)。A.1B.2C.3D.43 .下

19、列為空串的是(C)。A. " B. ”“ C.” "D "4 .樸素模式匹配算法在最好的情況下的運(yùn)行時(shí)間是(以一次內(nèi)循環(huán)為單位)(C)。A.M B.NC.MXN D.M+N(第五章)1 .已知廣義表LS= (a,b,c), (d,e,f),運(yùn)用head和tail函數(shù)取出LS中元素e的運(yùn)算是(C)A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)2 .將一個(gè)A1100,110曲三對(duì)角矩陣,按行優(yōu)先存入一維數(shù)組 B1 298中,A中元素a66, 65 (即該元

20、 素下標(biāo)i=66,j=65 )在B數(shù)組中白位置 K為(B)A.198B.195C.197D.1963 .若廣義表 A滿足Head (A) =Tail (A),則A為(B)。A.()B.()C.(),()D.(),(),()4 .廣義表 A= (a,b,(c,d),(e,(f,g),則下面式子 Head (Tail(Head(Tail(Tail(A)的值為(D)。A.(g) B. (d) C.cD.d5 .二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串,其行下標(biāo) i=0,1, 丁 8,列下標(biāo)j=1,2,,10.若A按行先 存儲(chǔ),元素A8,5的起始地址與當(dāng) A按列先存儲(chǔ)時(shí)的元素(B)的起始地址相同。設(shè)每

21、個(gè)字符占一個(gè)字節(jié)。A. A8 , 5B.A3 , 10C,A5 , 8D.A0 , 96 .在以下的敘述中,正確的是( B)A.線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B.二維數(shù)組是其數(shù)據(jù)元數(shù)為線性表的線性表C.棧的操作方式是先進(jìn)先出D.隊(duì)列的操作方式是先進(jìn)后出7二維數(shù)組SA中,每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié),行下標(biāo)i從07,歹U下標(biāo)j從09,從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi),該數(shù)組按列存放時(shí),元素 SA47的起始地址為(B)。A.SA+141B.SA+180C.SA+222D.SA+2258 .下面結(jié)論正確的是(B)。A. 一個(gè)廣義表的表頭肯定不是一個(gè)廣義表。B. 一個(gè)廣義表的表尾肯定是一個(gè)廣義表。

22、C.廣義表L=(),(A,B)的表頭為空表D.廣義表中原子個(gè)數(shù)即為廣義表的長(zhǎng)度9 .下面說(shuō)法不正確的是(A)A.廣義表的表頭總是一個(gè)廣義表B.廣義表的表尾總是一個(gè)廣義表C.廣義表難以用順序存儲(chǔ)結(jié)構(gòu)D,廣義表可以是一個(gè)多層次的結(jié)構(gòu)(第六章)1 .一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反,則該二叉樹(shù)一定滿足(C)。A.所有的結(jié)點(diǎn)均無(wú)左孩子B.所有的結(jié)點(diǎn)均無(wú)右孩子C.只有一個(gè)葉子結(jié)點(diǎn)D.是任意一棵二叉樹(shù)2 .一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn),其中椰子結(jié)點(diǎn)個(gè)數(shù)是( D)。A.250B.500C.254D.以上答案都不對(duì)3 .任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在前(先)序、中序、后序遍歷序列中的相對(duì)次序

23、(A)。A不發(fā)生變化B.發(fā)生變化C.不能確定4 .設(shè)A,B為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn),在中序遍歷時(shí), A在B前面的條件是(B)。.A在B的右方B. A在B的左方C.A是B的祖先D.A是B的子孫5 .在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中,數(shù)值結(jié)點(diǎn)最大編號(hào)為(D)A. (n+1)/2B.(n-1)/2C. n/2D. n/26 .在N個(gè)結(jié)點(diǎn)的線索二叉樹(shù)中,線索的數(shù)目為(C)。A.N-1B.NC.N+1 D.2N7 .設(shè)深度為K的二叉樹(shù)上只有度為 0和度為2的結(jié)點(diǎn),則這類二叉樹(shù)上所含的結(jié)點(diǎn)總數(shù)為( C)A.K+1B.2KC. 2K 1D, 2K+18 .下列有關(guān)二叉樹(shù)的說(shuō)法,正確的是(B)。A.二叉樹(shù)的度

24、為2B. 一棵二叉樹(shù)度可以小于2C.二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹(shù)中任意個(gè)結(jié)點(diǎn)的度都為29.在一棵深度為 H的完全二叉樹(shù)中,A.2HB.2 H-1C.2H-1所含結(jié)點(diǎn)的個(gè)數(shù)不小于(D.2H+1D)。10.在一棵具有N個(gè)結(jié)點(diǎn)的二叉樹(shù)第I層上,最多具有(C)個(gè)結(jié)點(diǎn)。A. 2IB. 2H-1C. .2H -1D.2N11 .在下列情況下,可稱為二叉樹(shù)的是(A.每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的樹(shù)C.每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的有序樹(shù)12 .樹(shù)最適合用來(lái)表示(C)。A.有序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)A)。B.哈夫曼樹(shù)D.每個(gè)結(jié)點(diǎn)只有一棵右子樹(shù)B.無(wú)序數(shù)據(jù)元素D.元素之間無(wú)聯(lián)系的數(shù)據(jù)A)的二

25、叉樹(shù)。13 .某二叉樹(shù)的前序序列和后序序列正好相反,則二叉樹(shù)A.空或只有一個(gè)結(jié)點(diǎn)B.任一結(jié)點(diǎn)無(wú)左子樹(shù)C.高度等于其結(jié)點(diǎn)數(shù)D.任一結(jié)點(diǎn)無(wú)右子樹(shù)14 .按照二叉樹(shù)的定義,具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有(C)種。.A.3B.4C.5D.615 .對(duì)一個(gè)滿二叉樹(shù),m個(gè)樹(shù)葉,n個(gè)結(jié)點(diǎn),深度為h,則(D)。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-116 .在一非空二叉樹(shù)的中序遍歷序列中,根結(jié)點(diǎn)的右邊( A)。A.只有右子樹(shù)上的所有結(jié)點(diǎn)B.只有右子樹(shù)上的部分結(jié)點(diǎn)C.只有左子樹(shù)上的部分結(jié)點(diǎn)D.只有左子樹(shù)上的所有結(jié)點(diǎn)17 .任何一棵二叉樹(shù)的結(jié)點(diǎn)在先序、中序、后序遍歷中的相對(duì)次序( A)。A.不發(fā)生改變

26、B.發(fā)生改變C.不能確定D.以上都不對(duì)D)18 .已知某二叉樹(shù)的后序遍歷序列是dabec,中序遍歷序列是 debac,它的前序遍歷序列是(A.acbedB.decabC.deabc D.cedba19 .由帶權(quán)為8、2、5、7的4個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù),該樹(shù)的帶權(quán)路徑長(zhǎng)度為( DA.23B.37C.46D.4320 .對(duì)二叉排序樹(shù)進(jìn)行(B)遍歷,可以得到該二叉樹(shù)所有結(jié)點(diǎn)構(gòu)成的排序序列。A.前序 B.中序C.后序D.按層次(第七章)1 .在一個(gè)有向圖中,所有頂點(diǎn)的入度和等于所有頂點(diǎn)的出度之和的( B)倍。A 1/2B.1C.2D.42 .用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí),通常采用( B)來(lái)實(shí)

27、現(xiàn)算法。A.棧B.隊(duì)列C.樹(shù)D.圖3 .具有n個(gè)頂點(diǎn)的無(wú)向完全圖,邊的總數(shù)為(D)。A,nB.n+1C.2n-1D.n (n-1) /24 .有n個(gè)頂點(diǎn)的連通 G的最小生成樹(shù)有(C)條邊。A.n-1B.nC.n+1D.不確定5 .一個(gè)有向無(wú)環(huán)圖的拓?fù)湫蛄袀€(gè)數(shù)是(B)。A.1個(gè) B.1個(gè)或多個(gè) C.0個(gè) D.多個(gè)6 .在AOE網(wǎng)中,入度為0的頂點(diǎn)稱為(B)A.起點(diǎn) B.源點(diǎn)C.終點(diǎn)D.匯點(diǎn)7 .Prim算法的時(shí)間復(fù)雜度是(B)A.O (n) B.O (n2)C.O (e) D.O(eloge)8 .在無(wú)向圖的鄰接矩陣 A中,若Aij=1 ,則A皿i的值為(C)A.i+jB.i-jC.1D.0(第

28、八章)1 .靜態(tài)查找表與動(dòng)態(tài)查找表的根本區(qū)別在于( B)A.它們的邏輯結(jié)構(gòu)不一樣B.施加在其上的操作不一樣C.所包含的數(shù)據(jù)元素類型不一樣D.存儲(chǔ)實(shí)現(xiàn)不一樣2 .順序查找適用于存儲(chǔ)結(jié)構(gòu)為(C)的線性表。A.哈希表B.壓縮存儲(chǔ)C.順序存儲(chǔ)或鏈接存儲(chǔ)D.索引存儲(chǔ)3 .對(duì)線性表進(jìn)行折半查找最方便的存儲(chǔ)結(jié)構(gòu)是(B)。A.順序表B.有序的順序表C.鏈表D,有序的鏈表4 .對(duì)一個(gè)排好序的線性表,用折半查找法檢索表中的元素,被檢索的表應(yīng)當(dāng)采用(A)。A.順序存儲(chǔ)B.鏈接存儲(chǔ)C.散列法存儲(chǔ)D.存儲(chǔ)表示不受限制5 .若在線性表中采用折半查找法查找元素,該線性表應(yīng)該( C)。A.元素按值有序B.采用順序存儲(chǔ)結(jié)構(gòu)C.

29、元素按值有序,且采用順序存儲(chǔ)結(jié)構(gòu)D.元素按值有序,且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)6 .在順序表(3,6,8,10,12,15,16,18,21,25,30)中,用折半查找法查找關(guān)鍵碼值11,所需的關(guān)鍵碼比較次數(shù)為(C)。A.2B.3C.4D.57 .用折半查找法查找一個(gè)長(zhǎng)度為10的、排好序的線性表,查找不成功時(shí),最多需要比較(C)次。A.5B.2C.4D.18 .采用順序查找方法查找長(zhǎng)度為n的線性表時(shí),每個(gè)元素的平均查找長(zhǎng)度為( C)。A.nB.n/2 C. (n+1) /2D.(n-1)/29 .有一個(gè)長(zhǎng)度為12的有序表,按折半查找法對(duì)該表進(jìn)行查找,在表內(nèi)每個(gè)元素等概率情況下查找成功時(shí)所需的平均比較次數(shù)

30、是(B)A.35/12B.37/12C.39/12D.41/1210 .設(shè)有100個(gè)元素,用折半查找法進(jìn)行查找時(shí),最小比較次數(shù)是( D)。A.1B.2C.4D.711 .利用逐點(diǎn)插入法建立序列(50,72,43,85,75,20,35,45,65,30)對(duì)應(yīng)的二叉排序樹(shù)以后,查找元素35要進(jìn)行(A)次元素間的比較。A.4B.5C.6D.712 .在關(guān)鍵字隨機(jī)分布的情況下,用二叉排序樹(shù)的方法進(jìn)行查找,其查找長(zhǎng)度與(B)量級(jí)相當(dāng)。A順序查找B折半查找C分塊查找D以上都不正確13 .如果要求一個(gè)線性表既能較快地查找,又能適應(yīng)動(dòng)態(tài)變化的要求,可以采用(C)查找方法。A順序B折半C散列D以上都不正確14

31、 .一棵平衡二叉樹(shù),其每個(gè)非終端節(jié)點(diǎn)的平衡因子均為0,則該樹(shù)共有(D)個(gè)結(jié)點(diǎn)。A.2 k-1-1B.2k-1C2k-1+1D.2k-115 .設(shè)哈希表上 m=14,哈希表函數(shù) H(key尸key%11。表中已有 4 個(gè)結(jié)點(diǎn):addr(15)=4 ; addr(38)=5 ; ;addr(61)=6 ; addr(84)=7;其余地址為空,如果用二次探測(cè)再散列處理沖突,關(guān)鍵字為49的結(jié)點(diǎn)的地址是(D)A.9B.8C.5D.316 .在哈希查找中,平均查找長(zhǎng)度主要與(C)有關(guān)。A.哈希表長(zhǎng)度B哈希元素的個(gè)數(shù)C裝填因子 D處理沖突方法17 .在采用線性探測(cè)法處理沖突的散列表上,假定裝填因子”的值為0

32、.5,則查找任一元素的平均查找長(zhǎng)度約為(B)A 1B 1.5C2D3.518 .在采用鏈接法處理沖突的散列表上,假定裝填因子 a的值為4,則查找任一元素的平均查找長(zhǎng)度約為(A)A 3B 3.5C2D 419 .若對(duì)一組關(guān)鍵字(23,44,36,48,52,73,64,58)建立散列表,采用 H (K) =K%7計(jì)算散列地址,則同義詞 元素的個(gè)數(shù)最多為(B)個(gè)A 2 B 3 C 4 D 520 .若對(duì)一組關(guān)鍵字(23,44,36,48,52,73,64,58)建立散列表,采用 H(K)=K%13計(jì)算散列地址,并采用鏈接 法處理沖突,則元素 64的初始散列地址(C)A.2B.8C.12D.13三、

33、簡(jiǎn)答題(第二章)(1)簡(jiǎn)述合適選用順序表或鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜。答:在實(shí)際應(yīng)用中,應(yīng)根據(jù)具體問(wèn)題的要求和性質(zhì)來(lái)選擇順序表或鏈表作為線性表的存儲(chǔ)結(jié)構(gòu),通常 有以下幾方面的考慮?;诳臻g的考慮。當(dāng)要求存儲(chǔ)的線性表長(zhǎng)度變化不大,易于事先確定其大小時(shí),為了節(jié)約存儲(chǔ)空間,宜采用順序表;反之,當(dāng)線性表長(zhǎng)度變化大,難以估計(jì)其存儲(chǔ)規(guī)模時(shí),采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好?;跁r(shí)間的考慮。若線性表的操作主要是進(jìn)行查找,很少做插入和刪除操作時(shí),采用順序表做存儲(chǔ) 結(jié)構(gòu)為宜;反之,若需要對(duì)線性表進(jìn)行頻繁地插入或刪除等操作時(shí),宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。并且,若鏈 表的插入和刪除主要發(fā)生在表的首、尾兩端,則采用尾指針表示

34、循環(huán)單鏈表為宜。(2)為什么在循環(huán)單鏈表中設(shè)置尾指針比設(shè)置頭指針更好?答:尾指針是指向終端節(jié)點(diǎn)的指針,用它來(lái)表示循環(huán)單鏈表可以使得查找鏈表的開(kāi)始節(jié)點(diǎn)和終端節(jié)點(diǎn) 都很方便,設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表,其尾指針為rear,則開(kāi)始節(jié)點(diǎn)和終端節(jié)點(diǎn)的位置分別是rear->next->next 和 rear,查找時(shí)間者B是 O (1)。(第三章)1 .鏈棧中為何不設(shè)置頭結(jié)點(diǎn)?答:鏈棧不需要在頭部附加頭結(jié)點(diǎn),因?yàn)闂6际窃陬^部進(jìn)行操作的,如果加了頭結(jié)點(diǎn),等于要對(duì)頭結(jié) 點(diǎn)之后的結(jié)點(diǎn)進(jìn)行操作,反而使算法更加復(fù)雜。所以只要有鏈表的頭指針就可以了。2 .循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么?如何判別它的空和滿?答:循環(huán)列隊(duì)

35、的優(yōu)點(diǎn)是:它可以克服順序列隊(duì)的假上溢”現(xiàn)象,能夠使存儲(chǔ)隊(duì)列的向量空間得到充分利用。判別循環(huán)隊(duì)列的空”或 滿”不能以頭尾指針是否相等來(lái)確定,一般是通過(guò)以下幾種方法:一個(gè)是另設(shè)一個(gè)布爾變量來(lái)區(qū)別隊(duì)列的空和滿;二是少用一個(gè)元素的空間,每次入隊(duì)前測(cè)試入隊(duì)后頭尾指針是否會(huì) 重合,如果會(huì)重合就認(rèn)為隊(duì)列已滿;三是設(shè)置一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素總數(shù),不僅可判別空或滿,還可 以得到隊(duì)列中元素的個(gè)數(shù)。(第四章)1 .試回答空串與空格串有何區(qū)別?答:空串是不含任何字符的串,長(zhǎng)度為0,空格串是有空格字符組成的串,串的長(zhǎng)度為空格的個(gè)數(shù)。2 .試找出分別滿足下面條件的所有二叉樹(shù)(1)前序序列和中序序列相同。答:空二叉樹(shù)或沒(méi)有左子樹(shù)的二叉樹(shù)(右單支樹(shù))(2)中序序列和后序序列相同。答:空二叉樹(shù)或沒(méi)有右子樹(shù)的二叉樹(shù)(左單支樹(shù))(3)前序序列和后序序列相同。答:空二叉樹(shù)或只有根的二叉樹(shù)。(4)前序、中序、后序序列相同。答:空樹(shù)或只有根結(jié)點(diǎn)的二叉樹(shù)3

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論