數(shù)據(jù)結(jié)構(gòu)樣卷一．判斷題(15分)1．(0)線性表的各種基本操作在順序存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)均比在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)效率要低。2．(0)一個(gè)有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)一定相等。3．(1)先序遍歷森林和先序遍歷與該森林相對應(yīng)的二叉樹，其結(jié)果不同。4．(1)不使用遞歸，也可實(shí)現(xiàn)二叉樹的先序、中序和后序遍歷。5．(1)散列法存儲(chǔ)的基本思想是由關(guān)鍵字的值決定數(shù)據(jù)的存儲(chǔ)地址。6．(1)采用折半查找法對有序表進(jìn)行查找總是比采用順序查找法對其進(jìn)行查找要快。7．(0)在任何情況下，快速排序方法的時(shí)間性能總是最優(yōu)的。(0)二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。(0)拓?fù)渑判蚴且环N內(nèi)部排序方法。10．(0)數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式。二．單選題(每個(gè)選擇項(xiàng)2分，共20分)1.單循環(huán)鏈表的主要優(yōu)點(diǎn)是(D)。不再需要頭指針已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨在進(jìn)行插入，刪除運(yùn)算時(shí)，能更好地保證鏈表不斷開從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用(D)存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表 B.單鏈表 C.雙鏈表 D.單循環(huán)鏈表3.在Hash函數(shù)H(k)=kMODm中，一般來講，m應(yīng)取(C)。A.奇數(shù) B.偶數(shù) C.素?cái)?shù) D.充分大的數(shù)4.圖的深度優(yōu)先遍歷算法類似于二叉樹的(A)，廣度優(yōu)先遍歷算法類似于二叉樹的(D)。D.層次遍歷D.層次遍歷((),(),())A.先序遍歷 D.層次遍歷D.層次遍歷((),(),())對樹而言，不合適的遍歷方法是(D )。A.先序遍歷 B.中序遍歷 C.后序遍歷若廣義表A滿足Head(A)==Tail(A)，則A為(B)。A.() B.(()) C.((),())D.下列二叉樹中，(A)可用于實(shí)現(xiàn)符號(hào)的不等長高效編碼。A.最優(yōu)二叉樹B.B-樹 C.二叉平衡樹 D二叉排序樹若進(jìn)棧序列為1234,則不能得到(B )的出棧序列。A.1342 B.1423 C.1243 D.1432TOC\o"1-5"\h\z9?循環(huán)隊(duì)列用數(shù)組A[m]存放其元素值，已知其頭尾指針分別是front和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是(D )。A.(rear—front+m)MODm B.rear—front+1C.rear—front-1 D.rear—front三.填空題(共20分，每空2分)1?對任何一棵二叉樹T,若其終端結(jié)點(diǎn)數(shù)為nO,度為2的結(jié)點(diǎn)數(shù)為n2,則n0與n2的關(guān)系為n0=n2+1 。折半插入排序是對直接插入排序算法的改進(jìn)，它著眼于減少 時(shí)間復(fù)雜度 。如果二叉樹中任何一個(gè)非終端結(jié)點(diǎn)的值都大于它的左子樹上所有結(jié)點(diǎn)的值而小于右子樹上所有結(jié)點(diǎn)的值，要得到各結(jié)點(diǎn)值的遞增序列，應(yīng)按 中序遍歷次序排列結(jié)點(diǎn)，這種樹稱為 二叉排序樹 。設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對出現(xiàn)的算法，采用 數(shù)據(jù)結(jié)構(gòu)最佳。具有n個(gè)頂點(diǎn)的無向完全圖的邊有_l/2*n(n-1) 條；具有n個(gè)頂點(diǎn)的有向完全圖的弧有_n*(n-1) 條。折半查找法適用于存儲(chǔ)結(jié)構(gòu)為 ，且按關(guān)鍵字排好序的線性表。棧和隊(duì)列是兩種特殊的線性表，棧的特點(diǎn)是 后進(jìn)先出 ;隊(duì)列的特點(diǎn)是 先進(jìn)先出 。四．簡答題(共30分，每題6分)日如圖1所示的二叉樹，.畫出其中序線索二叉樹；.畫出該二叉樹對應(yīng)的森林。某有向圖的鄰接表如圖2所示，試畫出該有向圖，并至少給出兩個(gè)拓?fù)渑判蛟谀惩ㄐ畔到y(tǒng)中，使用八個(gè)字母，這八個(gè)字母的使用頻率依次為23,2,16,18,16,7,10,8。試構(gòu)造一棵赫夫曼樹,并為這八個(gè)字母設(shè)計(jì)赫夫曼編碼。4．若要對關(guān)鍵字序列（25,86,23,46,68,35,72,54,24,32）由小到大進(jìn)行排序，請分別寫出采用下述排序方法的第一趟操作結(jié)果：快速排序法；基數(shù)排序法；起泡排序法。5.已知哈希函數(shù)為H（K）=Kmod13，關(guān)鍵字序列為25,37,52,43,84,99,120,15,26,11,70,82，采用鏈地址法處理沖突，試構(gòu)造此哈希表。五．算法設(shè)計(jì)題（共15分）設(shè)計(jì)一個(gè)判斷單鏈表（帶頭結(jié)點(diǎn)）L是否遞增有序的算法。（7分）設(shè)有兩個(gè)順序存儲(chǔ)的線性表A和B，A=0口2,…,am）,B=（b】?…,bn），現(xiàn)要按下列規(guī)則將B表合并到A表（假設(shè)A表空間足夠大），使