遵义师范学院专升本计算机科学与技术专业数据结构与C语言程序设计考试大纲
一、考试对象：
计算机应用技术、计算机科学教育、计算机软件3个专业的专科学生
二、考核内容：笔试（闭卷）
三、考试时量：150分钟
四、卷面分数：总分150分(其中C语言部分90分，数据结构部分60分)
五、试卷结构：
《C语言程序设计》部分(90分)
1、单项选择题（10小题，每小题2分，共20分）
2、阅读程序，写出程序运行结果（6小题，每小题5分，共30分）
3、程序补充填空(10空，每空2分，共20分)
4、程序设计题(2题，基础题1个8分，综合题1个12分，共20分)
《数据结构》部分(60分)
1、单项选择题(5小题，每小题2分，共10分)
2、判断题（10小题，每小题1分，共10分）
3、简答题（4小题，每小题5分，共20分）
4、算法填空题(5空，每空2分，共10分)
5、算法设计题（1小题，每小题10分，共10分）
六、参考教材：
[1] 严蔚敏 吴伟民 编著《数据结构（C语言版）》 清华大学出版社
[2] 谭浩强 编著《C 语言程序设计（第二版）》 清华大学出版社
七、考核内容
第一部分 C语言程序设计（共90分）
1、C语言概念（4分）
C语言的历史（识记）
现状和特点（识记）
C语言的基本结构（识记）
2、基本数据类型和表达式（10分）
C语言的基本数据类型、常量和变量、符号常量、变量的初始化、表达式和运算符，并能够运用进行数据处理（理解）
3、简单的C程序设计（10分）
C语句概述，掌握赋值语句、数据输出，数据输入，逻辑运算和条件控制，关系运算符和关系表达式，逻辑运算符和逻辑表达式，IF语句，SWITCH语句（理解，运用）
4、循环语句（12分）
循环结构程序设计概念，WHILE语句、DO-WHILE语句、FOR语句、BREAK语句和CONTINUE 语句，编程实现运用双重循环的嵌套解决问题。（理解，运用）
5、数组（14分）
一维数组与二维数组的定义、初始化及元素的引用；字符数组和字符串的基本概念和典型算法；字符串的输入和输出，字符串运算函数。（理解，运用）
6、函数（14分）
函数的定义，掌握函数的一般调用、函数的嵌套调用和函数的递归调用，函数参数的作用、变量的作用域和编译预处理、命令行参数的概念（带参数的主函数）、标准库函数。（理解，运用）
7、指针（14分）
指针的概念，变量的指针与指向变量的指针变量，包括定义、引用以及指针变量作为函数参数；数组的指针，包括指向数组的指针变量的定义与赋值、通过指针引用数组元素、数组名作为函数参数；字符串的指针与指向字符串的指针变量。（理解，运用）
8、结构体（8分）
结构和结构变量的定义，结构体的初始化与引用，结构体数组（理解）
完成单链表建立的程序设计（运用）
9、文件（4分）
文件的基本概念，文件的基本输入和输出函数（了解）
C语言程序设计考试部分涉及的常用算法：
1、分类（排序）算法：冒泡、选择、插入
2、检索（查找）算法：无序数据序列检索（见遍历算法）、有序数据序列检索（二分法）
3、遍历算法：数组的遍历、单向链表的遍历
4、简单的数值计算方法：如多项式函数的计算
5、其它基本算法：如进制转换
第二部分 数据结构部分（共60分）
1、数据结构与算法概念：（4分）
数据结构的含义，算法的要素及时间、空间复杂度的分析方法，以及数据结构所包含的三个方面：逻辑结构、存储结构、算法之间的区别和内在联系。（识记）
逻辑结构的分类：存集合、线性、树和图（理解）。
掌握算法度量的两个方面：时间、空间复杂度（理解，运用）。
算法书写的规范。（识记）
2、线性表（10分）
顺序表的存储结构及基本操作。（理解）
链表单链表、双向链表和循环链表的定义、存储结构、基本操作。（理解，运用）
静态链表的定义、存储结构和基本操作。（理解，运用）
3、堆栈与队列（8分）
堆栈的定义及其操作，堆栈的顺序存储结构、堆栈的链式存储结构。（理解，运用）
典型递归问题的C语言实现。递归算法设计的基本方法。（理解，运用）
队列的定义及其操作，队列的顺序存储结构、队列的链式存储结构。（理解，运用）
4、树和二叉树（16分）
树的定义、表示方法、基本术语、基本操作、存储结构。（识记）
二叉树的基本概念、性质、存储结构、基本操作及其实现。（识记，理解）
二叉树的遍历和二叉树遍历的应用。（理解，运用）
线索化的概念及实现。（理解）
哈夫曼树的基本概念、在编码中的应用。（理解，运用）
树转换为二叉树、森林转换为二叉树。（理解，运用）
5、图（8分）
图的定义和基本术语。（识记）
图的存储结构：邻接矩阵（理解）邻接表 （理解）十字链表的存储表示（了解）
深度优先搜索、广度优先搜索的遍历算法（理解，运用）
最小生成树的基本概念，用prim和Kruskal算法构造最小生成树的算法（理解，运用）
6、排序（8分）
排序基本概念和算法。（识记）
插入排序（理解，运用）
直接选择排序（理解，运用）
希尔排序（理解，运用）
堆排序算法（理解）
冒泡排序算法（理解，运用）
快速排序算法（理解，运用）
归并排序的思想（理解）
7、查找（6分）
查找的基本思想（识记）
顺序查找和二分查找的算法（理解，运用）
二叉排序树查找的基本思想（理解）
说明：
未在本大纲里提到的内容试卷中原则上不涉及。
计算机科学系
2009年11月5日