華東交通大學2013—2014學年第一學期考試卷
試卷編號： （a）卷
資料結構課程課程類別：必
閉卷考試日期：
考生注意事項：1、本試卷共 4 頁，答題紙4頁，總分 100 分，考試時間 120 分鐘。
2、考試結束後，考生不得將試卷、答題紙和草稿紙帶出考場。
一、選擇題(每題2分，共20分)
1． 根據資料元素之間關係的不同特性，通常有4類基本資料結構，它們是（ ）。
a．集合、線性結構、樹形結構、圖狀結構
b．集合、線性結構、非線性結構、網狀結構
c．線性結構、樹形結構、圖狀結構、網狀結構
d．線性結構、非線性結構、圖狀結構、網狀結構
2． 下面程式段的時間複雜度為 ( )。
void fun(int n)
a．o(log2n) b．o(n2) c．o(n×log2n) d．o(n)
3． 線性表的順序儲存結構是一種（ ）的儲存結構。
a．隨機訪問b．順序訪問
c．索引訪問d．雜湊訪問
4． 迴圈單鏈表la中，指標p所指結點為表尾結點的條件是（ ）。
a．p->next == nullb．p != null
c．p == nulld．p->next == la
5． 4個元素k、l、m、n依次入棧，入棧過程中允許元素出棧，假設某一時刻棧的狀態是m（棧頂）、l、k（棧底），則不可能的出棧順序是（ ）。
a．m、n、l、kb．n、m、l、k
c．m、n、k、ld．m、l、n、k
6． 對於二叉樹和度為2的樹，相同之處是（ ）。
a.每個結點都有乙個或兩個孩子結點。 b.至少有乙個度為2的結點。
c.每個結點至多只有乙個雙親結點。 d.至少有乙個根結點。
7． 在乙個具有5個頂點的無向圖中，要連通全部頂點至少需要( )條邊。
a. 3b. 4c. 5d.6
8． 已知乙個有向圖的弧集為，則由該圖產生的一種可能的拓撲序列為( )。
a. a,b,c,d,e b. a,b,d,e,b c. a,c,b,e,d d. a,c,d,b,e
9． 關鍵路徑是aoe網中（ ）。
a.從源點到匯點的最長路徑b.從源點到匯點的最短路徑
c.最長的迴路d.最短的迴路
10. 在有序表中折半查詢19，需要與表中關鍵值共進行（ ）次比較。
a.1b.2c.3d.4
二、填空題，按照空號填寫(每空2分，共30分)
1. 如果線性表經常進行插入刪除操作且長度變化較大，則採用（1）__儲存結構更合適。
2. 假設二維陣列a[0..4][0..7]，每個元素占用4個位元組，儲存器按位元組編址。已知陣列的基位址為1300，按行優先儲存時元素a[3][5]的位址是（2）__。
3. 用乙個大小為9的陣列來實現迴圈佇列，且當前隊尾和隊頭的值分別為5和2，當從佇列中刪除兩個元素，再加入四個元素後，隊尾值為_（3）_，隊頭的值為_（4）_。
4. 一棵完全二叉樹有18個結點，其中，葉子結點有 （5） 個，度為1的結點有 （6） 個。
5. 有向圖如圖1所示，根據迪傑斯特拉演算法，源點a到頂點e的最短路徑是（7）__，源點a到頂點e的最短路徑長度是（8）__；源點a到頂點f的最短路徑是（9）__。
6. 如圖2所示的二叉樹中，有（10）__個葉子，二叉樹的深度為（11）__，該樹對應的森林包含（12）__棵樹。
7. 乙個有向圖的鄰接表儲存如圖3所示，頂點v1的出度是（13）_，頂點v2的入度是 （14） ,從頂點v1出發，按照深度優先搜尋得到的頂點序列是（15） _。
圖3三、綜合題(共40分)
1. （5分）利用算符優先演算法對表示式6*（2+5）#求值，寫出操作符棧和運算元棧在任意時刻的狀態。
2. （5分）請選擇起泡排序、簡單選擇排序、快速排序、歸併排序，四種排序方法中的一種，對（46，35，60，90，72，11，25）進行排序，並寫出詳細排序過程。
3. （5分）已知二叉樹的先序遍歷序列為：abdgcef，中序遍歷序列為：dgbaecf，畫出這棵二叉樹。
4. （5分）乙個無向網如圖4所示，以v1為起始點，使用普里姆演算法按步驟畫出為圖4構造的最小生成樹。
5. （10分）設雜湊函式為 h(k) = k % 11，位址空間為 0..12，用線性探測再雜湊法解決衝突。
請畫出依次插入24，7，35，13，18，21，32所得到的雜湊表。（寫出雜湊位址的詳細計算過程）
6. （10分）給定6個葉子結點，其權值分別為，畫出構造的哈夫曼樹（權值小的為左孩子），並求出該哈夫曼樹的帶權路徑長度wpl。
四、演算法題(共10分)
已知單鏈表中，結點結構如下：
（1）寫出該結點結構lnode的定義。
（2）寫出在頭結點之後，插入data域為e的新結點s的演算法
void insert( linklist & l，elemtype e)
華東交通大學2013—2014學年第一學期考試卷答題紙
試卷編號： （a）卷
資料結構課程課程類別：必
閉卷考試日期：
考生注意事項：1、本試卷共 4 頁，答題紙4 頁，總分 100 分，考試時間 120 分鐘。
2、考試結束後，考生不得將試卷、答題紙和草稿紙帶出考場。
一、選擇題(每題2分，共20分)
二、填空題，按照空號填寫(每空2分，共30分)
三、綜合題(共40分)
1. （5分）（提示：請填寫完下表第3到10步）
2. （5分）
3. （5分）
4. （5分）
5. （10分）
6. （10分）
四、演算法題(共10分)
上大資料結構
var low high i j,t integer begin low 1 high n repeat t a low i low j high repeat while ij j 1 if ibegin a i a j i i 1 end while ii i 1 if ibegin a j a...
資料結構試卷 A
密封線密封線 考生姓名准考證號原所在單位 嘉應學院考試卷 a 電腦科學與技術專業資料結構試題 題號得分評卷人 二 判斷題 本大題共10小題，每小題1.5分，共15分，正確的在答題框內打上 t 錯誤的在答題框內打上 f 題號答案12 3456 78910 得分一二三 四五六七 總分複核人 一 單選題 ...
《資料結構》課程模擬試卷2019
學號姓名教師得分 一 填空 30分左右 1.由85個節點構成的完全二叉樹，其深度為其中第6層的節點數為 個。2 關鍵字1，2，3，5，13，18，27，對其進行折半查詢，那麼查詢關鍵字13的比較次數是 次。3 有一棵二叉樹，它的中序遍歷為 4，5，2，1，6,3，前序遍歷為 1，2，4，5，3，6那...