2016年中国农业大学081200计算机科学与技术考研大纲

　　821数据结构
　　一、考查目标
　　1．理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。
　　2．掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。
　　3．能够选择合适的数据结构和方法进行问题求解。

　　二、考试形式和试卷结构
　　1．试卷满分及考试时间
　　试卷满分150分，考试时间180分钟。
　　2．答题方式
　　答题方式为笔试、闭卷。
　　3．试卷内容与题型结构
　　单选题10题每小题2分共20分
　　填空题10题每小题2分共20分
　　简答题5题每小题5分共25分
　　综合题3题每小题15分共45分
　　算法题4题每小题10分共40分

　　三、考查内容
　　1．概念
　　（1）基本概念和术语
　　数据
　　数据结构
　　抽象数据类型
　　（2）算法的描述和分析
　　算法、算法的时间复杂度和空间复杂度概念
　　算法描述和算法分析的方法，对于一般算法能分析出时间复杂度

　　2．线性表
　　（1）线性表的概念
　　线性表的逻辑结构
　　线性表的存储结构：顺序表，单链表，双链表，循环链表
　　（2）线性表的实现
　　顺序存储结构：查找、插入、删除等主要操作及其平均时间性能分析
　　链式存储结构：查找、插入、删除等主要操作及其平均时间性能分析

　　3．栈、队列
　　（1）栈和队列的概念
　　栈和队列的逻辑结构
　　栈和队列的存储结构：顺序栈，循环队列，链式栈，链式队列
　　（2）栈和队列的实现
　　顺序存储结构：入栈、出栈、入队、出队等主要操作及其平均时间性能分析
　　链式存储结构：入栈、出栈、入队、出队等主要操作及其平均时间性能分析

　　4．数组和广义表
　　（1）数组和广义表的概念
　　数组和广义表的逻辑结构
　　数组的存储结构：特殊矩阵压缩存储、稀疏矩阵压缩存储（三元组表）
　　广义表的存储结构：链式存储
　　（2）数组和广义表的实现
　　数组顺序存储结构：一般数组顺序存储的地址计算方法
　　广义表链式存储结构：非空广义表的求表头和表尾运算

　　5．树和二叉树
　　（1）树和二叉树的概念
　　树和二叉树的逻辑结构
　　树和二叉树的存储结构：树的孩子兄弟二叉链表、二叉树的二叉链表
　　树和二叉树的遍历：树的三种遍历、二叉树的三种遍历
　　树和二叉树的转换
　　（2）树和二叉树的实现
　　二叉树的递归遍历
　　Huffman树
　　Huffman编码

　　6．图
　　（1）图的概念
　　图的逻辑结构
　　图的存储结构：邻接矩阵、邻接表
　　图的遍历：深度优先搜索、广度优先搜索
　　（2）图的实现
　　最小（代价）生成树：Prim和Kruskal方法
　　最短路径：Dijkstra方法
　　拓扑排序
　　关键路径

　　7．查找
　　（1）查找的概念
　　查找表、查找分类、查找结构
　　查找算法效率的评判标准：平均查找长度
　　（2）静态表及其查找
　　顺序查找
　　折半查找
　　（3）动态表及其查找
　　二叉排序树
　　平衡二叉树
　　（4）哈希表及其查找
　　哈希函数
　　处理冲突方法
　　哈希查找
　　（5）各种查找算法的分析

　　8．排序
　　（1）排序的概念
　　排序方法稳定性、排序分类
　　排序算法效率的评判标准
　　（2）插入排序
　　简单插入排序
　　希尔排序
　　（3）交换排序
　　冒泡排序
　　快速排序
　　（4）选择排序
　　简单选择排序
　　堆排序
　　（5）归并排序
　　二路归并排序
　　分治归并排序
　　（6）各种排序算法的比较

　　四、题型举例
　　1．选择题
　　在单链表中成功查找一个元素的等概率下的平均搜索长度是。
　　A.n    B.n/2   C.(n+1)/2   D.n+1
　　2．填空题
　　深度为5的二叉树至多有个结点。
　　3．简答题
　　请比较顺序表和单链表在存储空间和数据访问方面的特点。
　　4．综合题
　　已知一棵二叉树的先序遍历的结果是ABDECF，中序遍历的结果是DEBAFC，请画出这棵二叉树，并写出该二叉树的后序遍历结果。
　　5．算法题
　　分析下面算法功能，以及时间复杂度。
　　#defineList_Size100
　　typedefstruct{
　　ElemTypeelem[List_Size];
　　intlength;
　　}SqList;
　　voidex(SqListla,SqListlb,SqList&lc){
　　i=0;j=0;k=0;
　　while(i<la.length&&j<lb.length){
　　if(la.elem[i]<=lb.elem[j])lc.elem[k++]=la.elem[i++];
　　elselc.elem[k++]=lb.elem[j++];
　　}
　　while(i<la.length)lc.elem[k++]=la.elem[i++];
　　while(j<lb.length)lc.elem[k++]=lb.elem[j++];
　　}//ex
　　(2)用循环单链表实现队列，要求该队列只使用一个指向队尾指针。请写出结点和队列的类型定义，并分别编写队列初始化、入队、出队算法。

　　五、参考教材
　　(1)数据结构，严蔚敏编著，清华大学出版社
　　(2)数据结构，彭波主编，北京邮电大学出版社

　　电路原理考试大纲
　　一、考试性质
　　电路原理考试是电力系统及其自动化、自动化硕士生入学考试科目之一，由中国农业大学自行制定考试大纲、自行命题的选拔性考试。本考试大纲的制定力求反 映电力系统及其自动化、自动化硕士专业学位的特点，科学、公平、准确、规范地测评考生的相关知识基础、基本素质和综合能力。电路原理考试的目的是测试考生 的电路基础知识、电路分析与计算能力及电路原理应用能力。

　　二、评价目标
　　(1)要求考生具有较全面的电路基础知识。
　　(2)要求考生具有较强的电路分析与计算能力。
　　(3)要求考生具有较高的电路原理应用能力。

　　三、考试内容
　　（一）电路的基本概念和基本定律
　　1、电路的基本物理量
　　2、电压电流关联参考方向
　　3、理想电路元件特性
　　4、电功率的计算
　　5、基尔霍夫电流定律和基尔霍夫电压定律

　　（二）电路的等效变换
　　1、电阻的串、并联
　　2、Ｙ一Δ互换
　　3、两种电源模型的等效变换
　　4、含受控源的一端口的输入电阻

　　（三）电路的分析计算及电路定理
　　1、图、节点、支路、树与树支、连支、回路、网孔、平面图的概念
　　2、电路KCL和KVL方程的独立性
　　3、网孔电流法
　　4、回路电流法
　　5、节点电压法

　　（四）电路定理
　　1、叠加原理
　　2、戴维南定理和诺顿定理、最大功率传输
　　3、特勒根定理
　　4、互易定理

　　（五）含理想运算放大器电路的分析
　　1、运算放大器的基本概念
　　2、含理想运算放大器电路的分析计算及应用

　　（六）一阶电路
　　1、一阶电路的初始条件、时间常数
　　2、一阶电路零输入响应、零状态响应及全响应
　　3、一阶电路的三要素分析法
　　4、一阶电路的阶跃响应、冲激响应

　　（七）正弦稳态电路
　　1、正弦量三要素、有效值和相位差，正弦量的相量
　　2、电阻、电感、电容元件电压电流关系的相量形式
　　3、复阻抗、复导纳
　　4、相量图
　　5、正弦交流电路的分析
　　6、有功功率、无功功率、复功率的概念及计算
　　7、功率因数及其提高
　　8、串联谐振和并联谐振

　　（八）含有耦合电感的电路
　　1、互感的去耦等效电路
　　2、含互感电路的分析计算
　　3、空心变压器及理想变压器

　　（九）三相电路
　　1、相电压与线电压、相电流与线电流的关系
　　2、对称及不对称三相电路的计算
　　3、三相电路的功率测量

　　（十）非正弦周期电流电路
　　1、非正弦周期电量的有效值、平均功率
　　2、非正弦周期电流电路的稳态响应

　　（十一）拉氏变换及网络函数
　　1、线性电路的运算形式
　　2、用运算电路进行动态电路的复频域分析与计算
　　3、网络函数及其零、极点
　　4、网络函数与单位冲激响应的关系

　　（十二）电路方程的矩阵形式
　　1、割集、节点-支路关联矩阵、基本回路矩阵、基本割集矩阵
　　2、回路电流方程、节点电压方程、割集电压方程的矩阵形式
　　3、状态方程

　　（十三）二端口网络
　　1、二端口网络的参数矩阵及计算
　　2、二端口网络的等效电路
　　3、二端口网络的联接
　　4、回转器、负阻抗变换器

　　四、考试形式和试卷结构
　　（一）考试时间
　　考试时间为180分钟。
　　（二）答题方式
　　答题方式为闭卷、笔试。
　　试卷由试题和答题纸组成。答案必须写在答题纸相应的位置上。
　　（三）试卷满分及考查内容分数分配
　　试卷满分为150分，其中：
　　直流电路与交流电路90分，直流电路包括考试内容中的（一）～（四），交流电路包括考试内容中的（七）～（十）；
　　电路过渡过程30分，包括考试内容中的（六）、（十一）；
　　其他30分，包括考试内容中的（五）、（十二）、（十三）。
　　（四）试卷题型比例
　　直流电路与交流电路90分
　　单项选择题6小题，每小题5分，共30分
　　计算题3小题，每小题20分，共60分
　　电路过渡过程30分
　　单项选择题2小题，每小题5分，共10分
　　计算题1小题，每小题20分，共20分
　　其他30分
　　单项选择题2小题，每小题5分，共10分
　　计算题1小题，每小题20分，共20分

　　五、样卷（见附件一）
　　一、选择题（每题5分，共50分）
　　1．如图所示正弦稳态电路中，is(t)=5sin2t,i2=0,电压表的读数（有效值）为。
　　A20V      B40V       C30V       D10V
　　二、计算题（每题20分，共100分）
　　1、如下图（a）所示电路原处于稳定状态。时开关闭合，求时（b）中的电容电压和电流。

　　六、主要参考资料
　　《电路》邱关源主编高等教育出版社(第四版)