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