《 資料結構試卷（ a卷）
考試時間：_ __分鐘閉卷
班級學號姓名成績
一、 單項選擇:（每空2分，共30分）
1. 資料結構是一門研究非數值計算的程式設計問題中,資料元素的① 、資料資訊在計算機中的② 以及一組相關的運算等的課程。
① a．操作物件 ｂ．計算方法 ｃ．邏輯結構 ｄ．資料映象
② a．儲存結構 ｂ．關係運算演算法
2. 線性表的邏輯順序與儲存順序總是一致的，這種說法__ _。
a. 正確b. 不正確
3. 乙個棧的入棧序列a，b，c，d，e，則棧的輸出序列是____。
a. edcba b. decba c. dceab d. abcde
4. 棧的特點是____，佇列的特點是____。
a. 先進先出 b. 先進後出
5．空串與空格串是相同的，這種說法____。
a. 正確 b. 不正確
6. 二維陣列a中，每個元素a的長度為3個位元組，行下標i從0到7，列下標j從0到9，從首位址sa開始連續存放在儲存器內，該陣列按行存放時，陣列元素a[7][4]的起始位址為____。
a. sa+141 b. sa+144 c. sa+222 d. sa+225
7. 如果某二叉樹的前根次序遍歷結果為stuwv，中序遍歷為uwtvs，那麼該二叉樹的後序為a. uwvts b.
vwuts c. wuvts d. wutsv
8. 深度為5的二叉樹至多有____個結點。
a. 16 b. 32 c. 31 d. 10
9．在乙個無向圖中，所有頂點的度數之和等於所有邊數的____倍。
a. 1/2 b. 1 c. 2 d. 4
10.採用順序查詢方法查詢長度為n的線性表時，每個元素的平均查詢長度為____.
a. n b. n/2 c. (n+1)/2 d. (n-1)/2
11. 採用二分查詢方法查詢長度為n的線性表時，每個元素的平均查詢長度為____。
a．o（n2） b. o(nlog2n) c. o(n) d. o(log2n)
12. 下述幾種排序方法中，要求記憶體量最大的是____。
a. 插入排序 b. 選擇排序 c. 快速排序 d. 歸併排序
13. 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為____。
a. 希爾排序 b. 起泡排序 c. 插入排序 d. 選擇排序
二、填空:（每空2分,共20分）
1. 分析下面演算法（程式段），給出最大語句頻度 ，該演算法的時間複雜度是__ __。
for (i=0;i for (j=0;j a[i][j]=0;
2. 在雙向鍊錶中，每個結點有兩個指標域，乙個指向____ __，另乙個指向___ __。
3．空串是其長度等於____。
4．折半查詢的儲存結構僅限於且是_ ___。
5．乙個圖的表示法是唯一的，而表示法是不唯一的。
三、用圖表回答下列問題:（共20分
1．設某通訊系統使用八a，b ，c，d，e，f，g，h個字元，他們出現的概率w試構造對應的哈夫曼樹（請按左子樹根結點的權小於右子樹樹根結點的權的次序構造）?
2．根據下面的鄰接鍊錶，畫出相應的圖，並寫出每個頂點的度。
四、閱讀下列演算法，分析它的作用：（每小題10分，共20分）
閱讀下列演算法，說明該演算法的作用。
elemttype sqstack::pop( )
return x;
} // pop
1 有如下圖所示單鏈表，經過reverse 演算法處理後，單鏈表發生了什麼變化？
畫出處理後的單鏈表圖示。
void link ::reverse()
// reverse
五、演算法設計題（共10分）
1. 寫一演算法，統計二叉樹的葉子結點的個數。
資料結構 試題
西南科技大學網路教育學院重修補考試題單 課程名稱 資料結構專業班級命題教師 孫敏 學生姓名學號成績 考試時間月日第1頁共4 頁 一.填空題 每空2分,共20分 1.資料元素是 的基本單位 2.資料結構被形式的定義為 d,s 其中d是 的有限集合,s是d上 的有限集合 3.計算機演算法指的是 它的五個...
資料結構試題
a 排序是按照元素的值或某個域的值排列元素，使之成為有序表 b 線性表的排序不改變表中元素及其各個域的值 c 插入排序演算法的時間複雜度的數量級是o n2 d 對線性表排序不改變元素的儲存順序 8 對單鏈表表示法，以下說法錯誤的是 d a 資料域用於儲存線性表的乙個資料元素 b 指標域用於存放乙個指...
資料結構基礎概念
第一章緒論 程式設計的一般過程是 問題 想法 演算法 程式 其實質是資料表示和資料處理。資料結構是研究非數值問題中計算機的操作物件以及它們之間關係和操作的學科。資料元素是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。資料項是資料的最小單位，資料元素是討論資料結構時涉及的最小資料單位。從...