1、數(shù)據(jù)結(jié)構(gòu)與算法二您的姓名： 填空題 *一、單選題深度優(yōu)先搜索遍歷類似于二叉樹的（）. *先序遍歷先序遍歷(正確答案)中序遍歷后序遍歷按層次遍歷v的度是關(guān)聯(lián)于該頂點（）的數(shù)目. 單選題 *頂點頂點邊(正確答案)序號下標n個頂點的無向圖的鄰接矩陣是用（）數(shù)組存儲。. 單選題 *一維一維nn列(正確答案)n列n行任意列ne條邊的無向圖，采用鄰接表表示，則表頭向量大小為（）. 單選題 *n-1n-1n+1n(正確答案)n+ek1,k2單鏈表中的結(jié)點數(shù)為（）. 單選題 *k1k1k2(正確答案)k1-k2k1+k2廣度優(yōu)先遍歷類似于二叉樹的（）. 單選題*先序遍歷先序遍歷中序遍歷后序遍歷按層次遍歷(正確

2、答案)任何一個無向連通圖的最小生成樹（）. *只有一棵只有一棵有一棵或多棵(正確答案)一定有多棵可能不存在二、多選題在某圖中，下列選項中說法不正確的是（）. *A. A. 不存在頂點到自身的邊，或者重復(fù)的邊，則該圖是簡單圖不存在頂點到自身的邊，或者重復(fù)的邊，則該圖是復(fù)雜圖不存在頂點到自身的邊，或者重復(fù)的邊，則該圖是復(fù)雜圖(正確答案)不存在頂點到自身的邊，或者重復(fù)的邊，則該圖是無向圖(正確答案)不存在頂點到自身的邊，或者重復(fù)的邊，則該圖是有向圖(正確答案)有關(guān)圖的說法不正確的是（）. *有向圖的邊是有向的，又稱為弧有向圖的邊是有向的，又稱為弧有向圖的邊是有向的，又稱為箭頭(正確答案)(正確答案)

3、無正確答案(正確答案)關(guān)于有向圖的說法不正確的是（）*有向圖邊是有向的有向圖邊是有向的有向圖邊是無向的(正確答案)有向圖邊是可以有向也可以無向(正確答案)無正確答案(正確答案)對圖中頂點的集合，不正確的是（）. *可以為空可以為空(正確答案)不可以為空空與不空都可以(正確答案)都不對(正確答案)對圖的邊或弧上的數(shù)的說法錯誤的是（）. *量量(正確答案)值(正確答案)權(quán)重(正確答案)三、判斷題有向圖不能進行廣度優(yōu)先遍歷。（）. *對對錯(正確答案)V1則可以唯一確定該圖。（）. 單選題 *對對(正確答案)錯的頂點，則該圖一定是連通的。（）. 單選題*對對(正確答案)錯無向邊是指沒有方向的邊。（）

4、. 單選題*對對(正確答案)錯個數(shù)無關(guān)。（）. *對對錯(正確答案)圖的遍歷有：深度優(yōu)先搜索和廣度優(yōu)先搜索等方法。（） *對對(正確答案)錯對(正確答案)錯ne條邊的圖若采用鄰接矩陣存儲，則空間復(fù)雜度為：O（n*n）。對(正確答案)錯圖的逆鄰接表存儲結(jié)構(gòu)只適用于無向圖。（）. 單選題 *對對錯(正確答案)一、單選題在圖的表示法中，表示形式唯一的是（）單選題 *鄰接矩陣表示法鄰接矩陣表示法(正確答案)鄰接表表示法逆鄰接表表示法鄰接表和逆臨界表表示法ne條邊的圖中，所有頂點的度數(shù)之和等于（）. 單選題 *nne2n2e(正確答案)連通分量是（）的極大連通子圖. 單選題 *樹樹圖無向圖(正確答案)有

5、向圖下列關(guān)于圖的存儲結(jié)構(gòu)敘述正確的是（）. 單選題 *用鄰接矩陣存儲圖，占用空間大小只與圖中頂點數(shù)有關(guān)，而與邊數(shù)無關(guān)用鄰接矩陣存儲圖，占用空間大小只與圖中頂點數(shù)有關(guān)，而與邊數(shù)無關(guān)(案)用鄰接矩陣存儲圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點無關(guān)用鄰接表存儲圖，占用空間大小只與圖中頂點數(shù)有關(guān)，而與邊數(shù)無關(guān)用鄰接表存儲圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點數(shù)無關(guān)n，則該圖最多有（）條邊. 單選題 *n-1n-1n*nC. n(n+1)/2D. n(n-1)/2(正確答案)帶權(quán)的圖稱為（）單選題 *權(quán)權(quán)網(wǎng)(正確答案)有向圖路徑兩頂點之間的邊有方向，則該邊被稱為（）. 單選題 *無向邊無向邊有向邊

6、(正確答案)混合邊都不對無向圖的邊都是（）. 單選題 *A. A. 可以無向也可以有向有向的有向的無向的(正確答案)以上都不對二、多選題關(guān)于圖，下列選項中說法不正確的是（）. *任意兩頂點之間的邊都是有向邊，則該圖是有向圖任意兩頂點之間的邊都是有向邊，則該圖是有向圖任意兩頂點之間的邊都是有向邊，則該圖是無向圖(正確答案)(正確答案)無正確答案(正確答案)關(guān)于邊，下列選項中說法不正確的是（）. *兩頂點之間的邊有方向，則該邊被稱為無向邊兩頂點之間的邊有方向，則該邊被稱為無向邊(正確答案)兩頂點之間的邊有方向，則該邊被稱為有向邊兩頂點之間的邊有方向，則該邊被稱為混合邊(正確答案)無正確答案(正確答

7、案)無向圖中，兩頂點之間有邊則不正確的是（）. *互為兄弟互為兄弟(正確答案)互為堂兄弟(正確答案)互為鄰接點互為鄰居(正確答案)圖中的邊的集合錯誤的是（）. *不可以為空不可以為空(正確答案)必須為空(正確答案)可以為空D. D. 都不對(正確答案)圖按照邊的不同，可分為（）. *有向圖有向圖(正確答案)無向圖(正確答案)混合圖以上都不對三、判斷題圖的邊或弧上的數(shù)稱之為權(quán)。（）. *對對(正確答案)錯對(正確答案)錯i0Vi對(正確答案)錯圖是一對多的結(jié)構(gòu)（）. 單選題 *對對錯(正確答案)圖的存儲結(jié)構(gòu)有鄰接矩陣、鄰接表、十字鏈表。（）. 單選題 *對對(正確答案)錯有向圖中，指向該結(jié)點的弧

8、的數(shù)目稱之為入度。（）. 單選題 *A. A. 對(正確答案)B. B. 錯鄰接矩陣是圖的一種存儲結(jié)構(gòu)。（） *對對(正確答案)錯nn條邊。（） *對對錯(正確答案)一、單選題在順序表的查找中，順序查找是指（）. *跳躍式比較跳躍式比較用逐一比較的辦法順序查找關(guān)鍵字(正確答案)隨機選擇位置比較無正確答案關(guān)于關(guān)鍵字，下列選項中說法正確的是（）. 單選題 *主關(guān)鍵字是可以唯一標識一條記錄的關(guān)鍵字主關(guān)鍵字是可以唯一標識一條記錄的關(guān)鍵字(正確答案)主關(guān)鍵字是可以識別若干記錄的關(guān)鍵字主關(guān)鍵字是在表中出現(xiàn)的次數(shù)很多的關(guān)鍵字無正確答案關(guān)于查找表，以下說法正確的是（）. *若查找表中存在特定元素稱為查找失敗若

9、查找表中存在特定元素稱為查找失敗若查找表中存在特定元素稱為查找中若查找表中存在特定元素稱為未找到D. D. 若查找表中存在特定元素稱為查找成功(正確答案)對線性表進行折半查找時，要求線性表必須（）單選題 *以順序方式存儲以順序方式存儲以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排序以鏈接方式存儲以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序(正確答案)查找表是以（）為查找結(jié)構(gòu). 單選題 *集合集合(正確答案)圖樹文件衡量查找算法效率的主要標準是（）. *元素個數(shù)元素個數(shù)所需的存儲量平均查找長度(正確答案)算法難易程度在表長為的鏈表中進行線性查找，它的平均查找長度為（）. *ASLASLnASL(n+1)/2(正

10、確答案)C. ASLn(1/2) + 1D. ASLlog2n鏈表適用于（）查找. 單選題 *A. A. 順序(正確答案)二分二分隨機順序或二分二、多選題11率情況下查找成功所需的平均比較次數(shù)不為（）. *A. 33/11A. 33/11B.34/11(正確答案)C.32/11(正確答案)D.35/11(正確答案)順序查找法不適合于（）的存儲結(jié)構(gòu). *散列存儲散列存儲(正確答案)順序存儲或鏈接存儲(正確答案)(正確答案)n的線性表時，時間復(fù)雜度不是（）（）. *OO（n*n）(正確答案)O（nlog2n）(正確答案)O（n）(正確答案)O（log2n）12. 有一個有序表為1，3，9，12，3

11、2，41，45，62，75，77，82，95，100，當折半查找值為 82 的結(jié)點時，查找成功后的比較次數(shù)不是（）. *A. 1A. 1(正確答案)正確答案)48(正確答案)對于靜態(tài)表的順序查找法，若在表頭設(shè)置崗哨，則正確的查找方式不為（）. *0個元素往后查找該數(shù)據(jù)元素(正確答案)n個元素往開始前查找該數(shù)據(jù)元素1個元素往后查找該數(shù)據(jù)元素(正確答案)與查找順序無關(guān)(正確答案)三、判斷題順序查找法的平均查找長度為（n+1）/2。（）. 單選題 *對對(正確答案)錯查找表是不同類型的數(shù)據(jù)元素構(gòu)成的集合。（）. 單選題 *對對錯(正確答案)靜態(tài)查找表是查找特定元素的查找表。（）. 單選題 *對對(正

12、確答案)錯關(guān)鍵字是用于標識一個數(shù)據(jù)元素的某個數(shù)據(jù)項的值。（）. *對對(正確答案)錯對錯(正確答案)在有序的順序表和有序的鏈表上，均可以采用二分查找來提高查找速度。對錯(正確答案)順序查找法，表中元素可以任意存放。（）. 單選題 *對對(正確答案)錯順序查找不屬于靜態(tài)查找。（）. 單選題*對對錯(正確答案)一、單選題邊查找，邊改變集合內(nèi)的元素的查找表是（）. 單選題 *靜態(tài)查找表靜態(tài)查找表動態(tài)查找表(正確答案)混合查找表都不對52的結(jié)點的數(shù)目是（）. 單選題 *6654(正確答案)3根據(jù)二叉排序樹的特點，查找過程類似于（）. 單選題 *順序查找順序查找折半查找(正確答案)隨機查找都不對二叉排序

13、樹是否可能是一棵完全二叉樹（）單選題 *不可能不可能可能(正確答案)不確定能不能都不對3層最多有多少個結(jié)點（）. 單選題 *22正確答案)81數(shù)據(jù)結(jié)構(gòu)中，只查找，不改變集合內(nèi)的元素的查找表是（）. *動態(tài)查找表動態(tài)查找表靜態(tài)查找表(正確答案)混合查找表都不對數(shù)據(jù)結(jié)構(gòu)與算法里，根據(jù)二叉排序的定義可知（）. 單選題 *二叉排序樹的右子樹上結(jié)點的值小于根結(jié)點的值二叉排序樹的右子樹上結(jié)點的值小于根結(jié)點的值二叉排序樹的右子樹上結(jié)點的值大于根結(jié)點的(正確答案)二叉排序樹的右子樹上結(jié)點的值等于根結(jié)點的值D. D. 二叉排序樹的右子樹上結(jié)點的值小于等于根結(jié)點的值數(shù)據(jù)結(jié)構(gòu)與算法里，關(guān)于二叉排序樹的遞歸性說法對的

14、是（）. *二叉排序樹的左子樹也是任意二叉樹二叉排序樹的左子樹也是任意二叉樹二叉排序樹的左子樹也是二叉排序樹(正確答案)二叉排序樹的左子樹也是普通樹以上都不對二、多選題二叉排序的的哪些遍歷序列，不能得到一個升序序列，或非遞減有序序列（）. *先序序列先序序列(正確答案)中序序列后序序列(正確答案)按層次遍歷序列(正確答案)已知一棵樹是二叉排序樹，則該樹滿足（）. *若左子樹不為空，則左子樹上的所有結(jié)點的值（關(guān)鍵字）若左子樹不為空，則左子樹上的所有結(jié)點的值（關(guān)鍵字）(正確答案)若右子樹不為空，則右子樹上的所有結(jié)點的值（關(guān)鍵字）(正確答案)左、右子樹都分別為二叉排序樹；(正確答案)其中序序列是一個

15、非遞減有序序列；(正確答案)動態(tài)查找不包括（）查找. *順序查找順序查找(正確答案)二叉排序樹有序表(正確答案)索引順序表(正確答案)動態(tài)查找表：邊查找，邊改變集合中的元素，改變的方式可以是（）. *增加增加(正確答案)刪除(正確答案)移動交換關(guān)于二叉排序樹描述有誤的是（）. *二叉排序的右子樹上結(jié)點的關(guān)鍵字小于左子樹上的結(jié)點的關(guān)鍵字二叉排序的右子樹上結(jié)點的關(guān)鍵字小于左子樹上的結(jié)點的關(guān)鍵字(正確答案)二叉排序的左子樹上結(jié)點的關(guān)鍵字小于右子樹上的結(jié)點的關(guān)鍵字(正確答案)二叉排序的根結(jié)點的關(guān)鍵大于左子樹上結(jié)點的關(guān)鍵字三、判斷題（）. 單選題 *對對(正確答案)錯動態(tài)查找表：表結(jié)構(gòu)在查找過程中動態(tài)生

16、成。（）. 單選題 *對對(正確答案)錯動態(tài)查找常用的是二叉排序樹。（）. *對對(正確答案)錯的相應(yīng)的指針域置空即可。（）. 單選題 *對對錯(正確答案)在二叉排序樹中，根結(jié)點的值都小于孩子結(jié)點的值。（）. *對對錯(正確答案)動態(tài)查找表屬于集合結(jié)構(gòu)。（）. 單選題*對對錯(正確答案)對(正確答案)錯二叉排序樹根的左子樹上的結(jié)點的值都小于根的右子樹上的結(jié)點的值。對(正確答案)錯一、單選題數(shù)據(jù)結(jié)構(gòu)與算法里，關(guān)于二叉排序樹的中序序列描述正確的是（）. 單選題 *二叉排序樹的中序遍歷序列是升序序列二叉排序樹的中序遍歷序列是升序序列(正確答案)二叉排序樹的中序遍歷序列是降序序列二叉排序樹的中序序遍歷

17、列是亂序序列無正確答案二叉排序樹是（）經(jīng)常使用的方式. 單選題*動態(tài)查找動態(tài)查找(正確答案)靜態(tài)查找隨機查找D. D. 都不對二叉排序樹的定義具有（）性. 單選題 *反復(fù)反復(fù)遞歸(正確答案)回溯都不對先序遍歷一顆二叉排序樹的順序是（）. *(正確答案)都不對只查找不改變集合內(nèi)的元素的查找表是（）. 單選題 *動態(tài)查找動態(tài)查找靜態(tài)查找(正確答案)不確定都不對二叉排序樹的（）上結(jié)點的值都小于根結(jié)點的值。. 單選題 *左子樹左子樹(正確答案)右子樹左子樹和右子樹都不對數(shù)據(jù)結(jié)構(gòu)與算法里，關(guān)于二叉排序樹的遍歷順序說法正確的是（）. 單選題 *A. A. 中序遍歷一顆二叉排序樹的順序是：左子樹 根結(jié)點 右

18、子樹(正確答案)無正確答案0時，描述正確的是（）. 選題 *0個結(jié)點，這時它是一棵空二叉排序樹(正確答案)0個結(jié)點，這時它是一棵滿二叉排序樹0個結(jié)點，這時它是一棵完全二叉排序樹無正確答案二、多選題下列選項中說法正確的是（）. *(正確答案)查找表有動態(tài)查找表法(正確答案)查找表分為混合查找表查找表分為物理查找表O(n)是以下哪種算法的復(fù)雜度（）. *順序表直接獲取某個下標位置的值順序表直接獲取某個下標位置的值順序表刪除元素(正確答案)(正確答案)i個元素(正確答案)查找的結(jié)果可能在集合中也可能不在集合中，分別稱為（）. *查找成功查找成功(正確答案)查找失敗(正確答案)C. C. 不確定D.都不對查找表采用順序存儲結(jié)構(gòu)簡稱為順序表，順序表的查找方式有（）. *折半查找折半查找(正確答案)順序查找(正確答案)隨機查找都不對正確答案)正確答案)GH正確答案)