1、數據結構實踐環節考核指導摘要：可采用鄰接矩陣或鄰接表作為存儲結構,完成有向圖和無向圖的DFS和BFS操作.5,數據查找實現順序查找,折半查找及二叉排序查找算法,比較他們的查找速度.6,排序.關鍵詞：結構,數據,算法類別：專題技術來源：牛檔搜索（Niudown ）本文系牛檔搜索（Niudown ）根據用戶的指令自動搜索的結果，文中內涉及到的資料均來自互聯網，用于學習交流經驗，作品其著作權歸原作者所有。不代表牛檔搜索（Niudown ）贊成本文的內容或立場，牛檔搜索（Niudown ）不對其付相應的法律責任！數據結構實踐環節考核指導一、類型課程實驗考核二、目的與要求本課程的目的和任務是使學習者掌握

2、各種常用的數據結構和典型算法，為學習后續計算機專業課程提供必要的基礎，提高學習者運用數據結構解決實際問題的能力。本考核主要達到兩個目的：1檢查學生對數據的邏輯結構、存儲結構以及算法的理解程度。2檢查學生對數據結構的選擇以及算法設計和實現的應用能力。三、考核環境軟件要求：DOS 操作系統或Windows環境的MS-DOS模式； Turbo C 3.0系統。四、考核內容1、線性表的插入和刪除要求對有序順序表進行插入和刪除操作，設數據域為整數。要求對有序單鏈表進行插入和刪除操作，單鏈表的數據域是字符串，但不允許重復的串插入表中。刪除操作是根據輸入的字符串，先找到相應的結果后刪除之。2、棧和隊列操作對

3、一些簡單應用問題，如進制轉換、字符串輸入等，利用棧或隊列來實現。3、二叉樹操作要求采用二叉鏈表作為存儲結構，完成二叉樹的建立，先序、中序和后序以及按層次遍歷及求所有葉子和結點個數的操作等。4、圖的遍歷操作可采用鄰接矩陣或鄰接表作為存儲結構，完成有向圖和無向圖的DFS和BFS操作。5、數據查找實現順序查找、折半查找及二叉排序查找算法，比較他們的查找速度。6、排序實現直接插入、冒泡、直接選擇、快速、堆、歸并排序、并鼓勵實現基數排序。比較各種排序算法的運行速度。五、考核時間與形式考核時間為60分鐘；采用閉卷形式，所有答案都直接做到考核盤上。六、注意事項1、試卷和考核盤都要清楚地書寫姓名、準考證號和機

4、號信息；2、必須用藍、黑色鋼筆或圓珠筆書寫，字跡要清楚、卷面要整潔。3、考試期間嚴禁左顧右盼、交頭接耳；對機器或試卷中出現的問題由監考老師負責解決。七、題型與要求 請參考以下樣題。樣題一要求：將考試目錄下的c源程序test1.c（文件內容見附錄一）復制到本地計算機的硬盤上，然后按要求填入相應的語句，調試運行，并按下面要求輸入測試數據，在答題紙上寫出你所填入的語句以及運行測試的結果。題目：已知在順序存儲結構的線性表L上，以遞減順序輸入幾個整數：96，64，52，48，43，33，18，12，在test1.c中填入相應語句，使之能順利完成該遞減序列的插入和刪除操作。設表L中不應有相同的數據元素。測

5、試數據為：依次插入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源程序t

6、est3.c（文件內容見附錄三）復制到本地計算機的硬盤上，然后按要求填入相應的語句，調試運行，并按下面要求輸入測試數據，在答題紙上寫出你所填入的語句以及運行測試的結果。題目：由鍵盤任意鍵入n個正整數，建立其二叉排序樹的存儲，中序遍歷輸出結點序列，刪除若干數據后再按中序輸入。測試數據為：建立時輸入25，12，53，45，36，7，78，62，輸入0時為結束；依次插入數據45、60。答案：（1）（2）（3）測試結果為：附錄一：相關文件內容1文件test1.c的內容：/*test1.c*/#define ListSize 10typedef int DataType;typedef structDa

7、taType dataListSize;int length;seqlist;#define n 8#define Error printfvoid deletelist(seqlist *L);void insertlist(seqlist *L);main()seqlist *L;int i;char c;printf(請按遞減序輸入%d個整數(以空格為間隔):n,n);for(i=0;idatai);L-length=n;printf(請選擇:n);printf(A-插入-n);printf(B-刪除-n);printf(C-退出-n);scanf(n%c,&c);while(c!=c&

8、 c!=C)if (c=A|c=a) insertlist(L);else deletelist(L);printf(當前順序表中的數據為:n);for (i=0;ilength;i+)printf(%3d,L-datai);printf(n請再選擇:n);printf(A-插入-n);printf(B-刪除-n);printf(C-退出-n);scanf(n%c,&c);void insertlist(seqlist *L)int x,i,j;printf(n請輸入要插入的整數:);scanf(n%d,&x);printf(n在下面序列中插入%dn,x);for(i=0;ilength;i+

9、)printf(%3d,L-datai);i=0;/*/while (請考生填寫（1）) i+;/*/if (x=L-datai)Error(n重復插入,錯誤!n);else if (L-length=ListSize) Error(n表溢出,無法插入!);else printf(n將數據%d插入到第%d的位置上n,x,i);/*/請考生填寫（2）/*/void deletelist(seqlist *L)int x,i,j,num;printf(n請輸入要刪除的整數:);scanf(n%d,&x);printf(n在下面序列中刪除%dn,x);for(i=0;ilength;i+)print

10、f(%3d,L-datai);i=0;/*/while (請考生填寫（3）) i+;/*/if (x!=L-datai) Error(n沒有找到要刪除的整數!n);elseprintf(n刪除原表中第%d個位置以后的一個數據%dn,i,x);/*/請考生填寫（4）/*/2文件test2.c的內容：/*test2.c*/#include #include #define n 10#define Error printftypedef int KeyType;typedef char InfoType;typedef structKeyType key;InfoType otherinfo;Rec

11、Type;typedef RecType Seqlistn+1;int m,num; /*全局變量m和num存儲輸出的第趟結果及遞歸調用的次數*/Seqlist R;/*記錄待排序的10個數*/void Heapsort();main()Seqlist S;int i;char ch1,ch2;printf(請輸入10個待排序數據:(每個數據間用空格隔開)n);for(i=1;i=n;i+)scanf(%d,&Si.key);ch1=y;while (ch1=y | ch1=Y)printf(請選擇下列操作：n);printf(1-更新待排序數據-n);printf(2-堆排序-n);prin

12、tf(3-退出-n);scanf(n%c,&ch2);switch (ch2)case 1:printf(請輸入更新待排序數據：n);for (i=1;i=n;i+)scanf (%d,&Si.key);break;case 2:printf(請輸入要輸出第幾趟結果：);scanf(n%d,&m);for (i=1;in+1;i+)Ri.key=Si.key;Heapsort();break;case 3:ch1=n;break;default:ch1=n;void Heapify(int low,int high)int large;RecType temp=Rlow;for (large=

13、2*low;large=high;large*=2)if (largehigh & Rlarge.key=Rlarge.key)break;Rlow=Rlarge;low=large;Rlow=temp;/*Heapify*/void BuildHeap()/*將初始文件R1.n構造為大根堆*/int i;/*/請考生填寫（1） Heapify(i,n);/*/void Heapsort()/*對R1.n進行堆排序，用R0做暫存單元*/int i,k;BuildHeap();for (i=n;i1;i-)R0=R1;R1=Ri;Ri=R0;if (i=(n-m+1)printf(第%d趟的結果

14、是：,m);for (k=1;k=n;k+)printf(%5d,Rk.key);printf(n);printf(請輸入還要輸出第幾趟結果，不想輸出時請輸入0：);scanf(n%d,&m);/*/請考生填寫（2）/*/printf(最終排序結果是：);for (k=1;k=n;k+)printf(%5d,Rk.key);printf(n);/*Heapsort*/3文件test3.c的內容：/*test3.c*/#include #include typedef int KeyType;typedef struct nodeKeyType key;struct node *lchild,*

15、rchild;BSTNode;typedef BSTNode *BSTree;BSTree CreateBST(void);void InsertBST(BSTree *Tptr,KeyType Key);void DelBSTNode(BSTree *Tptr,KeyType Key);void InorderBST(BSTree T);main()BSTree T;char ch1,ch2;KeyType Key;printf(建立一棵二叉排序樹的二叉鏈表存儲n);T=CreateBST();ch1=y;while (ch1=y | ch1=Y)printf(請選擇下列操作：n);prin

16、tf(A-更新二叉排序樹存儲n);printf(B-二叉排序樹上的刪除n);printf(C-二叉排序樹中序輸出n);printf(D-退出n);scanf(n%c,&ch2);switch (ch2)case A:case a:T=CreateBST();break;case B:case b:printf(n請輸入要刪除的數據：);scanf(n%d,&Key);DelBSTNode(&T,Key);printf(刪除操作完畢。n);break;case C:case c:InorderBST(T);printf(n二叉排序樹輸出完畢。n);break;case D:case d:ch1=

17、n;break;default:ch1=n;BSTree CreateBST(void)BSTree T;KeyType Key;T=NULL;printf(請輸入一個關鍵字(輸入0時結束輸入)：n);scanf(%d,&Key);/*/while (Key)請考生填寫（1）printf(請輸入下一個關鍵字(輸入0時結束輸入)：n);scanf(n%d,&Key);/*/return T;void InsertBST(BSTree *T,KeyType Key)BSTNode *f,*p;p=(*T);while(p)if(p-key=Key)printf(樹中已有Key不需插入n);retu

18、rn;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)BSTNode *parent=NULL, *p, *q,*child;p=*T;/*/while(p)if(p-key=Key) break;parent=p

19、;請考生填寫（2）/*/if (!p) printf(沒有找到要刪除的結點n);return;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-rchild;/*/if (!parent) *T=child;else 請考生填寫（3）if (p!=q)q-key=p-key;/*/free(p);void InorderBST(BSTree T) if(T!=NULL)InorderBST(T-lchild);printf(%5d,T-key);InorderBST(T-rchild);附錄二：樣題參考答案樣題一答案：(1) ilength&xdatai(2) for (j=L-length-1;j=i;j-) L-dataj+1=L-dataj; L-datai=x; L-length+;(3) ilength&xdatai(4) for(j=i+1;jlength-1;j+);L-dataj-1=L-dataj;L-lengt