【正文】 ，則會出現(xiàn)下列問題：_________________。5．一個1010的三角矩陣a采用列優(yōu)先壓縮存儲后，如果首元素a[0][0]是第1個元素，那么a[4][2]是第______________個元素。 6．如果一個有向圖有5個頂點，則最多有___________________條弧。 7．采用快速排序法進行排序時，如果_________________，排序效率會大大降低。 8．設(shè)無向圖G有100條邊，則G至少有_____________個頂點。四、簡答題(共38分)1．排序(1)寫出線性表(26，45，12，20，30)采用快速排序算法排序后，第一趟結(jié)束時的結(jié)果。(4分)(2)線性表采用插入排序算法排序幾越后，有序部分是(16，20，40)．無序部分是(18，25)，再下一趟排序需要移動幾個元素?寫出下一趟結(jié)束時的結(jié)果。(4分)2．給出右圖所示二叉樹中序遍歷結(jié)果。(5分)3．已知5個結(jié)點的權(quán)值分別是4，6，1，13，7，試畫出這些結(jié)點構(gòu)成的Huffman樹。(5分)4．已知下圖是一個無向團。(1)畫出該無向圖的鄰接鏈表。(5分)(2)基于你給出的鄰接鏈表，求從頂點C出發(fā)的廣度優(yōu)先遍歷。(5分)5．(1)根據(jù)線性表(23，49，28，10，30，5，16)畫出二叉排序樹。(5分) (2)根據(jù)該二叉排序樹，查找數(shù)7，需要比較哪幾個數(shù)?(5分)五、程序填空題(共15分)1．已知QUEUE表示循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)，函數(shù)1eavequeue是將隊首元素的值放人變量e，然后刪除隊首元素，操作成功返回1，否則返回0。完成以下程序。(4分)Typedef struct { int data[100]。 int front。 /* 隊首元素的下標(biāo) */ int rear。 /* 等于隊尾元素的下標(biāo)加1 */}QUEUE。Leavequeue(QUEUE *Q, int *e){ if(__________________) return 0。 *e=Qdata[Qfront]。 Qfront= ______________。 return 1。}2．以下函數(shù)ins的功能是在順序表a中找到第一個值為x的元素，然后在該元素之前插入一個值為y的元素。如果找不到值為x的元素，則新元素成為順序表的最后一個元素。插入成功返回1，否則返回0。完成以下程序。(8分)typedef struct { int elem[100]。 int length。}SQ。 int ins(SQ *a, int x, int y) { int k,i。 if( ________________ ) return 0。 for(k=0。 kalength。 k++) if(aelem[k]==x) break。 if(k==alength) k。 else for(i=alength1。 ik。 i) ______________ 。 ________________ =y。 return 1。 }3．已知一個單鏈表的表首指針為h，每個結(jié)點含元素值data和下一結(jié)點的地址next。鏈表一共有5個結(jié)點，其元素值分別為100，200，300，400，500，經(jīng)過下列語句后，輸出什么結(jié)果?(3分) for(p=h。 pdata300。 p=pnext)。 pnext=pnextnext。 printf(%d, pdata)。六、編程題(共15分)1．已知二叉樹結(jié)點數(shù)據(jù)結(jié)構(gòu)如下，編寫算法求二叉樹的非葉子結(jié)點數(shù)目。(8分)Typedef struct LinkNode{ int data。 Struct LinkNode *lchild。 *rchild。}Node。2．已知單鏈表結(jié)點數(shù)據(jù)結(jié)構(gòu)如下，編寫算法判斷一個單鏈表中各結(jié)點的值是否由小到大排列。如果是(包括空表)，返回1，不是則返回0。(7分)Typedef struct LinkNode{ int data。 Struct LinkNode *next。}Node。模擬試題8一、選擇題(每小題1分，共8分)1．設(shè)一數(shù)列的順序為1，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層最少有( )個結(jié)點。 (A)0 (B)1 (C)2 (D)33．一個n個頂點的連通無向圖，其邊的個數(shù)至少為( )。 (A) n1 (B) n (C) n+1 (D)O n log n4．下列排序方法中，( )的比較次數(shù)與紀錄的初始排列狀態(tài)無關(guān)。 (A)直接插入排序 (B)起泡排序 (c)快速排序 (D)直接選擇排序5．一棵Huffman樹總共有11個結(jié)點，則葉子結(jié)點有( )個。 (A)5 (B)6 (C)7 (D)96．已知某算法的執(zhí)行時間為(n+n2)/2+log2 (n+2)，n 為問題規(guī)模，則該算法的時間復(fù)雜度是( )。 (A) O(n) (B) O(n2) (C) O(log2n) (D) O(nlog2n)7．如果一棵樹有10個葉子結(jié)點，則該樹總共至少有( )個結(jié)點。 (A)10 (B)11 (C)19 (D)2l 8．一個100100的三角矩陣a采用行優(yōu)先壓縮存儲后，如果首元素a[0][0]是第—個元素，那么a[4][2]是第( )個元素。 (A)13 (B)401 (C)402 (D)403二、判斷題(每題1分，共8分。正確的打√，錯誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個元素都最多只有一個直接前驅(qū)，則必為線性表。（ ）2．快速排序法在最好的情況下的時間復(fù)雜度是O(n)。( )3．進棧、出棧操作的時間復(fù)雜度是0(n)。( )4．進棧操作時，必須判斷棧是否已滿。( )5．一個有序的單鏈表不能采用折半查找法進行查找。( )6．二叉排序樹采用先序遍歷可以得到結(jié)點的有序序列。( )7．對長度為100的有序線性表用折半查找時，最小比較次數(shù)為0。（ ）8．對于二叉排序樹，根元素肯定是值最大的元素。( )三、填空題(每題2分，共15分)1．?dāng)?shù)據(jù)結(jié)構(gòu)有__________和__________等兩種物理結(jié)構(gòu)。2．某算法在求解一個10階方程組時，運算次數(shù)是500，求解一個30階方程組時，運算次數(shù)是4500，則該算法的時間復(fù)雜度為( )。 3．在一個長度為n的順序表中插入一個元素，最少需要移動__________個元素，最多需要移動__________個元素。 4．如果某有向圖的所有頂點可以構(gòu)成一個拓撲排序序列，則說明該有向圖__________。 5．如果指針p指向一棵二叉樹的一個結(jié)點，則判斷p沒有左孩子的邏輯表達式為____________。6．一個數(shù)組的長度為20，用于存放一個循環(huán)隊列，則隊列最多只能有__________個元素。 7．無向圖用鄰接矩陣存儲，其所有元素之和表示無向圖的__________。8．一個具有n個結(jié)點的線性表采用堆排序，在建堆之后還要進行__________次堆調(diào)整。四、簡答題(共38分)1．寫出線性表(26，4，12，25，30，6，15，20．16，2，18)采用二路歸并排序算法排序后，第一趟和第二趟結(jié)束時的結(jié)果。(5分)2．(1)給出右圖所示樹的后序遍歷結(jié)果。(4分) (2)采用孩子兄弟法將該樹轉(zhuǎn)換為一棵二叉樹。（5分）3．已知下圖是一個有向圖。(1)畫出該有向圖的鄰接鏈表。(4分)(2)基于你給出的鄰接鏈表，求從頂點5／出發(fā)的廣度優(yōu)先溫歷。(4分)4．用Prim算法(一條頂點一條頂點加入生成樹)求下圖的最小生成樹。(1)從頂點D開始，寫出各頂點加人生成樹的次序。(4分)(2)畫出最終的最小生成樹。(4分)5．已知下圖是一棵二叉排序樹。(1)計算平均查找長度。(4分)(2)畫出刪除值為46的結(jié)點后的二叉排序樹。(4分)五、程序填空題(共15分)1．以下是采用冒泡排序法對數(shù)組a進行排序。完成程序。(4分)bsort(int a[], int n){int n, i, j, tmp。for(i= ____________________ 。 i1。 i) { for(j=1。 ji。 j++) { if(____________________){tmp=a[j]。a[j]=a[j+1]。a[j+1]=tmp。} }}}2．在單鏈表(表首指針為head)的元素中找出最后一個值為e的元素，返回其指針；如果找不到，返回NULL。完成以下程序。(6分)Typedef struct LinkNode{ int data。 Struct LinkNode *next。}Node。Node *search_link(Node *head, int e){Node *p, *q。q= ________________ 。for(p=head。 ________________ 。 p=pnext) if(pdata==e) ________________。return q。}3．下列算法是輸出一顆二叉樹的第i層的所有結(jié)點的值，假定根結(jié)點是第1層。(5分)Typedef struct LinkNode{ int data。 Struct LinkNode *lchild, *rchild。}Node。void outi(Node *tree, int i){if(tree==NULL) return。if(i==1){printf(%d\n,treedata)。 return。}outi( ______________ )。outi( ______________ )。}六、編程題(共15分)1．兩個字符數(shù)組s，t中各放有一個串，編寫算法，將所有t中有而s中沒有的字符加到s中(逐個加到s的后面)。(8分)2．已知順序表的數(shù)據(jù)結(jié)構(gòu)如下，編寫算法．刪除順序表前面的10個元素。如果順序表中的元素少于10個，則刪完為止。(7分)typedef struct { int elem[100]。 int length。}SQ。模擬試題9一、選擇題(每小題1分，共8分)1．設(shè)有一個10階的對稱矩陣a，采用壓縮存儲方式，以行序為主存儲，a[0][0]的存儲地址為100，每個元素占1個地址空間，則a[3][2]的地址為( )。 (A)102 (B)105 (C)106 (D)1082．森林轉(zhuǎn)換為二叉樹后，從根結(jié)點開始一直沿著右子樹下去，一共有4個結(jié)點，表明( )。 (A)森林有4棵樹 (B)森林的最大深度為4 (c)森林的第一棵樹有4層 (D)森林有4個結(jié)點3．在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為( )。(A)e (B)2e (C)n2一e (D)n2—2e4．在內(nèi)部排序中，排序時不穩(wěn)定的有( )。(A)插入排序 (B)冒泡排序 (c)快速排序 (D)歸并排序5．設(shè)一數(shù)列的順序為1，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，16．一個n條邊的連通無向圖，其頂點的個數(shù)至多為( )。(A)n一1 (B)n (C)n十1 (D) n log2 n7．總共3層的完全二叉樹，其結(jié)點數(shù)至少有( )個。(A)3 (B)4 (C)7 （D）8 8．已知某算法的執(zhí)行時間為，n為問題規(guī)模，則該算法的時間復(fù)雜度是( )?！睞)O(n) (B)O(n2) (C)O(log2n) (D)0(n3log2n)二、判斷題(每題1分，共8分。正確的打√，錯誤的打x)1．只要是算法，肯定可以在有限的時間內(nèi)完成。( )2．無論是線性表還是樹，每一個結(jié)點的直接前驅(qū)結(jié)點最多只有一個。( )3．不論是行優(yōu)先還是列優(yōu)先，二維數(shù)組的最后一個元素的存儲位置是—樣的。（ ）4．直接插入排序時，關(guān)鍵碼的比較次數(shù)與記錄的初始排列無關(guān)。( )5．二叉樹的先序遍歷不可能與中序遍歷相同。( )6．任何一棵二叉樹，不可能沒有葉子結(jié)點。( )7．一個稀疏矩陣采用三元組法存儲不可能是((5,3,7),(5,4,4),(5,3,5))。（ ）。8．一個無序的順序表不能采用折半查找法進行查找。( )三、填空題(每題2分，共16分) 1．在一個長度為n的順序表中插入一個元素，平均需移動____________個元素，時間復(fù)雜度是____________。2．