【正文】 的數(shù)目等于圖中邊的數(shù)目 B．矩陣中非全零的行的數(shù)目等于圖中頂點的數(shù)目 C．第i行的非零元素的數(shù)目與第i列的非零元素的數(shù)目相等 D．第i行與第i列的非零元素的總數(shù)等于第i個頂點的度數(shù) (15)若從無向圖的任意一個頂點出發(fā)進行一次深度優(yōu)先搜索便可以訪問該圖的所有頂點，則該圖一定是一個( B )圖。 A．一定是無向圖 B。 A．一般矩陣 B．對稱矩陣 C．對角矩陣 D．稀疏矩陣 (8)若圖的鄰接矩陣中主對角線上的元素均為0，其余元素全為1，則可以斷定該圖一定 ( C ). A．是無向圖 B．是有向圖 C．是完全圖 D．不是帶權(quán)圖 (9)有向圖的鄰接表的第i個鏈表中的邊結(jié)點數(shù)目是第i個頂點的( B )。 A．n(n1)/2 B．n(n1) C．n(n+1)/2 D．n(2) (4)在一個具有n個頂點的無向圖中，要連通全部頂點至少需要(C )條邊。 (X )（12，13可不掌握） 二、單項選擇題。 (√ ) (10)對圖進行廣度優(yōu)先搜索的過程中要用到隊列。 (X ) (6)鄰接矩陣主要用來表示頂點之間的關(guān)系。 (X ) (2)在有向圖中，所有頂點的入度之和等于所有頂點的出度之和。 (14)已知某完全二叉樹采用順序存儲結(jié)構(gòu)，結(jié)點的存放次序為A,B，C,D，E，F(xiàn)，G，H，I，J，該完全二叉樹的后序序列為_____HDEBFGCA_________。 (10)若具有n個結(jié)點的非空二叉樹．樹有N0個葉結(jié)點，則該二叉樹有_______n01_____個度為2的結(jié)點，____n2n0+1________個度為1的結(jié)點。 (6)非空二叉樹中第i層最多有______ 2i1_________個結(jié)點。 (2)樹的層次定義為__樹中結(jié)點的最大層數(shù)__________________。(i≤h) ( B ) A．2i—1 B．2i1 C．2h—1 D．2h1 (6)深度為h的滿二叉樹共有( C )個結(jié)點。 A．有序的數(shù)據(jù)元素 B．無序的數(shù)據(jù)元素 C．?dāng)?shù)據(jù)元素之間具有層次關(guān)系的數(shù)據(jù) D．?dāng)?shù)據(jù)元素之間沒有關(guān)系的數(shù)據(jù) (2)按照二叉樹的定義，具有3個結(jié)點的二叉樹有( D )種形態(tài)(不考慮數(shù)據(jù)信息的組合情況)。 (X ) (14)哈夫曼樹中不存在度為1的結(jié)點。 (√ )(10)在所有深度相同的二叉樹中，滿二叉樹具有最大結(jié)點數(shù)目。 (X ) (6)在完全二叉樹中，沒有左孩子的結(jié)點一定是葉結(jié)點。 (√ ) (2)在樹型結(jié)構(gòu)中，每—個結(jié)點不能沒有前驅(qū)結(jié)點。 A．2 B．3 C．4 D．55．設(shè)有一5階上三角矩陣A［1..5，1..5］，現(xiàn)將其上三角中的元素按列優(yōu)先順序存放在一堆數(shù)組B［1..15］中。 A．廣義表中元素的個數(shù) B．廣義表中原子元素的個數(shù) C．廣義表中表元素的個數(shù) D．廣義表中括號嵌套的層數(shù) (4)廣義表的深度是指（ D ）。第五章數(shù)組和廣義表單項選擇題。 1~5Aadc bd 6~12abdca cb 第三章作業(yè)Aab4．如圖所示，設(shè)輸入元素的順序是A，B，C，D，通過棧的變換，在輸出端可得到各種排列。常見的非線性結(jié)構(gòu)有：二維數(shù)組，多為數(shù)組，廣義表，樹(二叉樹等)，圖(網(wǎng)等)。如（a1,a2,a3,.....,an）,a1為第一個元素，an為最后一個元素，此集合即為一個線性結(jié)構(gòu)的集合。5數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示。2數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體考慮。插入、刪除靈活 (不必移動節(jié)點，只要改變節(jié)點中的指針)。寫出在此二叉排序樹中查找“66”過程中進行比較的數(shù)值序列。三．解答題 輸入一個正整數(shù)序列（53,17,12,66,58,70,87,25,56,60），試完成下列各題。 A． (n1)/2 B. n/2 C. (n+1)/2 D. n3．適用于折半查找的表的存儲方式及元素排列要求為( ) A．鏈接方式存儲，元素?zé)o序 B．鏈接方式存儲，元素有序C．順序方式存儲，元素?zé)o序 D．順序方式存儲，元素有序3．當(dāng)采用分塊查找時，數(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ù)個數(shù)需相同4．二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。 A．k1 B．k C．2k D．K2 (13)若有向圖有k條邊，則相應(yīng)的鄰接表中就有( )個邊結(jié)點。 A．一定有奇數(shù)個頂點 B．一定有偶數(shù)個頂點 C．一定是有向圖 D。 A．n B．n+1 C．n1 D．2n (6)在帶權(quán)圖中，兩個頂點之間的路徑長度是( )。 A．1／2 B．1 C．2 D．4 (2)一個具有n個頂點的無向圖最多有( )條邊。 ( )(9) 設(shè)有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d，則e和d的關(guān)系為e=d。 ( ) (5)連通圖的最小生成樹是唯一的。 (1)n個頂點的無向圖最多有n(n1)條邊。 (13)已知二叉樹的前序遍歷序列為ABDCEFG，中序遍歷序列為DBCAFEG，其后序遍歷序列為__________。 (9)若二叉樹有N0個葉結(jié)點，n2個度為2的結(jié)點，則N0與n2的關(guān)系是________ ______。 (5)非空二叉樹一共有_______________種基本形態(tài)。 (1)任何非空樹中有且僅有一個結(jié)點沒有前驅(qū)結(jié)點，該結(jié)點就是樹的______ ______。 A．512 B．1024 C．2048 D．4096 (5)深度為h的滿二叉樹的第i層有( )個結(jié)點。 (1)樹型結(jié)構(gòu)最適合用來描述( )。 ( )(13)由二叉樹的前序序列和后序序列可以唯一地確定一棵二叉樹。 (9)滿二叉樹中的每個結(jié)點的度不是0就是2。 ( ) (5)在非空完全二叉樹中，只有最下面一層的結(jié)點為葉結(jié)點。 (1)在樹型結(jié)構(gòu)中，每一個結(jié)點最多只有一個前驅(qū)結(jié)點，但可以有多個后繼結(jié)點。 A．m和n相等 B．m不大于n C．m不小于n D．m與n無關(guān) (6)廣義表A=(( )，(a)，(b，(c，d)))的長度為（ ）。 A．深度為0 B．尚未賦值 C．不含任何原子元素 D．不含任何元素 (2)廣義表中元素分為（ ）。5．隊列中允許進行刪除的一端為___ ______。 D. plink = s。 B. slink = plink。 //數(shù)據(jù) struct node * Link。1≤i≤n十1，刪除表的第i個數(shù)據(jù)元素，首先需要移動表中( )個數(shù)據(jù)元素。 A．第1個單元的地址 B．第2個單元的地址 C．第3個單元的地址 n第4個單元的地址，每個元素占用4個存儲單元，第1個元素的存儲地址為100， 則第12個元素的存儲地址是( )。 4．用鏈表表示線性表的優(yōu)點是 （ ）。 2．對順序存儲的線性表，設(shè)其長度