讀萬卷書，行萬里路——劉彝
計算機系《資料結構》試題2003.6.
班級學號姓名
一、填空題（每空2分，共20分）
1． 與鏈式儲存結構相比，順序儲存結構的優點是
2． 設字元a、b、c、d、e 的權分別為23，29，14，19 和15，設計一棵huffman樹，則該huffman樹根結點的權為
3．設某二叉樹的前序和中序序列均為abcde，則它的後序序列是
4．在排序過程中，每一趟都不能確定任何乙個元素的最終位置，但能適用於鍊錶排序的排序演算法是排序
5．以陣列q[0..m]存放迴圈佇列中的元素，變數rear和qulen分別指示迴圈佇列中隊尾元素的實際位置和當前佇列中元素的個數，則佇列第乙個元素的實際位置是
6．將長度分別為m，n的兩個有序子表進行歸併，至多需要比較次
7．設源串s="bcdcdcb"，模式串p="cdcb"，按kmp演算法進行模式匹配，當"s2s3s4"="p1p2p3"，而s5≠p4時，s5應與比較
8．設序列，試建立表長為7的hash表
hash函式為h（key）=key mod 7，用線性探測法解決衝突，則56衝突次
9．設n>0，且有如下程式段：
int i; i = n;
while (i>0) i=i/10;
則該程式的時間複雜性為
10．假設以一維陣列作為n階對稱矩陣a的儲存空間，以行序為主序儲存a的下三角，則元素a[9][7]的值儲存在s[_______]中
二、求解圖的最小生成樹有哪些演算法？這些演算法各有什麼特點？各適用於
什麼情況？時間複雜性分別如何？（10分）
三．設有乙個表長為12的有序順序錶用二分查詢演算法進行查詢操作，試求解查詢成功情況下該錶的平均查詢長度，要求寫出求解過程
（10分）
四、快速排序是穩定的嗎？若不穩定，則舉出乙個不穩定的例項
（10分）
五、試編寫乙個演算法統計字串s中含有子串t的個數
（10分）
六、試編寫乙個演算法將線性表l中的資料建立一棵二叉排序樹
（12分）
七、已知有向圖g用鄰接表儲存，試寫出鄰接表的型別定義，並編寫乙個演算法求圖中每個頂點的出度和入度
（14分）
八、任你選擇乙個演算法進行改進，試給出改進前後的演算法描述，並說明演算法改進前後的效能區別
（14分）
2001級計算機專業《資料結構》試卷
第 1 頁共 6頁
讀萬卷書，行萬里路——劉彝
2023年廈大計算機系資料結構期末考A卷
一 10分 1 線性表的兩種儲存結構各有什麼優缺點？2 利用gethead和gettail操作，從廣義表 apple pear banana orange 中得出banana。二 10分 棧與佇列的區別和共同點是什麼？圖的深度優先探索和廣度優先搜尋分別適用上述哪種結構，並簡單說明理由？三 10分 給...
計算機系統結構試題
姓名學號 一 名詞解釋 每題3分，共15分 1.系列機 3.2 1cache經驗規則 2.強制性失效 4.指令級並行 二 試從目的 技術途徑 組成 分工方式 工作方式等5個方面對同構型多處理機和異構型多處理機做一比較 列表 10分 三 有哪幾種向量處理方式？它們對向量處理機的結構要求有何不同？6分 ...
計算機系統結構試題試題
姓名學號 一 填空題 20分，每空2分 1 在處理機中，若指令序列完成的順序總是與它們開始執行的順序保持一致，則只可能出現 相關，否則就有可能出現和 相關。2 設計i o系統的三個標準是和 3 單機和多機並行性發展的技術途徑有和 二 簡答題 20分，每題10分 1 在進行計算機系統設計時，乙個設計者...