大數(shù)據(jù)結(jié)構(gòu)常見題型整合

1、標(biāo)準(zhǔn)實(shí)用文案1、設(shè)棧的輸入序列是A. 1，2，4，3，B. 2，1，3, 4，C. 1 , 4 , 3, 2, D. 4 , 3 , 1 , 2,數(shù)據(jù)結(jié)構(gòu)常見題型整合1, 2 , 3 , 4,則（）不可能是其出棧序列。文檔2、在一個(gè)鏈隊(duì)列中，若f, r分別為隊(duì)首、隊(duì)尾指針，則插入 s所指結(jié)點(diǎn)的操作為（(A) f-next=c ； f=s(B) r-next=s ； r=s(C) s-next=r ； r=s(D) s-next=f ； f=s3、順序存儲(chǔ)的棧和隊(duì)列中已經(jīng)各有N個(gè)結(jié)點(diǎn)，要?jiǎng)h除一個(gè)結(jié)點(diǎn)分別需要移動(dòng)數(shù)據(jù)（次和（）次。A. N/2 , NB. N , N/2C. 0 , ND. N ,

2、 04、設(shè)有三個(gè)元素X,Y,Z順序進(jìn)棧（進(jìn)的過程中允許出棧），下列得不到的出棧排列是）。B. YZXC. ZXYD. ZYX5、一個(gè)遞歸算法必須包括（）。A. 遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分6、如下四個(gè)選項(xiàng)中，那個(gè)選項(xiàng)是能夠正確判斷循環(huán)隊(duì)列是否排滿元素的操作（其中MAXQSIZE表示隊(duì)列的容量）（）：A. if （Q.rear = Q.front）B. if （Q.rear = （Q.front + MAXQSIZE）C. if (Q.rear = (Q.front + 1) % MAXQSIZE)D. if (Q.front = (Q.rear + 1) %

3、 MAXQSIZE)7、假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素，其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（）。A. （rear-front+m）%mB. rear-front+1C. （front-rear+m）%mD . （rear-front）%m8、若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear和front的值分別為0和3，當(dāng) 從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？（）A. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 19、禾U用棧進(jìn)行十進(jìn)制數(shù)1348轉(zhuǎn)換成八進(jìn)制數(shù)，則入棧的數(shù)依次是（）。A. 1 , 3,4,8B

4、. 8,4,3 , 1C. 2,5,0,4D. 4,0,5,210、最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear ,隊(duì)頭是front ,則隊(duì)空的條件是B. rear=fr ontD. (rear-l) MOD n=frontA. (rear+1) MOD n=fro ntC. rear+1=front11、棧和隊(duì)列的共同點(diǎn)是（）A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共冋點(diǎn)1、棧是一操作受限（或限定僅在表尾進(jìn)行插入和刪除操作）的線性表，其運(yùn)算遵循后進(jìn)先出勺原則。2、隊(duì)列的插入操作在_隊(duì)尾_進(jìn)行，刪除操作在隊(duì)頭行，其特點(diǎn)是 先進(jìn)先出.3、 用S表示入棧操作，X表示出

5、棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的 S和X的操作串為SXSSXS XX4、 表達(dá)式求值是棧應(yīng)用的一個(gè)典型例子。5、 棧和隊(duì)列在本質(zhì)上都是同一種基本數(shù)據(jù)結(jié)構(gòu)的特例，這種基本的數(shù)據(jù)結(jié)構(gòu)就是 線性表6、 在作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否滿，在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否空。當(dāng)棧中元素為n個(gè)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明該棧的最大容量為n 。12、在二叉樹的第I層（I 1）上最多含有結(jié)點(diǎn)數(shù)為（）A. 2 1B. 2 1-1 -1C. 21-1D. 2 1 -113、深度為6的二叉樹最多有（）個(gè)結(jié)點(diǎn)A. 64B.63C.32D.3114、一棵樹高為K的完全二叉樹至少有（）個(gè)

6、結(jié)點(diǎn)A.2k -B.2k-1-C.2 k-1D.215、有關(guān)二叉樹下列說法正確的是（A.二叉樹的度為2C.二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為）B. 一棵二叉樹的度可以小于22 D.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為16、n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為（A. 2nB. n IC. n + l)D. n17、線性表和樹的結(jié)構(gòu)區(qū)別在于（）A 前驅(qū)數(shù)量不同，后繼數(shù)量相同C 前驅(qū)和后繼的數(shù)量都相同B.前驅(qū)數(shù)量相同，后繼數(shù)量不同D .前驅(qū)和后繼的數(shù)量都不同18、已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E ，后綴形式為 ABC*+DE/-，則其前綴形式為（）A. -A+B*C/DEB. -A+B*CD/EC.

7、 -+*ABC/DED. -+A*BC/DE19、設(shè)有一表示算術(shù)表達(dá)式的二叉樹（見下圖）它所表示的算術(shù)表達(dá)式是()A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G)C. (A*B+C)/(D*E+(F-G ) ) D. A*B+C/D*E+F-G20、一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度（深度）（符號(hào)x表示取不大于x的最大整A. log 2 nB. log2 n 1 C. log2(n 1)D. log 2 n 121、利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是（）。A .指向最左孩子B.指向最右孩子C.空D .非空22、已知一棵二叉樹的前序遍歷結(jié)果為ABCDE

8、F，中序遍歷結(jié)果為 CBAEDF，則后序遍歷的結(jié)果為（ ）。A . CBEFDAB. FEDCBAC. CBEDFAD .不定23、若前序遍歷二叉樹的結(jié)果為序列A、B、C,則有 不同的二叉樹可以得到這一結(jié)果。A. 3B. 4C. 5D. 624、線索二叉樹是一種（）結(jié)構(gòu)。A .邏輯B .邏輯和存儲(chǔ)C .物理D .線性二、填空題7、 對(duì)于任意一棵二叉樹，如果其葉子結(jié)點(diǎn)數(shù)為NO ,度為1的結(jié)點(diǎn)數(shù)為N1，度為2的結(jié)點(diǎn)數(shù)為 N2，貝y N0=_ N2 + 1。8、 具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為9。9、 一個(gè)深度為4的二叉樹，其結(jié)點(diǎn)至少有4 個(gè)，至多有 15 個(gè)：10、 深度為H的完全二叉樹至少

9、有2H-1個(gè)結(jié)點(diǎn)：至多有 2h-1個(gè)結(jié)點(diǎn);H和結(jié)點(diǎn)總數(shù) N之間的關(guān)系是 H= log 2N +1 。11、若用鏈表存儲(chǔ)一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，N個(gè)結(jié)點(diǎn)的二叉樹共有2N 個(gè)指針域，其中 有_N-1_個(gè)指針域是存放了地址，有N+1.個(gè)指針是空指針。12、 設(shè)一棵赫夫曼樹有6個(gè)葉子結(jié)點(diǎn)，權(quán)值分別為3、4、7、14、15、20 ,則根結(jié)點(diǎn)的權(quán)值是_6313、 對(duì)一棵完全二叉樹，設(shè)一個(gè)結(jié)點(diǎn)的編號(hào)為i,若它的左孩子結(jié)點(diǎn)存在，則其編號(hào)為2i若右孩子結(jié)點(diǎn)存在，則其編號(hào)為2i+1;而雙親結(jié)點(diǎn)的編號(hào)為_ i / 2 。14、 赫夫曼樹是帶權(quán)路徑長(zhǎng)度最小

10、的二叉樹，又稱最優(yōu)二叉樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。15、下面程序段的功能是建立二叉樹的算法，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。typedef struct node int data;struct node *lchild; _struct node *rchild BiTNode, *BiTree;void createBitree(BiTree &T)scanf( “ %c” , &ch);if(ch=#) T=NULL else T=( BiTNode *)malloc(sizeof(BiTNode);T-data=ch;createBitree(T-lchild)createBitre

11、e(T-rchild);16、二叉樹由_根結(jié)點(diǎn),_左子樹_, _右子樹 三個(gè)基本單元組成。17、 樹的鏈表存儲(chǔ)結(jié)構(gòu)常用的有三種，其中，雙親 表示法一一以一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn)，在每個(gè)結(jié)點(diǎn)中設(shè)一個(gè)指示器指示雙親結(jié)點(diǎn)的位置。孩子 表示法一一每個(gè)結(jié)點(diǎn)的孩子以單鏈表的形式存儲(chǔ)，n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表，n個(gè)頭指針又組成一個(gè)線性表，并以順 序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。孩子兄弟表示法一一以二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，鏈表中的結(jié)點(diǎn)的兩個(gè)指針分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。/P135-13618、利用樹的孩子兄弟表示法存儲(chǔ)，可以將一棵樹轉(zhuǎn)換為二叉樹19、在二叉樹中，指針 p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_ p-

12、lchild=NULL &p-rchlid=NULL。20、樹的孩子兄弟表示法和二叉樹的二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹的特殊情況）可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。21、樹和二叉樹邏輯上都是樹形結(jié)構(gòu)，但是二叉樹不是樹的特例，二叉樹與樹是兩個(gè)不同的概念。二叉樹的度_至多為2，樹無此限制；二叉樹有左右子樹之分，即使在只有一個(gè)分 枝的情況下， 也必須指出是 左子樹還是右子樹，樹無此限制。三、簡(jiǎn)答題1、已知一棵二叉樹的前序遍歷的結(jié)果是ABKCDFGHIJ，中序遍歷的結(jié)果是 KBCDAFHIGJ,試畫出這棵二叉

13、樹，并寫出后序遍歷結(jié)果。答案：當(dāng)前序序列為 ABKCDFGHIJ，中序序列為KBCDAFHIGJ時(shí)，逐步形成二叉樹的過程如下圖 所示：這棵二叉樹的后序遍歷結(jié)果是：KDCB I H J G FA2、某通信電文由A、B、C、D、E、F六個(gè)字符組成，它們?cè)陔娢闹谐霈F(xiàn)的次數(shù)（權(quán)值）分別是16，5，7, 3，8，1。試畫出其哈夫曼樹，確定其對(duì)應(yīng)的哈夫曼編碼，并計(jì)算其帶權(quán)路徑長(zhǎng)度。為使結(jié)果唯一，請(qǐng)將權(quán)值較小的結(jié)點(diǎn)作為其雙親的左孩子，而將權(quán)值較大的結(jié)點(diǎn)作為其雙親的右孩子。答案：哈夫曼樹如下：對(duì)應(yīng)的哈夫曼編碼如下:A: 0B: 101C: 110D:1001E: 111F: 1000帶權(quán)路徑長(zhǎng)度為：WPL=(

14、1+3)*4+(5+7+8)*3+16* 仁92加上中序線索。答案:ABDEHCFGDHEBAFCGHEDBFGCA3、對(duì)下圖所示二叉樹分別按前序、中序、后序遍歷，給出相應(yīng)的結(jié)點(diǎn)序列，同時(shí)給二叉樹(1 )前序序列:(2) 中序序列:(3) 后序序列:(4 )中序線索見圖中虛線箭頭所示。25、以下數(shù)據(jù)結(jié)構(gòu)中，哪種具有非線性結(jié)構(gòu)？D 十字鏈表A .棧B.隊(duì)列C .雙向鏈表26、下面關(guān)于圖的存儲(chǔ)的敘述中正確的是（）。A. 用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)。B. 用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān)。C. 用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空

15、間大小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān)。D. 用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)27、 在圖的鄰接表存儲(chǔ)結(jié)構(gòu)上執(zhí)行深度優(yōu)先搜索遍歷類似于二叉樹上的（）A.先根遍歷B中根遍歷C后根遍歷D.按層次遍歷28、 圖的廣度優(yōu)先遍歷算法類似于樹的（）。A.中根遍歷B.先根遍歷C.后根遍歷D.按層次遍歷29、 設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有（）條邊。A . n-1B. n（n-1）/2C.n（n+1）/2D . 030、 設(shè)有n個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（）條邊才能確保是一個(gè)連通圖。A. n-1B. nC. n+1D . nlogn ;31、一個(gè)含有n個(gè)頂點(diǎn)的非連通圖

16、，則（）:A .它的邊一定不大于n-132、要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（B.它的邊一定不大于 nD .它的邊一定大于 0）條邊。C .它的邊一定小于n-1D. 2nC. n+l33、 下列說法不正確的是()。A .圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問一次B .遍歷的基本算法有兩種：深度遍歷和廣度遍歷C .圖的深度遍歷不適用于有向圖D .圖的深度遍歷是一個(gè)遞歸過程34、無向圖 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)，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是()。A. a,b,

17、e,c,d,f B. a,c,f,e,b,dC. a,e,b,c,f,dD . a,e,d,f,c,b35、 若一個(gè)連通圖有n個(gè)頂點(diǎn)，則它的生成樹有()條邊。A. nB. n-1C. n+1D. n(n-1)/2二、填空題22、鄰接多重表適于表示稀疏無向圖，鄰接表、逆鄰接表和十字鏈表適于表示稀疏有向圖。23、設(shè)有向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有n(n-1)條弧。24、右圖中頂點(diǎn) D的出度是 325、8層完全二叉樹至少有_ 128（第七層滿，加第八層1個(gè) ）_個(gè)結(jié)點(diǎn)，擁有100個(gè)結(jié)點(diǎn)的 完全二叉樹的最大層數(shù)為 _7_。26、 求圖的最小生成樹有兩種算法： _普里姆（Prim ）算法和克魯斯卡爾

18、（Kruskal ）算法. 其中，克魯斯卡爾算法適合于求邊稀疏的稀疏圖的最小生成樹。普里姆算法適用于求邊稠密的網(wǎng)的最小生成樹。27、對(duì)于含n個(gè)頂點(diǎn)e條邊的無向連通圖，利用普里姆算法生成最小代價(jià)生成樹其時(shí)間復(fù)雜度為 0（n 2），利用克魯斯卡爾算法生成最小代價(jià)生成樹其時(shí)間復(fù)雜度為O（eloge） _.28、 在無向圖的 深度優(yōu)先遍歷算法 中，DFS (從某個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖的算法)被 調(diào)用了幾次就說明該圖有幾個(gè)聯(lián)通分量。29、 一個(gè)有n個(gè)結(jié)點(diǎn)的圖，最少有 1個(gè)連通分量，最多有 n 個(gè)連通分量。30、 判斷一個(gè)無向圖是一棵樹的條件是_有n個(gè)頂點(diǎn)，n-1條邊的無向連通圖。31、有向圖G的強(qiáng)連通

19、分量是指 有向圖的極大強(qiáng)連通子圖_。32、 右圖中的強(qiáng)連通分量的個(gè)數(shù)為3 個(gè)。33、 一個(gè)連通圖的生成樹_是一個(gè)極小連通子圖。34、 若用n表示圖中頂點(diǎn)數(shù)目，則有 _n(n-1)/2 _ 邊的無向圖成為完全圖。35、 已知一無向圖 G= ( V，E),其中 V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e) 現(xiàn)用某 一種圖遍歷方法從頂點(diǎn) a開始遍歷圖，得到的序列為 abecd，則采用的是 深度優(yōu)先 遍歷 方法。36、為實(shí)現(xiàn)圖的廣度優(yōu)先搜索，除了一個(gè)標(biāo)志數(shù)組標(biāo)志已訪問的圖的結(jié)點(diǎn)外，還需隊(duì)列存放被訪問的結(jié)點(diǎn)以實(shí)現(xiàn)遍歷。37、設(shè)無向圖G有n個(gè)頂點(diǎn)，m條邊。閱讀下面

20、用鄰接表存儲(chǔ)該圖的算法。(設(shè)頂點(diǎn)值用1n或0n-1編號(hào))，并在畫線處完成填空。void CreatGraph (AdjList g)/ 建立有n個(gè)頂點(diǎn)和 m 條邊的無向圖的鄰接表存儲(chǔ)結(jié)構(gòu)int n,m;sca nf(%d%d，&n,&m);for (i =1,i=n;i+)_/輸入頂點(diǎn)信息，建立頂點(diǎn)向量sca nf(&gi.vertex);gi.firstarc=n ull;for (k=1;kadjvex=j; p_n ext=gi.firstarc; gi.firstarc=p;/將邊結(jié)點(diǎn)鏈入p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=i; p

21、_n ext=gj.firstarc;gj.frstarc=p;三、簡(jiǎn)答題4、已知一個(gè)無向網(wǎng)的頂點(diǎn)集為a,b,c,d,e,其鄰接矩陣如下所示1 4abcde122 34365(1) 畫出該無向網(wǎng)圖形；寫出相應(yīng)的遍歷序列。(2) 根據(jù)鄰接矩陣從頂點(diǎn) a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷,答案:(1)該無向網(wǎng)圖形如下:深度優(yōu)先序列為：a b c d e ; 廣度優(yōu)先序列為：a b d c e36、適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（）A 鏈接方式存儲(chǔ)，元素?zé)o序B 鏈接方式存儲(chǔ)，元素有序C 順序方式存儲(chǔ)，元素?zé)o序D 順序方式存儲(chǔ)，元素有序37、對(duì)有18個(gè)元素的有序表 A作折半查找，則查找

22、A3的比較序列的下標(biāo)為（）A.1 , 2, 3B.9 , 5 , 2 , 3C.9 , 5 , 3D.9 , 4 , 2 , 3R3的關(guān)鍵字等于給定值，查38、對(duì)有14個(gè)數(shù)據(jù)元素的有序表 R進(jìn)行折半搜索，搜索到找過程中兀素比較的順序依次為（）。A. R6, R2 ,R4, R3B. R6, R4 ,R2, R3C. R0, R1 ,R2, R3D. R0, R13 ,R2, R339、對(duì)N個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長(zhǎng)度為（）A . （ N+1 ） /2B. N/2C. ND. （1+N ） *N /240、有一個(gè)長(zhǎng)度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，

23、在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（）。A. 35/12B.37/12C.39/12D.43/1241、當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度（）A 必定快B.不一定 C.在大部分情況下要快D.取決于表遞增還是遞減42、 設(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)（）次比較后查找成功。A.2 B. 3 C. 4D.1243、 在查找過程中，只完成查找操作，這種查找稱為（）A

24、.靜態(tài)查找B.動(dòng)態(tài)查找C.內(nèi)部查找D.外部查找44、 分別以下列序列 構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(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）二、填空題38、 對(duì)大小均為n的有序表和無序表分別進(jìn)行順序查找，在等概率查找的情況下，對(duì)于查找失敗，它們的平均查找長(zhǎng)度是_不同的，對(duì)于查找成功

25、，他們的平均查找長(zhǎng)度是 相同的。39、 執(zhí)行順序查找時(shí)，儲(chǔ)存方式可以是順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，二分法查找時(shí)，要求線性表丿順序存儲(chǔ)且有序 _。40、在數(shù)據(jù)結(jié)構(gòu)中一般采用 平均查找長(zhǎng)度 衡量查找算法時(shí)間性能，而對(duì)于排序算法一班通 過統(tǒng)計(jì)記錄的 比較次數(shù)和移動(dòng)次數(shù)衡量排序算法的時(shí)間性能。41、 設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較_7_ 次就可以斷定數(shù)據(jù)元素X是否在查找表中42、 二叉查找樹的查找效率與二叉樹的樹型有關(guān)，在呈單枝樹時(shí)其查找效率最低。43、若表中元素個(gè)數(shù)為n，則順序查找該表中的元素，若查找成功，則比較關(guān)鍵字的次數(shù)最多為_次，平均比較次數(shù)為(n+1)/

26、2;若進(jìn)行折半查找，則最大比較次數(shù)是_ log 歲+i 。44、 給定一個(gè)主關(guān)鍵字， 在長(zhǎng)為n的有序表中進(jìn)行折半查找，則最多經(jīng)過logzn +1次比較即可確定該關(guān)鍵字是否在表中，至少經(jīng)過1次比較即可確定該關(guān)鍵字在表中。)中，用二分(折半)法查找關(guān)鍵碼值45、在順序表(8,11,15,19,25,26,30,33,42,48,5020，需做的關(guān)鍵碼比較次數(shù)為_4_。46、在有序表A1.12中，采用二分查找算法查等于A12的元素，所比較的元素下標(biāo)依次為 _6,9,11,12。47、己知有序表為(12,18,24,35,47,50,62,83,90,115，134)當(dāng)用二分法查找 90 時(shí)，需2 查

27、找成功，47時(shí)4 功，查100時(shí)，需3 才能確定不成 功。48、 假定查找有序表A1.12中每個(gè)元素的概率相等，則進(jìn)行二分查找時(shí)的平均查找長(zhǎng)度為37/12。49、 在查找中，能夠唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字稱之為主關(guān)鍵字，能夠標(biāo)識(shí)若干記錄的關(guān)鍵字稱之為次關(guān)鍵詞。50、 動(dòng)態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有_插入_和 _刪除運(yùn)算,而后者 不包含這兩種運(yùn)算。51、 已知二叉排序樹的左右子樹均不為空，則左子樹所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)值， 右子樹 所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值。三、簡(jiǎn)答題5、設(shè)有序表為(a, b, c, d, e, f, g, h, i, j, k, p, q)，請(qǐng)分別畫

28、出對(duì)給定值a, g和n進(jìn)行折半查找的過程?！敬鸢浮?1)查找a的過程如下(圓括號(hào)表示當(dāng)前比較的關(guān)鍵字 )，經(jīng)過三次比較，查找成功。下標(biāo)422*4+旅10+11-113*區(qū)間J第一次出較岳flP*1即3匾亦第二次出較卩b*讓)ft評(píng)hh-1P肝1a fi蹌三校比較A(a Jbcf.2a b.(2)g的查找過程如下，一次比較成功。a b c d e f (g) h i j k p q (3) n的查找過程如下，經(jīng)過四次比較，查找失敗。下時(shí)2*-4-9-1011-12*13區(qū)間口b+第二次匕匕較,b*er卵1i*第三汝詭a+-1b*C+-nh十iPjp(Pk亦第四次比較V備2hSF6、構(gòu)造有12個(gè)元

29、素的二分查找的判定樹，并求解下列問題：(1 )各元素的查找長(zhǎng)度最大是多少？(2 )查找長(zhǎng)度為1、2、3、4的元素各有多少？具體是哪些元素?(3 )查找第5個(gè)元素依次要比較哪些元素？（4 ）試求解在等概率情況下，查找成功情況下二分查找的平均查找長(zhǎng)度。【答案】12個(gè)元素的二叉判斷樹如下圖所示：（1 ）最大查找長(zhǎng)度是樹的深度4。（2 ）查找長(zhǎng)度為1的元素有1個(gè)，為第6個(gè)，查找長(zhǎng)度為 2的元素有2個(gè)，為第3個(gè)和 第9個(gè)，查找長(zhǎng)度為3的元素有4個(gè)，為第1、4、7、11個(gè)，查找長(zhǎng)度為4的元素有5個(gè)， 為第 2、5、8、10、12 個(gè)。（3 ）查找第五個(gè)元素依次比較6，3，4，5。n（4 ）根據(jù) ASLPi

30、Ci,平均查找長(zhǎng)度 ASL = （ 1+2*2+4*3+5*4）/12 = 37/12i 17、設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 ,試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹。8、已知序列40, 30, 50, 24 , 28 , 46 , 60, 10。試畫出由該輸入序列構(gòu)成的二叉排序 樹，并分別給出依次執(zhí)行下列操作后的二叉排序樹（共畫四棵樹）（1 ）插入數(shù)據(jù)42和80 ；（ 2 ）刪除數(shù)據(jù)30 ；（ 3 ）刪除數(shù)據(jù)50。答案：枱入42駐S0盾45、 n個(gè)記錄進(jìn)行直接插入排序時(shí)，記錄最小的比較次數(shù)是（）A.（ n-1）_B.0C.（ n+3）（

31、n-2）/2D.n 2/246、對(duì)n個(gè)記錄進(jìn)行希爾排序，所需要的輔助存儲(chǔ)空間為（）。A.0 （log 2n）B.O （n ） C.O （1）47、 就平均性能而言，目前最好的內(nèi)排序方法是（A.冒泡 B.希爾插入 C.交換 D.快速D.0 （ n2）排序法。）A. O(logn)B.0(n)C. 0(n*logn)D . 0(n 2)48、直接插入排序在最好情況下的時(shí)間復(fù)雜度為（49、以下算法思路分別出自什么排序算法：取當(dāng)前最小的數(shù)，插入到已經(jīng)排好序的數(shù)據(jù)末尾：（）；取當(dāng)前要排序的數(shù)，插入到已經(jīng)排好序的數(shù)據(jù)中適當(dāng)位置：（）；相鄰兩個(gè)數(shù)比較，如果大小順序顛倒就把兩者交換過來：（）。A.插入排序、選

32、擇排序、起泡排序B.選擇排序、插入排序、起泡排序C.插入排序、選擇排序、快速排序D.選擇排序、插入排序、快速排序50、設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20, 15 ,14 ,18 , 21 , 36 , 40 , 10)，則以20為基準(zhǔn) 記錄的一趟快速排序結(jié)束后的結(jié)果為()。(A) 10,15 ,14 ,18,20,36,40,21(B) 10,15 ,14 ,18 ,20,40,36 ,21(C) 10,15,14,20,18,40,36,2l(D) 15,10 ,14,18,20,36,40 ,2151、下列四種排序算法中，哪一個(gè)需要采用遞歸調(diào)用的方式實(shí)現(xiàn)A、直接插入排序B、快速排序C、冒泡

33、排序D、折半插入排序52、從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（）排序法。A.插入B.選擇C.希爾D.快速53、快速排序方法在（）情況下最不利于發(fā)揮其長(zhǎng)處。A. 要排序的數(shù)據(jù)量太大B. 要排序的數(shù)據(jù)中含有多個(gè)相同值C. 要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)D. 要排序的數(shù)據(jù)已基本有序54、對(duì)一組數(shù)據(jù)（84，47, 25，15，21 ）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為84(1)84 47 25 15 21(2)15 47 25 84 21(3)15 21 25 84 47( 4)15 21 25 47則采用的排序是（）。A.

34、選擇B.冒泡C.快速D.插入55、在希爾排序算法中，需要借助（）實(shí)現(xiàn)A、直接插入排序一 B、快速排序C、冒泡排序D、折半插入排序56、若用冒泡排序方法對(duì)序列10,14,26,29,41,52從大到小排序，需進(jìn)行（）次比較。A. 3B. 10C. 15D. 2557、在下列排序算法中，哪一個(gè)算法的時(shí)間復(fù)雜度與初始排序無關(guān)（）。A.直接插入排序B.起泡排序C.快速排序D.選擇排序58、對(duì)下列四種排序方法，在排序中關(guān)鍵字比較次數(shù)同記錄初始排列無關(guān)的是（）。D.二分法插入進(jìn)行排序，增量分別A .直接插入B.起泡排序C.快速排序59、若采用希爾排序法對(duì)序列 12,36,21,7,2,19,6,31,49

35、,13,27,38,5 為5、3、1。那么當(dāng)增量為3時(shí)，排序結(jié)束后的序列是哪一個(gè)A. 5, 2, 19, 6, 27, 21, 7, 31,38, 12, 36, 49, 13 B. 12,6, 5, 7,2,19, 36, 21,49,13,27,38, 31 C. 7, 2, 5, 12, 6, 19, 13, 21,38, 31,27, 49, 36 D. 2, 6, 5, 7, 12, 13, 27, 21,31, 19, 36, 38, 49 、填空題52、直接插入排序、折半插入排序、起泡排序都屬于穩(wěn)定排序。希爾排序、快速排序、選53、直接插入排序用監(jiān)視哨的作用是畢，提高了查找效率。54、對(duì)有限個(gè)記錄進(jìn)行起泡排序，第 一次發(fā)生記錄交換的位置 。擇排序都屬于不穩(wěn)定排序。免去查找過程中每一步都要檢測(cè)整個(gè)表是