數據結構期末考試試題數據結構期末考試試題數據結構期末考試試題資料僅供參考文件編號：2022年4月數據結構期末考試試題版本號：A修改號：1頁次：1.0審核：批準:發(fā)布日期：1．線性鏈表不具有的特點是（）。A．隨機訪問B．不必事先估計所需存儲空間大小C．插入與刪除時不必移動元素D．所需空間與線性表長度成正比2．設一個棧的輸入序列為1，2，3，4，則輸出序列不可能是()。A．1,2,3,4B．4,3,2,1C．1,3,2,4D．4,1,2,33．下列排序算法中，()排序在每趟結束后不一定能選出一個元素放到其排好序的最終位置上。A．歸并B．冒泡C．選擇D．堆4．下列序列中，()是執(zhí)行第一趟快速排序后得到的序列(排序的關鍵字類型是字符串)。A．[da,ax,eb,de,bb]ff[ha,gc]B．[cd,eb,ax,da]ff[ha,gc,bb]C．[gc,ax,eb,cd,bb]ff[da,ha]D．[ax,bb,cd,da]ff[eb,gc,ha]5．設有一個10階的對稱矩陣A[10][10]，采用壓縮存儲方式按行將矩陣中下三角部分的元素存入一維數組B[]中，A[0][0]存入B[0]中，則A[8][5]在B[]中（）位置。A．32B．33C．41D．656.下面哪一種圖的鄰接矩陣肯定是對稱矩陣()。A．有向圖B．無向圖C．AOV網D．AOE網7．具有2008個結點的二叉樹，其深度至少為()。A．9B．10C．11D．128.關鍵路徑是邊表示活動的網（AOE網）中的()。A．從源點到匯點的最長路徑B．從源點到匯點的最短路徑C．最長的回路D．最短的回路9．一個廣義表為(a,(a,b),d,e,((i,j),k))，則該廣義表的長度為()。A．不確定B．8C．5D．610．設循環(huán)隊列中數組的下標范圍是0～n–1，其頭尾指針分別為f和r，則其元素個數為()。A．r–fB．r–f+1C．(r–f)modn+1D．(r–f+n)modn1．算法具有的五個重要特性是：有窮性，確定性，_______，輸入和輸出。2．一組記錄的關鍵字為（45,80,55,40,42,85），則利用堆排序的方法建立的初始堆為____________。3．對如下無向圖G，從結點V1出發(fā)，寫出一個按深度優(yōu)先遍歷圖的結點序列：__________________。V1eq\o\ac(○,1)V1V6V2eq\o\ac(○,2)eq\o\ac(○,5)V6V2V8V7V4V3eq\o\ac(○,3)eq\o\ac(○,4)V8V7V4V3V5第3題圖eq\o\ac(○,6)第4題圖V54．寫出右上圖中的一個拓撲有序序列____________________。5．對于順序存儲的線性表，訪問結點和刪除結點的時間復雜度分別為_____________。6．平衡二叉樹上所有結點的平衡因子只可能是________________。7．假定對線性表R[1..60]進行分塊查找，共分為10塊，每塊長度等于6。若假定查找索引表和塊均用順序查找的方法，則查找每一個元素的平均查找長度為___________。8．將一棵有100個結點的完全二叉樹從根這一層開始，每一層上從左到右依次對結點進行編號，根結點的編號為1，則編號為37的雙親結點編號為_______。9．設有一個字符串s=’science’，其非空子串的數目是________。10．有n個頂點的強連通有向圖G至少有________條弧。一棵二叉樹的先序序列和中序序列分別如下，先序序列：ABCDEFGHIJ中序序列：CBDEAGIHJF畫出該二叉樹。（3分）寫出其后序序列。（3分）2．給出用Kruskal算法構造下列帶權圖的最小生成樹的過程。V1V23V1V2V3V3V6V6V4V4V5V53.已知一個長度為12的表（6，8，4，12，2，10，7，3，9，1，11，5）。（1）將表中的元素依次插入到一個初始為空的二叉排序樹中，畫出該二叉排序樹并求其在等概率下的平均查找長度。（3分）（2）若先對表中的記錄排序，構成有序表后再對其進行折半查找，畫出判定樹并求其在等概率下的平均查找長度。（3分）4．已知哈希表地址空間為0..10，哈希函數為H(key)=keyMOD11，采用鏈地址法處理沖突，將下面數據序列依次插入該哈希表中，并求出在等概率下查找成功時的平均查找長度。12，24，1，34，38，44，27，22。5．假定用于通信的電文僅由8個字母a，b，c，d，e，d，f，g，h組成，各個字母在電文中出現的頻率分別為5，23，3，6，10，11，36，4。要求：（1）以這些頻率作為葉子結點的權值構造Huffman樹。（2分）（2）試為這8個字母設計不等長Huffman編碼。（2分）Abcdefgh

（3）計算出電文總長度。（2分）

1.有兩個不帶頭結點的單循環(huán)鏈表，鏈表頭指針分別為a和b。編寫一個過程將鏈表b鏈到鏈表a之后，鏈接后的鏈表仍保持循環(huán)鏈表形式。2.試編寫一個計算二叉樹的葉子結點數的算法。要求二叉樹采用鏈式存儲結構。3.請寫出監(jiān)視哨設在高下標端的插入排序算法。0621.具有n(n>0)個結點的完全二叉樹的深度為（）A.log2nB.log2nC.log2n+1D.log2n+12.一個棧的進棧序列是a，b，c，d，e，則棧的不可能的輸出序列是（）3.數據在計算機存儲器內表示時，物理地址與邏輯地址相同且連續(xù)，稱之為（）A.存儲結構B.邏輯結構C.順序存儲結構D.鏈式存儲結構4.對二叉排序樹的左子樹中所有結點與右子樹中所有結點的關鍵字大小關系是()A.小于B.大于C.等于D.不小于5.按照二叉樹的定義，具有3個節(jié)點的二叉樹______種（）D.56.廣義表（（a））的表尾是()A．aB.（a）C．（）D.(（a）)7．設有兩個串p和q，求在q在p中首次出現的位置的運算稱為（）A.模式匹配B.連接C.求子串D.求串長8.引入二叉線索樹的目的是（）A．加快查找結點的前驅或后繼的速度B．為了能在二叉樹中方便的進行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結果唯一9．在有n個葉子結點的哈夫曼樹中，其結點總數為A.不確定+110．與單鏈表相比，雙向鏈表的優(yōu)點之一是A．插入、刪除更簡單B.可以進行隨機訪問C．可以省略表頭指針或表尾指針D.訪問前后相鄰結點更方便1．Prim算法適合求__________的網的最小生成樹，而Kruskal算法適用于求___________的網的最小生成樹。2.循環(huán)單鏈表L為空的條件是________________。3.在對隊列中，新插入的元素只能插入到___________。4．平衡二叉樹上所有結點的平衡因子只可能是________________。5．一個有序表{1，3，9，12，32，41，45，62，75，77，82，95，99}，當采用折半查找法查找關鍵字為82的元素時，_______________次比較后查找成功。6．設二維數組A[6][10],每個數組元素占4個存儲單元，若按行優(yōu)先順序存放數組元素，A[0][0]的存儲地址是860，則A[3][5]的存儲地址是_______________。7．可以進行拓撲排序的一定是______________。8．求單鏈表長度算法的時間復雜度是________。9.在直接插入排序、希爾排序、直接選擇排序、快速排序、堆排序和歸并排序中，平均比較次數最少的排序方法是________________。1.已知一個二叉樹的中序遍歷序列為DGBAECF,后序遍歷序列為GDBEFCA,請給出：畫出該二叉樹。（3分）寫出其后序序列。（3分）．對關鍵字序列{11,78,10,1,3,2,4,21}構造哈希表，取散列地址為HT[0..10]，散列函數為H(K)＝K％11，試用線性探查法沖突，畫出相應的哈希表，并分別求查找成功和不成功時的平均查找長度。3.已知關鍵字序列{503，87，512，61，908，170，897，275，653，462}，采用快速排序算法對該序列作升序排序時的每一趟的結果。4.從一棵空樹開始，逐個讀入并插入下列關鍵字：{40，28，6，72，100，3，54，1，80，91，38}請首先建立二叉排序樹，然后刪除節(jié)點72，并給出刪除節(jié)點72后的二叉樹。給定權集W={2,3,4,7,8,9},試構造關于W的一棵哈夫曼樹，并求帶權路徑長度WPL。1.有一個有序單鏈表（從小到大排序），表頭指針為L，設計一個算法向該單鏈表中插入一個元素為x的結點，并使插入后鏈表仍然有序。2.二叉樹采用鏈式存儲結構，試編寫算法求二叉樹的深度。3..二叉樹采用鏈式存儲結構，試設計一個按層次順序（同層自左向右）遍歷二叉樹的算法。答案A選擇題（每小題2分，共20分）二、填空題（每小題2分，共20分）1．可行性2．（85,80,55,40,42,45）3．V1,V2,V3,V5,V4,V6,V7,V8(答案不惟一)4．1,2,3,5,6,4(答案不惟一)5.O(1)和O(n)6.–1,0,17.98.189.2610．n三、解答下列各題(每小題6分，共30分)1．該二叉樹為（3分）：ABFCDGEHIJ后序序列：CEDBIJHGFA（3分）2．V1V2V1V2V1V2111V3V6V3V6V3V611V4V5V5V42V5（2分）（1分）（1分）V13V2V13V2114V3V6V3V611V42V5V42V5（1分）（1分）3．（1）二叉排序樹為：648257121310911（2分）等概率下平均查找長度ASL=（1+2*2+3*4+4*3+5*2）/12=13/4=（1分）（2）排序后進行折半查找的判定樹為：639147112581012（2分）等概率下平均查找長度ASL=（1+2*2+3*4+4*5）/12=37/12（1分）第1頁(共3頁)4．哈希函數值為：（1分）H(12)=1H(24)=2H(1)=1H(34)=1H(38)=5H(44)=0H(27)=5H(22)=0哈希表為：（3分）022441112342243452738678910平均查找長度ASL=(1×4+2×3+3×1)/8=13/8=（2分）5．（1）Huffman樹為：（2分）9839591722233671011113456（2）其huffman編碼為（2分）注：此題答案不唯一，只要滿足哈夫曼編碼的要求都可。abcdEfgH01001000000101001011110001（3）電文總碼數為4*5+2*23+4*3+4*6+3*10+3*11+2*36+4*4=253（2分）四、算法設計(每小題10分，共30分)說明：每小題中：1．思路正確3分2．算法正確5分3．算法完整2分（1）typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidConnect(LinkLista,LinkListb){ey>[i+1].key)

{

[k+1].key=[i].key;ey>[j].key;++j)

[j-1]=[j];（1）二叉樹是：（4分）（2）后序序列為：GDBEFCA（2分）2.解：首先求出散列地址，據此得到哈希表見下圖。012345678910117813242110查找成功的平均比較次數為：ASL＝(1＋1＋2＋1＋3＋2＋8＋l)／8＝查找不成功的平均查找長度為：ASLunsucc＝(8＋7＋6＋5＋4＋3＋2＋1＋1＋1＋9)／11≈3.每趟快速排序的結果如下：{4628727561170}503{8979086535