專業 00計算機班級學號姓名
一、 填空題（2分x 15=30分）
1．n行n列的下三角矩陣a[n][n]，採用壓縮儲存到一維陣列s[n*(n+1)/2]中，若按以行序為主儲存，則a[i][j]對應的s中的儲存位置是 （1） 。
2．fifo是英文 （2） 的縮寫，表示 （3） 結構。
3．lifo是英文 （4） 的縮寫，表示 （5） 結構。
4．.一棵二叉樹有23個結點，這些結點的度要麼是0，要麼是2。這棵二叉樹中度為2的結點有 （6） 個。
5. 在乙個無環有向圖g中，若存在一條從頂點i到頂點j的弧，則在頂點的拓撲序列中，頂點i與頂點j的先後次序是 （7） 。
6. 已知乙個有向圖的鄰接矩陣表示，計算第i個結點的度的方法是 （8） 。
7．乙個有向圖的鄰接表中，若表結點的個數是m，則圖中邊的條數是（9）條。
8．判定乙個有向圖是否存在迴路除了可以利用深度優先遍歷演算法外，還可以利用 （10）。
9. 設乙個閉雜湊表的容量為m，用線性探測法解決衝突，要插入乙個鍵值，若插入成功，至多要進行 （11） 次比較。
10．二分查詢的儲存結構僅限於 （12） 。
11. 在插入排序、希爾排序、快速排序、堆排序、歸併排序中，排序是不穩定的有 （13） 。
12．在堆排序和快速排序中，若原始記錄無序，則最好選用 （14） 。
13. 將兩個長度分別m和n（m>n）的排好序的表歸併成乙個排好序的表，至少要進行（15）次鍵值比較。
二、 應用題 （選7題x10分=70分）
1． 用給出的一組字元a，b，c，d，e，f，g的權值是，建立一棵哈夫曼樹，並給出每個字元的哈夫曼編碼。
2． 依次把結點插入到初始狀態為空的平衡二叉樹中,使得在每次插入後保持該樹仍然是平衡二叉樹。依次畫出每次插入後所形成的平衡二叉樹。
3． 畫出對長度為9的有序表進行二分查詢的一棵判定樹，並求其等概率時查詢成功的平均查詢長度。
4． 使用雜湊函式h(key)=key % 9，把乙個整數值轉換成雜湊表下標，現要把資料1，13，12，34，38，33，27，22插入到雜湊表中（表長為9）。
1）使用線性探測法構造雜湊表。
2) 使用鏈位址法構造雜湊表。
5． 對於g1所示的連通圖，請畫出：
1） 以頂點1為根的深度優先生成樹；
2） 如果有關節點，請找出所有的關節點(計算機專業做)
6． 對於g2所示的無向圖，採用克魯斯卡爾演算法構造最小生成樹（要求畫出構造過程的每一步）。
7． 對於如圖g3所示的aoe網，求出各事件、各活動可能的最早開始時間和允許的最晚完成時間及活動的時間餘量，並問哪些活動是關鍵活動。
8． 對於有向無環圖g4，畫出圖的鄰接表，並根據該鄰接表寫出拓撲有序序列。
9． 對資料(46,25,78,12,62,38)進行直接插入排序,請寫出排序的每趟的過程。（計算機專業不做）
10． 對資料序列(46,25,78,12,62,31,80,29)進行快速排序,請寫出排序的第一趟排序的詳細過程
11．將資料序列(28,76,54,39,87,14,46,25,78,62)按shell排序法進行排序,增量序列為5，3，1，請寫出每倘排序完成之後的序列狀態。
12. 將資料(46,15,78,29,62,37,70,12)進行降序排序,請寫出堆排序的初建堆過程。
13. 將資料序列(46,35,78,12,62,38,80,29)進行歸併排序,請寫出每趟排序過程。
14. 將資料序列(986,321,123,432,500,654,018,765,987,210)進行基數排序,請寫出每趟分配、收集排序過程。
專業班級學號姓名
一、 填空（2分x15=30分）
（1）（2）
（3）（4）
（5）（6）
（7）（8）
（9）（10）
（11）
（12）
（13）
（14）
(15)
資料結構b卷答案：
一、填空（2分x15=30分）
（1） i*(i+1)/2+j
（2） first in first out
（3） 佇列
（4） last in first out
（5） 棧
（6） 11
（7） 不變
（8） 第i 行及第i列非零元素之和
（9） m./2
（10）拓撲排序
（11）m
（12）有序的順序表
（13）希爾排序、快速排序、堆排序
（14）快速排序
（15）m
資料結構與拓撲資料結構
資料結構在gis中對於資料的採集 儲存 查詢 檢索和應用分析等操作方式有著重要的影響，一種高效率的資料結構應該具備以下幾個要求 1 組織的資料能夠表示要素之間的層次關係，便於不同資料聯絡於覆蓋 2 正確反映地理實體之間的空間排列方式和各實體之間的相互關係 3 便於訪問與檢索 4 節省儲存空間，減少資...
06 07資料結構與演算法B卷
江西財經大學 06 07第一學期期末考試試卷 試卷 03266b授課課時 112 課程名稱 資料結構與演算法適用物件 本科 一 單項選擇題 從下列各題四個備選答案中選出乙個正確答案，並將其代號寫在答題紙相應位置處。答案錯選或未選者，該題不得分。每小題2分，共24分。1.資料結構被形式地定義為 k,r...
《資料結構》作業
本課程作業由兩部分組成。第一部分為 客觀題部分 由選擇題組成，每題1分，共15分。第二部分為 主觀題部分 由簡答題和應用題組成，共15分。作業總分30分，將作為平時成績記入課程總成績。客觀題部分 一 選擇題 每題1分，共10題 1 順序儲存結構中資料元素之間的邏輯關係是由 表示的。a.線性結構 b....