自考指導

自考《數據結構》實踐環節試題考核指導一

《數據結構》實踐環節考核指導

一、類型

課程實驗考核

二、目的與要求

本課程的目的和任務是使學習者掌握各種常用的數據結構和典型算法，為學習后續計算機專

業課程提供必要的基礎，提高學習者運用數據結構解決實際問題的能力。本考核主要達到兩

個目的：

1．檢查學生對數據的邏輯結構、存儲結構以及算法的理解程度。

2．檢查學生對數據結構的選擇以及算法設計和實現的應用能力。

三、考核環境

軟件要求：

DOS操作系統或Windows環境的MS-DOS模式；

TurboC3.0系統。

四、考核內容

1、線性表的插入和刪除

要求對有序挨次表進行插入和刪除操作，設數據域為整數。

要求對有序單鏈表進行插入和刪除操作，單鏈表的數據域是字符串，但不允許重復的串插入

表中。刪除操作是按照輸入的字符串，先找到相應的結果后刪除之。

2、棧和隊列操作

對一些簡單應用問題，如進制轉換、字符串輸入等，利用棧或隊列來實現。

3、二叉樹操作

要求采用二叉鏈表作為存儲結構，完成二叉樹的建立，先序、中序和后序以及按層次遍歷及

求所有葉子和結點個數的操作等。

4、圖的遍歷操作

可采用鄰接矩陣或鄰接表作為存儲結構，完成有向圖和無向圖的DFS和BFS操作。

5、數據查找

實現挨次查找、折半查找及二叉排序查找算法，比力他們的查找速度。

6、排序

實現直接插入、冒泡、直接選擇、快速、堆、歸并排序、并鼓勵實現基數排序。比力各種排

序算法的運行速度。

五、考核時間與形式

考核時間為60分鐘；

采用閉卷形式，所有答案都直接做到考核盤上。

六、注意事項

1、試卷和考核盤都要清楚地書寫姓名、準考證號和機號信息；

2、必需用藍、黑色鋼筆或圓珠筆書寫，筆跡要清楚、卷面要整潔。

3、考試期間嚴禁左顧右盼、竊竊私語；對機器或試卷中出現的問題由監考老師負責解決。

七、題型與要求

請參考以下樣題。

樣題一

要求：將考試目錄下的c源程序test1.c（文件內容見附錄一）復制到本地計算機的硬盤上，

然后按要求填入相應的語句，調試運行，并按下面要求輸入測試數據，在答題紙上寫出你所

填入的語句以及運行測試的結果。

標題問題：已知在挨次存儲結構的線性表L上，以遞減挨次輸入幾個整數：96，64，52，

48，43，33，18，12，在test1.c中填入相應語句，使之能順利完成該遞減序列的插入和刪

除操作。設表L中不應有相同的數據元素。測試數據為：依次插入5、18、57，再依次刪除

48、20、12。（注：線性表從第0個位置開始存放數據。）

答案：

（1）

（2）

（3）

（4）

測試結果為：

樣題二

要求：將考試目錄下的c源程序test2.c（文件內容見附錄二）復制到本地計算機的硬盤上，

然后按要求填入相應的語句，調試運行，并按下面要求輸入測試數據，在答題紙上寫出你所

填入的語句以及運行測試的結果。

標題問題：由鍵盤任意鍵入n個正整數關鍵字，采用堆排序法進行排序，輸出第一趟、第五

趟及最后一趟的結果。測試數據為：取n=10，建立時輸入25，12，53，6，45，36，7，78，

62，17。

答案：

（1）

（2）

測試結果為：