注：不含主觀題第1題算法的時(shí)間復(fù)雜度取決于（）A問題的規(guī)模B待處理數(shù)據(jù)的初態(tài)C前兩個都是第2題計(jì)算機(jī)算法指的（），它必須具可讀性、健壯性、高性能這四個個特性。A計(jì)算方法B排序方法C解決問題的步驟序列D調(diào)度方法第3題從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（

）兩大類。A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C線性結(jié)構(gòu)、非線性結(jié)構(gòu)D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)第4題數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。A存儲B物理C邏輯D物理和存儲第5題算法分析的目的是（）。A找出數(shù)據(jù)結(jié)構(gòu)的合理性B分析算法的效率以求改進(jìn)C研究算法中輸入和輸出的關(guān)系D分析算法的易懂性和文檔性第6題計(jì)算機(jī)中的算法指的是解決某一個問題的有限運(yùn)算序列，它必須具備具備輸入、輸出和（）等5個特性。A可行性、可移植性和可擴(kuò)充性B易讀性、穩(wěn)定性和安全性C確定性、有窮性和穩(wěn)定性D可行性、確定性和有窮性第7題下面程序的時(shí)間復(fù)雜度為（）。for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;AO(m*n)BO(n*n)CO(m*m)DO(m+n)第8題程序段i=0;s=0;while(++i<=n){intp=1;for(j=0;j<i;j++)p*=j;s=s+p;}該程序段的時(shí)間復(fù)雜度為（）。AO(n)BO(n*logn)CO(n*n*n)DO(n*n)第9題以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)A樹B字符串C隊(duì)D棧第10題順序存儲設(shè)計(jì)時(shí)，存儲單元的地址（）。A一定連續(xù)B一定不連續(xù)C不一定連續(xù)D部分連續(xù)，部分不連續(xù)第11題數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。（）第12題數(shù)據(jù)項(xiàng)是數(shù)據(jù)處理的最小單位。（）第13題算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。（）第14題健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（）第15題算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算法實(shí)際上就是程序了。（）第16題程序一定是算法。（）第17題數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)無關(guān)。（）第18題所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個上界。（）第19題同一個算法，實(shí)現(xiàn)語言的級別越高，執(zhí)行效率就越低。（）第20題算法效率的評價(jià)用時(shí)間復(fù)雜度和空間復(fù)雜度兩個方面進(jìn)行。（）第二章測試線性表第1題線性表是具有n個（）的有限序列（n>0）。A表元素B字符C數(shù)據(jù)元素D數(shù)據(jù)項(xiàng)E信息項(xiàng)第2題若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲方式最節(jié)省時(shí)間。A順序表B雙鏈表C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D單循環(huán)鏈表第3題某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運(yùn)算時(shí)間。A單鏈表B僅有頭指針的單循環(huán)鏈表C雙鏈表D僅有尾指針的單循環(huán)鏈表第4題設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用（）最節(jié)省時(shí)間。A單鏈表B單循環(huán)鏈表C帶尾指針的單循環(huán)鏈表D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表第5題鏈表不具有的特點(diǎn)是（）A插入、刪除不需要移動元素B可隨機(jī)訪問任一元素C不必事先估計(jì)存儲空間D所需空間與線性長度成正比第6題一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（）。A110B108C100D120第7題在n個結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O（1）的操作是（）。A訪問第i個結(jié)點(diǎn)（1≤i≤n）和求第i個結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n）。B在第i個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)（1≤i≤n）C刪除第i個結(jié)點(diǎn)（1≤i≤n）D將n個結(jié)點(diǎn)從小到大排序第8題非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿足（）。Ap->next=headBp->next=NULLCp=NULLDp=head第9題鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間（）。A分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B只有一部分，存放結(jié)點(diǎn)值C只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系的指針D分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)第10題單鏈表的存儲密度（）。A大于1B等于1C小于1D不能確定第11題已知L是不帶頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試選擇合適的語句序列，完成在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列。（）AS->next=P->next;P->next=S;BP->next=S;S->next=P->next;CP->next=S;DP->next=S;第12題12已知L是不帶頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試選擇合適的語句序列，完成在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列。（）AS->next=P->next;P->next=S;BP->next=S;S->next=P->next;CQ=L;while(Q->next!=P)Q=Q->next;S->next=P;Q->next=S;DQ=L;while(Q->next!=P)Q=Q->next;Q->next=S;S->next=P;第13題下述算法的功能是什么?（）A刪除最后一個結(jié)點(diǎn)B將開始結(jié)點(diǎn)刪除，而原來的第二個結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。C將開始結(jié)點(diǎn)摘下鏈接到最后一個結(jié)點(diǎn)后面，而原來的第二個結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。D將最后結(jié)點(diǎn)摘下鏈接到放到第一個結(jié)點(diǎn)之前第14題在順序表中插入或刪除一個元素，需要平均移動（）的元素，具體移動的元素個數(shù)與表長和該元素在表中的位置有關(guān)。A表中所有B表中一半第15題雙向循環(huán)鏈表的頭指針為head，若帶頭結(jié)點(diǎn)，則表空的條件是（）。Ahead->next==NULLBhead==NULLChead->next==head或者h(yuǎn)ead->prior==head第16題對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（）第17題鏈?zhǔn)酱鎯Y(jié)構(gòu)對存儲的數(shù)據(jù)區(qū)域連續(xù)或不連續(xù)沒有要求。（）第18題線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。（）第19題線性表采用鏈接存儲，插入和刪除操作需要移動數(shù)據(jù)元素。（）第20題在循環(huán)鏈表L中，已知指針p指向某一結(jié)點(diǎn)，可以找到p的前驅(qū)。（）第21題順序存儲方式只能用于存儲線性結(jié)構(gòu)。（）第22題在長度為n的單鏈表L中查找某個數(shù)據(jù)元素必須從頭指針出發(fā)逐個查找比較，所以時(shí)間復(fù)雜度為O(n)。（）第23題鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時(shí)，任何情況下都比在順序存儲結(jié)構(gòu)中效率高。（）第24題線性表的順序存儲結(jié)構(gòu)是可以按序號隨機(jī)存取的。（）第25題集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。（）第三章測試棧與隊(duì)列第1題對于隊(duì)列操作數(shù)據(jù)的原則是（）A先進(jìn)先出B后進(jìn)先出C后進(jìn)后出D不分順序第2題表達(dá)式a*(b+c)-d的后綴表達(dá)式是（）Aabcd*+-B-+*abcdCabc*+d-Dabc+*d-第3題在設(shè)計(jì)遞歸函數(shù)時(shí)，如不用遞歸過程就應(yīng)借助于數(shù)據(jù)結(jié)構(gòu)（）A隊(duì)列B線性表C廣義表D棧第4題若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（）AiBn=iCn-i+1D不確定第5題棧和隊(duì)列的共同點(diǎn)是（）A都是后進(jìn)先出B都是先進(jìn)先出C只允許在端點(diǎn)處插入和刪除元素D沒有共同點(diǎn)第6題判定一個循環(huán)隊(duì)列Q（最多有m0個元素采用“少用一個元素空間”來判別隊(duì)空隊(duì)滿）為滿的條件是（）AQ->front==Q->rearBQ->front!==Q->rearCQ->front==!(Q->rear+1)%m0DQ->front==(Q->rear+1)%m0第7題7、一個遞歸算法必須包括（）。A遞歸部分B終止條件和遞歸部分C迭代部分D終止條件和迭代部分第8題用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)（）。A僅修改隊(duì)頭指針B僅修改隊(duì)尾指針C隊(duì)頭、隊(duì)尾指針都要修改D隊(duì)頭,隊(duì)尾指針都可能要修改第9題遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列B多維數(shù)組C棧D線性表第10題在作進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否(①),在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否(②)。當(dāng)棧中元素為n個,作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說明該棧的最大容量為(③)。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續(xù)的內(nèi)存空間時(shí),應(yīng)將兩棧的(④)分別設(shè)在這片內(nèi)存空間的兩端,這樣,當(dāng)(⑤)時(shí)，才產(chǎn)生上溢。A滿，空，n,棧底，兩個棧的棧頂在?？臻g的某一位置相遇.B空，滿，n,棧底，其中一個棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn).C滿，空，n+1,深度，兩個棧的棧頂在?？臻g的某一位置相遇.D空，滿，n/2,棧底，兩個棧均不空,且一個棧的棧頂?shù)竭_(dá)另一個棧的棧底.E上溢，空，n-1,棧底，其中一個棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn).第11題消除遞歸不一定需要使用棧，此說法對嗎？（）第12題兩個棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（）第13題有n個數(shù)順序（依次）進(jìn)棧，出棧序列有Cn種，Cn=[1/（n+1）]*（2n）!/[(n!)*(n!)]。（）第14題棧與隊(duì)列是一種特殊操作的線性表。（）第15題若輸入序列為1,2,3,4,5,6,則通過一個棧可以輸出序列3,2,5,6,4,1.（）第16題只有那種使用了局部變量的遞歸過程在轉(zhuǎn)換成非遞歸過程時(shí)才必須使用棧。（）第17題7、棧是一種插入與刪除操作在表的一端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。（）第18題隊(duì)列邏輯上是一個下端和上端既能增加又能減少的線性表。（）第19題循環(huán)隊(duì)列可以用順序結(jié)構(gòu)存儲也可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)。（）第20題棧和隊(duì)列的存儲方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞?。（）第五章測試數(shù)組與廣義表第1題下面關(guān)于串的的敘述中，哪一個是不正確的？（）A串是字符的有限序列B空串是由空格構(gòu)成的串C模式匹配是串的一種重要運(yùn)算D串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯Φ?題若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’,執(zhí)行concat(replace(S1,substr(S1,4,3),S3),substr(S4,index(S2,‘8’),length(S2)))其結(jié)果為（）AABC###G0123BABCD###2345CABC###G1234DABCD###1234第3題設(shè)有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（）A求子串B聯(lián)接C模式匹配D求串長第4題模式匹配算法是在主串中快速尋找模式的一種有效的方法，如果設(shè)主串的長度為m，模式的長度為n，樸素的模式匹配算法的時(shí)間復(fù)雜性是（）。Am+nBm*nCmDn第5題兩個字符串A和B的長度分別為m和n。求這兩個字符串最大共同子串算法的時(shí)間復(fù)雜度為T(m,n)。最優(yōu)的T(m,n)為：（）。AO（m*n）BO（m）CO（n）DO（m+n）第6題假設(shè)有60行70列的二維數(shù)組a[1…60,1…70]以列序?yàn)橹餍蝽樞虼鎯Γ浠刂窞?0000，每個元素占2個存儲單元，那么第32行第58列的元素a[32,58]的存儲地址為（）。（無第0行第0列元素）A16902B16904C14454D答案A、B、C均不對第7題設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分按行序存放在一維數(shù)組B[1,n(n-1)/2]中，對下三角部分中任一元素ai,j(i≤j),在一維數(shù)組B中下標(biāo)k的值是（）。Ai(i-1)/2+j-1Bi(i-1)/2+jCi(i+1)/2+j-1Di(i+1)/2+j第8題下面說法不正確的是（）。A廣義表的表頭總是一個廣義表B廣義表的表尾總是一個廣義表C廣義表難以用順序存儲結(jié)構(gòu)D廣義表可以是一個多層次的結(jié)構(gòu)第9題對特殊矩陣采用壓縮存儲的目的主要是為了（）。A使表達(dá)變得簡單B對矩陣元素的存取變得簡單C去掉矩陣中的多余元素D減少不必要的存儲空間第10題稀疏矩陣一般的壓縮存儲方式有兩種，即（）。A二維數(shù)組和三維數(shù)組B三元組表和散列表C散列表和十字鏈表D三元組表和十字鏈表第11題串的存儲結(jié)構(gòu)有：順序串和鏈串。（）第12題從數(shù)據(jù)結(jié)構(gòu)角度講，串屬于線性結(jié)構(gòu)。與線性表的不同在于串的數(shù)據(jù)元素是字符，同時(shí)操作對象常常是一個串。（）第13題空格是一個字符，其ASCII碼值是32?？崭翊怯煽崭窠M成的串，其長度等于空格的個數(shù)。空串是不含任何字符的串，即空串的長度是零。（）第14題數(shù)組不適合作為任何二叉樹的存儲結(jié)構(gòu)。（）第15題稀疏矩陣壓縮存儲后，必會失去隨機(jī)存取功能。（）第16題數(shù)組是同類型值的集合。（）第17題一個稀疏矩陣Am*n采用三元組形式表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運(yùn)算。（）第18題二維以上的數(shù)組其實(shí)是一種特殊的廣義表。（）第19題廣義表的取表尾運(yùn)算，其結(jié)果通常是個表，但有時(shí)也可是個單元素值。（）第20題廣義表L=（a，（b，c）），進(jìn)行Tail（L）操作后的結(jié)果為（（b，c））。（）第六章測試樹與二叉樹第1題設(shè)有一表示算術(shù)表達(dá)式的二叉樹（見下圖），它所表示的算術(shù)表達(dá)式是（）AA*B+C/(D*E)+(F-G)B(A*B+C)/(D*E)+(F-G)C(A*B+C)/(D*E+（F-G）)DA*B+C/D*E+F-G第2題在下述結(jié)論中，正確的是（）①只有一個結(jié)點(diǎn)的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換;④深度為K的完全二叉樹的結(jié)點(diǎn)個數(shù)小于或等于深度相同的滿二叉樹的結(jié)點(diǎn)個數(shù)。A①②③B②③④C②④D①④第3題設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點(diǎn)，B的根為p,p的右子樹結(jié)點(diǎn)個數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個數(shù)是（）Am-nBm-n-1Cn+1D條件不足，無法確定第4題若一棵二叉樹具有10個度為2的結(jié)點(diǎn)，5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個數(shù)是（）A9B11C15D不確定第5題設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個數(shù)分別為M1，M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個數(shù)是（）。AM1BM1+M2CM3DM2+M3第6題一棵完全二叉樹上有9個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是（）A2B5C4D3E以上答案都不對第7題設(shè)給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）A不確定B2nC2n+1D2n-1第8題二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為（）A2^IB2^(I-1)-1C2^(I-1)D2^I-1第9題對于有n個結(jié)點(diǎn)的二叉樹,其高度為（）An(log2(n))Blog2(n)Clog2n+1D不確定第10題高度為K的二叉樹最大的結(jié)點(diǎn)數(shù)為（）。A2^kB2^(k-1)C2^k-1D2^(k-1)-1第11題利用二叉鏈表存儲樹，則根結(jié)點(diǎn)的右指針是（）。A指向左孩子B指向右孩子C空D非空第12題樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的（）.A先序序列B中序序列C后序序列第13題在下列存儲形式中，哪一個不是樹的存儲形式？（）A雙親表示法B孩子鏈表表示法C孩子兄弟表示法D順序存儲表示法第14題已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（）。ACBEFDABFEDCBACCBEDFAD不定第15題由3個結(jié)點(diǎn)可以構(gòu)造出多少種不同的樹？（）A2B3C4D5第16題樹在計(jì)算機(jī)內(nèi)的表示方式有()。A順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)B多重鏈表表示法C雙親表示法、孩子表示法、孩子兄弟表示法第17題現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有（）種不同的二叉樹可以得到這一遍歷結(jié)果。A2B3C4D5第18題深度為k的完全二叉樹至少有（）個結(jié)點(diǎn)。A2^(k-1)B2^k-1C2^kD2^(k+1)第19題設(shè)有N個結(jié)點(diǎn)的完全二叉樹順序存放在向量A[1:N]中，其下標(biāo)值最大的分支結(jié)點(diǎn)為（）。ANB(N-1)/2CN-1DN/2第20題二叉樹與樹、森林之間依據(jù)（）可以互相轉(zhuǎn)換。A順序存儲結(jié)構(gòu)B孩子表示法C孩子兄弟表示法第21題二叉樹是度為2的有序樹。（）第22題完全二叉樹一定存在度為1的結(jié)點(diǎn)。（）第23題對于有N個結(jié)點(diǎn)的二叉樹，其高度為log2n。（）第24題深度為K的二叉樹中結(jié)點(diǎn)總數(shù)≤2^k-1。（）第25題對一棵二叉樹進(jìn)行層次遍歷時(shí)，應(yīng)借助于隊(duì)列實(shí)現(xiàn)。（）第26題由一棵二叉樹的前序序列和后序序列可以唯一確定它。（）第27題完全二叉樹中，若一個結(jié)點(diǎn)沒有左孩子，則它必是樹葉。（）第28題二叉樹只能用二叉鏈表表示。（）第29題一棵有n個結(jié)點(diǎn)的二叉樹，從上到下，從左到右用自然數(shù)依次給予編號，則編號為i的結(jié)點(diǎn)的左兒子的編號為2i(2i<n)，右兒子是2i+1（2i+1<n）。（）第30題給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。（）第31題二叉樹中每個結(jié)點(diǎn)至多有兩個子結(jié)點(diǎn),而對一般樹則無此限制.因此,二叉樹是樹的特殊情形。（）第32題必須把一般樹轉(zhuǎn)換成二叉樹后才能進(jìn)行存儲。（）第33題將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點(diǎn)沒有右子樹。（）第34題樹與二叉樹是兩種不同的樹型結(jié)構(gòu)。（）第35題當(dāng)一棵具有n個葉子結(jié)點(diǎn)的二叉樹的WPL值為最小時(shí)，稱其樹為Huffman樹，且其二叉樹的形狀必是唯一的。（）第36題用二叉鏈表存儲包含n個結(jié)點(diǎn)的二叉樹時(shí)，結(jié)點(diǎn)的2n個指針區(qū)域中有n+1個空指針。（）第37題二叉樹由根結(jié)點(diǎn)，左子樹，右子樹三個基本單元組成，所以，二叉樹有五種基本形態(tài)。（）第38題樹和森林都可以轉(zhuǎn)換為二叉樹，轉(zhuǎn)換而來的二叉樹均沒有右子樹。（）第39題哈夫曼樹是用來構(gòu)建哈夫曼編碼的，在哈夫曼樹中沒有度為1的結(jié)點(diǎn)。（）第40題二叉樹的前序遍歷序列和后序遍歷序列正好相反的二叉樹只有一個結(jié)點(diǎn)。（）第七章測試圖第1題設(shè)無向圖的頂點(diǎn)個數(shù)為n，則該圖最多有（）條邊。An-1Bn(n-1)/2Cn(n+1)/2D0En^2第2題在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的2倍，在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（）倍。A1/2B2C1D4第3題下列哪一種圖的鄰接矩陣是對稱矩陣？（）A有向圖B無向圖CAOV網(wǎng)DAOE網(wǎng)第4題從鄰接陣矩A（如下圖所示）可以看出，該圖共有（）個頂點(diǎn)。A2B3C6D4E以上答案均不正確第5題4題中的鄰接矩陣A，如果是有向圖，該圖共有（）條弧。A2B3C6D4E以上答案均不正確第6題4題中的鄰接矩陣A，如果是無向圖，該圖共有（）條邊。A2B3C6D4E以上答案均不正確第7題下列說法不正確的是（）A圖的遍歷是從給定的源點(diǎn)出發(fā)每一個頂點(diǎn)僅被訪問一次B遍歷的基本算法有兩種：深度遍歷和廣度遍歷C圖的深度遍歷不適用于有向圖D圖的深度遍歷是一個遞歸過程第8題無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖從a出發(fā)進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）Aa,b,e,c,d,fBa,c,f,e,b,dCa,e,b,c,f,dDa,e,d,f,c,b第9題對題8中的無向圖G=(V,E)從a出發(fā)進(jìn)行廣度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）Aa,b,e,c,d,fBa,c,f,e,b,dCa,e,b,c,f,dDa,e,d,f,c,b第10題在無向圖G的鄰接表表示中，每個頂點(diǎn)的鄰接點(diǎn)建立一個單鏈表，稱之為結(jié)點(diǎn)的鄰接表，鄰接表中所含的結(jié)點(diǎn)數(shù)等于該頂點(diǎn)的（）A度數(shù)B依附的邊數(shù)C出度D入度第11題在有向圖G的鄰接表表示中，每個頂點(diǎn)的鄰接點(diǎn)建立一個單鏈表，稱之為結(jié)點(diǎn)的鄰接表，鄰接表中所含的結(jié)點(diǎn)數(shù)等于該頂點(diǎn)的（）A度數(shù)B依附的邊數(shù)C出度D入度第12題在圖采用鄰接矩陣存儲時(shí)，Prim算法的時(shí)間復(fù)雜度為（）AO(n)BO(n+e)CO(n2)DO(n3)第13題求解Floyd算法的時(shí)間復(fù)雜度為（）AO（n）BO（n+c）CO（n*n）DO（n*n*n）第14題任何一個無向連通圖的最小生成樹（）A只有一棵B有一棵或多棵C一定有多棵D可能不存在第15題構(gòu)造連通網(wǎng)最小生成樹的兩個典型算法是（）AFloyd算法和Prim算法BPrim算法和kruskal算法CPrim算法和Dijkstra算法DDijkstra算法和Prim算法第16題樹中的結(jié)點(diǎn)和圖中的頂點(diǎn)就是指數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素（）第17題在n個結(jié)點(diǎn)的無向圖中，若邊數(shù)大于n-1,則該圖必是連通圖（）第18題有e條邊的無向圖，在鄰接表中有e個結(jié)點(diǎn)（）第19題強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)（）第20題用鄰接矩陣法存儲一個圖所需的存儲單元數(shù)目與圖的邊數(shù)有關(guān)（）第21題有向圖G的強(qiáng)連通分量是指有向圖的極大強(qiáng)連通子圖（）第22題在有向圖的鄰接矩陣表示中，第I個頂點(diǎn)入度就是第I列非零元素個數(shù)（）第23題鄰接矩陣適用于有向圖和無向圖的存儲，但不能存儲帶權(quán)的有向圖和無向圖，而只能使用鄰接表存儲形式來存儲它（）第24題為了實(shí)現(xiàn)圖的廣度優(yōu)先搜索，除了一個標(biāo)志數(shù)組標(biāo)志已訪問的圖的結(jié)點(diǎn)外，還需使用隊(duì)列存放被訪問的結(jié)點(diǎn)以實(shí)現(xiàn)遍歷（）第25題只有連通無向圖存在生成樹，不連通的圖存在生成森林（）第26題Prim（普里姆）算法適用于求邊稀疏的網(wǎng)的最小生成樹（）第27題連通圖上各邊權(quán)值均不相同，則該圖的最小生成樹是唯一的（）第28題Dijkstra算法是用來求從源點(diǎn)到其余各頂點(diǎn)的最短路徑的，該算法是按路徑長度遞增次序依次產(chǎn)生的（）第29題判斷一個有n個頂點(diǎn)的無向圖是一棵樹的條件是有n-1條邊（）第30題對于一個具有n個頂點(diǎn)e條弧的有向圖，用逆鄰接表存儲，方便獲取頂點(diǎn)的入度（）第31題可以利用圖的遍歷過程來判斷一個圖是否連通，并可得到其連通分量。如果在遍歷的過程中，不止一次調(diào)用遍歷過程，則說明該圖是一個非連通圖。調(diào)用遍歷過程的次數(shù)就是該圖連通分量的個數(shù)（）第八章測試查找算法第1題若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為()。A(n-1)/2Bn/2C(n+1)/2Dn第2題下面關(guān)于二分查找的敘述正確的是()A表必須有序，表可以順序方式存儲，也可以鏈表方式存儲B表必須有序，而且只能從小到大排列C表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型D表必須有序，且表只能以順序方式存儲第3題當(dāng)在一個有序的順序存儲表上查找一個數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度()A必定快B不一定C在大部分情況下要快D取決于表遞增還是遞減第4題當(dāng)采用分快查找時(shí)，數(shù)據(jù)的組織方式為()A數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊C數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊D數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同第5題既希望較快的查找又便于線性表動態(tài)變化的查找方法是()A順序查找B折半查找C索引順序查找D哈希法查找第6題分別以下列序列構(gòu)造二叉排序樹，與用其它三個序列所構(gòu)造的結(jié)果不同的是()A(100，80，90，60，120，110，130）B(100，120，110，130，80，60，90）C(100，60，80，90，120，110，130）D(100，80，60，90，120，130，110)第7題設(shè)有一組記錄的關(guān)鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法構(gòu)造散列表，散列函數(shù)為H（key）=keyMOD13,散列地址為1的鏈中有（）個記錄。A1B2C3D4第8題下面關(guān)于哈希(Hash，雜湊)查找的說法正確的是()A哈希函數(shù)構(gòu)造的越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小B除留余數(shù)法是所有哈希函數(shù)中最好的C不存在特別好與壞的哈希函數(shù)，要視情況而定D若需在哈希表中刪去一個元素，不管用何種方法解決沖突都只要簡單的將該元素刪去即可第9題散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以()取其值域的每個值。A最大概率B最小概率C平均概率D同等概率第10題將10個元素散列到100000個單元的哈希表中，則（）產(chǎn)生沖突。A一定會B一定不會C仍可能會第11題已知一個長度為11的順序表L，其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數(shù)最多的是（）次A3B4C5D6第12題如果按關(guān)鍵碼值遞增的順序依次將關(guān)鍵碼值插入到二叉排序樹中，則對這樣的二叉排序樹檢索時(shí)，平均比較次數(shù)為__________。A(n+1)/2Bn/2Clog2nDn第13題在哈希查找中，“比較”操作一般也是不可避免的。第14題哈希函數(shù)越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突概率小.第15題裝填因子是散列表的一個重要參數(shù)，它反映散列表的裝滿程度。第16題哈希法的平均查找長度不隨表中結(jié)點(diǎn)數(shù)目的增加而增加，而是隨負(fù)載因子的增大而增大。第17題哈希表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含任何指針。第18題若哈希表的負(fù)載因子α<1，則可避免碰撞的產(chǎn)生。第19題查找相同結(jié)點(diǎn)的效率折半查找總比順序查找高。第20題用順序表和單鏈表表示的有序表均可使用折半查找方法來提高查找速度。第21題在索引順序表中，實(shí)現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關(guān)，而且與每塊中元素個數(shù)有關(guān)。第22題順序查找法適用于存儲結(jié)構(gòu)為順序或鏈接存儲的線性表。第23題折半查找法的查找速度一定比順序查找法快。第24題就平均查找長度而言，分塊查找最小，折半查找次之，順序查找最大。第25題對大小均為n的有序表和無序表分別進(jìn)行順序查找，在等概率查找的情況下，對于查找成功，它們的平均查找長度是相同的，而對于查找失敗，它們的平均查找長度是不同的。第26題對一棵二叉排序樹按前序方法遍歷得出的結(jié)點(diǎn)序列是從小到大的序列。第27題有n個數(shù)存放在一維數(shù)組A[1..n]中，在進(jìn)行順序查找時(shí)，這n個數(shù)的排列有序或無序其平均查找長度不同。第28題N個結(jié)點(diǎn)的二叉排序樹有多種，其中樹高最小的二叉排序樹查找性能是最佳的。第29題在任意一棵非空二叉排序樹中，刪除某結(jié)點(diǎn)后又將其插入，則所得二排序叉樹與原二排序叉樹相同。第30題設(shè)關(guān)鍵字序{45,24,53，45,12,24,90}，從空樹出發(fā)依次讀入關(guān)鍵字建立二叉排序樹BT，對BT進(jìn)行查找，其平均查找長度為11/5。第31題二叉排序樹和折半查找的判定樹是一樣的。第32題平均查找長度是用來衡量查找算法的時(shí)間性能的，其定義為：為了確定記錄在查找表中的位置，需要和給定值進(jìn)行比較的關(guān)鍵字個數(shù)的期望值。第九章測試排序算法第1題下列排序算法中，其中（）是穩(wěn)定的。A堆排序，冒泡排序B快速排序，堆排序C直接選擇排序，歸并排序D歸并排序，冒泡排序第2題若需在O(nlog2n)的時(shí)間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）。A快速排序B堆排序C歸并排序D直接插入排序第3題排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是（）排序法。A插入B選擇C歸并D冒泡第4題下列排序算法中（）不能保證每趟排序至少能將一個元素放到其最終的位置上。A快速排序B希爾排序C堆排序D冒泡排序第5題一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準(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,79)第6題在下面的排序方法中，輔助空間為O（n）的是（）。A希爾排序B堆排序C選擇排序D歸并排序第7題下列排序算法中，在待排序數(shù)據(jù)已有序時(shí)，花費(fèi)時(shí)間反而最多的是（）排序。A冒泡B希爾C快速D堆第8題就平均性能而言，目前最好的內(nèi)排序方法是（）排序法。A冒泡B希爾插入C交換D快速第9題如果待排序序列中兩個數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。（）就是不穩(wěn)定的排序方法。A冒泡排序B歸并排序C希爾排序D直接插入排序第10題在下列排