【正文】 二叉樹類型定義如下。(每空2分)void SqList_Intersect(SqList A, SqList B, SqList amp。9．直接選擇排序算法在最好情況下所做的交換元素的次數(shù)為________________。( ) 4．如果一個(gè)串中的所有字符均在另一個(gè)串中出現(xiàn)，則說明前者是后者的子串。}Node。(7分)typedef struct{ int elem[100]。 ________________ = pnext。(1)畫出該無向圖的鄰接矩陣。( )7．一個(gè)稀疏矩陣采用三元組法存儲(chǔ)不可能是((5,3,7),(5,4,4),(5,3,5))。}SQ。 p=pnext) if(pdata==e) ________________。for(i= ____________________ 。8．一個(gè)具有n個(gè)結(jié)點(diǎn)的線性表采用堆排序，在建堆之后還要進(jìn)行__________次堆調(diào)整。 (A)13 (B)401 (C)402 (D)403二、判斷題(每題1分，共8分。(8分)Typedef struct LinkNode{ int data。 for(k=0。 int front。4．順序存儲(chǔ)的隊(duì)列如果不采用循環(huán)方式，則會(huì)出現(xiàn)下列問題：_________________。 (A)A，B，C，D，E (B)B，C，D，E，A (C)E，A，B，C，D (D)E，D，C，B，A 3．在所有排序方法中，關(guān)鍵碼的比較次數(shù)與記錄的初始排列無關(guān)的是( (A)快速排序 (B)冒泡排序 (C)直接插入排序 (D)直接選擇排序4．設(shè)一棵二叉樹共用20個(gè)度為2的結(jié)點(diǎn)，則葉子結(jié)點(diǎn)共有( )個(gè)。(5分)int strc(char s[], char t[]){ int i。stop++。( )6．設(shè)一棵二叉樹共用50個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn))，則共有49個(gè)度為1的結(jié)點(diǎn)7．一個(gè)有序的單鏈表采用折半查找法比順序查找效率高得多。 (A) front==rear (B) (rear+1)%MAXSIZE==front (C) frontrear==1 (D) rear%MAXSIZE==front6.—個(gè)55的對(duì)稱矩陣采用壓縮存儲(chǔ)，需要存儲(chǔ)( )個(gè)元素。①試按表中元素的次序依次插入一棵初始為空的二叉排序樹，字符之間以字典順序比較大小．并畫出對(duì)應(yīng)的二叉排序樹，且求出在等概率情況下查找成功的平均查找長度。(A)4 (D)5 (L)6 (D)7二、填空題(22分，前4題每空2分，第5題每空1分)1．若要在一個(gè)單鏈表的*p結(jié)點(diǎn)之前插入一個(gè)*s結(jié)點(diǎn)時(shí)，可執(zhí)行下列操作snext=____________； pnext=s；t=pdata；pdata=____________；sdata=____________。 pnextprior=s。i++)for(j=0。7．設(shè)一棵二叉樹共用50個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn))，則它共有__________個(gè)度為2的結(jié)點(diǎn)。( )3．在堆中執(zhí)行INSERT與DELETEMIN運(yùn)算都只需O(log2n)時(shí)間。 (A)快速排序 (B)堆排序 (c)歸并排序 (D)計(jì)數(shù)排序4．若按( )列出二叉排序樹中所存儲(chǔ)的元素，則恰好是集合中所有元素從小到大的排序。 2．線性表有順序表和鏈表兩種存儲(chǔ)結(jié)構(gòu)，簡述各自關(guān)于運(yùn)算實(shí)現(xiàn)的優(yōu)缺點(diǎn)。6．具有128個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_______________。( )5．對(duì)于n個(gè)記錄的集合進(jìn)行冒泡排序，在最壞情況下的時(shí)間復(fù)雜度是0(n2)。7．按________________遍歷二叉樹，可以得到按值遞增的關(guān)鍵碼序列，在下圖中所示的二叉樹中，檢索關(guān)鍵碼85的過程中，需與85進(jìn)行比較的關(guān)健碼序列為________________。( )10．作為解決一類特定問題的算法，不能沒有輸入運(yùn)算項(xiàng)。 (2)寫出按先序、中序、后序遍歷該二叉樹所得的結(jié)點(diǎn)序列。 (A)3 (B)4 (C)5 (D)110．線索化二叉樹中某結(jié)點(diǎn)D，沒有左孩子的主要條件是( )。 (A)D一＞Lchild＝NULL (B)D一＞1tag＝1 (C)D一＞Rchild＝NULL (D)D一＞1tag＝0二、填空題(每空2分，共22分)1．對(duì)于一個(gè)以順序?qū)崿F(xiàn)的循環(huán)隊(duì)列Q[0…m—1]，隊(duì)首、隊(duì)尾指針分別為f和r，其判空的條件是____________，判滿的條件是______________。 (3)畫出二叉樹的后序線索化樹。( )模擬試題2一、選擇題(20分)1．?dāng)?shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的( )以及它們之間的相互關(guān)系。8．下列算法實(shí)現(xiàn)二叉樹排序樹上的查找，請(qǐng)?jiān)诳崭裉幪钌线m當(dāng)?shù)恼Z句，完成上述功能。( )6．用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間與圖中結(jié)點(diǎn)的個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。7．有向圖G用鄰接矩陣A[1…m，1…m ]存儲(chǔ)，其第i行的所有元素值之和等于頂點(diǎn)vi的__________________。 3．給定有序表D＝{15，17，18，22，35，60，88，93}，用折半查找法在D中查找18，試用圖示法表示查找過程。 (A)先序 (B)中序 (C)后序 (D)按層次5．在下列4棵樹中，哪一棵是完全二叉樹( )。( )4．一棵滿二叉樹同時(shí)又是一棵平衡樹。8．高度為h(≥0)的二叉樹，至少有__________個(gè)結(jié)點(diǎn)，最多有________個(gè)結(jié)點(diǎn)。jt。 (C) pnext=s。 2．計(jì)算機(jī)軟件系統(tǒng)中有兩種處理字符串長度的方法，一種是采用_____________另一種是采用_________。②若對(duì)表中元素先排序構(gòu)成有序表，試求在等概率情況下對(duì)此有序表進(jìn)行折半查找成功的平均查找長度。 (A)5 (B)10 (C)15 (D)207．一個(gè)無向連通圖有5個(gè)頂點(diǎn)8條邊，則其生成樹將要去掉( )條邊。( )8．一個(gè)圖可以沒有邊，但不能沒有頂點(diǎn)。_______________=e。 for(i=0。 (A)40 (B)19 (C)20 (D)2l5．在具有N個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為( )。5．一個(gè)1010的三角矩陣a采用列優(yōu)先壓縮存儲(chǔ)后，如果首元素a[0][0]是第1個(gè)元素，那么a[4][2]是第______________個(gè)元素。 /* 隊(duì)首元素的下標(biāo) */ int rear。 kalength。 Struct LinkNode *lchild。正確的打√，錯(cuò)誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個(gè)元素都最多只有一個(gè)直接前驅(qū)，則必為線性表。四、簡答題(共38分)1．寫出線性表(26，4，12，25，30，6，15，20．16，2，18)采用二路歸并排序算法排序后，第一趟和第二趟結(jié)束時(shí)的結(jié)果。 i1。return q。模擬試題9一、選擇題(每小題1分，共8分)1．設(shè)有一個(gè)10階的對(duì)稱矩陣a，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a[0][0]的存儲(chǔ)地址為100，每個(gè)元素占1個(gè)地址空間，則a[3][2]的地址為( )。（ ）。(5分) (2)基于你給出的鄰接矩陣，求從頂點(diǎn)A出發(fā)的深度優(yōu)先遍歷。 free(p)。 int length。模擬試題10一、選擇題(每小題1分，共10分)1．若線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)元素的值，則采用( )存儲(chǔ)方式最節(jié)省時(shí)間。( )5．對(duì)稱矩陣的存儲(chǔ)只需要存儲(chǔ)一半的數(shù)據(jù)元素。四、簡答題(每小題5分，共30分)1．己知一棵樹的雙親表示存儲(chǔ)映像圖如下所示，試畫出該樹的邏輯示意圖2．己知一帶權(quán)有向圖的鄰接矩陣表示如下，試畫出其邏輯圖。C{ int i=1,j=1,k=0。(6分)typedef struct node{Datatype Data。 /* 再次遞歸調(diào)用 */ } }____________________________________________________六、編程題(共15分) 1．編寫函數(shù)用于實(shí)現(xiàn)將一棵二叉樹中所有子樹左、右交換。在空格處填上合適的語句或表達(dá)式完成該算法。 8．在有序表A[1…18]中，采用折半查找法查找元素值等于A[7]的元素，所比較過的元素的下標(biāo)依次為_____________。( ) 3．在鏈隊(duì)列中，即使不設(shè)置尾指針也能進(jìn)行人隊(duì)操作。struct LinkNode *next。完成以下算法。 pf=pfnext)。(5分) 4．已知左下圖是一個(gè)無向圖。( )6．任何一棵二叉樹，不可能沒有葉子結(jié)點(diǎn)。 int length。 ________________ 。(4分)bsort(int a[], int n){int n, i, j, tmp。 7．無向圖用鄰接矩陣存儲(chǔ)，其所有元素之和表示無向圖的__________。 (A)10 (B)11 (C)19 (D)2l 8．一個(gè)100100的三角矩陣a采用行優(yōu)先壓縮存儲(chǔ)后，如果首元素a[0][0]是第—個(gè)元素，那么a[4][2]是第( )個(gè)元素。六、編程題(共15分)1．已知二叉樹結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下，編寫算法求二叉樹的非葉子結(jié)點(diǎn)數(shù)目。 if( ________________ ) return 0。(4分)Typedef struct { int data[100]。3．一個(gè)無向連通圖有6個(gè)頂點(diǎn)7條邊，則其生成樹有_____________條邊。 (A)3 (B)4 (C)5 (D)12．設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳，B，C，D，E，下列( )是不可能的出棧序列。}3．寫出以下程序的輸出結(jié)果。int push(STACK *s, int e){if(__________________) return 0。( )5．在冒泡排序中，關(guān)鍵碼的比較次數(shù)與記錄的初始排列無關(guān)。(A)4 （B)5 (C)6 (D)205．在具有N個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件為( )。( )四、應(yīng)用題(20分)1．已知—個(gè)長度為12的表{Jan，F(xiàn)eb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec}。 (A)Shell排序 (c)直接插入排序15．已知8個(gè)元素(34，76，45，18，26，54，92，65)，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹，該樹的深度為( )。 pnext=s。im。6．哈希表的兩種形式是：__________和__________。( )2．二叉排序樹的左、右子樹都是二叉排序樹。 (A)2n 〔B)n (C)n/2 (D)n(n1)2．設(shè)連通圖G的頂點(diǎn)數(shù)為n，則G的生成樹的邊數(shù)為( ) (A)n (B)n一1 (C)2n (D) 2n13．下列哪種排序需要的附加存儲(chǔ)開銷最小( )。 }三、應(yīng)用題(24分) 1．已知一棵二叉樹的中序遍歷結(jié)果為DBHEAFICG，先序遍歷結(jié)果為ABDEFHCFIG，試畫出該二叉樹。5．后序序列和中序序列相同的二叉樹為_________________。( )4．若有一個(gè)葉子結(jié)點(diǎn)是某子樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹的先序遍歷的最后一個(gè)結(jié)點(diǎn)。6．設(shè)圖G的頂點(diǎn)數(shù)為n，邊數(shù)為e，第i個(gè)頂點(diǎn)的度數(shù)為D(vi)則e＝________________(即邊數(shù)與各頂點(diǎn)的度數(shù)之間的關(guān)系)。 ( )9．表中的每一個(gè)元素都有前驅(qū)和后繼元素。三、應(yīng)用題(16分) 1．設(shè)二叉樹的順序存儲(chǔ)結(jié)構(gòu)如下：(4分)1234567891011121314151617181920EAF^D^H^^C^^^GI^^^^B (1)根據(jù)其存儲(chǔ)結(jié)構(gòu)，畫出二叉樹。(A)13 (B)33 (C)18 (D)409．如果結(jié)點(diǎn)A有3個(gè)兄弟，且B為A的雙親，則B的度為( )。2．循環(huán)鏈表的主要優(yōu)點(diǎn)是__________________。 2．一棵完全二叉樹共有21個(gè)結(jié)點(diǎn)，現(xiàn)順序存放在一個(gè)矢量中，矢量的下標(biāo)正好為結(jié)點(diǎn)的序號(hào)，試問序號(hào)為12的雙親結(jié)點(diǎn)存在嗎?為什么?(4分) 3．線性表有順序表和鏈表兩種存儲(chǔ)結(jié)構(gòu)，簡述各自的優(yōu)缺點(diǎn)。 (A)理想結(jié)構(gòu)，物理結(jié)構(gòu) (B)理想結(jié)構(gòu)，抽象結(jié)構(gòu) (c)物理結(jié)構(gòu)，邏輯結(jié)構(gòu) (D)抽象結(jié)構(gòu)，邏輯結(jié)構(gòu)2．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址( )。 bitreptr * bstsearch(bitreptr *t，keytype k) { if (t==NULL)