。擔(dān)由此引。擔(dān)由此引起的一切場紀律，并知道考專 班 學(xué)號 學(xué)生簽名數(shù)據(jù)結(jié)構(gòu)課 課程類別：必修課閉題—二三四五六七八九 分注意：除第一大題外其余各題答案必須填寫在后面的答題一．選擇填空題（1－5題每空2分，6－13題每空1分已知P結(jié)點是某雙向鏈表的中間從下列提供的答案在P結(jié)點后插入S結(jié)點的語句序列 G_L_F C_在P結(jié)點前插入S結(jié)點的語句序列是_H_M_E_D 刪除P結(jié)點的直接后繼結(jié)點的語句序列是_OKAR刪除P結(jié)點的直接前驅(qū)結(jié)點的語句序列是_ J_BR_刪除P結(jié)點的語句序列 I_N_Q （A）p->next=p->next->next;(B)p->prior=p->prior-(C)p- (D)p- (E)s-(I)p->prior->next=p->next;(J)Q->prior-=p（L）p-（M）p->prior->prior（O）Q=（P）Q=p- (R)表長為13希表中已填有關(guān)鍵字為23，46，69,28的記錄，用除留余數(shù)法構(gòu)造哈希函數(shù)現(xiàn)有第5，6個記錄，其關(guān)鍵字為35，39按二次探測再散列的方法處理，將它填入表中相應(yīng)的位置。2題35在下標為11位置，39填在下標為73題4題根據(jù)上圖判斷下列拓撲序列不正確的 C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C1—C3—C2--C4--C5--C7--C9--C10--C11--C6--C12--C1—C4—C2—C3--C5--C7--C9--C10--C11--C6--C12--寫出第4題圖中所有的關(guān)鍵路徑 在下圖中那種序列是深度優(yōu)先遍歷序 5題 (B) (D)在順序表上做插入運算，平均要移動表中一半元素。當表長n大時，算法的效率相當?shù)汀⒁豢糜?9個結(jié)點的完全二叉樹到右依次對結(jié)點進行根結(jié)點的號碼為1，則編號為50的結(jié)點的左孩子編號為D.(A)98(B99(C)100(D8．n個頂點的完全有向圖中含有邊的條數(shù) B (A) (B)n(n- (C) (D)棧和隊列的共同特點 D (A)都是先進后 （B）都是先進先（C）沒有共同點（D）許在端點處插入和刪 即數(shù)據(jù)之間的相互關(guān)系和數(shù)據(jù)的 物理結(jié)構(gòu) 即數(shù)據(jù)結(jié)構(gòu)在計在循環(huán)鏈表中，可以根據(jù)任一結(jié)點的地址遍歷整個鏈表，而單鏈表中需知道 表頭結(jié)點 才能遍歷整個鏈表。12．棧通常采用的兩種結(jié)構(gòu) C 。（A）循環(huán)和鏈式結(jié)構(gòu)（B）散列和索引結(jié)（C）鏈式和數(shù)組結(jié)構(gòu) （D）線性和非線性結(jié)構(gòu) 二．簡答題（60分在棧的操作中，進棧順123456，問能否得到435612135426的出棧序列明為什么不能得到或如何能得（即寫出以push（S，X）表示進棧和以pop（S，X）表示出棧的操作序列（6利用廣義表的GetTail和GetHead操作寫出函數(shù)表達式L3從下面的廣義表中取L3（4分＝（（（，試分別畫出具有三個結(jié)點的樹和三個結(jié)點的二叉樹的所同形態(tài)（7分已知一棵二叉樹的先序系列為ABDGHJKECFIM,中序序列GDJHKBEACFMI,試畫出此二（7分）分別對下圖按普里姆算法（從A結(jié)點開始）和克魯斯卡爾算法畫出其最小生成樹（8分）18題假設(shè)用于通信的電文由八個字母A,B,C,D,E,F,G,H組成，字母在電文中出現(xiàn)的頻率分別為 0.19,0.02,0.06,0.32,0.21,0.10為這八個字母設(shè)計哈夫曼樹且分別寫出其哈夫曼編碼，計算其帶權(quán)路徑長度WPL（8分）記錄的關(guān)鍵字序列42，45，78，86,試構(gòu)造一棵二叉排序樹，并寫出其構(gòu)造過分21題利用迪杰斯特拉(Dijkstra)算法求上圖中從頂點0到其他各頂點間的最短