1、上机考试大纲 1全国高等教育自学考试信息管理类专业数据结构上机考核大纲2005 年 11 月一、 考核目标 掌握并能熟练应用线性表、栈、队列、串、二叉树等数据结构的常用算法，排序和查找常用算法。二、 考核要求考核目标中提及的常用算法及其简单应用，能独立编写实现算法的函数。三、 编程语言 C 程序设计语言四、 软件环境Visual C+ 6.0 或 TURBO C五、 考核方式 闭卷考试，用时一个小时。每个考生从一组试题中选定一道试题。为试题中的算法编写函数，或为应用编写程序。六、 考试范围 线性表、栈、队列、串、二叉树等数据结构上的基本算法，线性表、栈、队列和二叉树的简单应用；插入排序、直接选
2、择排序、堆排序、冒泡排序、快速排序、分配排序及其应用；顺序查找、二分法查找、二叉排序树上的查找算法，及其应用。七、 结果提交要求 考生将自已的解答以源程序文件形式存入考盘中，并要求源程序文件按以下格式命名： 试题代码考号.c，或 试题代码考号.cpp其中考号是考生参加本课程上机考试的准考证号，试题代码是上机考试时所选试题代码。例如，某考生的考号为 200601，选用 D 卷考试，则源程序文件名为：D200601.cpp八、 试题形式试题是要求编写一个或多个函数，每个函数都给出详细的功能说明。如以下试题样例。【试题样例】二叉树的前序遍历序列和中序遍历序列能唯一确定一棵二叉树。试编写已知二叉树的前
3、序遍历序列和二叉树的中序遍历序列，以及二叉树的结点个数，构造一棵二叉树的函数。设二叉树的结点类型为：typedef struct node int data;struct node * lChild; struct node * rChild; BNode;函数采用递归方法，构造二叉树的函数模型为：Bnode * builtBiTree(int preS, int inS, int n)数组 preS存储二叉树的前序遍历序列，数组 inS 存储中序遍历序列，n 是二叉树结点个上机考试大纲 2数。由前序遍历序列的首元素确定二叉树根结点的值，由根结点在中序遍历序列中的位置能确定二叉树的左子树结点和
4、右子树结点。对于左、右子树，采用同样的方法能确定子树的根结点，以及它们的左、右子树。九、 解答要求按考题要求编写包含算法函数的完整源程序文件。例如，对于上述样题，以下就是一种可能的解答。 【样题解答】#include #include #define N 20int aN = 10, 5, 7, 6, 18, 15, 17, 16,/前序序列bN = 5, 6, 7, 10, 15, 16, 17, 18;/中序序列typedef struct node int data; struct node * lChild; struct node * rChild; BNode;BNode * bu
5、iltBiTree(int preS, int inS, int n) BNode *r; int k;if( n data = preS0 ;for(k = 0; k lChild = builtBiTree(preS + 1, inS, k);r-rChild = builtBiTree(preS+k+1, inS+k+1, n-k-1);return r;void preT(BNode *t) if(t) printf(“%4d“,t-data); preT(t-lChild); preT(t-rChild);void inT(BNode *t) if(t) inT(t-lChild);
6、 printf(“%4d“,t-data); inT(t-rChild);void main() BNode * t;t = builtBiTree(a, b, 8);preT(t); printf(“n“); inT(t); printf(“n“);十、 评分办法 上机考核以通过和不通过计成绩。通过的解答必须要有正确按要求命名的源程序文件。试题虽只要求编写完成指定功能的函数，但解答必须同时给出驱动调用该函数的主函数，即是一个完整的源程序文件，且程序能通过编译、并运行。若程序能通过编译、并运行，在运行测试时，结果基本正确，则给予通过成绩。凡发生以下情况之一者，一律作不通过计分：无源程序文件、编译不通过、不能运行，运行测试结果基本不正确。
