【正文】 (9分)typedef struct node{ int Data。struct node *left。 /* 遞歸調(diào)用 */ p(w1)。 /* C表長(zhǎng)度置位 */ } /* SqList_Intersect */3．對(duì)下面的遞歸算法，要求寫出調(diào)用P(3)的執(zhí)行結(jié)果。if([i]==[j]) ／* 當(dāng)發(fā)現(xiàn)了一個(gè)在A和B中都存在的元素 *／ {[_____________]=[i]。 ／* 下標(biāo)初始化，A、B、C的下標(biāo)都從1開始 */ while(i= amp。 ／* 找不到該元素 *／}2．以下算法將元素遞增排列的順序存儲(chǔ)線性表A和B的元素的交集存人線性表C中。if(R[m].key==K) ／* 找到該元素 *／ return m。(25 10 20 3l 5 100 16 3 44 61 18 8l 38 40 15)五、程序填空題(第2題各6分，第3題3分，共15分) 1．以下算法為折半查找算法，在空格處填上合適的語句或表達(dá)式完成該算法。3．已知一有向圖如下圖所示，試畫出從A點(diǎn)出發(fā)的深度優(yōu)先生成樹。 7．具有M個(gè)頂點(diǎn)的連通圖至少有___________條邊，而具有M個(gè)頂點(diǎn)的強(qiáng)連通圖則至少有_____________條邊。ABCDEFGHIJKLMNOPQRSTUVW’，由如下運(yùn)算可以得到串S2，S2＝Concat(Sub(S1，19，3)，Sub(Sl，4，2)，Sub(S1，14，1)，Sub(S1，20，1))，則S2＝________________。( ) 10．對(duì)一無序數(shù)據(jù)序列而言，用堆排序比用直接插入排序花費(fèi)的時(shí)間多。( )6．一棵二叉樹的中序遍歷序列與該二叉樹轉(zhuǎn)換成森林的后序遍歷序列相同。( ) 2．已知指針p指向鏈表L中的某結(jié)點(diǎn)，執(zhí)行語句p＝p一＞next不會(huì)刪除該鏈表中的結(jié)點(diǎn)。 (A)O(n) (H)O(log2n) (C)0(nlog2n) (D)O(n2)9．若表R在排序前已按鍵值遞增順序排列，則( )算法的比較次數(shù)最少。 (A) S1的棧底位置為0，S2的棧底位置為n+1 (B) S1的棧底位置為0，S2的棧底位置為n／2 (c) S1的棧底位置為1，S2的棧底位置為n (D) S1的棧底位置為1，S2的棧底位置為n/25．隊(duì)列操作的原則是( )。 (A)單鏈表 (B)雙向鏈表 (C)單循環(huán)鏈表 (D)順序表2．串的長(zhǎng)度是( )。 (7分)typedef struct LinkNode{int data。}六、編程題(共15分)1．編寫算法，求一個(gè)整型數(shù)組中不同值的個(gè)數(shù)。 i++) { if(____________0) c++。}SQ。}3．以下算法是將線性表L中所有負(fù)數(shù)元素刪除，返回被刪除的元素個(gè)數(shù)。 if(r[k]==e) _______________。(4分)int search(elem r[],int n,int e){int i1,i2,k。}}return head。 pfnext!=p。Node *delete)Node *head, Node *p){Node *pf。請(qǐng)完成如下程序。(4分)5．用Kruskal算法(一條邊一條邊地加入生成樹)求右下圖的最小生成樹。(5分) 3．假設(shè)字符a，b，c，d，e，寫出a，b，c，d，e，f的Huffman編碼。8．如果某線性表的每一個(gè)元素都沒有后繼元素，則其長(zhǎng)度最多是_______________。4．有向圖用鄰接矩陣存儲(chǔ)，其第i列的所有元素之和等于頂點(diǎn)i的______________。8．一個(gè)無序的順序表不能采用折半查找法進(jìn)行查找。( )5．二叉樹的先序遍歷不可能與中序遍歷相同。正確的打√，錯(cuò)誤的打x)1．只要是算法，肯定可以在有限的時(shí)間內(nèi)完成。(A)3，2，5，4，1 (B)1，5，4，2，3(C)2，4，3，5，1 (D)4，5，3，2，16．一個(gè)n條邊的連通無向圖，其頂點(diǎn)的個(gè)數(shù)至多為( )。 (A)102 (B)105 (C)106 (D)1082．森林轉(zhuǎn)換為二叉樹后，從根結(jié)點(diǎn)開始一直沿著右子樹下去，一共有4個(gè)結(jié)點(diǎn)，表明( )。(7分)typedef struct { int elem[100]。outi( ______________ )。void outi(Node *tree, int i){if(tree==NULL) return。}3．下列算法是輸出一顆二叉樹的第i層的所有結(jié)點(diǎn)的值，假定根結(jié)點(diǎn)是第1層。for(p=head。 Struct LinkNode *next。a[j+1]=tmp。 i) { for(j=1。完成程序。(4分)5．已知下圖是一棵二叉排序樹。(4分)(2)基于你給出的鄰接鏈表，求從頂點(diǎn)5／出發(fā)的廣度優(yōu)先溫歷。(5分)2．(1)給出右圖所示樹的后序遍歷結(jié)果。6．一個(gè)數(shù)組的長(zhǎng)度為20，用于存放一個(gè)循環(huán)隊(duì)列，則隊(duì)列最多只能有__________個(gè)元素。2．某算法在求解一個(gè)10階方程組時(shí)，運(yùn)算次數(shù)是500，求解一個(gè)30階方程組時(shí)，運(yùn)算次數(shù)是4500，則該算法的時(shí)間復(fù)雜度為( )。( )6．二叉排序樹采用先序遍歷可以得到結(jié)點(diǎn)的有序序列。（ ）2．快速排序法在最好的情況下的時(shí)間復(fù)雜度是O(n)。 (A) O(n) (B) O(n2) (C) O(log2n) (D) O(nlog2n)7．如果一棵樹有10個(gè)葉子結(jié)點(diǎn)，則該樹總共至少有( )個(gè)結(jié)點(diǎn)。 (A)0 (B)1 (C)2 (D)33．一個(gè)n個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為( )。(7分)Typedef struct LinkNode{ int data。 *rchild。 printf(%d, pdata)。鏈表一共有5個(gè)結(jié)點(diǎn)，其元素值分別為100，200，300，400，500，經(jīng)過下列語句后，輸出什么結(jié)果?(3分) for(p=h。 i) ______________ 。 k++) if(aelem[k]==x) break。 int ins(SQ *a, int x, int y) { int k,i。完成以下程序。 return 1。 /* 等于隊(duì)尾元素的下標(biāo)加1 */}QUEUE。完成以下程序。(1)畫出該無向圖的鄰接鏈表。(4分)(2)線性表采用插入排序算法排序幾越后，有序部分是(16，20，40)．無序部分是(18，25)，再下一趟排序需要移動(dòng)幾個(gè)元素?寫出下一趟結(jié)束時(shí)的結(jié)果。 6．如果一個(gè)有向圖有5個(gè)頂點(diǎn)，則最多有___________________條弧。2．已知某算法的執(zhí)行時(shí)間為(n+n2)/2+log2 (2n+1)，n 為問題規(guī)模，則該算法的時(shí)間復(fù)雜度是________________。( )6．圖的生成樹的邊數(shù)應(yīng)小于頂點(diǎn)數(shù)。正確的打√，錯(cuò)誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個(gè)元素都最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，則元素必為線性表。 (A) front==rear (B) (rear+1)%MAXSIZE==front (C) frontrear==1 (D) rear%MAXSIZE==front6．設(shè)有1000個(gè)元素，用折半查找時(shí)，最小比較次數(shù)為( )。模擬試題7一、選擇題(每小題1分，共8分)1．如果樹的結(jié)點(diǎn)A有4個(gè)兄弟，而且B為A的雙親，則B的度為( )。(7分)Typedef struct LinkNode{ int data。 return(s[i]t[i])。 s[i]!=0amp。 return 。 if (__________________) return NULL。 Struct LinkNode *lchild。return 1。 /* 棧頂元素的下標(biāo) */}STACK。(1)各元素的平均查找長(zhǎng)度是多少？(4分)(2)查找值為10的元素，查找時(shí)與哪些元素進(jìn)行了比較?(4分)五、程序填空題(共15分)1．己知STACK表示棧的數(shù)據(jù)結(jié)構(gòu)，push為將一個(gè)值為e的元素進(jìn)棧，若成功返回1，否則返回0。(5分)3．已知下圖是一個(gè)有向圖。( )四、簡(jiǎn)答題(共38分)1．排序(1)寫出線性表(26，45，12，z0，30，5，15，29，16，2，18)采用基數(shù)排序后，第一趟結(jié)束時(shí)的結(jié)果。4．Huffman樹沒有度為1的結(jié)點(diǎn)。三、判斷題(每題1分，共8分。5．設(shè)循環(huán)隊(duì)列Q[1..N]的首尾指針為F，R，當(dāng)插入元素時(shí)尾指針只加1，首指針F總是指向隊(duì)列中第一個(gè)元素的前一個(gè)位置，則隊(duì)列中元素的個(gè)數(shù)為____________。 (A)3 (B)4 (C)5 (D)68．設(shè)一棵二叉樹共有50個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn))，則共有( )個(gè)度為2的結(jié)點(diǎn) (A)25 (B)49 (C)50 (D)51二、填空題(每題2分，共16分)1．一個(gè)算法，如果不論問題規(guī)模大小，運(yùn)行所需時(shí)間都一樣，則該算法的時(shí)間復(fù)雜度是_____________。 (A)5 (B)6 (C)7 (D)8 4．具有20個(gè)結(jié)點(diǎn)的二叉樹，其深度最大為( )。4．試設(shè)計(jì)將數(shù)組A[0…N—1]中所有奇數(shù)移到所有偶數(shù)之前的算法，要求不另外增加存儲(chǔ)空間，且時(shí)間復(fù)雜度為O(n)。五、算法設(shè)計(jì)(18分)1．已知線性表的元素按遞增順序排列，并以帶首結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。2．已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，畫出這棵二叉樹。( )9．按中序遍歷一棵二叉排序樹所得到的中序遍歷序列是一個(gè)遞增序列10．進(jìn)棧操作push(x，s)作用子鏈接棧時(shí)，無需判滿。( )5．對(duì)于n個(gè)記錄的集合進(jìn)行冒泡排序，在最壞情況下的時(shí)間復(fù)雜度是0(n2)。三、判斷題(10分)1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單元。 3．假定對(duì)線性表R[059]進(jìn)行分塊查找，共分10塊，每塊長(zhǎng)度等于6。 (A)1 (B)2 (C)3 (D)413．在順序存儲(chǔ)的線性表R[029]上進(jìn)行順序查找的平均查找長(zhǎng)度為(①)，進(jìn)行二分查找的平均查找長(zhǎng)度為(②)，講行分塊查找（設(shè)分為5塊)的平均查找長(zhǎng)度為(③) ①(A)15 (B)15．5 (C)16 (D)20 ②(A)4 (B)62／15 (C)64／15 (D)25／6 ③(A)6 (B)11 (C)5 (D)6．514．在所有排序方法中，關(guān)健碼的比較次數(shù)與記錄的初始排列無關(guān)的是( )。 (A)串中不同字符的個(gè)數(shù) (B)串中不同字母的個(gè)數(shù) (C)串中所含字符的個(gè)數(shù)n(n＞0) (D)串中所含字符的個(gè)數(shù)n(n≥0)7．若有一個(gè)棧的輸入序列是l，2，…，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是( )。 snext=pnext。 pnextprior=s。 snext=pnext。 sprior=p。 (A) ni (B) ni+1 (C) ni1 (D) i3．在一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)．在查找成功的情況下需平均比較( )個(gè)元素結(jié)點(diǎn)。j++)for(k=0。for(i=0。im。五、算法設(shè)計(jì)(28分)1．編寫一個(gè)程序，輸出二叉排序樹BT中最小的鍵值。四、應(yīng)用題(20分)1．依次輸入集合{20，13，22，5，16，3，48，24}中的鍵值，得到一棵二叉排序樹，試畫出該二叉排序樹并求出在等概率下成功查找的平均查找長(zhǎng)度。5．設(shè)鏈值序列為{K1,K2,…,Kn}，用篩選法建堆必須從第__________個(gè)元素開始篩選。______________＝f。 ( )9．表中的每一個(gè)元京都有前驅(qū)和后繼元素。( )5．即使某排序算法是不穩(wěn)定的，但該方法仍有實(shí)際應(yīng)用價(jià)值。 (B)p＝p一＞next (C)p＝p一＞next一＞next (D)P一＞next＝p二、判斷題(10分)1．具有線性序關(guān)系的集合中，若a，b是集合中的任意兩個(gè)元素，則必有ab的關(guān)系。(A)必須是連續(xù)的 (B)連續(xù)不連續(xù)都可以(c)部分地址必須是連續(xù)的 (D)必須是不連續(xù)的8．具有2000個(gè)結(jié)點(diǎn)的二叉樹，其高度至少為( )。j++) for(j=n。6．下面程序段的時(shí)間復(fù)雜度為( )。( )模擬試題4一、選擇題(20分)1．n個(gè)頂點(diǎn)的無向圖的鄰接表中結(jié)點(diǎn)總數(shù)最多有( )個(gè)。（ ）5．二叉排序樹中，任一結(jié)點(diǎn)的值都大于或等于其孩子的值。(8分)五、判斷題(每題1分，共8分。 4．快速排序?yàn)槭裁词遣环€(wěn)定的排序?試舉例說明。