【正文】 ft=s；（設(shè)結(jié)點中的兩個指針域分別為left和right）。（ ）9．線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（ ）7．先序遍歷一棵二叉排序樹得到的結(jié)點序列不一定是有序的序列。（ ）5．哈夫曼樹中沒有度數(shù)為1的結(jié)點。（ ）3．設(shè)某堆中有n個結(jié)點，則在該堆中插入一個新結(jié)點的時間復(fù)雜度為O(log2n)。二、判斷題(20分)1．不論是入隊列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。 (C) topnext=top。 (A) top=top+1。 (A) 20 (B) 256 (C) 512 (D) 10249．設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（ ）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)7．設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（ ）。 (A) 先序遍歷 (B) 中序遍歷 (C) 后序遍歷 (D) 層次遍歷5．設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為（ ）。 (A) n (B) n1 (C) 2n (D) 2n13．設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（ ）。３． 在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計直接插入排序算法數(shù)據(jù)結(jié)構(gòu)試卷（七）一、選擇題(30分)1．設(shè)某無向圖有n個頂點，則該無向圖的鄰接表中有（ ）個表頭結(jié)點。四、算法設(shè)計題(20分)１． 設(shè)計在順序有序表中實現(xiàn)二分查找的算法。9．快速排序算法的空間復(fù)雜度平均情況下為__________，最壞的情況下為__________。7．設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是_____________________________________________。5．設(shè)二叉樹中度數(shù)為0的結(jié)點數(shù)為50，度數(shù)為1的結(jié)點數(shù)為30，則該二叉樹中總共有_______個結(jié)點數(shù)。3．設(shè)有向圖G的二元組形式表示為G =（D，R），D={1，2，3，4，5}，R={r}，r={1,2，2,4，4,5，1,3，3,2，3,5}，則給出該圖的一種拓?fù)渑判蛐蛄衉_________。（ ）三、填空題(30分)1．for(i=1，t=1，s=0；i=n；i++) {t=t*i；s=s+t；}的時間復(fù)雜度為_________。（ ）9．中序遍歷二叉排序樹可以得到一個有序的序列。（ ）7．設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（ ）5．設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（ ）3．冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。 (A) 第i行非0元素的個數(shù)之和 (B) 第i列非0元素的個數(shù)之和 (C) 第i行0元素的個數(shù)之和 (D) 第i列0元素的個數(shù)之和二、判斷題(20分)1．調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。 (A) 99 (B) 100 (C) 101 (D) 102，則在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為（ ）。 (A) frontnext=s；front=s； (B) snext=rear；rear=s； (C) rearnext=s；rear=s； (D) snext=front；front=s；，則建立該圖鄰接表的時間復(fù)雜度為（ ）。 (A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)10. 深度為k的完全二叉樹中最少有（ ）個結(jié)點。 (A) 3 (B) 4 (C) 5 (D) 68．順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為（ ）。 (A) 空或只有一個結(jié)點 (B) 高度等于其結(jié)點數(shù) (C) 任一結(jié)點無左孩子 (D) 任一結(jié)點無右孩子6．一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是（ ）。(A) head==0 (B) headnext==0(C) headnext==head (D) head!=04．時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（ ）。 (A) 20 (B) 30 (C) 40 (D) 452．執(zhí)行一趟快速排序能夠得到的序列是（ ）。2． 設(shè)計兩個有序單鏈表的合并排序算法。4. 設(shè)散列表的長度為8，散列函數(shù)H(k)=k mod 7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。2. 設(shè)無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權(quán)值之和。 } return(0)。 else if(____________) high=mid1。 while(low=high){ ________________________________。}。struct record{int key。exchange=1。______________。 j_____________。i=n1。9. 下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。7. 設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點i的________，第i列中所有非零元素個數(shù)之和等于頂點i的__________。5. 設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。3. 設(shè)有一個n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在n(n+1)個連續(xù)的存儲單元中，則A[i][j]與A[0][0]之間有_______個數(shù)據(jù)元素。 (A) 40，42，45，55，80，83 (B) 42，40，45，80，85，88 (C) 42，40，45，55，80，85 (D) 42，40，45，85，55，80二、填空題(共20分)1. 設(shè)有一個順序共享棧S[0：n1]，其中第一個棧項指針top1的初值為1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是____________________。 (A) abedfc (B) acfebd (C) aebdfc (D) aedfcb9．設(shè)輸入序列是……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（ ）。 (A) Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m1)Nm (C) N2+2N3+3N4+……+(m1)Nm (D) 2Nl+3N2+……+(m+1)Nm7．設(shè)有序表中有1000個元素，則用二分查找查找元素X最多需要比較（ ）次。 (A) “STRUCTURE” (B) “DATA” (C) “ASTRUCTUR” (D) “DATASTRUCTURE”5．設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為（ ）。 (A) 40，50，20，95 (B) 15，40，60，20 (C) 15，20，40，45 (D) 45，40，15，203．設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進行一趟歸并后的結(jié)果為（ ）。數(shù)據(jù)結(jié)構(gòu)試卷（五）一、選擇題(20分) 1．?dāng)?shù)據(jù)的最小單位是（ ）。2. 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。下圖所示的森林：　　(1) 求樹（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列；（3）將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；設(shè)散列表的地址范圍是[ 0..9 ]，散列函數(shù)為H（key）= （key 2 +2）MOD 9,并采用鏈表處理沖突，請畫出元素9依次插入散列表的存儲結(jié)構(gòu)。_______________________。k=a[i] % p。i++){s=(lklist *)malloc(sizeof(lklist))。for(i=0。im。 lklist *s。} lklist。typedef struct node {int key。14． 設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。12． 設(shè)無向圖對應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個數(shù)_________第i列上非0元素的個數(shù)（填等于，大于或小于）。10． 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為________________________。8． 設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_______個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中_______個元素。6． 設(shè)哈夫曼樹中共有99個結(jié)點，則該樹中有_________個葉子結(jié)點；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有_____個空指針域。4． 深度為k的完全二叉樹中最少有____________個結(jié)點。2． 設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點X，則刪除結(jié)點X需要執(zhí)行的語句序列為_________________________________________________________（設(shè)結(jié)點中的兩個指針域分別為llink和rlink）。 (A) N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（ ）。 (A) 必須判別棧是否為滿 (B) 必須判別棧是否為空 (C) 判別棧元素的類型 (D) 對棧不作任何判別8．下列四種排序中（ ）的空間復(fù)雜度最大。 (A) n (B) n1 (C) m (D) m16．設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進行（ ）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。 (A) n (B) e (C) 2n (D) 2e4．在二叉排序樹中插入一個結(jié)點的時間復(fù)雜度為（ ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)2．設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（ ）個結(jié)點。2． 設(shè)計一個求結(jié)點x在二叉樹中的雙親結(jié)點算法。3．已知序列（10，18，4，3，6，12，1，9，18，8）請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。}三、計算題(每題10分，共30分)，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。 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ù)湫蛄袨開___________________。10. 設(shè)有n個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點的雙親結(jié)點編號為____________，右孩子結(jié)點的編號為___________。8. 設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較________次就可以斷定數(shù)據(jù)元素X是否在查找表中。6. 設(shè)有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d，則e和d的關(guān)系為_________。4. 設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點i的________，第i列上所有元素之和等于頂點i的________。2. 設(shè)一棵完全二叉樹中有500個結(jié)點，則該二叉樹的深度為__________；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有___________個空指針域。 (A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 插入排序（ ）的空間復(fù)雜度最大。 (A) n，e (B) e，n (C) 2n，e (D) n，2e8. 設(shè)某強連通圖中有n個頂點，則該強連通圖中至少有（ ）條邊。(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è)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均平均查找長度為（ ）。 (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)； (