【正文】 ___第i列上非0元素的個(gè)數(shù)（填等于，大于或小于）。10． 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為_(kāi)_______________________。8． 設(shè)順序線(xiàn)性表中有n個(gè)數(shù)據(jù)元素，則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中_______個(gè)數(shù)據(jù)元素；刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中_______個(gè)元素。6． 設(shè)哈夫曼樹(shù)中共有99個(gè)結(jié)點(diǎn)，則該樹(shù)中有_________個(gè)葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該樹(shù)中有_____個(gè)空指針域。4． 深度為k的完全二叉樹(shù)中最少有____________個(gè)結(jié)點(diǎn)。2． 設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列為_(kāi)________________________________________________________（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。 (A) N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過(guò)（ ）。 (A) 必須判別棧是否為滿(mǎn) (B) 必須判別棧是否為空 (C) 判別棧元素的類(lèi)型 (D) 對(duì)棧不作任何判別8．下列四種排序中（ ）的空間復(fù)雜度最大。 (A) n (B) n1 (C) m (D) m16．設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行（ ）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。 (A) n (B) e (C) 2n (D) 2e4．在二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)2．設(shè)一棵二叉樹(shù)的深度為k，則該二叉樹(shù)中最多有（ ）個(gè)結(jié)點(diǎn)。2． 設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹(shù)中的雙親結(jié)點(diǎn)算法。3．已知序列（10，18，4，3，6，12，1，9，18，8）請(qǐng)用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。}三、計(jì)算題(每題10分，共30分)，中序遍歷序列是EFAGBCHKIJD，畫(huà)出此二叉樹(shù)，并畫(huà)出它的后序線(xiàn)索二叉樹(shù)。 else if (tkeyk) t=tlchild。bitree *bstsearch(bitree *t, int k){ if (t==0 ) return(0)。 struct node *rchild。typedef struct node{int key。 else return(1)。 if (i==j) return(1)。amp。 j=i=k % p。}。struct record{int key。12. 設(shè)有向圖G中有向邊的集合E={1，2，2，3，1，4，4，2，4，3}，則該圖的一種拓?fù)湫蛄袨開(kāi)___________________。10. 設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照從自上到下、從左到右從1開(kāi)始順序編號(hào)，則第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為_(kāi)___________，右孩子結(jié)點(diǎn)的編號(hào)為_(kāi)__________。8. 設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較________次就可以斷定數(shù)據(jù)元素X是否在查找表中。6. 設(shè)有向圖G中有n個(gè)頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d，則e和d的關(guān)系為_(kāi)________。4. 設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲(chǔ)結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的________，第i列上所有元素之和等于頂點(diǎn)i的________。2. 設(shè)一棵完全二叉樹(shù)中有500個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的深度為_(kāi)_________；若用二叉鏈表作為該完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則共有___________個(gè)空指針域。 (A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 插入排序（ ）的空間復(fù)雜度最大。 (A) n，e (B) e，n (C) 2n，e (D) n，2e8. 設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（ ）條邊。(A) 10，15，14，18，20，36，40，21 (B) 10，15，14，18，20，40，36，21 (C) 10，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，216．設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均平均查找長(zhǎng)度為（ ）。 (A) q=pnext；pdata=qdata；pnext=qnext；free(q)；(B) q=pnext；qdata=pdata；pnext=qnext；free(q)； (C) q=pnext；pnext=qnext；free(q)； (D) q=pnext；pdata=qdata；free(q)；4．設(shè)有n個(gè)待排序的記錄關(guān)鍵字，則在堆排序中需要（ ）個(gè)輔助記錄單元。數(shù)據(jù)結(jié)構(gòu)試卷（三）一、選擇題(每題1分，共20分)1．設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09}，則數(shù)據(jù)結(jié)構(gòu)A是（ ）。四、算法設(shè)計(jì)題(16分) 1． 設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線(xiàn)性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部分的每個(gè)關(guān)鍵字均大于等于Ki。5． 設(shè)有無(wú)向圖G，要求給出用普里姆算法構(gòu)造最小生成樹(shù)所走過(guò)的邊的集合。3． 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。8． 已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn)1出發(fā)，DFS遍歷的輸出序列是 ，BFS遍歷的輸出序列是 三、應(yīng)用題(36分)1． 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡(jiǎn)單選擇排序和第4趟直接插入排序后的結(jié)果。6. 設(shè)某無(wú)向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e=_______。4. 快速排序的最壞時(shí)間復(fù)雜度為_(kāi)__________，平均時(shí)間復(fù)雜度為_(kāi)_________。_________________。stack,int x){if (==m1) printf(“overflow”)。} sqstack。typedef struct {int s[100]。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8二、填空題(24分)1. 為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問(wèn)題是____________________和__________________________。 (A) 9 (B) 10 (C) 11 (D) 127．設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有（ ）個(gè)表頭結(jié)點(diǎn)。 (A) BADC (B) BCDA (C) CDAB (D) CBDA5．設(shè)某無(wú)向完全圖中有n個(gè)頂點(diǎn)，則該無(wú)向完全圖中有（ ）條邊。 (A) 2m1 (B) 2m (C) 2m+1 (D) 4m3．設(shè)順序循環(huán)隊(duì)列Q[0：M1]的頭指針和尾指針?lè)謩e為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（ ）。 int CountX(LNode* HL,ElemType x)數(shù)據(jù)結(jié)構(gòu)試卷（二）一、選擇題(24分)1．下面關(guān)于線(xiàn)性表的敘述錯(cuò)誤的是（ ）。 else return Find(_______________,item)。//查找成功 return ___________。 item){ if (BST==NULL) return false。 39。 ABC (BTright)。Lnext){ q=L；L=L－next；p=L； S1： while(p－next) p=p－next； S2： p－next=q；q－next=NULL； } return L； } 請(qǐng)回答下列問(wèn)題： （1）說(shuō)明語(yǔ)句S1的功能； （2）說(shuō)明語(yǔ)句組S2的功能； （3）設(shè)鏈表表示的線(xiàn)性表為（a1,a2, …,an）,寫(xiě)出算法執(zhí)行后的返回值所表示的線(xiàn)性表。四、閱讀算法（每題7分，共14分）1. LinkList mynote(LinkList L) {//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 if(Lamp。 用克魯斯卡爾算法得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。 3. 已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V={1,2,3,4,5,6,7}。三、計(jì)算題（每題 6 分，共24分）1. 在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線(xiàn)性表，表頭指針為A [0].next，試寫(xiě)出該線(xiàn)性表。11. 在堆排序的過(guò)程中，對(duì)任一