《程序设计与数据结构》

《《程序设计与数据结构》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、贵州师范大学2014年硕士研究生入学考试大纲（复试）（科目：050程序设计与数据结构）一、考查目标本复试题目包括计算机科学与技术专业两门主要课程：程序设计、数据结构,希望了解考生对该两门课程掌握的情况，主要考查：1、掌握结构化程序设计的基本方法，了解面向对象程序设计的基本思路，对两种方法编写的程序有读、改、写的能力，能实现计算机常用算法的编制。2、对计算机语言冇较好的了解，能识别程序语言屮的语法错误，能用像C++等语言编程，知道程序设计技巧和程序设计风格。3、掌握数据结构的基木概念、基木原理和基木方法。4、各种基本类型的数据

2、结构的特征、操作、存储表示和基本应用；5、各种基木查找表的特征及其查找方法；基木的排序方法。6、基本算法性能的分析与评价。7、使用C（或C++）语言的风格描述算法和进行程序设计，具备综合应用相关知识分析问题和解决问题的能力。二、考试形式与试卷结构（-）试卷成绩及考试时间本试卷满分为100分。考试时间为180分钟。（-）答题方式笔试（三）试卷内容结构程序设计内容占50分，其中程序设计基本知识约10分、读程序和分析程序的能力约25分、写程序的能力约15分。数据结构内容占50分，其中数据结构基本知识约10分、算法分析与评价约20、

3、算法设计与综合应用约20分。（四）试卷题型结构选择题和填空题：共30分简答题和综合应用题（含读程序）：共30分设计与应用分析题（含编写程序）：40分三、考查范围《程序设计部分》1、像程序设计语言C/C++的发展，程序设计语言词、句了的组成，数据类型与表达式等概念，程序的基本组成，算法的概念和表示。2、程序设计的上机过程，运行调试中常见错误的鉴别。3、顺序结构、选择结构和循环结构语句的语法规定，能运用三种结构编写程序。4、了解常用的程序风格和规范。5、掌握函数组装程序的意义，对库函数、口定义函数、局部变量和全程变量有正确的知识

4、，并能用函数进行程序设计，了解递归函数。6、对批量数据的处理，能正确运用数组或结构体进行程序设计，能熟练处理字符数据。7、了解指针、文件和异常处理、类与对象、封装、重载、继承的概念，能读懂面向对象程序。《数据结构部分》1、抽象数据类型，数据的逻辑结构与存储结构，算法基本特性与算法分析方法。2、线性表的定义、逻辑结构、存储结构、基木操作、基木算法性能的分析。3、栈的定义、特性、存储结构、基木操作、基本算法性能的分析，栈与递归算法及其基本应用。4、队列的定义、特性、存储结构、基本操作、基本算法性能的分析以及基本应用。5、串的定义

5、、基木概念、存储结构与基木操作；串的模式匹配算法；6、数组的定义、存储结构与基木操作；特姝矩阵和稀疏矩阵的压缩存储；广义表的基本性质，求广义表的长度、表头与表尾。7、树的基本概念和基本操作；二叉树的基本概念、性质及存储结构；二叉树的先序、屮序及后序遍历算法；树与二义树之间的转换、森林与二叉树之间的转换；哈夫曼树(Huffman)＞哈夫曼编码的构造及带权路径长度的计算。8、图的基木概念和基木操作；图的存储结构；图的深度优先搜索遍历与广度优先搜索遍历；生成树、最小生成树；克鲁斯卡尔(Kruskal)算法、普里姆(Prim)算法。

6、9、查找的概念；顺序查找、折半查找、分块查找、索引顺序表的查找算法；二叉排序树与平衡二叉树，B■树与B+树；哈希(Hash)表的概念，哈希函数的基本构造方法与解决冲突的基木方法，哈希表的建立和查找。各种查找算法的性能分析及其应用。10、内部排序的概念及其排序的稳定性；冒泡排序、快速排序、直接插入排序、折半插入排序、2■路插入排序、希尔排序、直接选择排序、锦标赛排序、堆排序、归并排序、基数排序；各种排序算法的评价(稳定性、时间复杂度、空间复朵性度)及其应用。四、样题单项选择题1.对下列关键字序列用快速排序法进行排序时，速度蝕快

7、的情形是：【】A.{25、23、30、17、21、5、9}B.{5、9、17、21、23、25、30}C.{30、25、23、21、17、9、5}D.{21、25、5、17、9、23、30}2.从下列关于程序风格的叙述中选出五条正确的叙述，将序号按由小到大顺序写在答案处。①应将功能独立n有可能重复使用的程序段编写成子程序②为了缩短源程序的长度应删去源程序中的注释③一般而言，语言的级别越高，用它编出的程序越短④使用括号以改善表达的清晰性⑤一般不进行实数的相等比较⑥使用有意义的标识符⑦通常宁可牺牲程序的运行速度也要注意程序的可读

8、性⑧尽量使用GOTO语句來缩短程序的长度⑨编码时应尽可能使用全局变量⑩应尽可能多地输出中间结果答：二、填空题1.程序的3种基木控制结构是【】、【】和【】。2.广义表D=((),(e),(a,(b,c,d)))的长度是【】。三、简答题1.什么是面向过程的程序设计？2.请解释赫夫曼树M赫夫曼编