密封線密封線
考生姓名准考證號原所在單位
嘉應學院考試卷（a）
電腦科學與技術專業資料結構試題
題號得分評卷人
二、判斷題：（本大題共10小題，每小題1.5分，共15分，正確的在答題框內打上「t」，錯誤的在答題框內打上「f」）。題號答案12
3456
78910
得分一二三
四五六七
總分複核人
一、單選題（本大題共10小題，每小題1.5分，共15分）：在下面的每乙個小題中所列出的四個選項中只有乙個選項是符合題目要求的，請將正確的選項填在答題框內。題號答案12
3456
78910
得分1、設函式f(n)=10n1.5+200nlgn,g(n)=5n1.5+500nlgn,則下列式子成立的是（）。
（a）f(n)=o(nlgn)(b) g(n)=o(nlgn)(c) f(n)=o(g(n))(d) f(n)=o(n2)2、在表長為n的順序表上做插入運算，平均要移動的結點數為（）。（a）n(b) n/2(c) n/3(d) n/4
3、在雙鏈表某結點（己知其位址）前，插入一新結點，其所需時間是（）。（a）o（1）(b) o(lgn)(c) o(n)(d) o(n2)
4、設長度為n的鏈佇列用單迴圈鍊錶表示，若只設頭指標，則出隊操作的時間複雜度為（）。（a）o(1)(b) o(lgn)(c) o(n)do(n2)5、空串是指（）。
（a）空白串（b）長度為零的串（c）長度為1的串（d）僅由空格組成的串6、設n階方陣是乙個上三角矩陣，則需儲存的元素個數為()。（a）n(b) n2(c)n2/2(d)n(n+1)/2
7、對於任何一棵二叉樹t，如果其終端結點數為n0,度為2的結點數為n2，則（）。(a) n0=n2+1(b)n2=n0+1(c)n0=2n2+1(d)n2=2n0+18、有m個葉結點的哈夫曼樹所具有的結點數為（）。(a)m(b) m+1(c) 2m(d) 2m-19、有n個結點的無向圖的邊數最多是（）。
(a)n+1(b) n(n-1)/2(c) n(n+1)(d) 2n(n+1)10、廣度優先遍歷類似於二叉樹的（）。
（a）先序遍歷（b）中序遍歷（c）後序遍歷（d）層次遍歷
1.線性表採用鏈式儲存時，結點和結點內部的儲存空間可以是不連續的。2.單鏈表中的頭結點就是單鏈表的第乙個結點。
3.若乙個棧的輸入序列為123n，其輸出序列的第乙個元素為n，則其輸出序列的每個元素ai一定滿足ai=n-i+1(i=1,2...,n)。
4.若串s='goodstudents',其子串的數目是12。
5.對於同一組結點，由於建立二叉排序樹時插入結點的先後次序不同，
所構成的二叉排序樹的形態及深度也不同，所以含有n個結點的二叉排序樹不唯一。6.一棵樹中的葉子結點數一定等於與其對應的二叉樹中的葉子結點數。
7.有64個結點的完全二叉樹的深度為7。(根的層次為1)。
8.有向圖用鄰接矩陣表示後，頂點i的入度等於鄰接矩陣中第i列的元素個數。9.快速排序的速度在所有的排序方法中是最快的，且所需的附加空間也最小。
10.有n個數存放在一維陣列a[1..n]中，在進行順序查詢時，這n個數的排列有序或無序，其平均查詢長度不同。
三、填空題：（本大題共10小題，每空2分，共20分）
1、在單鏈表中，刪除指標p所指結點的後繼結點的語句是。
2、取出廣義表a=((x, y, z), (a, b, c, d))中的原子b的函式是。
3、己知完全二叉樹的第八層有8個結點（根為第一層），則其葉子結點數是。
4、將下三角矩陣a[1….8，1….8]的下三角部分逐行地儲存到起始位址為1000的記憶體單元中，已知每個元素佔4個單元，則a[7，5]的位址是。
5、有n個結點的強連通有向圖g至少有條弧。
6、求最短路徑的dijkstra演算法的時間複雜度為。
7、在有序表a[1….20]中，採用二分查詢演算法查詢元素值等於a[12]的元素，所比較的元素的下標依次為。
8、直接選擇排序演算法所執行的元素交換次數最多為。
9、在帶有頭結點的單鏈表l中，第乙個元素結點的指標是。
共三頁第1頁
密封線密封線
10、具有100個結點的完全二叉樹的的深度是。
四、解答下列各題：（共30分，第1、2小題各為7分，第3、4題各為8分）1、一棵二叉樹的先序序列和中序序列分別如下，請畫出該二叉樹。
先序序列：abcdefghij中序序列：cbedaghfji
3、有一組關鍵碼序列（38，19，65，13，97，49，41，95，1，73），採用氣泡排序方法由小到大進行排序，請寫出每趟的結果。
4、設雜湊函式為h（k）=kmod7，閉雜湊表的位址空間為0，…，6，開始時雜湊表為空，用線性探測法解決衝突，請畫出依次插入鍵值23，14，9，6，30，12，18後的雜湊表。
2、對下面給出的資料序列，構造一棵哈夫曼樹，並求出其帶權路徑長度。
4，5，6，7，10，12，15，18，23
共三頁第2頁
共三頁第3頁
密封線密封線
五、演算法設計題：（共20分，每小題10分）
1、設計演算法將陣列a[1~n]按從小到大的次序進行排序，要求一旦發現有序即停止。
2、設二叉樹按二叉鍊錶儲存，設計演算法求二叉樹的樹葉結點的個數。
共三頁第4頁
《資料結構》模擬試卷一
a.98b.99c.50d.48 8 下列序列中，a 是執行第一趟快速排序後得到的序列 排序的關鍵字型別是字串 a.da ax eb de bb ff ha gc b.cd eb ax da ff ha gc bb c.gc ax eb cd bb ff da ha d.ax bb cd da ff...
資料結構期末試卷
浙江大學寧波理工學院200 8 200 9 學年 一 學期 資料結構 乙 課程期末考試試卷 b 答案 開課分院 資訊分院 考試形式 閉卷 考試日期 2008 年 12 月 28 日，考試所需時間 120 分鐘 考生姓名學號考生所在分院 專業班級 一 單項選擇題 本大題共10小題，每小題2分，共20分...
資料結構C 模擬試卷
第 1 題.復合題共計 10 分 選擇題 第 1.1 題.客觀單選題 1 分 線性表的邏輯順序和儲存順序總是一致的，這種說法 正確不正確 有些情況可能是正確的 取決於機器實現 第 1.2 題.客觀單選題 1 分 乙個順序表第1個元素的儲存位址是100，每個元素占用位元組數為5，第5個元素的起始位址是...