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