2022年數(shù)據(jù)結(jié)構(gòu)考試題6

1、要求：所有的題目的解答均寫在答題紙上（每張答題紙上要寫清楚姓名、班號和學號） ，需寫清楚題目的序號。每張答題紙都要寫上姓名和序號。一、單項選擇題（每小題2 分，共 20 分）1. 在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲。a. 數(shù)據(jù)的處理方法b. 數(shù)據(jù)元素的類型c. 數(shù)據(jù)元素之間的關系d. 數(shù)據(jù)的存儲方法2. 下述函數(shù)中對應的漸進時間復雜度（n 為問題規(guī)模）最小是。a.t1(n)=nlog2n+5000n b.t2(n)=n2- 8000n c.t3(n)= nn2log- 6000n d.t4(n)=7000log2n 3. 設線性表有n 個元素，以下操作中，在順序表上實現(xiàn)比

2、在鏈表上實現(xiàn)效率更高。a.輸出第 i（1in）個元素值b.交換第 1 個元素與第2 個元素的值c.順序輸出這n 個元素的值d.輸出與給定值x 相等的元素在線性表中的序號4. 設 n 個元素進棧序列是p1，p2，p3，pn，其輸出序列是1，2，3，n，若 p3=3，則 p1的值。a.可能是 2 b.一定是 2 c.不可能是1 d.一定是 1 5. 以下各種存儲結(jié)構(gòu)中，最適合用作鏈隊的鏈表是。a.帶隊首指針和隊尾指針的循環(huán)單鏈表b.帶隊首指針和隊尾指針的非循環(huán)單鏈表c.只帶隊首指針的非循環(huán)單鏈表d.只帶隊首指針的循環(huán)單鏈表6. 對于鏈串s （長度為n，每個結(jié)點存儲一個字符），查找元素值為ch 的算

3、法的時間復雜度為。a.o(1) b.o(n) c.o(n2) d.以上都不對7. 設二維數(shù)組a610 ，每個數(shù)組元素占用4 個存儲單元，若按行優(yōu)先順序存放的數(shù)組元素 a35 的存儲地址為1000，則 a00 的存儲地址是。a.872 b.860 c.868 d.864 8. 一個具有1025 個結(jié)點的二叉樹的高h 為。a.11 b.10 c.111025 d.121024 9. 一棵二叉樹的后序遍歷序列為dabec ，中序遍歷序列為debac ，則先序遍歷序列為。a.acbed b.decab c.deabc d.cedba 10. 對圖 1 所示的無向圖， 從頂點 1 開始進行深度優(yōu)先遍歷；

4、可得到頂點訪問序列。精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁，共 7 頁 - - - - - - - - -精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁，共 7 頁 - - - - - - - - -2 數(shù)據(jù)結(jié)構(gòu)期末考試試題（共3 頁）a.1 2 4 3 5 7 6 b.1 2 4 3 5 6 7 c.1 2 4 5 6 3 7 d.1 2 3 4 5 7 6 1 2 3 4 5 6 7 圖 1 一個無向圖二、填空題 （每題 2 分，共 10 分）1. 順序隊和鏈隊的區(qū)別僅在于的不同

5、。2. 在有 n 個頂點的有向圖中，每個頂點的度最大可達。3. 對有18 個元素的有序表r1.18 進行二分查找，則查找r3 的比較序列的下標為。4. 對含有 n 元素的關鍵字序列進行直接選擇排序時，所需進行的關鍵字之間的比較次數(shù)為。5. 已知關鍵字序列為2,7,4,3,1,9,10,5,6,8 ，采用堆排序法對該序列作升序排序時，構(gòu)造的初始堆（大根堆）是。 （不用畫出堆，只需寫出初始堆的序列）三、問答題（共 40 分）1. 一棵完全二叉樹上有1001 個結(jié)點，其中葉結(jié)點的個數(shù)是多少？（需寫出推導過程，8分）2. 給出如下各種情況下求任意一個頂點的度的過程（只需文字描述）： （8 分）（1）含

6、 n 個頂點的無向圖采用鄰接矩陣存儲；（2）含 n 個頂點的無向圖采用鄰接表存儲；（3）含 n 個頂點的有向圖采用鄰接矩陣存儲；（4）含 n 個頂點的有向圖采用鄰接表存儲。3. 將整數(shù)序列 4,5,7,2,1,3,6 中的數(shù)依次插入到一棵空的平衡二叉樹中，試構(gòu)造相應的平衡二叉樹。（要求畫出每個元素插入過程，若需調(diào)整，還需給出調(diào)整后的結(jié)果，并指出是什么類型的調(diào)整，12 分）4. 當實現(xiàn)插入直接排序過程中，假設r0.i-1 為有序區(qū)， ri.n-1 為無序區(qū)，現(xiàn)要將ri 插入到有序區(qū)中，可以用二分查找來確定ri 在有序區(qū)中的可能插入位置，這樣做能否改善直接插入排序算法的時間復雜度?為什么 ?（8

7、分）5. 簡述外排序的兩個階段。（4 分）四、算法設計題 （每小題 10 分，共 30 分）1. 設計一個算法delminnode(linklist *&l)， 在帶頭結(jié)點的單鏈表l 中刪除所有結(jié)點值最小的結(jié)點（可能有多個結(jié)點值最小的結(jié)點）。2. 假設二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲，設計一個算法copy(btnode *b,btnode *&t) ，由二叉樹b 復制成另一棵二叉樹t。3. 假設一個無向圖是非連通的，采用鄰接表作為存儲結(jié)構(gòu)，試設計一個算法，輸出圖精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁，共 7 頁 - - -

8、 - - - - - -精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁，共 7 頁 - - - - - - - - -數(shù)據(jù)結(jié)構(gòu)期末考試試題（共3 頁）3 中各連通分量的節(jié)點序列。精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 3 頁，共 7 頁 - - - - - - - - -精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 3 頁，共 7 頁 - - - - - - - - -4 數(shù)據(jù)結(jié)構(gòu)期末考試試題（共3 頁）參考答案一、單項選擇題（每小題2 分，共

9、20 分）1. c 2. d 3. a 4. a 5. b 6. b 7. b 8. c 9. d 10. a 二、填空題 （每題 2 分，共 10 分）1. 存儲方法或存儲結(jié)構(gòu)。2. 2(n-1)。3. 9、 4、2、3 4. n(n-1)/2。5. 10,8,9,6,7,2,4,5,3,1。 （序列不全對不給分）三、問答題（共 40 分）1. 答：二叉樹中度為1 的結(jié)點個數(shù)只能是1 或 0。設 n1=1，n=n0+n1+n2=n0+n2+1=1001，由性質(zhì) 1 可知 n0=n2+1，由兩式可求n0=500.5，不成立；設n1=0，n=n0+n1+n2=n0+n2=1001，由性質(zhì) 1 可

10、知 n0=n2+1，由兩式可求n0=501。本題答案為：501。評分標準：只給出結(jié)果給3 分，推導過程占5 分。2. 答：對于鄰接矩陣表示的無向圖，頂點i 的度等于第i 行中元素等于1 的個；對于鄰接矩陣表示的有向圖，頂點i 的出度等于第i 行中元素等于1 的個數(shù)；入度等于第i 列中元素等于 1 的個數(shù)；度數(shù)等于它們之和。對于鄰接矩陣表示的無向圖，頂點i 的出度等于g-adjlisti 為頭結(jié)點的單鏈表中結(jié)點的個數(shù)；入度需要遍歷各頂點的邊表，若g-adjlistk 為頭結(jié)點的單鏈表中存在頂點編號為i 的結(jié)點，則頂點i 的入度增1；度數(shù)等于它們之和。評分標準：有向圖、無向圖兩種存儲方式各占4 分

11、。3. 建立平衡二叉樹過程如圖2 所示 (圖中加陰影的結(jié)點表示要調(diào)整的結(jié)點)。精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁，共 7 頁 - - - - - - - - -精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁，共 7 頁 - - - - - - - - -數(shù)據(jù)結(jié)構(gòu)期末考試試題（共3 頁）5 lr 調(diào)整1 2 -1 0 0 0 -2 -1 0 0 0 插入 5 插入 4 4 5 7 4 插入 7 5 4 7 rr 調(diào)整5 4 插入 2 1 0 1 7 5 4 0 2 插入 1 2 0

12、 7 5 4 2 0 1 1 0 0 7 5 2 0 1 0 4 ll 調(diào)整插入 3 插入 6 2 -1 0 7 5 2 0 1 1 4 0 3 0 0 -1 5 4 2 0 1 0 3 0 7 -1 0 -2 5 4 2 0 1 0 3 1 7 0 6 rl 調(diào)整0 0 -0 6 4 2 0 1 0 3 0 7 0 5 圖 2 構(gòu)造平衡二叉樹過程評分標準：每次調(diào)整占1 分。4.答：不能。因為在這里，二分查找只減少了關鍵字間的比較次數(shù)，而記錄的移動次數(shù)不變，時間的復雜度仍為o(n2)。評分標準：答對“不能”占3 分，說明理由占5 分。5. 答：生成初始歸并段（或順串），采用多路平衡歸并方法進行

13、歸并。四、算法設計題 （共 30 分）1. 解：用 p 從頭至尾掃描單鏈表，pre 指向 *p 結(jié)點的前驅(qū)， 用 minp 保存值最小的結(jié)點指針， minpre 指向 *minp結(jié)點的前驅(qū)。一面掃描，一面比較，將最小值的結(jié)點放到*minp中。算法如下：void delminnode(linklist *&l) 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁，共 7 頁 - - - - - - - - -精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁，共 7 頁 - - - - - -

14、 - - -6 數(shù)據(jù)結(jié)構(gòu)期末考試試題（共3 頁）linklist *pre=l,*p=pre-next,*minp=p,*minpre=pre; elemtype mindata=p-data; while (p!=null & p-datadata; p=p-next; p=pre-next; while (p!=null) if (p-data=mindata) pre-next=p-next; free(p); pre=pre-next; p=pre-next; 評分標準：根據(jù)算法的正確性評分，不考慮算法的時間復雜度。2解：遞歸算法如下：void copy(btnode *b,b

15、tnode *&t) btnode *l,*r; if (b=null) t=null; else t=(btnode *)malloc(sizeof(btnode); copy(b-lchild,l); copy(b-rchild,r); t-lchild=l; t-rchild=r; 評分標準：根據(jù)算法的正確性評分，不考慮算法的時間復雜度。3. 解：采用深度優(yōu)先搜索遍歷非連通圖，并輸出各連通分量節(jié)點序列的算法如下：dfsgraph(agraph *g) int i,j=1; /用 j 記錄連通分量的序號for (i=0;in;i+) if (visitedi=0) printf(第%d 個連通分量節(jié)點序列:,j+); 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 6 頁，共 7 頁 - - - - - - - - -精品學習資料 可選擇p d f -