【正文】 在二叉排序樹T中找出值最大的元素，返回其地址，如果空樹返回NULL。 *rchild。 for(p=T。}3．寫出以下程序的輸出結(jié)果。amp。}main(){ Printf(“%d\n”, strc(“student”, “study”))。 Struct LinkNode *lchild。 (A)3 (B)4 (C)5 (D)12．設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳，B，C，D，E，下列( )是不可能的出棧序列。 (A)0 (B)1 (C)10 (D)5007．將一個(gè)元素進(jìn)入隊(duì)列的時(shí)間復(fù)雜度是( )。( )2．先序遍歷一棵一又搜索樹所得的結(jié)點(diǎn)訪問序列不可能是鎂值遞增序列、( )3．若有一個(gè)葉子結(jié)點(diǎn)是某子樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹的先序遍歷的最后一個(gè)結(jié)點(diǎn)。( )7．進(jìn)棧操作時(shí)，必須判斷棧是否已滿。3．一個(gè)無向連通圖有6個(gè)頂點(diǎn)7條邊，則其生成樹有_____________條邊。 7．采用快速排序法進(jìn)行排序時(shí)，如果_________________，排序效率會(huì)大大降低。(4分)2．給出右圖所示二叉樹中序遍歷結(jié)果。(5分)(2)基于你給出的鄰接鏈表，求從頂點(diǎn)C出發(fā)的廣度優(yōu)先遍歷。(4分)Typedef struct { int data[100]。Leavequeue(QUEUE *Q, int *e){ if(__________________) return 0。}2．以下函數(shù)ins的功能是在順序表a中找到第一個(gè)值為x的元素，然后在該元素之前插入一個(gè)值為y的元素。(8分)typedef struct { int elem[100]。 if( ________________ ) return 0。 if(k==alength) k。 ________________ =y。 pdata300。六、編程題(共15分)1．已知二叉樹結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下，編寫算法求二叉樹的非葉子結(jié)點(diǎn)數(shù)目。}Node。 Struct LinkNode *next。 (A) n1 (B) n (C) n+1 (D)O n log n4．下列排序方法中，( )的比較次數(shù)與紀(jì)錄的初始排列狀態(tài)無關(guān)。 (A)10 (B)11 (C)19 (D)2l 8．一個(gè)100100的三角矩陣a采用行優(yōu)先壓縮存儲(chǔ)后，如果首元素a[0][0]是第—個(gè)元素，那么a[4][2]是第( )個(gè)元素。( )3．進(jìn)棧、出棧操作的時(shí)間復(fù)雜度是0(n)。( )7．對(duì)長度為100的有序線性表用折半查找時(shí)，最小比較次數(shù)為0。 3．在一個(gè)長度為n的順序表中插入一個(gè)元素，最少需要移動(dòng)__________個(gè)元素，最多需要移動(dòng)__________個(gè)元素。 7．無向圖用鄰接矩陣存儲(chǔ)，其所有元素之和表示無向圖的__________。(4分) (2)采用孩子兄弟法將該樹轉(zhuǎn)換為一棵二叉樹。(4分)4．用Prim算法(一條頂點(diǎn)一條頂點(diǎn)加入生成樹)求下圖的最小生成樹。(1)計(jì)算平均查找長度。(4分)bsort(int a[], int n){int n, i, j, tmp。 ji。} }}}2．在單鏈表(表首指針為head)的元素中找出最后一個(gè)值為e的元素，返回其指針；如果找不到，返回NULL。}Node。 ________________ 。(5分)Typedef struct LinkNode{ int data。if(i==1){printf(%d\n,treedata)。}六、編程題(共15分)1．兩個(gè)字符數(shù)組s，t中各放有一個(gè)串，編寫算法，將所有t中有而s中沒有的字符加到s中(逐個(gè)加到s的后面)。 int length。 (A)森林有4棵樹 (B)森林的最大深度為4 (c)森林的第一棵樹有4層 (D)森林有4個(gè)結(jié)點(diǎn)3．在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為( )。(A)n一1 (B)n (C)n十1 (D) n log2 n7．總共3層的完全二叉樹，其結(jié)點(diǎn)數(shù)至少有( )個(gè)。( )2．無論是線性表還是樹，每一個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)最多只有一個(gè)。( )6．任何一棵二叉樹，不可能沒有葉子結(jié)點(diǎn)。( )三、填空題(每題2分，共16分) 1．在一個(gè)長度為n的順序表中插入一個(gè)元素，平均需移動(dòng)____________個(gè)元素，時(shí)間復(fù)雜度是____________。5．一棵深度為5的二叉樹，至少有_______________個(gè)葉子結(jié)點(diǎn)。四、簡答題(共38分) 1．堆排序 (1)寫出線性表(16，4，12，25，30，6，15．11，20，2，18)調(diào)整為大頂堆(用二叉樹表示)。(5分) 4．已知左下圖是一個(gè)無向圖。(1)寫出各條邊加入生成樹的次序(用權(quán)值表示)。(4分)typedef struct LinkNode{int data。if(head==p){ head=__________________。 pf=pfnext)。}2．已知數(shù)組r有n個(gè)元素，并已經(jīng)由小到大排序。i1=0。 if(er[k])i2=k1。完成以下算法。int deln(SQ *L){／* 算法思路是，對(duì)每個(gè)元素做以下循環(huán)，如果第i個(gè)元素大于等于0，且前面有c個(gè)小于0的元素，則將它前移c個(gè)位置*／int i，c。 else if(c0) xe[i ________________]=xe[i]。例如數(shù)組{5，3，5，7，3，6}，不同的值有3個(gè)。struct LinkNode *next。 (A)串中不同字母的個(gè)數(shù) (B)串中不同字符的個(gè)數(shù) (c)串中所含字符的個(gè)數(shù)，且大于0 (D)串中所含字符的個(gè)數(shù)3．?dāng)?shù)組A[1..5，1..6]的每個(gè)元素占5個(gè)單元，將其按行優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[5，5]的地址為( )。 (A)先進(jìn)先出 (B)后進(jìn)先出 (c)只能進(jìn)行插入 (D)只能進(jìn)行刪除6．在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空鏈域的個(gè)數(shù)為( )。 (A)直接插入排序 (B)快速排序 (c)歸并排序 (D)選擇排序10．下列排序算法中，時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為0(log2n)的是( )。( ) 3．在鏈隊(duì)列中，即使不設(shè)置尾指針也能進(jìn)行人隊(duì)操作。（ ）7．用Prim算法和Kruskal算法求最小生成樹的代價(jià)不一定相同。（ ）三、填空題(每空2分，共計(jì)20分) 1．設(shè)單鏈表中指針p指著結(jié)點(diǎn)A，若要?jiǎng)h除A之后的結(jié)點(diǎn)(假設(shè)存在), 則需要修改指針的操作為_______________。 4 只有64個(gè)結(jié)點(diǎn)的完全二叉樹的深度為___________________。 8．在有序表A[1…18]中，采用折半查找法查找元素值等于A[7]的元素，所比較過的元素的下標(biāo)依次為_____________。 4．以(1，3，6，7，9，15，22)為權(quán)值，構(gòu)造一棵Huffman樹，并求出其WPL。(每空2分)int BinSearch(SqList R, KeyType K){／* 參數(shù)R為線性表，元素從0到n，R具有字段key為關(guān)鍵碼，參數(shù)K為待查關(guān)鍵碼 *／int i=0, j=n。if(R[m].keyk________________。在空格處填上合適的語句或表達(dá)式完成該算法。amp。 /* 添加到C中 */ i++。(3分)void p(int w)。 /* 再次遞歸調(diào)用 */ } }____________________________________________________六、編程題(共15分) 1．編寫函數(shù)用于實(shí)現(xiàn)將一棵二叉樹中所有子樹左、右交換。struct node *right } *BTree。struct node *next } *LinkList。鏈表類型定義如下。(6分)typedef struct node{Datatype Data。 p(w1)。 }}/* while */=k。if(________________) j++。C{ int i=1,j=1,k=0。 ／* 將查找區(qū)間定為右半邊 *／}__________________。while(ij){ m=(i+j)/2。6．對(duì)下面數(shù)據(jù)表，寫出采用快速排序法的前兩層遞歸調(diào)用結(jié)果。四、簡答題(每小題5分，共30分)1．己知一棵樹的雙親表示存儲(chǔ)映像圖如下所示，試畫出該樹的邏輯示意圖2．己知一帶權(quán)有向圖的鄰接矩陣表示如下，試畫出其邏輯圖。 6．右圖中v3的入度和出度分別為__________________。 3．字符串S1＝39。( )9．對(duì)相同關(guān)鍵碼集合，以不同次序插入初始為空的樹中，一定得到不同的二叉排序樹。( )5．對(duì)稱矩陣的存儲(chǔ)只需要存儲(chǔ)一半的數(shù)據(jù)元素。正確的打√，錯(cuò)誤的打x) 1．線性表的惟一存儲(chǔ)形式就是鏈表。 (A)空或只有一個(gè)結(jié)點(diǎn) (B)高度等于其結(jié)點(diǎn)數(shù) (c)任一結(jié)點(diǎn)無左孩子 (D)任一結(jié)點(diǎn)無右孩子8．在具有n個(gè)結(jié)點(diǎn)且為完全二叉樹的二叉排序樹中查找一個(gè)關(guān)鍵碼，其平均比較次數(shù)的數(shù)量級(jí)為( )。為這兩個(gè)棧分配空間的最佳方案是( )。模擬試題10一、選擇題(每小題1分，共10分)1．若線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)元素的值，則采用( )存儲(chǔ)方式最節(jié)省時(shí)間。(8分)2．已知單鏈表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下，編寫算法，刪除單鏈表的表首結(jié)點(diǎn)與表尾結(jié)點(diǎn)。return c。 iLlength。 int length。}return 1。while(i1=i2){ k=(i1+i2)/2。完成下面程序。 free(p)。}else{ for(pf=head。}Node。(4分)五、程序填空題(共15分)1．已知單鏈表的表首指針為head，下面的函數(shù)delete是從單鏈表中刪除指針為p的結(jié)點(diǎn)，并返回新的表首指針。(5分) (2)基于你給出的鄰接矩陣，求從頂點(diǎn)A出發(fā)的深度優(yōu)先遍歷。(5分) 2．給出右圖所示樹的先序遍歷的結(jié)果。7．衡量一個(gè)算法的優(yōu)劣主要看它的______________效率和_______________效率。3．具有26個(gè)結(jié)點(diǎn)的完全二叉樹的深度為____________。（ ）。（ ）4．直接插入排序時(shí)，關(guān)鍵碼的比較次數(shù)與記錄的初始排列無關(guān)。〔A)O(n) (B)O(n2) (C)O(log2n) (D)0(n3log2n)二、判斷題(每題1分，共8分。(A)插入排序 (B)冒泡排序 (c)快速排序 (D)歸并排序5．設(shè)一數(shù)列的順序?yàn)?，2，3，4，5，通過棧結(jié)構(gòu)不可能排成的順序數(shù)列為( )。模擬試題9一、選擇題(每小題1分，共8分)1．設(shè)有一個(gè)10階的對(duì)稱矩陣a，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a[0][0]的存儲(chǔ)地址為100，每個(gè)元素占1個(gè)地址空間，則a[3][2]的地址為( )。如果順序表中的元素少于10個(gè)，則刪完為止。}outi( ______________ )。}Node。return q。q= ________________ 。(6分)Typedef struct LinkNode{ int data。a[j]=a[j+1]。 i1。(4分)五、程序填空題(共15分)1．以下是采用冒泡排序法對(duì)數(shù)組a進(jìn)行排序。(4分)(2)畫出最終的最小生成樹。(1)畫出該有向圖的鄰接鏈表。四、簡答題(共38分)1．寫出線性表(26，4，12，25，30，6，15，20．16，2，18)采用二路歸并排序算法排序后，第一趟和第二趟結(jié)束時(shí)的結(jié)果。 5．如果指針p指向一棵二叉樹的一個(gè)結(jié)點(diǎn)，則判斷p沒有左孩子的邏輯表達(dá)式為____________。( )三、填空題(每題2分，共15分)1．?dāng)?shù)據(jù)結(jié)構(gòu)有__________和__________等兩種物理結(jié)構(gòu)。( )5．一個(gè)有序的單鏈表不能采用折半查找法進(jìn)行查找。正確的打√，錯(cuò)誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個(gè)元素都最多只有一個(gè)直接前驅(qū)，則必為線性表。 (A)5 (B)6 (C)7 (D)96．已知某算法的執(zhí)行時(shí)間為(n+n2)/2+log2 (n+2)，n 為問題規(guī)模，則該算法的時(shí)間復(fù)雜度是( )。模擬試題8一、選擇題(每小題1分，共8分)1．設(shè)一數(shù)列的順序?yàn)?，2，3，4，5，通過棧結(jié)構(gòu)不可能排成的順序數(shù)列為( ) (A)3，2，5，4，1 (B)1，5，4，2，3 (C)2，4，3，5，1 (D)4，5，3，2，12．二叉樹的第3層最少