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