数据结构实践环节考核指导

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