【正文】 標(biāo) 表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過 指針 表示元素之間的關(guān)系的。23．二維數(shù)組M的每個(gè)元素是6個(gè)字符組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M至少需要 540個(gè)字節(jié)；M的第8列和第5行共占108個(gè)字節(jié)。31．某二叉樹的前序遍歷序列是abdgcefh，中序序列是dgbaechf，其后序序列為 gdbehfca 。一個(gè)索引隸屬于某個(gè)數(shù)據(jù)記錄集，它由若干索引項(xiàng)組成，索引項(xiàng)的結(jié)構(gòu)為 關(guān)鍵字 和 關(guān)鍵字對應(yīng)記錄的地址 。（ ）5．線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。（ ）13．鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表，進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序表中效率高。（）20．?dāng)?shù)組元素的下標(biāo)值越大，存取時(shí)間越長。（ √ ）28．用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。( ) 36．冒泡排序算法關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)。（1）A ＝ ｛D，R｝，其中：D＝｛a，b，c，d，e，f，g，h｝，R ＝｛r｝，r ＝ ｛a，b，b，c，c，d，d，e，e，f，f，g，g，h｝（2）B ＝ ｛D，R｝，其中：D＝｛a，b，c，d，e，f，g，h｝，R ＝｛r｝，r ＝ ｛d，b，d，g，d，a，b，c，g，e，g，h，e，f｝（3）C ＝ ｛D，R｝，其中：D＝｛1，2，3，4，5，6｝，R ＝｛r｝，r ＝ ｛（1，2），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（4，6）｝2．簡述順序表和鏈表存儲(chǔ)方式的特點(diǎn)。如果輸入項(xiàng)序列由A，B，C組成，試給出全部可能的輸出序列。11．假設(shè)二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，如圖所示。17．對有五個(gè)頂點(diǎn){v1,v2,v3,v4,v5}的圖的鄰接矩陣如圖所示，解答下列問題：（1）畫出邏輯圖。21．使用克魯斯卡爾算法構(gòu)造出如圖所示的圖G的一棵最小生成樹。給出其鄰接矩陣和鄰接表表示。（1）給出按后序遍歷得到的數(shù)列R2。五、算法設(shè)計(jì)題。6．假設(shè)二叉樹采用鏈?zhǔn)酱鎯?chǔ)方式存儲(chǔ)，編寫一個(gè)二叉樹前序遍歷的非遞歸算法。12．有一個(gè)不帶頭結(jié)點(diǎn)的單鏈表L（至少有一個(gè)結(jié)點(diǎn)），其頭指針為head。14．在數(shù)組a[0…n1]中存放有n個(gè)不同的整數(shù)，請編寫一個(gè)函數(shù)，將a中的n個(gè)數(shù)按從小到大的順序排列，要求使用改進(jìn)的插入排序算法，元素a[i]要插入的位置由折半（二分）查找算法找到。10．編寫一個(gè)單鏈表倒鏈程序，即將單鏈表中每個(gè)結(jié)點(diǎn)的前驅(qū)與后繼關(guān)系顛倒。5．有一個(gè)不帶頭結(jié)點(diǎn)的單鏈表L（至少有一個(gè)結(jié)點(diǎn)），其頭指針為head。38．設(shè)散列表的長度m＝13（0，1，2，…，12），散列函數(shù)為H（k）＝k mod m，給定的關(guān)鍵字序列為{19，14，23，10，68，20，84，27，55，11}。（3）畫出在二叉樹bt中刪除“12”后的樹結(jié)構(gòu)。解答下列問題：（1）畫出相應(yīng)的AOE圖；（2）給出各事件的最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間；（3）找出關(guān)鍵路徑，并指明完成該工程所需最短時(shí)間；（4）若把AOE網(wǎng)視為AOV網(wǎng)，給出其一個(gè)拓?fù)湫蛄械睦?。并在給定的鄰接表的基礎(chǔ)上，指出從頂點(diǎn)1出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列。試畫出對應(yīng)的哈夫曼樹（請按左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造），并求出每個(gè)字符的哈夫曼編碼。（2） 寫出該樹的先序遍歷序列。（2）對帶頭結(jié)點(diǎn)的鏈表，表頭指針是指向頭結(jié)點(diǎn)的非空指針，因此空表與非空表的處理是一樣的。（ ）四、應(yīng)用簡答題。(√ )34．在平衡二叉樹中，任意結(jié)點(diǎn)左右子樹的高度差（絕對值）不超過1。（ √ ）26．度為2的有序樹是二叉樹。（ ）18．長度為1的串等價(jià)于一個(gè)字符型常量。（ ）11．取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān)。(√ )3．抽象數(shù)據(jù)類型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無關(guān)。37．已知圖G的鄰接表如圖所示，其從頂點(diǎn)v1出發(fā)的深度優(yōu)先搜索序列為_v1v2v3v6v5v4_，其從頂點(diǎn)v1出發(fā)的廣度優(yōu)先搜索序列為_v1v2v5v4v3v6__。29．深度為5的二叉樹至多有 31 個(gè)結(jié)點(diǎn)。 21．一個(gè)字符串中 任意個(gè)連續(xù)字符構(gòu)成的部分 稱為該串的子串。14．當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應(yīng)采用 順序 存儲(chǔ)結(jié)構(gòu)。6．?dāng)?shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法是 順序 、 鏈?zhǔn)? 、 索引 和 散列 存儲(chǔ) 。A．插入 B．選擇　 　 C．交換　　 D．歸并102． D 在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。D．沒有左子樹的二叉排序樹。A B樹和B+樹都能有效的支持順序查找 B B樹和B+樹都能有效的支持隨機(jī)查找C B樹和B+樹都是平衡的多叉樹 D B樹和B+樹都可用于文件索引結(jié)構(gòu)96．以下說法錯(cuò)誤的是 B 。A．a(chǎn) B （） C （a） D （（a））89．廣義表（（a））的表頭是 C ，表尾是 B 。 D ①只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0；②二叉樹的度為2；③二叉樹的左右子樹可任意交換；④深度為K的順序二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。A．方便運(yùn)算 B． 方便存儲(chǔ) C．提高運(yùn)算速度 D．減少存儲(chǔ)空間69．設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a1，1為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占1個(gè)地址空間，則a8，5的地址為 B 。A．連接 B． 模式匹配 C．求子串 D．求串長62．?dāng)?shù)組A中，每個(gè)元素的長度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素A[8][5]的起始地址為 C 。A．無法判斷隊(duì)列是否為空 B．無法判斷隊(duì)列是否為滿 C．隊(duì)列不可能滿 D．以上說法都不對54．若用一個(gè)大小為6的數(shù)值來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為 B 。h =sA．sttop != 1 B．sttop == 1 C．sttop != MaxSize D． sttop == MaxSize 44．判定一個(gè)順序棧st（最多元素為MaxSize）為滿的條件是 D 。C．pnext=s；pnext=snext D．pnext=snext；pnext=s36．線性表的順序存儲(chǔ)結(jié)構(gòu)是一種 A 。29．線性表是具有n個(gè) B 的有限序列。A．刪除單鏈表中的第一個(gè)元素B．刪除單鏈表中的最后一個(gè)元素C．在單鏈表第一個(gè)元素前插入一個(gè)新元素D．在單鏈表最后一個(gè)元素后插入一個(gè)新元素23．與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是 D 。A．head == NULL B headnext ==NULL C．headnext ==head D head!=NULL15．帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 B 。 i++) for(j=0。 in。A．邏輯 B．存儲(chǔ) C．邏輯和存儲(chǔ) D．物理4．在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ) C 。A．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu) B．?dāng)?shù)據(jù)結(jié)構(gòu) C．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu) D．?dāng)?shù)據(jù)元素之間的關(guān)系3．在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的 A 結(jié)構(gòu)。for( I =0。 in。A．可隨機(jī)訪問任一結(jié)點(diǎn) B．插入刪除不需要移動(dòng)元素C．不必事先估計(jì)存儲(chǔ)空間 D．所需空間與其長度成正比14．不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 A 。A．O（1） B．O（n） C．O（n2） D．O（nlog2n）22．在一個(gè)長度為n（n1）的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行 B 操作與鏈表的長度有關(guān)。C線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作。A．pnext=s；snext=pnext B． snext=pnext ；pnext=s。A．i B．n－i C．n－i＋1 D．不確定43．判定一個(gè)順序棧st（最多元素為MaxSize）為空的條件是 B 。C．snext=hA．對隊(duì)列中的元素排序 B．取出最近進(jìn)隊(duì)的元素 C．在隊(duì)頭元素之前插入元素 D．刪除隊(duì)頭元素53．對于循環(huán)隊(duì)列 D 。A．可以順序存儲(chǔ) B．?dāng)?shù)據(jù)元素是一個(gè)字符C．可以