软件理论基础——兰州交通大学2006硕士考试大纲-易考网-Easy考研网提供考研试卷专业清单-考研一站式_Easy考研网_考研资料、考研专业课试题、考研专业目录、考研参考书目、考研咨询、考研辅导报名、考研书籍、考研会员服务

软件理论基础——兰州交通大学2006硕士考试大纲

http://www.ezkaoyan.com 2006-4-18

考试科目代码及名称: 416软件理论基础

考查要点:
1、数据结构部分
数据结构课程主要测试考生对数据的逻辑结构、存储结构和相应算法的掌握程度。测试分为：一、数据结构的基本概念、原理、性质，数据结构的逻辑关系，数据结构的存储描述等的熟悉程度。二、综合应用数据结构的原理，解决一些应用性的问题的能力。三、熟练应用数据结构的基本算法对一定逻辑关系的数据进行算法设计。从而对考生有较全面的评价。具体考察内容：
（1）概论：熟悉数据结构的基本概念和术语，掌握算法的描述和算法分析的基本方法。
（2）线性结构：熟悉线性表的逻辑结构，掌握线性表的顺序、链式存储结构及算法。熟悉栈、队列的逻辑结构和存储结构，掌握基本的算法。熟悉串的定义及其操作，理解串的存储结构和串基本操作的实现。理解数组的定义和运算，熟悉数组的顺序存储结构，掌握矩阵的压缩存储，熟悉广义表的定义，掌握广义表的基本操作和存储结构。
（3）树和二叉树：熟悉树的结构定义，掌握二叉树的定义、性质、存储，掌握二叉树的先序、中序和后序遍历的递归，了解非递归算法，理解线索二叉树，熟悉树和森林与二叉树的相互转化，掌握哈夫曼树的求解及哈夫曼编码。
（4）图：熟悉图的定义和术语，掌握图的存储结构（邻接矩阵、邻接表），熟悉图的深度优先搜索和广度优先搜索，熟悉最小生成树的Prim和Kruscal算法，熟悉有向无环图的拓扑排序和关键路径、最短路径。
（5）查找：熟悉顺序、折半查找算法，掌握二叉排序树的建立、查找和删除，熟悉B-树的建立、删除，掌握哈希表构造、解决冲突的方法（开放定址法、链地址法），掌握平均查找长度。
（6）内部排序：掌握直接、折半、希尔插入排序，起泡、快速排序，简单选择、堆排序，归并排序，链式基数排序，掌握各种内部排序方法的比较讨论，熟悉每一种排序的性能分析（时间性能、空间性能、稳定性）。
2、离散数学部分
（1）数理逻辑：命题及其表示法，联结词，命题公式与翻译，真值表与等价公式，重言式与蕴含式，对偶与范式，推理理论，谓词的概念与表示，命题函数与量词，谓词公式与翻译，变元的约束，谓词演算的等价与蕴含式，前束范式，谓词演算的推理理论。
（2）集合论：集合的概念和表示法，集合的运算，序偶与笛卡儿积，关系及其表示，关系的性质，关系的运算﹙求逆，复合，闭包﹚，集合的划分与覆盖，等价关系与等价类，相容关系，序关系，函数的概念，单射，双射，满射，逆函数和复合函数。
（3）代数系统：代数系统，代数系统上的运算及其性质，半群，群与子群，阿贝尔群和循环群，陪集与拉格朗日定理，同态与同构，格的概念，分配格，有补格，布尔代数。
（4）图论：图的基本概念，路与回路，图的矩阵表示，欧拉图与汉密尔顿图，平面图，对偶图与着色，树与生成树，根树及其应用。
题型、分值及考试时间：
1．数据结构部分试卷共75分，题型由以下几种组成：
单项选择题、填空题：主要考核基本概念、简单计算等。
简答题、应用题：利用数据结构的原理，求解一些基本问题。
算法设计题：对一定逻辑关系的数据进行算法设计和时间效率分析。
2．离散数学部分试卷共75分，题型包括：选择题，简答题，证明题。
3．考试时间为180分钟。
参考书目（包括书名、作者、、出版社、出版时间）：
1．《数据结构》（C语言版或Pascal语言版）（第2版）严蔚敏吴伟民编著，清华大学出版社.
2．《离散数学结构》（第四版，影印版）Bernard Kolman, Robert C.Busby, Sharon Cutler Ross等，高等教育出版社.
《离散数学》朱一清编著，电子工业出版社.