【正文】 規(guī)模，則該算法的時間復雜度是________________。4．順序存儲的隊列如果不采用循環(huán)方式，則會出現(xiàn)下列問題：_________________。 6．如果一個有向圖有5個頂點，則最多有___________________條弧。 8．設(shè)無向圖G有100條邊，則G至少有_____________個頂點。(4分)(2)線性表采用插入排序算法排序幾越后，有序部分是(16，20，40)．無序部分是(18，25)，再下一趟排序需要移動幾個元素?寫出下一趟結(jié)束時的結(jié)果。(5分)3．已知5個結(jié)點的權(quán)值分別是4，6，1，13，7，試畫出這些結(jié)點構(gòu)成的Huffman樹。(1)畫出該無向圖的鄰接鏈表。(5分)5．(1)根據(jù)線性表(23，49，28，10，30，5，16)畫出二叉排序樹。完成以下程序。 int front。 /* 等于隊尾元素的下標加1 */}QUEUE。 *e=Qdata[Qfront]。 return 1。如果找不到值為x的元素，則新元素成為順序表的最后一個元素。完成以下程序。 int length。 int ins(SQ *a, int x, int y) { int k,i。 for(k=0。 k++) if(aelem[k]==x) break。 else for(i=alength1。 i) ______________ 。 return 1。鏈表一共有5個結(jié)點，其元素值分別為100，200，300，400，500，經(jīng)過下列語句后，輸出什么結(jié)果?(3分) for(p=h。 p=pnext)。 printf(%d, pdata)。(8分)Typedef struct LinkNode{ int data。 *rchild。2．已知單鏈表結(jié)點數(shù)據(jù)結(jié)構(gòu)如下，編寫算法判斷一個單鏈表中各結(jié)點的值是否由小到大排列。(7分)Typedef struct LinkNode{ int data。}Node。 (A)0 (B)1 (C)2 (D)33．一個n個頂點的連通無向圖，其邊的個數(shù)至少為( )。 (A)直接插入排序 (B)起泡排序 (c)快速排序 (D)直接選擇排序5．一棵Huffman樹總共有11個結(jié)點，則葉子結(jié)點有( )個。 (A) O(n) (B) O(n2) (C) O(log2n) (D) O(nlog2n)7．如果一棵樹有10個葉子結(jié)點，則該樹總共至少有( )個結(jié)點。 (A)13 (B)401 (C)402 (D)403二、判斷題(每題1分，共8分。（ ）2．快速排序法在最好的情況下的時間復雜度是O(n)。( )4．進棧操作時，必須判斷棧是否已滿。( )6．二叉排序樹采用先序遍歷可以得到結(jié)點的有序序列。（ ）8．對于二叉排序樹，根元素肯定是值最大的元素。2．某算法在求解一個10階方程組時，運算次數(shù)是500，求解一個30階方程組時，運算次數(shù)是4500，則該算法的時間復雜度為( )。 4．如果某有向圖的所有頂點可以構(gòu)成一個拓撲排序序列，則說明該有向圖__________。6．一個數(shù)組的長度為20，用于存放一個循環(huán)隊列，則隊列最多只能有__________個元素。8．一個具有n個結(jié)點的線性表采用堆排序，在建堆之后還要進行__________次堆調(diào)整。(5分)2．(1)給出右圖所示樹的后序遍歷結(jié)果。（5分）3．已知下圖是一個有向圖。(4分)(2)基于你給出的鄰接鏈表，求從頂點5／出發(fā)的廣度優(yōu)先溫歷。(1)從頂點D開始，寫出各頂點加人生成樹的次序。(4分)5．已知下圖是一棵二叉排序樹。(4分)(2)畫出刪除值為46的結(jié)點后的二叉排序樹。完成程序。for(i= ____________________ 。 i) { for(j=1。 j++) { if(____________________){tmp=a[j]。a[j+1]=tmp。完成以下程序。 Struct LinkNode *next。Node *search_link(Node *head, int e){Node *p, *q。for(p=head。 p=pnext) if(pdata==e) ________________。}3．下列算法是輸出一顆二叉樹的第i層的所有結(jié)點的值，假定根結(jié)點是第1層。 Struct LinkNode *lchild, *rchild。void outi(Node *tree, int i){if(tree==NULL) return。 return。outi( ______________ )。(8分)2．已知順序表的數(shù)據(jù)結(jié)構(gòu)如下，編寫算法．刪除順序表前面的10個元素。(7分)typedef struct { int elem[100]。}SQ。 (A)102 (B)105 (C)106 (D)1082．森林轉(zhuǎn)換為二叉樹后，從根結(jié)點開始一直沿著右子樹下去，一共有4個結(jié)點，表明( )。(A)e (B)2e (C)n2一e (D)n2—2e4．在內(nèi)部排序中，排序時不穩(wěn)定的有( )。(A)3，2，5，4，1 (B)1，5，4，2，3(C)2，4，3，5，1 (D)4，5，3，2，16．一個n條邊的連通無向圖，其頂點的個數(shù)至多為( )。(A)3 (B)4 (C)7 （D）8 8．已知某算法的執(zhí)行時間為，n為問題規(guī)模，則該算法的時間復雜度是( )。正確的打√，錯誤的打x)1．只要是算法，肯定可以在有限的時間內(nèi)完成。( )3．不論是行優(yōu)先還是列優(yōu)先，二維數(shù)組的最后一個元素的存儲位置是—樣的。( )5．二叉樹的先序遍歷不可能與中序遍歷相同。( )7．一個稀疏矩陣采用三元組法存儲不可能是((5,3,7),(5,4,4),(5,3,5))。8．一個無序的順序表不能采用折半查找法進行查找。2．一個55的對稱矩陣采用壓縮存儲，需要存儲____________個元素。4．有向圖用鄰接矩陣存儲，其第i列的所有元素之和等于頂點i的______________。6．快速排序法在最差的情況下的時間復雜廢是______________。8．如果某線性表的每一個元素都沒有后繼元素，則其長度最多是_______________。(5分) (2)在上述堆的堆頂元素去掉，把堆的最后一個元素放到堆頂位置，再調(diào)整為大頂堆(用二叉樹表示)。(5分) 3．假設(shè)字符a，b，c，d，e，寫出a，b，c，d，e，f的Huffman編碼。(1)畫出該無向圖的鄰接矩陣。(4分)5．用Kruskal算法(一條邊一條邊地加入生成樹)求右下圖的最小生成樹。(5分)(2)畫出最終的最小生成樹。請完成如下程序。struct LinkNode *next。Node *delete)Node *head, Node *p){Node *pf。 free(p)。 pfnext!=p。 ________________ = pnext。}}return head。下面的函數(shù)serach的功能是采用折半查找法查找值為e的元素，并返回其下標，如果找不到，返回1。(4分)int search(elem r[],int n,int e){int i1,i2,k。i2=n1。 if(r[k]==e) _______________。 else ________________。}3．以下算法是將線性表L中所有負數(shù)元素刪除，返回被刪除的元素個數(shù)。(7分)typedef struct{ int elem[100]。}SQ。 ／* c將記錄小于0的元素個數(shù) *／for(i=0,c=0。 i++) { if(____________0) c++。 }xlength=_________________。}六、編程題(共15分)1．編寫算法，求一個整型數(shù)組中不同值的個數(shù)。提示：可先將數(shù)組排序。 (7分)typedef struct LinkNode{int data。}Node。 (A)單鏈表 (B)雙向鏈表 (C)單循環(huán)鏈表 (D)順序表2．串的長度是( )。 (A)1140 (B)1145 (C)1120 (D)l1254．若用數(shù)組S[1..n]作為兩個棧S1和S2的共用存儲結(jié)構(gòu)，對任何一個棧，只有當S全滿時才不能進行人棧操作。 (A) S1的棧底位置為0，S2的棧底位置為n+1 (B) S1的棧底位置為0，S2的棧底位置為n／2 (c) S1的棧底位置為1，S2的棧底位置為n (D) S1的棧底位置為1，S2的棧底位置為n/25．隊列操作的原則是( )。 (A)n—l (D)2n一1 (C)n十1 (D)2n十17．某二叉樹的中序序列和后序序列正好相反，則該二叉樹一定是( )的二叉樹。 (A)O(n) (H)O(log2n) (C)0(nlog2n) (D)O(n2)9．若表R在排序前已按鍵值遞增順序排列，則( )算法的比較次數(shù)最少。 (A)堆排序 (D)冒泡排序 (c)簡單選鋒排序 (D)快速排序二、判斷題(每小題1分，共10分。( ) 2．已知指針p指向鏈表L中的某結(jié)點，執(zhí)行語句p＝p一＞next不會刪除該鏈表中的結(jié)點。( ) 4．如果一個串中的所有字符均在另一個串中出現(xiàn)，則說明前者是后者的子串。( )6．一棵二叉樹的中序遍歷序列與該二叉樹轉(zhuǎn)換成森林的后序遍歷序列相同。( )8．折半查找說法的前提之一是線性表有序。( ) 10．對一無序數(shù)據(jù)序列而言，用堆排序比用直接插入排序花費的時間多。 2．對于一個以順序?qū)崿F(xiàn)的循環(huán)隊列Q[0…M1]，隊首、隊尾指針分別為f和r，隊列判空的條件是________________。ABCDEFGHIJKLMNOPQRSTUVW’，由如下運算可以得到串S2，S2＝Concat(Sub(S1，19，3)，Sub(Sl，4，2)，Sub(S1，14，1)，Sub(S1，20，1))，則S2＝________________。 5．已知二叉樹中葉子數(shù)為50，僅有一個孩子的結(jié)點數(shù)為30，則總結(jié)點數(shù)為___________________。 7．具有M個頂點的連通圖至少有___________條邊，而具有M個頂點的強連通圖則至少有_____________條邊。9．直接選擇排序算法在最好情況下所做的交換元素的次數(shù)為________________。3．已知一有向圖如下圖所示，試畫出從A點出發(fā)的深度優(yōu)先生成樹。 5．己知下面二又排序樹各結(jié)點的值依次為1～9，請寫出該二叉排序樹按層次遍歷的結(jié)果。(25 10 20 3l 5 100 16 3 44 61 18 8l 38 40 15)五、程序填空題(第2題各6分，第3題3分，共15分) 1．以下算法為折半查找算法，在空格處填上合適的語句或表達式完成該算法。 ／* 查找區(qū)間初始化 *／int m。if(R[m].key==K) ／* 找到該元素 *／ return m。 ／* 將查找區(qū)間定為左半邊 *／else________________。 ／* 找不到該元素 *／}2．以下算法將元素遞增排列的順序存儲線性表A和B的元素的交集存人線性表C中。(每空2分)void SqList_Intersect(SqList A, SqList B, SqList amp。 ／* 下標初始化，A、B、C的下標都從1開始 */ while(i= amp。 j=) ／* A、B表均末到表尾 */ {if([i]==[j]) ／* A表元素比B表元素小，A表下標后移 *／______________________。if([i]==[j]) ／* 當發(fā)現(xiàn)了一個在A和B中都存在的元素 *／ {[_____________]=[i]。 j++。 /* C表長度置位 */ } /* SqList_Intersect */3．對下面的遞歸算法，要求寫出調(diào)用P(3)的執(zhí)行結(jié)果。 { if(w0) { print(w, )。 /* 遞歸調(diào)用 */ p(w1)。二叉樹類型定義如下。struct node *left。 2．編寫函數(shù)用于刪除元素遞增排列的帶首結(jié)點單鏈表L中值大于mink且小于maxk的所有元素，并給出其時間復雜度。(9分)typedef struct node{ int Data。