數(shù)據(jù)結(jié)構(gòu)--重修作業(yè)題(1).doc

第一章 緒論一、選擇題 3.在數(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）線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)（D）內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 5.算法分析的目的是（）。 （A） 找出數(shù)據(jù)結(jié)構(gòu)的合理性 （B）研究算法中的輸入和輸出的關(guān)系 （C）分析算法的效率以求改進(jìn)（D）分析算法的易懂性和文檔性 二、判斷題 1.數(shù)據(jù)的機(jī)內(nèi)表示稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。（ ） 2.算法就是程序。（ ） 5.算法的時(shí)間復(fù)雜度取決于問(wèn)題的規(guī)模和待處理數(shù)據(jù)的初態(tài)。（ ） 三、填空題 1.數(shù)據(jù)邏輯結(jié)構(gòu)包括_、_、_ 和_四種類(lèi)型,其中樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱(chēng)為_(kāi)。 2.在線(xiàn)性結(jié)構(gòu)中,第一個(gè)結(jié)點(diǎn)_前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有_個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)_后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有_個(gè)后續(xù)結(jié)點(diǎn)。 3.在樹(shù)形結(jié)構(gòu)中,樹(shù)根結(jié)點(diǎn)沒(méi)有_結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有_個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有_結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以_。 4.在圖形結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以_。 5.線(xiàn)性結(jié)構(gòu)中元素之間存在_關(guān)系,樹(shù)形結(jié)構(gòu)中元素之間存在_關(guān)系,圖形結(jié)構(gòu)中元素之間存在_關(guān)系。8.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比較,主要優(yōu)點(diǎn)是_。 9.設(shè)有一批數(shù)據(jù)元素,為了最快的存儲(chǔ)某元素,數(shù)據(jù)結(jié)構(gòu)宜用_結(jié)構(gòu),為了方便插入一個(gè)元素,數(shù)據(jù)結(jié)構(gòu)宜用_結(jié)構(gòu)。 四、算法分析題,求下列算法段的語(yǔ)句頻度及時(shí)間復(fù)雜度 for （i=1;i=n;i+） for (j=1;j=i;j+) for ( k=1;ktop=0 （C）ST.top!=m0-1（D）ST.top=m0-15.一個(gè)隊(duì)列的入列序列是1,2,3,4,則隊(duì)列的輸出序列是（ ）。（A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,16.循環(huán)隊(duì)列用數(shù)組A0,m-1存放其元素值,已知其頭尾指針?lè)謩e是front和rear則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（ ）（A）(rear-front+m)%m （B） rear-front+1 （C）rear-front-1（D）rear-front7.棧和隊(duì)列的共同點(diǎn)是（ ）（A） 都是先進(jìn)后出 （B）都是先進(jìn)先出（C）只允許在端點(diǎn)處插入和刪除元素（D）沒(méi)有共同點(diǎn)9.4個(gè)元素a1，a2，a3和a4依次通過(guò)一個(gè)棧，在a4進(jìn)棧前，棧的狀態(tài)，則不可能的出棧序是（）(A)a4，a3，a2，a1(B)a3，a2，a4，a1 (C)a3，a1，a4，a2(D)a3，a4，a2，a110.以數(shù)組Q0.m1存放循環(huán)隊(duì)列中的元素，變量rear和qulen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的實(shí)際位置和當(dāng)前隊(duì)列中元素的個(gè)數(shù)，隊(duì)列第一個(gè)元素的實(shí)際位置是（）(A)rearqulen(B)rearqulenm(C)mqulen (D)1（rearmqulen）% m二、填空題1.棧的特點(diǎn)是_,隊(duì)列的特點(diǎn)是_。2.線(xiàn)性表、棧和隊(duì)列都是_結(jié)構(gòu),可以在線(xiàn)性表的_位置插入和刪除元素，對(duì)于棧只能在_插入和刪除元素，對(duì)于隊(duì)列只能在_插入元素和_刪除元素。3.一個(gè)棧的輸入序列是12345,則棧有輸出序列12345是_。(正確/錯(cuò)誤)4.設(shè)棧S和隊(duì)列Q的初始狀態(tài)皆為空，元素a1，a2，a3，a4，a5和a6依次通過(guò)一個(gè)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)列的順序是a3，a5，a4，a6，a2，a1則棧S至少應(yīng)該容納_個(gè)元素。三、算法設(shè)計(jì)題 1.鏈棧的出棧入棧算法。2.順序循環(huán)隊(duì)列的出隊(duì)入隊(duì)算法.第四章 串和數(shù)組 一、選擇題 1.下列關(guān)于串的敘述中，正確的是（ ）(A)一個(gè)串的字符個(gè)數(shù)即該串的長(zhǎng)度 (B)一個(gè)串的長(zhǎng)度至少是1(C)空串是由一個(gè)空格字符組成的串 (D)兩個(gè)串S1和S2若長(zhǎng)度相同，則這兩個(gè)串相等2. 二維數(shù)組M的元素是4個(gè)字符(每個(gè)字符占一個(gè)存儲(chǔ)單元)組成的串,行下標(biāo)i的范圍從0到4,列下標(biāo)j的范圍從0到5,M按行存儲(chǔ)時(shí)元素M35的起始地址與M按列存儲(chǔ)時(shí)元素( ) 的起始地址相同。（A）M24（B）M34（C）M35（D）M443.數(shù)組A810中,每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié),從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi),存放該數(shù)組至少需要的單元數(shù)是（ ）。（A）80（B）100（C）240（D）2704.數(shù)組A810中,每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié),從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi),該數(shù)組按行存放時(shí),元素A74的起始地址為（ ）。（A）SA+141（B）SA+144（C）SA+222（D）SA+2255.數(shù)組A810中,每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié),從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi),該數(shù)組按列存放時(shí),元素A47的起始地址為（ ）。（A）SA+141（B）SA+180（C）SA+222（D）SA+2256.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種,即（ ）。（A） 二維數(shù)組和三維數(shù)組（B）三元組和散列（C）三元組和十字鏈表 （D）散列和十字鏈表7.若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣,只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換,就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算,這種觀點(diǎn)（ ）。（A）正確（B）錯(cuò)誤8.設(shè)矩陣A是一個(gè)對(duì)稱(chēng)矩陣,為了節(jié)省存儲(chǔ),將其下三角部分按行序存放在一維數(shù)組B1,n(n-1)/2中,對(duì)下三角部分中任一元素ai,j(i=j),在一組數(shù)組B的下標(biāo)位置k的值是（ ）。（A）i(i-1)/2+j-1（B）i(i-1)/2+j（C）i(i+1)/2+j-1 (D)i(i+1)/2+j4.串是一種特殊的線(xiàn)性表,其特殊性表現(xiàn)在（ ）(A)可以順序存儲(chǔ) (B)數(shù)據(jù)元素是一個(gè)字符(C)可以鏈?zhǔn)酱鎯?chǔ) (D)數(shù)據(jù)元素可以是多個(gè)字符5設(shè)串S1=ABCDEFG,s2=PQRST,函數(shù)CONCAT（X，Y）返回X和Y串的連接串，SUBSTR（S，I，J）返回串S從序號(hào)I開(kāi)始的J個(gè)字符組成的字串，LENGTH（S）返回串S的長(zhǎng)度，則CONCAT（SUBSTR（S1，2，LENGTH（S2），SUBSTR（S1，LENGTH（S2），2）的結(jié)果串是（ ）（A）BCDEF (B) BCDEFG (C)BCPQRST (D)BCDEFEF 2、 填空題1. 己知二維數(shù)組Amn采用行序?yàn)橹鞣绞酱鎯?chǔ),每個(gè)元素占k個(gè)存儲(chǔ)單元,并且第一個(gè)元素的存儲(chǔ)地址是LOC(A00),則A00的地址是_。2.二維數(shù)組A1020采用列序?yàn)橹鞣绞酱鎯?chǔ),每個(gè)元素占一個(gè)存儲(chǔ)單元,并且A00的存儲(chǔ)地址是200,則A612的地址是_。3.有一個(gè)10階對(duì)稱(chēng)矩陣A,采用壓縮存儲(chǔ)方式(以行序?yàn)橹?且A00=1),則A85的地址是_。4.設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組S1.n*(n+1)/2中,若按行序?yàn)橹鞔鎯?chǔ),則Aij對(duì)應(yīng)的S中的存儲(chǔ)位置是_。5.若A是按列序?yàn)橹餍蜻M(jìn)行存儲(chǔ)的46的二維數(shù)組,其每個(gè)元素占用3個(gè)存儲(chǔ)單元,并且A00的存儲(chǔ)地址為1000,元素A13的存儲(chǔ)地址為_(kāi),該數(shù)組共占用_個(gè)存儲(chǔ)單元。三、算法設(shè)計(jì) 1.串的模式匹配算法。第五章 樹(shù)與二叉樹(shù)3.二叉樹(shù)的前序遍歷序列中,任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面,這種說(shuō)法（ ）(A)正確 (B)錯(cuò)誤 （C）不同情況下答案不確定4.由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度最大為2,所以二叉樹(shù)是一種特殊的樹(shù),這種說(shuō)法（ ） 2. 正確 （B）錯(cuò)誤 （C）不同情況下答案不確定5.設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn),則此類(lèi)二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為（ ）。（A）2h （B）2h-1（C）2- 9 -3+1（D）h+16.已知某二叉樹(shù)的后序遍歷序列是dabec。中序遍歷序列是debac,它的前序遍歷序列是（ ）。（A）acbed （B）decab（C）deabc （D）cedba7.如果T2是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù),那么T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的（ ）（A）前序（B）中序（C）后序（D）層次序8.某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪(fǎng)問(wèn)順序是abdgcefh,中序遍歷的結(jié)點(diǎn)訪(fǎng)問(wèn)順序是dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪(fǎng)問(wèn)順序是（ ）。（A）bdgcefha （B）gdbecfha （C）bdgaechf （D）gdbehfca9.二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法（ ）（A）正確（B）錯(cuò)誤（C）不同情況下答案不確定10.按照二叉樹(shù)的定義,具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有（ ）種。（A）3（B）4（C）5（D）611.在一非空二叉樹(shù)的中序遍歷序列中,根結(jié)點(diǎn)的右邊（ ）（A）只有右子樹(shù)上的所有結(jié)點(diǎn)（B）只有右子樹(shù)上的部分結(jié)點(diǎn)（C）只有左子樹(shù)上的部分結(jié)點(diǎn)（D）只有左子樹(shù)上的所有結(jié)點(diǎn)12.樹(shù)最適合用來(lái)表示（ ）。（A）有序數(shù)據(jù)元素（B）無(wú)序數(shù)據(jù)元素（C）元素之間具有分支層次關(guān)系的數(shù)據(jù)（D）元素之間無(wú)聯(lián)系的數(shù)據(jù)13.任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（ ）（A）不發(fā)生改變（B）發(fā)生改變（C）不能確定D.以上都不對(duì)15.對(duì)一個(gè)滿(mǎn)二叉樹(shù),m個(gè)樹(shù)葉,n個(gè)結(jié)點(diǎn),深度為h,則（ ）（A）n=h+m （B）h+m=2n（C）m=h-1（D）n=2h-1 16.如果某二叉樹(shù)的前序?yàn)閟tuwv,中序?yàn)閡wtvs,那么該二叉樹(shù)的后序?yàn)椋?）（A）uwvts （B）vwuts（C）wuvts （D）wutsv17.具有五層結(jié)點(diǎn)的二叉平衡樹(shù)至少有（ ）個(gè)結(jié)點(diǎn)。（A）10（B）12（C）15（D）173. 已知一棵樹(shù)邊的集合為，,，畫(huà)出這棵樹(shù)，并回答下列問(wèn)題： 哪個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)？ 1 哪些結(jié)點(diǎn)是葉子結(jié)點(diǎn)？ 2 哪個(gè)結(jié)點(diǎn)是結(jié)點(diǎn) G 的雙親結(jié)點(diǎn)？ 3 哪些結(jié)點(diǎn)是結(jié)點(diǎn) G 的祖先結(jié)點(diǎn)？ 4 哪些結(jié)點(diǎn)是結(jié)點(diǎn) G 的孩子結(jié)點(diǎn)？ 5 哪些結(jié)點(diǎn)是結(jié)點(diǎn) E 的子孫結(jié)點(diǎn)？ 6 哪些結(jié)點(diǎn)是結(jié)點(diǎn) E 的兄弟結(jié)點(diǎn)？哪些是結(jié)點(diǎn) F 的兄弟結(jié)點(diǎn)？ 7 結(jié)點(diǎn) B 和 N 的層次分別是多少？8 樹(shù)的深度是多少？1) 以結(jié)點(diǎn) C 為根的子樹(shù)的深度是多少？4. 已知一棵二叉樹(shù)的先序、中序和后序序列如下，其中各有一部分未給出其值，請(qǐng)構(gòu)造出該二叉樹(shù)。 先序：A_CDEF_H_J 中序：C_EDA_GFI_ 后序：C_ _BHGJI_ _5. 已知一棵樹(shù)的度為4，其中度為4的結(jié)點(diǎn)的數(shù)目為3，度為3的結(jié)點(diǎn)的數(shù)目為4，度為2的結(jié)點(diǎn)的數(shù)目為54.按照下列給定二叉樹(shù)的先序遍歷序列、中序遍歷和后序遍歷序列，分別構(gòu)造出二叉樹(shù)。 1 先序遍歷序列： EBADCFHGIKJ 中序遍歷系列： ABCDEFGHIJK 2 中序遍歷序列： ACBGEDF 后序遍歷序列： ABCDEFG 3 度為1的結(jié)點(diǎn)的數(shù)目為2，請(qǐng)求出該樹(shù)中的葉子結(jié)點(diǎn)的數(shù)目。二、判斷題 1.二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都是2。（ ）2.由二叉樹(shù)結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵二叉樹(shù)。（ ）3.一棵哈夫曼樹(shù)中不存在度為1的結(jié)點(diǎn)。（ ）4.平衡二叉排序樹(shù)上任何一個(gè)結(jié)點(diǎn)的左、右子樹(shù)的高度之差的絕對(duì)值不大于2（ ）6. 三、填空題 3.若結(jié)點(diǎn)A有三個(gè)兄弟(包括A本身),并且B是A的雙親結(jié)點(diǎn),B的度是_4.若一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)采用標(biāo)準(zhǔn)鏈接存儲(chǔ)結(jié)構(gòu),那么該二叉樹(shù)所有結(jié)點(diǎn)共有_個(gè)空指針域。5.已知二叉樹(shù)的前序序列為ABDEGCFHIJ,中序序列為DBGEAHFIJC,寫(xiě)出后序序列_。6.已知二叉樹(shù)的后序序列為FGDBHECA,中序序列為BFDGAEHC ,并寫(xiě)出前序序列_。7.找出滿(mǎn)足下列條件的二叉樹(shù)1）先序和中序遍歷，得到的結(jié)點(diǎn)訪(fǎng)問(wèn)順序一樣。_2）后序和中序遍歷，得到的結(jié)點(diǎn)訪(fǎng)問(wèn)順序一樣。_3）先序和后序遍歷，得到的結(jié)點(diǎn)訪(fǎng)問(wèn)順序一樣。_9.一棵二叉樹(shù)有67個(gè)結(jié)點(diǎn)，這些結(jié)點(diǎn)的度要么是0，要么是2。這棵二叉樹(shù)中度為2的結(jié)點(diǎn)有_個(gè)。10.含有100個(gè)結(jié)點(diǎn)的樹(shù)有_條邊。四、問(wèn)答題 4.有七個(gè)帶權(quán)結(jié)點(diǎn),其權(quán)值分別為3,7,8,2,6,10,14,試以它們?yōu)槿~結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)(請(qǐng)按照每個(gè)結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)造,并計(jì)算出帶權(quán)路徑長(zhǎng)度WPL及該樹(shù)的結(jié)點(diǎn)總數(shù)。5.有一電文共使用五種字符a,b,c,d,e,其出現(xiàn)頻率依次為4,7,5,2,9。(1)試畫(huà)出對(duì)應(yīng)的編碼哈夫曼樹(shù)(要求左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán))。(2)求出每個(gè)字符的晗夫曼編碼。(3)求出傳送電文的總長(zhǎng)度。(4)并譯出編碼系列1100011100010101的相應(yīng)電文。第七章 圖 一、判斷題 1.一個(gè)無(wú)向圖的鄰接矩陣中各非零元素之和與圖中邊的條數(shù)相等。（ ） 2.一個(gè)有向圖的鄰接矩陣中各非零元素之和與圖中邊的條數(shù)相等。（ ） 3.一個(gè)對(duì)稱(chēng)矩陣一定對(duì)應(yīng)著一個(gè)無(wú)向圖。（ ） 4.一個(gè)有向圖的鄰接矩陣一定是一個(gè)非對(duì)稱(chēng)矩陣。（ ） 二、選擇題 1.在一個(gè)無(wú)向圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（ ）倍。 （A）1/2（B）1（C）2（D）42.在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ ）倍。 （A）1/2（B）1（C）2（D）43.一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有（ ）條邊。 （A）n （B）n(n-1)（C）n(n-1）/2（D）2n4.具有4個(gè)頂點(diǎn)的無(wú)向完全圖有（ ）條邊。 （A）6（B）12（C）16（D）205.具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有（ ）條邊才能確保是一個(gè)連通圖。 （A）5（B）6（C）7（D）86.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中,要連通全部頂點(diǎn)至少需要（ ）條邊。 （A）n （B）n+1（C）n-1（D）n/27.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖,若采用鄰接矩陣表示,則該矩陣的大小（ ） （A）n （B）(n-1) 2（C）n-1 （D）n28.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖,若采用鄰接表表示,則表頭向量的大小為（ ），所有鄰接表中的結(jié)點(diǎn)總數(shù)是（ ）。 （A）n （B）n+1（C）n-1（D）n+e（A）e/2（B）e（C）2e （D）n+e9.采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的（ ）。 （A）先序遍歷（B）中序遍歷（C）后序遍歷（D）按層遍歷 10.采用鄰接表存儲(chǔ)的圖的寬度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的（ ）。 （A）先序遍歷（B）中序遍歷（C）后序遍歷（D）按層遍歷 11.判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?還可以利用（ ）.（A）求關(guān)鍵路徑的方法（B）求最短路徑的Dijkstm方法 （C）寬度優(yōu)先遍歷算法（D）深度優(yōu)先遍歷算法 12.用Prim算法求下列連通的帶權(quán)圖的最小代價(jià)生成樹(shù)，在算法執(zhí)行的某刻，已選取的頂點(diǎn)集合U1，2，5，邊的集合TE（1，2），（2，5），要選取下一條權(quán)值最小的邊，應(yīng)當(dāng)從（ ）組中選取。 (A)（1，4），（3，4），（3，5），（2，5）(B)（5，4），（5，3），（5，6） (C)（1，2），（2，3），（3，5） (D)（3，4），（3，5），（4，5），（1，4） 三、填空題 1.n個(gè)頂點(diǎn)的連通圖至少_條邊。 2.在一個(gè)無(wú)環(huán)有向圖G中，若存在一條從頂點(diǎn)i到頂點(diǎn)j的弧，則在頂點(diǎn)的拓?fù)湫蛄兄?，頂點(diǎn)i與頂點(diǎn)j的先后次序是_。 3.在一個(gè)無(wú)向圖的鄰接表中，若表結(jié)點(diǎn)的個(gè)數(shù)是m，則圖中邊的條數(shù)是_條。 4. 如果從一個(gè)頂點(diǎn)出發(fā)又回到該頂點(diǎn)，則此路徑叫做_。 5.如果從一無(wú)向圖的任意頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪(fǎng)問(wèn)所有頂點(diǎn)，則該圖一定是_。 6.若采用鄰接表的存儲(chǔ)結(jié)構(gòu)，則圖的廣度優(yōu)先搜索類(lèi)似于二叉樹(shù)的_遍歷。 7. 一個(gè)連通圖的生成樹(shù)是該圖的_連通子圖。若這個(gè)連通圖有n個(gè)頂點(diǎn), 則它的生成樹(shù)有_條邊。 第八章 查找 一、判斷題 1.用二分查找法對(duì)一個(gè)順序表進(jìn)行查找，這個(gè)順序表可以是按各鍵值排好序的，也可以是沒(méi)有按鍵值排好序的。（ ） 3.哈希表的定義函數(shù)H（key）=key%p(p=m)這種方法是直接定址法。（ ） 2、 填空題 1.順序查找法的平均查找長(zhǎng)度為_(kāi)，二分查找法的平均查找長(zhǎng)度為_(kāi)，分塊查找法(以順序查找確定塊)的平均查找長(zhǎng)度為_(kāi)，分塊查找法(以二分查找確定塊)的平均查找長(zhǎng)度為_(kāi)。 2.在各種查找方法中,平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查法方法是_3.二分查找的存儲(chǔ)結(jié)構(gòu)僅限于_,且是_。 4.在分塊查找方法中,首先查找_,然后再查找相應(yīng)的_。 5.長(zhǎng)度為255的表,采用分塊查找法,每塊的最佳長(zhǎng)度是_。 7.假設(shè)在有序線(xiàn)性表A1.20上進(jìn)行二分查找,則比較一次查找成功的結(jié)點(diǎn)數(shù)為_(kāi),則比較二次查找成功的結(jié)點(diǎn)數(shù)為_(kāi),則比較三次查找成功的結(jié)點(diǎn)數(shù)為_(kāi),則比較四次查找成功的結(jié)點(diǎn)數(shù)為_(kāi),則比較五次查找成功的結(jié)點(diǎn)數(shù)為_(kāi),平均查找長(zhǎng)度為_(kāi)。 9.己知一個(gè)有序表為(12,18,20,25,29,32,40,62,83,90,95,98),當(dāng)二分查找值為29和90的元素時(shí),分別需要_次和_次比較才能查找成功；若采用順序查找時(shí),分別需要_次和_次比較才能查找成功。 三、選擇題 1.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（ ）的線(xiàn)性表。 （A）散列存儲(chǔ)（B）順序存儲(chǔ)或鏈接存儲(chǔ)（C）壓縮存儲(chǔ)（D）索引存儲(chǔ) 2.對(duì)線(xiàn)性表進(jìn)行二分查找時(shí),要求線(xiàn)性表必須（ ）。 （A）以順序方式存儲(chǔ)（B）以鏈接方式存儲(chǔ) （C）以順序方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序 （D）以鏈接方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序 3.采用順序查找方法查找長(zhǎng)度為n的線(xiàn)性表時(shí),每個(gè)元素的平均查找長(zhǎng)度為（ ） （A）n （B）n/2（C）(n+1)/2（D）(n-1)/24.采用二分查找方法查找長(zhǎng)度為n的線(xiàn)性表時(shí),每個(gè)元素的平均查找長(zhǎng)度為（ ） （A）O(n2)（B）O(log2n)（C）O(n)（D）O(log2n-1)5.二分查找和二叉排序樹(shù)的時(shí)間性能（ ）。 （A）相同? （B）不相同? （C）無(wú)法比較 6.有一個(gè)有序表為1,3,9,12,32,41,45,62,75,77,82,95,100,當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí),（ ）次比較后查找成功。 （A）1（B）2（C）4（D）88.有一個(gè)長(zhǎng)度為12的有序表,按二分查找法對(duì)該表進(jìn)行查找,在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（? ） （A）35/12（B）37/12（C）39/12（D）43/129.采用分塊查找時(shí),若線(xiàn)性表中共有625個(gè)元素,查找每個(gè)元素的概率相同,假設(shè)采用順序查找來(lái)確定結(jié)點(diǎn)所在的塊時(shí),每塊應(yīng)分（ ）個(gè)結(jié)點(diǎn)最佳。 （A）10（B）25（C）6（D）62510.如果要求一個(gè)線(xiàn)性表既能較快地查找,又能適應(yīng)動(dòng)態(tài)變化的要求,可以采用（ ）查找方法。 （A）分塊（B）順序（C）二分（D）散列 第九章 排序 一、選擇題 1.在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄得初始排列次序無(wú)關(guān)的是（ ） （A）希爾排序 （B）起泡排序 （C）插入排序 （D）選擇排序 2.設(shè)有1000個(gè)無(wú)序的元素,希望用最快的速度挑選出其中前10個(gè)最大的元素,最好（ ）排序法。 （A）起泡排序（B）快速排序（C）堆排序（D）基數(shù)排序 3.在待排序的元素序列基本有序的前提下,效率最高的排序方法是（ ） （A）插入排序（B）選擇排序（C）快速排序（D）歸并排序 4.一組記錄的排序碼為(46,79,56,38,40,84),則利用堆排序的方法建立的初始推為（ ）。 （A）79,46,56,38,40,80 （B）84,79,56,38,40,46（C）84,79,56,46,40,38 （D）84,56,79,40,46,385.一組記錄的關(guān)鍵碼為(46,79,56,38,40,84),則利用快速排序的方法,以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ ）。 （A）38,40,46,56,79,84（B）40,38,46,79,56,84（C）40,38,46,56,79,84（D）40,38,46,84,56,796.一組記錄的排序碼為(25,48,16,35,79,82,23,40,36,72),其中含有5個(gè)長(zhǎng)度為2的有序表,按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為（ ）。 （A）16,25,35,48,23,40,79,82,36,72（B）16,25,35,48,79,82,23,36,40,72（C）16,25,48,35,79,82,23,36,40,72（D）16,25,35,48,79,23,36,40,72,827.排序方法中,從未排序序列中依次取出元素與己排序序列(初始時(shí)為空)中的元素進(jìn)行比較,將其放入己排序序列的正確位置上的方法,稱(chēng)為（ ） （A）希爾排序（B）起泡排序（C）插入排序（D）選擇排序 8.排序方法中,從未排序序列中挑選元素并將其依次放入己排序序列(初始為空)的一端的方法,稱(chēng)為（ ） （A）希爾排序（B）歸并排序（C）插入排序（D）選擇排序 9.用某種排序方法對(duì)線(xiàn)性表(25,84,21,47,15,27,68,35,20)進(jìn)行排序時(shí),元素序列的變化情況如下: (1)25,84,21,47,15,27,68,35,20 ?(2)20,15,21,25,47,27,68,35,84 (3)15,20,21,25,35,27,47,68,84 ?(4)15,20,21,25,27,35,47,68,845則所采用的排序方法是（ ）。 （A）選擇排序（B）希爾排序（C）歸并排序（D）快速排序 10.下述幾種排序方法中,平均查找長(zhǎng)度最小的是（ ） （A）插入排序（B）選擇排序（C）快速排序（D）歸并排序 11.下述幾種排序方法中,要求內(nèi)存量最大的是（ ）。 （A）插入排序（B）選擇排序（C）快速排序（D）歸并排序 12.快速排序方法在情況下最不利于發(fā)揮其長(zhǎng)處。( )（A）要排序的數(shù)據(jù)量太大? （B）要排序的數(shù)據(jù)中含有多個(gè)相同值 （C）要排序的數(shù)據(jù)已基本有序（D）要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù) 13.設(shè)有10000個(gè)元素組成的無(wú)序序列,希望盡快挑選出其中前10個(gè)最大值元素,在不改變已有算法結(jié)構(gòu)的前提下,以下幾種內(nèi)排序算法中(? ?)最合適。 (A)選擇排序法(B)快速排序法(C)堆排序法(D)冒泡排序法。 14.下列四種排序方法中，不穩(wěn)定的方法是（ ） (A)直接插入排序 (B)冒泡排序 (C)歸并排序(D)直接選擇排序 二、判斷題 1.用直接選擇排序方法分別對(duì)序列S1（1，2，3，4，5，6，7）和序列S2（7，5，3，2，4，1， 6）進(jìn)行排序，兩者的比較次數(shù)不相同。（ ） 2.快速排序是所有排序中速度最快的一種。（ ） 3.堆排序是直到最后一趟排序結(jié)束之前所有元素才能在其最終的位置上。（ ） 三、填空題 1.試五種排序方法與對(duì)應(yīng)的操作聯(lián)系起來(lái): (A)歸并排序 _(B)選擇排序 _ (C)冒泡排序 _ (D)插入排序 _(E)快速排序_ (1)從待排序序列中依次取出元素與己排序序列中的元素作比較將其放入己排序序列中的正確的位置上。 (2)從待排序序列中挑選元素,并將其放入己排序序列的一端。 (3)依次將相鄰的有序表合并成一個(gè)有序表。 (4)每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間,其中左區(qū)間中元素的鍵