2015年上海理工大学081200计算机科学与技术考研大纲

　　考研网快讯，据上海理工大学研究生院消息，2015年上海理工大学计算机科学与技术考研大纲已发布，详情如下：
　　《数据结构及计算机组成原理》考试大纲和参考书目
　　第一部分数据结构
　　参考教材：
　　《数据结构》（C语言版），严蔚敏等主编，清华大学出版社，2007年3月
　　第一章绪论
　　明确数据结构的定义、研究的内容，掌握算法及算法分析的概念，了解抽象数据类型的
　　概念。
　　第二章线性表
　　掌握线性表的概念，两种存储结构顺序表和链表的表示和实现、掌握链表（单链表、
　　单循环链表和双向链表）上的查找、插入、删除基本操作及能编写链表上的综合操作程序。
　　第三章栈和队列
　　掌握栈的概念，掌握顺序栈、链栈的进栈、出栈操作程序。能利用栈写出表达式求值过
　　程，能用栈读写递归程序。
　　掌握队列的概念，掌握循环队列、循环链队列的入队、出队操作程序。
　　第四章串
　　掌握串的基本运算的含义，掌握求子串位置的定位函数，理解KMP模式匹配算法和时
　　间复杂度。
　　第五章多维数组和广义表
　　掌握多维数组及特殊矩阵的地址公式，广义表的运算和存储。了解广义表的递归算法。
　　第六章树和二叉树。
　　掌握树、二叉树的定义、术语，二叉树的性质，掌握二叉树的递归和非递归遍历算法，
　　掌握中序线索二叉树的概念和遍历算法，掌握Haffman树及其应用，了解树与二叉树的关系，
　　了解回溯法与树的遍历。
　　第七章图
　　掌握图的定义、术语，掌握图的存储，图的遍历算法，掌握最小生成树、拓扑排序、关
　　键路径、最短路径概念，了解其算法。
　　第九章查找
　　掌握有序表的查找算法和查找的时间复杂度，掌握二叉排序树的查找、插入和删除算法，
　　掌握平衡二叉树和B-树的插入、删除概念。
　　掌握哈希表构造、解决冲突的方法及哈希表的查找。
　　第十章内部排序
　　掌握直接插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序和希尔排
　　您所下载的资料来源于kaoyan.com考研资料下载中心
　　获取更多考研资料，请访问http://download.kaoyan.com
　　序算法和时间复杂度，了解基数排序的概念。
　　专业课《数据结构》考试大纲和参考书目
　　参考教材:《数据结构·C语言版》,严蔚敏主编,清华大学出版社
　　参考用书:《数据结构习题详解》,李春葆编著,清华大学出版社
　　课程内容（无标记章节一般了解、不考，打*号标记章节要求掌握，打**号标记章节要求重
　　点掌握）
　　绪论
　　数据结构定义
　　基本概念和术语
　　*算法描述和算法分析
　　抽象数据类型的表示和实现
　　线性表
　　线性表的基本概念
　　线性表顺序表示和实现
　　线性表的链式表示和实现：
　　**线性链表
　　**循环链表
　　*双向链表
　　顺序存储结构与链式存储结构的比较
　　**线性表的应用举例
　　栈和队列
　　*抽象数据类型栈的定义
　　*栈的表示和实现
　　栈的应用举例：
　　迷宫求解
　　**表达式求值
　　**栈与递归的实现
　　*抽象数据类型队列的定义
　　*链队列—队列的链式表示和实现
　　**循环队列—队列的顺序表示和实现
　　串
　　串类型的定义
　　串的表示和实现
　　**串的模式匹配算法
　　串的应用举例
　　数组和广义表
　　数组的定义
　　*数组的顺序表示和实现
　　您所下载的资料来源于kaoyan.com考研资料下载中心
　　获取更多考研资料，请访问http://download.kaoyan.com
　　*矩阵的压缩存储：
　　特殊矩阵
　　稀疏矩阵
　　*广义表的概念
　　*广义表的存储
　　广义表的应用举例
　　树和二叉树
　　树的定义和基本术语
　　*二叉树：
　　二叉树的定义
　　二叉树的性质
　　二叉树的存储结构
　　**二叉树的遍历
　　**线索二叉树
　　树和森林：
　　树的存储结构
　　静态链表
　　树、森林和二叉树的转换
　　树的遍历
　　*树的应用举例：
　　哈夫曼树
　　哈夫曼编码
　　回溯法与树的遍历
　　图
　　*图的定义和基本术语
　　图的存储结构：
　　**邻接矩阵
　　**邻接表
　　十字链表
　　邻接多重表
　　**图的遍历：
　　深度优先搜索遍历
　　广度优先搜索遍历
　　*最小生成树：
　　生成树和最小生成树
　　普里姆算法
　　克鲁斯卡尔算法
　　有向无环图及应用：
　　*拓扑排序
　　关键路径
　　您所下载的资料来源于kaoyan.com考研资料下载中心
　　获取更多考研资料，请访问http://download.kaoyan.com
　　最短路径
　　查找
　　查找基本概念
　　顺序表的查找：
　　顺序查找
　　**有序表的查找
　　分块查找
　　8.3树表的查找
　　*8.3.1二叉搜索树
　　*8.3.2平衡二叉树
　　8.3.3B_树
　　8.3.4B+树
　　*8.4哈希表
　　8.4.1哈希表的基本概念
　　8.4.2构造哈希函数的方法
　　8.4.3解决哈希冲突的方法
　　8.4.4哈希表的查找
　　*第九章排序
　　9.1排序的基本概念
　　9.2插入排序
　　9.2.1直接插入排序
　　9.2.2希尔排序
　　9.3交换排序
　　9.3.1冒泡排序
　　9.3.2快速排序
　　9.4选择排序
　　9.4.1直接选择排序
　　9.4.2堆排序
　　9.5归并排序
　　9.6基数排序
　　9.7各种内部排序方法比较
　　9.8外排序
　　**二叉排序树
　　*平衡二叉树
　　*B_树
　　B+树
　　哈希表：
　　*哈希表的基本概念
　　构造哈希函数的方法
　　*解决哈希冲突的方法
　　您所下载的资料来源于kaoyan.com考研资料下载中心
　　获取更多考研资料，请访问http://download.kaoyan.com
　　*哈希表的查找
　　内部排序
　　排序的基本概念
　　**插入排序：
　　直接插入排序
　　希尔排序
　　**冒泡排序
　　**快速排序
　　**选择排序：
　　直接选择排序
　　堆排序
　　**归并排序
　　基数排序
　　*各种内部排序方法比较
　　第一部分计算机组成原理
　　一、考试范围
　　计算机系统概论，运算方法与运算器，内部存储器，指令系统，中央处理机，总线系统，
　　外围设备，输入输出系统，操作系统支持。
　　在考查基本概念、基本理论的基础上，注重考查学生运用基本知识分析和解决实际问题
　　的能力。要求学生对计算机组成原理有比较深入的认识，主要包括下面3个方面：
　　1、深刻理解计算机系统各功能部件的功能、组成和工作原理，正确理解各功能部件之
　　间相互关系以及它们在计算机系统中所起的作用。
　　2、了解和掌握计算机系统某些部件的设计与分析技术，包括数据与指令的编码、存储、
　　输人输出等。
　　3、理解和掌握计算机系统中的基本概念和方法，并能将这些概念和方法运用在后继课
　　的学习中。
　　二、考试形式与试卷结构
　　1.考查内容及其考查比例：基本概念占30%分、理解占30%分、综合能力占40%分。
　　2.试卷结构与考试题型：填空题、选择、问答题、综合计算题等。
　　三、参考书目
　　《计算机组成原理》（第四版），白中英主编，科学出版社，2007年12月。
　　您所下载的资料来源于kaoyan.com考研资料下载中心
　　获取更多考研资料，请访问http://download.kaoyan.com
　　四、考查要点
　　1、计算机系统层次结构的实际含义，各部件的基本功能。计算机系统的基本概念：寄
　　存器、算术逻辑单元、存储器、字、字节、地址、指令流、地址流、CPU、总线、主存、
　　辅存、DMA等。
　　2、数的基本知识，计算机中数的表示方法，机器数的定义及与真值的互换，信息校验
　　的实际意义和方法。定点数运算方法；浮点数四则运算方法；算术逻辑单元的组成及工作原
　　理。运算器的功能，功能部件和结构。
　　3、存储器的基本知识，现代主存储器的结构和工作原理、设计原理和方法；高速缓冲
　　存储器的组织、工作原理，地址影象方法及替换算法；软硬盘存储器的结构及工作原理，磁
　　记录原理和磁记录方式；存储器的校验和CRC码校验。虚拟存储器概念及有关内容。
　　4、指令系统的意义和重要性；指令格式，指令和操作数的寻址方式和寻址过程；完备
　　性指令系统的设计。
　　5、中央处理机的功能与组织，指令处理的相关知识和控制原理，时序发生器设置的意
　　义及时序产生器的组织和工作原理。微程序控制器和硬布线控制器的设计思想、原理、组织
　　特征、工作原理及有关知识；流水CPU的有关概念。
　　6、单机系统总线结构及其特征，总线的仲裁与通信及其有关知识。
　　7、外围设备的类型、功能和特点；多种信息存储或显示方式的工作原理。
　　8、几种输入输出控制方式的控制原理和数据传送的过程。中断系统设置的意义及中断
　　过程实现的技术和相关知识。
　　9、操作系统对计算机各功能部件的工作机理。

　　点击【2015年上海理工大学研究生考试大纲】查看更多考研大纲。
【相关阅读】
研究生招生专业索引
2015年全国各学校考研大纲汇总