【文章內(nèi)容簡(jiǎn)介】 行的數(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è)( )圖。A． 非連通 B．連通 C．強(qiáng)連通 D．完全三． 求出下圖的最小生成樹(shù)習(xí)題八 查找一、單項(xiàng)選擇題，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為( )。 A． (n1)/2 B. n/2 C. (n+1)/2 D. n3．適用于折半查找的表的存儲(chǔ)方式及元素排列要求為( ) A．鏈接方式存儲(chǔ)，元素?zé)o序 B．鏈接方式存儲(chǔ)，元素有序C．順序方式存儲(chǔ)，元素?zé)o序 D．順序方式存儲(chǔ)，元素有序3．當(dāng)采用分塊查找時(shí)，數(shù)據(jù)的組織方式為 ( ) 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．正確 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è)再散列法解決沖突，則放入的位置的下標(biāo)是( ) A．8 B．3 C．5 D．9 二、填空題1. 順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為_(kāi)_ __次；當(dāng)使用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)為_(kāi)_ __。2. 在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關(guān)鍵碼值20，需做的關(guān)鍵碼比較次數(shù) 為_(kāi) _次.3．在散列存儲(chǔ)中，裝填因子α= ，α的值越大，表明__ _ _；α的值越小，表明__ __。三．解答題 輸入一個(gè)正整數(shù)序列（53,17,12,66,58,70,87,25,56,60），試完成下列各題。（1） 按次序構(gòu)造一棵二叉排序樹(shù)BS。（2） 依此二叉排序樹(shù)，如何得到一個(gè)從大到小的有序序列？（3） 寫(xiě)出在此二叉排序樹(shù)中查找“66”過(guò)程中進(jìn)行比較的數(shù)值序列。第九章 排序已知10個(gè)數(shù)據(jù)元素為（54，28，16，34，73，62，95，60），對(duì)該數(shù)列按從小到大排序，分別寫(xiě)出直接插入排序、希爾排序（d=4 ,2 ,1）、起泡排序、簡(jiǎn)單選擇排序和歸并排序5種排序方法每一趟排序后的序列。答案第一章答案. 數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算輸入 輸出 有窮性 確定性 可行性線性結(jié)構(gòu)和非線性結(jié)構(gòu)數(shù)據(jù)元素之間的邏輯關(guān)系 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示順序順序比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小 (每個(gè)節(jié)點(diǎn)都由數(shù)據(jù)域和指針域組成，所以相同空間內(nèi)假設(shè)全存滿的話順序比鏈?zhǔn)酱鎯?chǔ)更多)。邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。插入、刪除靈活 (不必移動(dòng)節(jié)點(diǎn)，只要改變節(jié)點(diǎn)中的指針)。查找結(jié)點(diǎn)時(shí)鏈?zhǔn)酱鎯?chǔ)要比順序存儲(chǔ)慢。每個(gè)結(jié)點(diǎn)是由數(shù)據(jù)域和指針域組成。時(shí)間復(fù)雜度 空間復(fù)雜度1是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并由計(jì)算機(jī)程序處理的符號(hào)的總稱。2數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體考慮。一個(gè)數(shù)據(jù)元素由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位3數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)元素類中各數(shù)據(jù)元素之間存在的關(guān)系4數(shù)據(jù)的邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)之間關(guān)系的描述，有時(shí)就把邏輯結(jié)構(gòu)簡(jiǎn)稱為數(shù)據(jù)結(jié)構(gòu)。邏輯結(jié)構(gòu)形式地定義為（K，R）（或（D，S）），其中，K是數(shù)據(jù)元素的有限集，R是K上的關(guān)系的有限集。5數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示。6對(duì)于數(shù)據(jù)結(jié)構(gòu)課程而言，簡(jiǎn)單地說(shuō)，線性結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有序（次序）集合。它有四個(gè)基本特征：1．集合中必存在唯一的一個(gè)第一個(gè)元素；2．集合中必存在唯一的一個(gè)最后的元素；3．除最后元素之外，其它數(shù)據(jù)元素均有唯一的后繼；4．除第一元素之外，其它數(shù)據(jù)元素均有唯一的前驅(qū)。數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)指的是數(shù)據(jù)元素之間存在著“一對(duì)一”的線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。如（a1,a2,a3,.....,an）,a1為第一個(gè)元素，an為最后一個(gè)元素，此集合即為一個(gè)線性結(jié)構(gòu)的集合。相對(duì)應(yīng)于線性結(jié)構(gòu)，非線性結(jié)構(gòu)的邏輯特征是一個(gè)結(jié)點(diǎn)元素可能對(duì)應(yīng)多個(gè)直接前驅(qū)和多個(gè)后繼。常用的線性結(jié)構(gòu)有：線性表（包括順序表和鏈表），棧，隊(duì)列，雙隊(duì)列，數(shù)組，串。關(guān)于廣義表，是一種非線性的數(shù)據(jù)結(jié)構(gòu)。常見(jiàn)的非線性結(jié)構(gòu)有：二維數(shù)組，多為數(shù)組，廣義表，樹(shù)(二叉樹(shù)等)，圖(網(wǎng)等)。7第二章作業(yè)一、 判斷題(在你認(rèn)為正確的題后的括號(hào)中打√，否則打X)。1。（2，4，6，8，9：√； 1，3，5，7，10：x）二、單項(xiàng)選擇題。 1~5Aadc bd 6~12abdca cb 第三章作業(yè)Aab4．如圖所示，設(shè)輸入元素的順序是A，B，C，D，通過(guò)棧的變換，在輸出端可得到各種排列。若輸出序列的第一個(gè)元素為D，則輸出序列為_(kāi)__DCBA____________。5．隊(duì)列中允許進(jìn)行刪除的一端為_(kāi)___隊(duì)首______。，則對(duì)輸入序列a,b,c,d,e進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為_(kāi)__bceda__。第五章數(shù)組和廣義表單項(xiàng)選擇題。 (1)空的廣義表是指廣義表（ D ）。 A．深度為0 B．尚未賦值 C．不含任何原子元素 D．不含任何元素 (2)廣義表中元素分為（ C ）。 A．原子元素 B．表元素 C．原子元素和表元素 D．任意元素 (3)廣義表的長(zhǎng)度是指（ A ）。 A．廣義表中元素的個(gè)數(shù) B．廣義表中原子元素的個(gè)數(shù) C．廣義表中表元素的個(gè)數(shù) D．廣義表中括號(hào)嵌套的層數(shù) (4)廣義表的深度是指（ D ）。 A．廣義表中元素的個(gè)數(shù) B．廣義表中原子元素的個(gè)數(shù) C．廣義表中表元素的個(gè)數(shù) D．廣義表中括號(hào)嵌套的層數(shù) (5)在一個(gè)長(zhǎng)度為n，包含m個(gè)原子元素的廣義表中，（ B ）。 A．m和n相等 B．m不大于n C．m不小于n D．m與n無(wú)關(guān) (6)廣義表A=(( )，(a)，(b，(c，d)))的長(zhǎng)度為（ B ）。 A．2 B．3 C．4 D．5 (7)廣義表A：(( )，(a)，(b，(c，d)))的深度為（ B ）。 A．2 B．3 C．4 D．55．設(shè)有一5階上三角矩陣A［1..5，1..5］，現(xiàn)將其上三角中的元素按列優(yōu)先順序存放在一堆數(shù)組B［1..15］中。已知B［1］的地址為100，每個(gè)元素占用2個(gè)存儲(chǔ)單元，則A［3，4］的地址為（　C　?。〢．116 B．118 C．120 D．122，可應(yīng)用的串運(yùn)算是( D ) ，則C數(shù)組的大