讀過一本好書，像交了乙個益友。——藏克家
一、型別
課程實驗考核
二、目的與要求
本課程的目的和任務是使學習者掌握各種常用的資料結構和典型演算法，為學習後續計算機專業課程提供必要的基礎，提高學習者運用資料結構解決實際問題的能力。本考核主要達到兩個目的：
1．檢查學生對資料的邏輯結構、儲存結構以及演算法的理解程度。
2．檢查學生對資料結構的選擇以及演算法設計和實現的應用能力。
三、考核環境
軟體要求：
dos 作業系統或windows環境的ms-dos模式；
turbo c 3.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）測試結果為：
樣題三要求：將考試目錄下的c源程式test3.c（檔案內容見附錄三）複製到本地計算機的硬碟上，然後按要求填入相應的語句，除錯執行，並按下面要求輸入測試資料，在答題紙上寫出你所填入的語句以及執行測試的結果。
題目：由鍵盤任意鍵入n個正整數，建立其二叉排序樹的儲存，中序遍歷輸出結點序列，刪除若干資料後再按中序輸入。測試資料為：
建立時輸入25，12，53，45，36，7，78，62，輸入0時為結束；依次插入資料45、60。
答案：（1）
（2）（3）
測試結果為附錄一：相關檔案內容
1．檔案test1.c的內容：
/*test1.c*/
#define listsize 10
typedef int datatype;
typedef structseqlist;
#define n 8
#define error printf
void deletelist(seqlist *l);
void insertlist(seqlist *l);
main()
rectype;
typedef rectype seqlist[n+1];
int m,num; /*全域性變數m和num儲存輸出的第趟結果及遞迴呼叫的次數*/
seqlist r;/*記錄待排序的10個數*/
void heapsort();
main()
r[low]=temp;
}/*heapify*/
void buildheap()
/*heapsort*/
3．檔案test3.c的內容：
/*test3.c*/
#include
#include
typedef int keytype;
typedef struct nodebstnode;
typedef bstnode *bstree;
bstree createbst(void);
void insertbst(bstree *tptr,keytype key);
void delbstnode(bstree *tptr,keytype key);
void inorderbst(bstree t);
main()
void insertbst(bstree *t,keytype key)
f=p;
p=(keykey)?p->lchild:p->rchild;
}p=(bstnode*)malloc(sizeof(bstnode));
p->key=key;
p->lchild=p->rchild=null;
if ((*t)==null) (*t)=p;
else if (keykey) f->lchild=p;
else f->rchild=p;
}/*insertbst*/
void delbstnode(bstree *t,keytype key)
q=p;
if (q->lchild && q->rchild)
for (parent=q,p=q->rchild; p->lchild; parent=p,p=p->lchild);
child=(p->lchild)?p->lchild:p->rchildif (!parent) *t=child;
else
void inorderbst(bstree t)
{ if(t!=null)
{inorderbst(t->lchild);
printf("%5d",t->key);
inorderbst(t->rchild附錄二：樣題參***樣題一答案：
(1) ilength&&xdata[i]
(2) for (j=l->length-1;j>=i;j--)
l->data[j+1]=l->data[j];
l->data[i]=x;
l->length++;
(3) ilength&&xdata[i]
(4) for(j=i+1;j<=l->length-1;j++);
l->data[j-1]=l->data[j];
l->length--;
測試結果為：
插入5後：將資料5插入到第8的位置上。
96 64 52 48 43 33 18 12 5
插入18後：重複插入，錯誤!
插入57後：將資料57插入到第2的位置上。
96 64 57 52 48 43 33 18 12 5
刪除48後：刪除原表中第4個位置以後的乙個資料48。
96 64 57 52 43 33 18 12 5
刪除20後：沒有找到要刪除的整數。
96 64 57 52 43 33 18 12 5
刪除12後：刪除原表中第7個位置以後的乙個資料12。
96 64 57 52 43 33 18 5
樣題二答案：
(1) for(i=n/2;i>0;i--)
heapify(i,n);
(2) heapify(1,i-1);
測試結果為：
第一趟的結果為：17 62 53 25 45 36 7 6 12 78
第五趟的結果為：7 25 12 6 17 36 45 53 62 78
最後一趟的結果為：6 7 12 17 25 36 45 53 62 78
樣題三答案：
(1)insertbst(&t,key);
(2)p=(keykey)?p->lchild:p->rchild;
讀過一本好書，像交了乙個益友。——藏克家3)if(p==parent->lchild)
parent->lchild=child;
else parent->rchild=child;
測試結果為：
刪除45前的中序遍歷序列為：6，7，12，17，25，36，45，53，62，78
刪除45後的中序遍歷序列為：6，7，12，17，25，36，53，62，78
刪除60：沒有找到要刪除的結點1
讀過一本好書，像交了乙個益友。——藏克家
資料結構複習指導
1.資料結構是指 a a.資料元素的組織形式 b.資料型別 c.資料儲存結構d.資料定義 2.資料在計算機儲存器內表示時，實體地址與邏輯位址不相同的，稱之為 c a.儲存結構b.邏輯結構 c.鏈式儲存結構d.順序儲存結構 3.樹形結構是資料元素之間存在一種 d a.一對一關係 b.多對多關係 c.多...
資料結構複習指導
elemtype data struct btnode lchild,rchild,parent btnode,bintree 例 用二叉鍊錶儲存n個結點的二叉樹 n 0 共有 n 1 個空指標域 採用三叉鍊錶儲存，共有 n 2 個空指標域。空樹 bt null 左右子樹均空 bt lchild n...
《資料結構》複習指導
自學考試 資料結構 複習指導 第一章 緒論 一 概念 資料結構 是一門研究程式設計中計算機操作的物件以及它們之間的關係和運算的一門學科。資料 是描述額觀事物的數 字元以及所有能輸入到計算機中被電腦程式加工處理的資訊的集合。資料元素 資料元素是資料的基本單位。乙個資料項或多個資料項 域 資料項是資料的...