《《数据结构》实践环节考核指导1351》由会员分享，可在线阅读，更多相关《《数据结构》实践环节考核指导1351（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构实践环节考核指导实践环节考核指导 1351135121、勿以恶小而为之，勿以善小而不为陈寿三国志 数据结构实践环节考核指导一、类型课程实验考核二、目的与要求本课程的目的和任务是使学习者掌握各种常用的数据结构和典型算法，为学习后续计算机专业课程提供必要的基础，提高学习者运用数据结构解决实际问题的能力本考核主要达到两个目的：1检查学生对数据的逻辑结构、存储结构以及算法的理解程度2检查学生对数据结构的选择以及算法设计和实现的应用能力三、考核环境软件要求：DOS 操作系统或 Windows 环境的 MS-DOS 模式；Turbo C 3.0 系统四、考核内容1、线性表的插入和删除要求对
2、有序顺序表进行插入和删除操作，设数据域为整数要求对有序单链表进行插入和删除操作，单链表的数据域是字符串，但不允许重复的串插入表中删除操作是根据输入的字符串，先找到相应的结果后删除之2、栈和队列操作对一些简单应用问题，如进制转换、字符串输入等，利用栈或队列来实现3、二叉树操作要求采用二叉链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历及求所有叶子和结点个数的操作等4、图的遍历操作可采用邻接矩阵或邻接表作为存储结构，完成有向图和无向图的DFS 和 BFS 操作5、数据查找实现顺序查找、折半查找及二叉排序查找算法，比较他们的查找速度6、排序实现直接插入、冒泡、直接选择、快速、堆、归
3、并排序、并鼓励实现基数排序比较各种排序算法的运行速度五、考核时间与形式考核时间为 60 分钟；采用闭卷形式，所有答案都直接做到考核盘上六、注意事项1、试卷和考核盘都要清楚地书写姓名、准考证号和机号信息；2、必须用蓝、黑色钢笔或圆珠笔书写，字迹要清楚、卷面要整洁3、考试期间严禁左顾右盼、交头接耳；对机器或试卷中出现的问题由监考老师负责解决七、题型与要求请参考以下样题样题一要求：将考试目录下的 c 源程序 test1.c（文件内容见附录一）复制到本地计算机的硬盘上，然后按要求填入相应的语句，调试运行，并按下面要求输入测试数据，在答题纸上写出你所填入的语句以及运行测试的结果题目：已知在顺序存储结构的
4、线性表 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 个正整数关键字，采用
5、堆排序法进行排序，输出第一趟、第五趟及最后一趟的结果测试数据为：取 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
6、答案：（1）（2）（3）测试结果为：附录一：相关文件内容1文件 test1.c 的内容：/*test1.c*/#define ListSize 10typedef int DataType;typedef structDataType 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“,
7、n);for(i=0;idatai);L-length=n;printf(“请选择:n“);printf(“A-插入-n“);printf(“B-删除-n“);printf(“C-退出-n“);scanf(“n%c“,while(c!=celse 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“,void insertlist
8、(seqlist *L)int x,i,j;printf(“n 请输入要插入的整数:“);scanf(“n%d“,printf(“n 在下面序列中插入%dn“,x);for(i=0;ilength;i+)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 del
9、etelist(seqlist *L)int x,i,j,num;printf(“n 请输入要删除的整数:“);scanf(“n%d“,printf(“n 在下面序列中删除%dn“,x);for(i=0;ilength;i+)printf(“%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 #i
10、nclude #define n 10#define Error printftypedef int KeyType;typedef char InfoType;typedef structKeyType key;InfoType otherinfo;RecType;typedef RecType Seqlistn+1;int m,num; /*全局变量 m 和 num 存储输出的第趟结果及递归调用的次数*/Seqlist R;/*记录待排序的 10 个数*/void Heapsort();main()Seqlist S;int i;char ch1,ch2;printf(“请输入 10 个待
11、排序数据:(每个数据间用空格隔开)n“);for(i=1;i=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 趟的结果是：“,m);for (k=1;k#
12、include typedef int KeyType;typedef struct nodeKeyType key;struct node *lchild,*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(“建
13、立一棵二叉排序树的二叉链表存储n“);T=CreateBST();ch1=y;while (ch1=y | ch1=Y)printf(“请选择下列操作：n“);printf(“A-更新二叉排序树存储n“);printf(“B-二叉排序树上的删除n“);printf(“C-二叉排序树中序输出n“);printf(“D-退出n“);scanf(“n%c“,switch (ch2)case A:case a:T=CreateBST();break;case B:case b:printf(“n 请输入要删除的数据：“);scanf(“n%d“,DelBSTNode(printf(“删除操作完毕n“);break;case C:case c:InorderBST(T);printf(“n 二叉排序树输出完毕n“);break;case D:case d:ch1=n;break;default:ch1=n;BSTree CreateBST(void)BSTree T;KeyType Key;T=NULL;printf(“请输入一个关键字(输入 0 时结
