2016年上海理工大学光电信息与计算机工程学院考研大纲

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

　　《电工技术基础》课程考试大纲
　　参考教材：
　　<<电工学>>上册(电工技术)，第六版，秦曾煌主编，高等教育出版社，2003年12月
　　1.电路的基本概念与基本定律
　　了解电路模型的概念，电路的组成部分和作用。区分电压、电流参考方向和实际方向，掌握电源有载工作和开路、短路时的电压、电流和功率。重点掌握欧姆定律和基尔霍夫定律及其电路计算方法。了解电位的概念、电压与电位的区别。
　　2.电路的分析方法
　　掌握电阻串联、并联的等效计算方法，了解电压源和电流源模型及其等效变换，重点掌握用支路电流法、结点电压法、叠加定理、戴维南定理和诺顿定理分析电路。
　　3.电路的暂态分析
　　了解电阻、电感和电容元件的电性能，了解电路暂态过程产生的原因，掌握储能元件的换路定则。掌握RC、RL电路的零输入响应、零状态响应和全响应的概念和分析，重点掌握电路三要素中初始值、稳态值和时间常数的概念，并用三要素法分析一阶电路。
　　4.正弦交流电路
　　掌握正弦量的相量表示法及相量的运算，重点掌握用相量法分析正弦交流电路，以及阻抗的串并联计算方法。掌握功率因数的概念和功率因数提高的目的和方法。
　　5.三相电路
　　掌握三相对称电源的线电压和相电压的概念及相应的线电压、相电压的大小和相位关系。在星形和三角形连接时，对称和不对称三相负载的电路分析计算及三相电路的功率计算。
　　6.磁路与铁心线圈电路
　　了解磁路及其分析方法，了解交流铁心线圈电路及计算分析。掌握变压器的工作原理，特性及含变压器电路的分析计算。
　　7.交流电动机
　　重点掌握三相异步电动机的构造、转动原理、电路分析和机械特性。掌握电动机的起动、制动和调速。了解电动机的铭牌数据含义。
　　8．直流电动机
　　一般了解直流电动机的构造、工作原理、机械特性和起动、反转和调速。
　　9．控制电机
　　一般了解伺服电机、测速发电机和步进电机。
　　10．继电接触器控制系统
　　了解常用控制电器及电路，了解电动机直接起动、正反转的控制电路及其行程和时间控制电路。
　　11．可编程控制器及其应用
　　一般了解可编程控制器的构造、工作方式和程序编制。
　　12．工业企业供电与安全用电
　　了解发电和输电、工业企业的配电，重点了解安全用电，接地和接零，掌握节约用电的方法。
　　13．电工测量
　　了解电工测量仪表的分类和类型，掌握电压、电流和功率的测量，了解万用表、兆欧表等常用的电工测量工具及使用。

　　《数据结构及操作系统》考试大纲
　　第一部分：数据结构
　　一、参考书目
　　数据结构（第二版），严蔚敏主编，2006，清华大学出版社。
　　二、考试内容要求
　　1、了解数据结构及其分类、数据结构与算法的密切关系。
　　2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。
　　3、掌握设计算法的步骤和算法分析方法。
　　4、掌握数据结构在排序和查找等常用算法中的应用。
　　5、初步掌握文件组织方法和索引技术。
　　三、考试内容
　　1、数据结构基本概念及简单的算法分析
　　1)什么是数据结构
　　2)抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言
　　3)数据结构的抽象层次
　　4)算法定义
　　5)性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂.
　　2、数组
　　1)作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组；数组的顺序存储方式
　　2)顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例
　　3)字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配
　　3、链表
　　1)单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；单链表的游标类；静态链表
　　2)循环链表：循环链表的类定义；用循环链表解约瑟夫问题；多项式及其相加：多项式的类定义；多项式的加法
　　3)双向链表
　　4、栈和队列
　　1)栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示
　　2)队列：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示；3)队列的应用举例
　　4)优先级队列：优先级队列的定义；优先级队列的存储表示
　　5、递归
　　1)递归的概念
　　2)迷宫问题
　　3)递归过程与递归工作栈
　　4)利用栈实现的迷宫问题非递归解法
　　5)广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广6)义表的访问算法；广义表的递归算法
　　6、树与森林
　　1)树和森林的概念：树的定义；树的术语；树的抽象数据类型
　　2)二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型
　　3)二叉树的表示：数组表示；链表存储表示
　　4)二叉树遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例；二叉树遍历的游标类；不用栈的二叉树中序遍历算法
　　5)线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化
　　6)堆：堆的定义；堆的建立；堆的插入与删除
　　7)树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历
　　二叉树的计数
　　8)霍夫曼树：路径长度；霍夫曼树；霍夫曼编码
　　7、集合与搜索
　　1)集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用位向量实现集合抽象据类型；用有序链表实现集合的抽象数据类型
　　2)等价类：等价关系与等价类；确定等价类的链表方法；并查集
　　3)简单的搜索结构：搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的对分搜索
　　4)二叉搜索树：定义；二叉搜索树上的搜索；二叉搜索树的插入；二叉搜索树的删除；与二叉搜索树相关的中序游标类
　　5)AVI树：AVI树的定义；平衡化旋转；AVI树的插入和删除；AVI树的高度
　　8、图
　　1)图的基本概念：图的基本概念；图的抽象数据类型
　　2)图的存储表示：邻接矩阵；邻接表；邻接多重表
　　3)图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；重连通分量
　　4)最小生成树：克鲁斯卡尔算法；普里姆算法
　　5)活动网络：用顶点表示活动的网络；用边表示活动的网络
　　9、排序
　　1)插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序
　　2)交换排序：起泡排序；快速排序
　　3)选择排序：直接选择排序；锦标赛排序；堆排序
　　4)归并排序：归并；迭代的归并排序算法；递归的表归并排序
　　5)基数排序：多关键码排序；链式基数排序
　　6)外排序：外排序的基本过程；k路平衡归并；初始归并段的生成；最佳归并树
　　10、索引与散列结构
　　1)静态索引结构：线性索引；倒排表；m路静态查找树
　　2)动态索引结构：动态的m路查找树；b_树；b_树的插入；b_树的删除；b+树
　　3)散列：词典的抽象数据类型；散列表与散列方法；散列函数；处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析
　　第二部分：操作系统
　　一、参考书目
　　汤小丹等，《计算机操作系统》（第三版），西安电子科技大学出版社，2007年
　　二、考试内容范围
　　要求考生重点掌握操作系统设计方法与实现技术，能够运用所学的操作系统原理、方法与技术分析问题和解决问题。
　　1、操作系统引论
　　操作系统的目标与作用；操作系统的发展与分类；操作系统的基本特性与主要功能。
　　2、进程管理
　　进程的基本概念；进程控制；进程同步（进程同步的基本概念、实现临界区互斥的基本方法、信号量、经典同步问题）；进程通信（共享存储系统、消息传递系统、管道通信）；线程概念；线程的实现。
　　3、处理机调度
　　调度的基本概念；调度的基本准则；典型调度算法（先来先服务调度算法、短作业（短进程、短线程）优先调度算法、时间片轮转调度算法、优先级调度算法、高响应比优先调度算法、多级反馈队列调度算法）。
　　4、死锁
　　死锁的基本概念；死锁预防；死锁避免（系统安全状态、银行家算法）；死锁检测与解除。
　　5、存储器管理
　　程序装入与链接；连续分配管理方式；非连续分配管理方式（基本分页存储管理方式、基本分段存储管理方式；段页式存储管理方式）；虚拟存储器的基本概念；请求分页存储管理方式；请求分段存储管理方式；页面置换算法（最佳置换算法（OPT）、最近最久未少使用置换算法（LRU）、时钟置换算法（CLOCK））。
　　6、设备管理
　　I/O系统；I/O控制方式；缓冲管理；I/O软件；设备分配；磁盘存储器的管理（磁盘性能、磁盘调度、磁盘高速缓存）。
　　7、文件管理
　　文件与文件系统的基本概念；文件的逻辑结构（顺序文件；索引文件；索引顺序文件）；外存分配方式（连续分配、链接分配、索引分配）；文件控制块和索引节点；目录结构；文件存储空间的管理方法；文件共享；文件保护。
　　三、试卷结构
　　基本知识测试占50%，综合应用测试占50%。
　　命题着重考察考生对基本概念、基本知识和基本理论的掌握情况，以及对基本方法的运用能力。