【正文】 B．是有向圖 C．是完全圖 D．不是帶權(quán)圖 (9)有向圖的鄰接表的第i個(gè)鏈表中的邊結(jié)點(diǎn)數(shù)目是第i個(gè)頂點(diǎn)的( B )。 A．度數(shù) B．出度 C．人數(shù) D．邊數(shù) (10)若某圖的鄰接表中的邊結(jié)點(diǎn)數(shù)目為奇數(shù)，則該圖( C )。 A．一定有奇數(shù)個(gè)頂點(diǎn) B．一定有偶數(shù)個(gè)頂點(diǎn) C．一定是有向圖 D?？赡苁菬o向圖 (11)若某圖的鄰接表中的邊結(jié)點(diǎn)數(shù)目為偶數(shù)，則該圖( C)。 A．一定是無向圖 B?？赡苁怯邢驁D C．可能是無向圖，也可能是有向圖 D．一定有偶數(shù)個(gè)頂點(diǎn) (12)若無向圖有k條邊，則相應(yīng)的鄰接表中就有( C)個(gè)邊結(jié)點(diǎn)。 A．k1 B．k C．2k D．K2 (13)若有向圖有k條邊，則相應(yīng)的鄰接表中就有( B )個(gè)邊結(jié)點(diǎn)。 A．k1 B．k C．2k D．K2 (14)對于一個(gè)不帶權(quán)的無向圖的鄰接矩陣而言，( C )。 A．矩陣中非零元素的數(shù)目等于圖中邊的數(shù)目 B．矩陣中非全零的行的數(shù)目等于圖中頂點(diǎn)的數(shù)目 C．第i行的非零元素的數(shù)目與第i列的非零元素的數(shù)目相等 D．第i行與第i列的非零元素的總數(shù)等于第i個(gè)頂點(diǎn)的度數(shù) (15)若從無向圖的任意一個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索便可以訪問該圖的所有頂點(diǎn)，則該圖一定是一個(gè)( B )圖。B． 非連通 B．連通 C．強(qiáng)連通 D．完全三． 求出下圖的最小生成樹克魯斯卡算法：習(xí)題八 查找一、單項(xiàng)選擇題，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長度ASL為( C )。 A． (n1)/2 B. n/2 C. (n+1)/2 D. n3．適用于折半查找的表的存儲方式及元素排列要求為( D ) A．鏈接方式存儲，元素?zé)o序 B．鏈接方式存儲，元素有序C．順序方式存儲，元素?zé)o序 D．順序方式存儲，元素有序3．當(dāng)采用分塊查找時(shí)，數(shù)據(jù)的組織方式為 ( B ) A．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊C. 數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊D. 數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個(gè)數(shù)需相同4．二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法（ A ）。A．正確 B. 錯(cuò)誤5. 設(shè)哈希表長為14，哈希函數(shù)是H(key)=key%11,表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測再散列法解決沖突，則放入的位置是( A ) A．8 B．3 C．5 D．9 二、填空題1. 順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為__n __次；當(dāng)使用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)為__n+1 __。2. 在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關(guān)鍵碼值20，需做的關(guān)鍵碼比較次數(shù)為_4_.3．在散列存儲中，裝填因子α的值越大，則__裝滿程度越大，再填寫記錄時(shí)發(fā)生碰撞的可能性越大；α的值越小，則__裝滿程度越大 ，再填寫記錄時(shí)發(fā)生碰撞的可能性越小 __。三．解答題 輸入一個(gè)正整數(shù)序列（53,17,12,66,58,70,87,25,56,60），試完成下列各題。（3） 按次序構(gòu)造一棵二叉排序樹BS。（4） 依此二叉排序樹，如何得到一個(gè)從大到小的有序序列？（5） 寫出在此二叉排序樹中查找“66”過程中進(jìn)行比較的數(shù)值序列。答案（1） （2）中序遍歷生成的二叉排序樹 （3）53,66 第九章 排序已知10個(gè)數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對該數(shù)列按從小到大排序，分別寫出直接插入排序、希爾排序（d=5，3，1）、起泡排序、簡單選擇排序和歸并排序5種排序方法每一趟排序后的序列。直接插入： 原始數(shù)據(jù)：54，28，16，34，73，62，95，60，26，43第一趟：28，54，16，34，73，62，95，60，26，43第二趟：16，28，54，34，73，62，95，60，26，43第三趟：16，28，34，54，73，62，95，60，26，43第四趟：16，28，34，54，73，62，95，60，26，43第五趟：16，28，34，54，62，73，95，60，26，43第六趟：16，28，34，54，62，73，95，60，26，43第七趟：16，28，34，54，60，62，73，95，26，43第八趟：16，26，28，34，54，60，62，73，95，43第九趟：16，26，28，34，43，54，60，62，73，95希爾排序：原始數(shù)據(jù)： 54，28，16，34，73，62，95，60，26，43第一趟（d=5）：54，28，16，26，43，62，95，60，34，73第二趟（d=3）：26，28，16，54，43，34，73，60，62，95第三趟（d=1）：16，26，28，34，43，54，60，62，73，95起泡排序： 原始數(shù)據(jù)： 54，28，16，34，73，62，95，60，26，43第一趟： 28，16，34，54，62，73，60，26，43，95第二趟： 16，28，34，54，62，60，26，43，73，95第三趟： 16，28，34，54，60，26，43，62，73，95第四趟： 16，28，34，54，26，43，60，62，73，95第五趟： 16，28，34，26，43，54，60，62，73，95第六趟： 16，28，26，34，43，54，60，62，73，95第七趟： 16，26，28，34，43，54，60，62，73，95第八趟： 16，26，28，34，43，54，60，62，73，95 （此趟無交換，結(jié)束）簡單選擇排序：原始數(shù)據(jù)： 54，28，16，34，73，62，95，60，26，43第一趟： 16，54，28， 34，73，62，95，60，26，43第二趟： 16，26，54， 28，34，73，62，95，60，43第三趟： 16，26，28，54， 34，73，62，95，60，43第四趟： 16，26，28，34，54， 73，62，95，60，43第五趟： 16，26，28，34，43，54， 73，62，95，60第六趟： 16，26，28，34，43，54， 73，62，95，60第七趟： 16，26，28，34，43，54，60， 73，62，95第八趟： 16，26，28，34，43，54，60，62， 73， 95第九趟： 16，26，28，34，43，54，60，62， 73， 95歸并排序：原始數(shù)據(jù)： 54，28，16，34，73，62，95，60，26，43第一趟： [28，54] [16，34] [62，73] [60， 95] [26，43]第二趟： [16，28，34，54] [60，62，73，95] [26，43]第三趟： [16，28，34，54，60，62，73，95] [26，43]第四趟： 16，26，28，34，43，54，60，62， 73， 95