硕士研究生入学考试大纲数据结构.docVIP

目录 I 考查目标 2 II 考试形式和试卷结构 2 III 考查内容 2 IV. 题型示例及参考答案 3 全国硕士研究生入学统一考试数据结构考试大纲 I 考查目标 全国硕士研究生入学统一考试硕士专业学位《数据结构》考试是为江苏大学招收硕士生设置的具有选拔性质的考试科目。其目的是科学、公平、有效地测试考生是否具备攻读专业硕士所必须的基本素质、一般能力和培养潜能,以利用选拔具有发展潜力的优秀人才入学,为国家的经济建设培养具有良好职业道德、法制观念和国际视野、具有较强分析与解决实际问题能力的专业人才。考试要求考生比较系统地掌握数据结构课程的概念、基本原理和方法,能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 具体来说要求考生： 理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异,以及各种基本操作的实现。 掌握基本的数据处理原理和方法的基础上,能够对算法进行设计与分析。 能够选择合适的数据结构和方法进行问题求解。 II 考试形式和试卷结构 试卷满分及考试时间 试卷满分为150分,考试时间180分钟。 答题方式 答题方式为闭卷、笔试。 试卷内容与题型结构 单项选择题 10题,每小题1分, 共10分 填空题 题数不定,每空1分, 共10分 应用题 题数不定, 共80分 简答题 题数不定, 共30分 算法设计题 题数不定, 共20分 III 考查内容 1　绪论1.1　数据结构的基本概念和术语1.2　算法的定义、性能标准和复杂度 2　线性表2.1　线性表的定义2.2　线性表的顺序表示和实现2.3　线性表的链表表示和实现2.4　线性表的应用3　栈队列3.1　栈和队列的基本概念 3.2　栈和队列的顺序存储结构 3.3　栈和队列的链式存储结构 3.4　栈和队列的应用 4　串、数组和广义表4.1　字符串的定义、存储结构和操作,模式匹配算法4.2　数组的定义和顺序存储结构,特殊矩阵和稀疏矩阵的压缩存储 4.3　广义表的定义和存储结构 5.　树和森林5. 1　树的定义和术语,树的表示形式和基本操作5. 2　二叉树的定义、性质和基本操作5. 3　二叉树的顺序存储结构和链式存储结构 5. 4　二叉树的遍历5. 5　线索二叉树5. 6　哈夫曼树和哈夫曼编码5. 7　树的存储结构,树、森林和二叉树的转换,树和森林的遍历5. 8　等价类及其表示6　图6. 1　图的定义、术语和基本操作6. 2　图的存储结构(邻接矩阵、邻接表)6. 3　图的深度优先遍历、广度优先遍历和连通分量6. 4　最小生成树、最短路径、拓扑排序和关键路径 7　查找7. 1　查找的基本概念7. 2　顺序查找法、折半查找法和索引顺序表上的查找 7. 3　二叉排序树的定义,二叉排序树上的查找、插入和删除,二叉排序树查找的性能分析7. 4　平衡二叉树的定义,平衡旋转,平衡二叉树的插入和删除7. 5　散列表的基本概念、构造和分析8　内部排序8. 1　排序的基本概念8. 2　交换排序(冒泡排序,快速排序)8. 3　插入排序(直接插入排序,折半插入排序,希尔排序)8. 4　选择排序(直接选择排序,锦标赛排序,堆排序)8. 5　两路归并排序8. 6　基数排序8. 7　各种内部排序算法的比较和应用 IV. 题型示例及参考答案 一、单项选择题(每小题1分,共10分) 设有数组A[i,j],数组的每个元素长度为3字节,i的值为1 到8,j的值为1 到10,数组从内存首地址SA开始顺序存放,当以列为主存放时,元素A[5,8]的存储首地址为( )。 (A) SA+180 (B) SA+141 (C) SA+222 (D) SA+225 在双向链表指针p的结点前插入一个指针q的结点操作是( )。 (A) p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q； (B) q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q; (C) p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink; (D) q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q; 一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有( )结点。 (A) 2h (B