北師大數(shù)院12-13年數(shù)據(jù)結構試卷A+答案

1、北京師范大學20122013學年第 1 學期期末考試試卷（A卷）課程名稱： 數(shù)據(jù)結構 任課教師姓名： 劉玉銘 卷面總分： 100 分 考試時長： 120 分鐘 考試類別：閉卷 院（系）： 數(shù)學科學學院 專 業(yè)： 年級： 2011 姓 名： 學 號： 題號第一題第二題第三題第四題總分得分閱卷教師（簽字）： 裝 訂 線一、 單項選擇題（每題2分，共10題20分）題號12345678910答案CADDDABBAC1 從邏輯上可以把數(shù)據(jù)結構分為 兩大類。A 動態(tài)結構、靜態(tài)結構 B 順序結構、鏈式結構C 線性結構、非線性結構 D 初等結構、構造型結構2 在雙向鏈表中，刪除p所指的結點時修改指針_。Ap-

2、>next->prior=p->prior; p->prior->next=p->next;Bp->next=p->next->next; p->next-prior=p;Cp->prior->next=p; p->prior=p->prior->prior;Dp->prior=p->next->next; p->next=p->prior->prior;3 已知二維數(shù)組A46采用列序為主序方式存儲，每個元素占用4個存儲單元，并且A34的存儲地址為1234，元素A00的

3、存儲地址是（ ）。 A1322B1146C1310D11584 設樹T 的度為4，其中度為1，2，3 和4 的結點個數(shù)分別為4，2，1，1 ，則T 中的葉子數(shù)為_。A5B6C7D85 由3 個結點可以構造出多少種不同的二叉樹？_。A2B3C4D56 已知一棵二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBAEDF，則后序遍歷的結果為_。ACBEFDABFEDCBACCBEDFAD不定7 為便于判別有向圖中是否存在回路，可借助于_。A廣度優(yōu)先搜索算法B拓撲排序算法C最短路徑算法D最小生成樹算法 8 具有n個頂點的無向連通圖至少含有的邊數(shù)為( )。AnBn-1Cn+1D2n9 具有12 個關

4、鍵字的有序表，折半查找的平均查找長度_。A. 3.1B. 4C. 2.5D. 510 用某種排序方法對序列（25，84，21，47，15，27，68，35，20）進行排序，記錄序列的變化情況如下，則采取的排序方法是_。（25，84，21，47，15，27，68，35，20）（15，20，21，25，47，27，68，35，84）（15，20，21，25，35，27，47，68，84）（15，20，21，25，27，35，47，68，84）A直接選擇排序B冒泡排序C快速排序D二路歸并排序二、 判斷（每題1分，共10題10分）題號12345678910答案×××

5、15;××1 順序存儲方式只能用于存儲線性結構。2 棧和隊列都是限制存取點的線性結構。3 若輸入序列為1，2，3，4，5，6，則通過一個?？梢暂敵鲂蛄?，5，4，6，2，3。4 稀疏矩陣壓縮存儲后，必會失去隨機存取功能。5 數(shù)組可看成線性結構的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。6 廣義表中的元素或者是一個不可分割的原子，或者是一個非空的廣義表。 LS = ( a1, a2, ×××, an )其中：ai 或為原子 或為廣義表7 采用二叉鏈表作存儲結構，樹的先根序遍歷和其相應的二叉樹的先根序遍歷的結果是一樣的。8 用一維數(shù)

6、組存儲二叉樹時，總是以先根序遍歷順序存儲結點。9 有n個頂點的無向圖, 采用鄰接矩陣表示, 圖中的邊數(shù)等于鄰接矩陣中非零元素個數(shù)之和的一半。10 Hash 表的平均查找長度與處理沖突的方法無關。三、 填空題（每題2分，共10題20分）1 已知指針 p 指向單鏈表L 中的某結點，則刪除其后繼結點的語句是： p->next = p->next->next; free(p); 。2 表達式 a+(b*c-d)/e+f*g/h)+i/j 的后綴表達式是： abc*d-e/fg*h/+ +ij/+ 。3 循環(huán)隊列用數(shù)組A0.m-1存放其元素值，已知其頭尾指針分別是front 和rear

7、 ，則當前隊列的元素個數(shù)是： (rear front + m) % m 。4 廣義表 A =（a，b），（c，d，e），取出A 中的原子e 的操作是： Head(Tail(Tail(Head(Tail(Head(A) 。5 在一棵二叉樹中，度為零的結點的個數(shù)為n0,度為2 的結點的個數(shù)為n2,則有： n0 = n2 + 1 。6 高度為8 的完全二叉樹至少有 26 = 64 個葉子結點。7 己知有序表為(12,18,24,35,47,50,62,83,90,115，134)，當用二分法查找90 時，需比較 2 次查找成功。8 非葉子結點最大深度為3 的3 階B-樹中，最多有 2+2*3+2*9

8、 = 26 個關鍵字。9 高度為5（除葉子層之外）的 3 階B-樹中，至少有 31 個結點。10 設用希爾排序對數(shù)組98，36，-9，0，47，23，1，8，10，7進行排序，給出的步長（也稱增量序列）依次是4，2，1，寫出第一趟結束后，數(shù)組中數(shù)據(jù)的排列次序： 10，7，-9，0，47，23，1，8， 98， 36 。四、 簡答題（每題5分，共10題50分）1 畫出廣義表（a，b），（），c，（d）的存儲結構圖（采用頭尾指針的鏈表結構，標志1表示表結點，標志0表示原子結點）0a1··0b0c0d1··1·1··11·

9、;·1·1·2 已知樹的先根序列和后根序列分別為 ABCEFGD 和 BEGFCDA，請畫出該樹對應的二叉樹，并畫出這棵樹。ABCDEFG ABCDEFG3 設用于通信的電文由6個字母A，B，C，D，E，F(xiàn)組成,各個字母在電文中出現(xiàn)的頻率分別為0.10，0.34，0.08，0.16，0.20，0.12，試填寫下表構造赫夫曼樹，為這8個字母設計哈夫曼編碼，(同一層的左子樹根權值小于右子樹根權值)0.100.200.340.120.160.080.180.280.380.621.000000011111B 11F 100D 101C 000A 001E 01字符wei

10、ghtparentlchildrchild1A0.107002B0.3410003C0.087004D0.168005E0.209006F0.1280070.1893180.28106490.381175100.621182111.000910字符ABCDEF編碼00111000101011004 對下面的3 階B-樹，依次執(zhí)行下列操作，畫出各步操作的結果，（1）插入26 （2） 插入853 12 451002461 7053 9030 37503 12 4510024 3061 7053 90375026 45 7010061 535085903 12 24 3037265 對如圖的鄰接表，

11、從項點v2開始進行深度優(yōu)先搜索，寫出深度優(yōu)先遍歷時訪問頂點的順序，并畫出相應的深度優(yōu)先生成樹。v1v2v3v4v5v6v7v8從項點v2開始進行深度優(yōu)先遍歷時訪問頂點的順序：v2-v4-v1-v8-v3-v6-v5-v76 求出下面AOE網的所有關鍵活動（列出所有頂點的最早發(fā)生時間ve、最遲發(fā)生時間vl，和所有活動弧的最早發(fā)生時間ee、最遲發(fā)生時間el）拓撲序列：146235789頂點vevl活動eeelV100a100V266a202V346a303V458a466V577a546V6710a658V71516a778V81414a877V91818a9710a101516a111414關鍵

12、活動：a1, a4, a8, a117 使用普里姆算法構造，在如圖所示的圖G中，從結點A開始構造圖G的一棵最小生成樹（畫出每一步生成的子樹）。ABCDEF812951615247A AC1 ACE14ACDE514 ACDEF5124 ABCDEF516248 已知散列表的地址空間為A0.11，散列函數(shù) H（k）= k mod 11，采用平方探測法處理沖突。請將下列數(shù)據(jù)26,25,23,33,21,24,45依次插入到散列表中，并計算出在等概率情況下查找成功時的平均查找長度。關鍵字26252333212445哈希值43101021哈希地址01234567891011關鍵字33232425264

13、521比較次數(shù)1111141等概率情況下查找成功時的平均查找長度： (1+1+1+1+1+4+1)/7=10/79 根據(jù)序列 31、19、23、45、63、15、57、9，建立一個大頂堆。（畫出畫出主要過程）453157196323159 453123196357159453123631957159 31632345195715910 給出一組關鍵字 T = (12，2，16，30，8，28，4，10，20，6，18)，設內存工作區(qū)可容納4 個記錄，寫出用置換-選擇排序得到的全部初始歸并段。12，2，16，30，8，28，4，10，20，6，188，28，4，10，20，6，1812，2，16，3028，4，10，20，6，1812，8，16，3024，10，20，6，1812，28，16，302，810，20，6，184，28，16，302，8，1220，6，184，2