2019-西安电子科技大学-833《计算机学科专业基础综合》-考试大纲.docx

2019年西安电子科技大学833《计算机学科专业基础综合》考试大纲考察目标计算机学科专业基础综合考试涵盖数据结构和计算机组织与体系结构等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法,能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。考试形式和试卷结构试卷满分及考试时间:本试卷满分为150,考试时间为180分钟答题方式:闭卷,笔试试卷内容结构:数据结构75分、计算机组织与体系结构75分考察范围数据结构:【总体要求】“数据结构”要求学生掌握数据结构的基本理论和基本方法,使学生具备基本的数据结构分析、设计、求解实际问题的能力。要求掌握数据结构的基本概念、基本原理和基本方法;掌握线性表、树与二叉树、图的逻辑结构、物理结构、基本操作,以及基本操作在不同的物理结构上的实现,并能够对操作算法进行基本的时间复杂度和空间复杂度进行分析;掌握基本的查找和排序方法,并能够利用这些方法对实际问题进行分析和求解,具备采用C或C++或JAVA语言设计与实现算法的能力。(一)、算法的基本定义,数据结构的逻辑结构和物理结构,算法的性能评价方法。(二),线性表的顺序存储和链式存储,线性表的基本运算在顺序存储和链式存储结构上的实现。  (三)、基本操作和存储结构。(四)、(五)、数组的顺序存储和特殊矩阵的压缩存储。(六)、存储结构和性质,树与二叉树的遍历,树、森林与二叉树的转换,哈夫曼(Huffman)树的概念和应用。(一)树的概念(二)二叉树二叉树的定义及主要特征二叉树的顺序存储结构二叉树的链式存储结构二叉树的遍历线索二叉树的基本概念和构造(三)树、森林树的存储结构树、森林与二叉树的转换树和森林的遍历(四)树与等价问题(五)哈夫曼(Huffman)树和哈夫曼编码(七)、图的遍历、图的基本应用算法。(一)   图的基本概念(二)   图的存储结构 邻接矩阵法 邻接表法 逆邻接表法十字链表邻接多重表(三)   图的遍历 深度优先遍历广度优先遍历(四)   图的基本应用算法连通分量与最小生成树拓扑排序关键路径 最短路径(八)、静态查找表和动态查找表、哈希表。(一)   查找的基本概念(二)   静态查找表顺序查找法 折半查找法索引顺序查找法(三) 动态查找表   二叉排序树及其基本操作平衡二叉树概念B树及其基本操作B+树的基本概念(五)   哈希(Hash)表哈希表的基本概念哈希函数的构造冲突的解决方法(六)   查找算法的分析及应用 (九)、排序算法和性能分析。(一)   排序的基本概念(二)   插入排序直接插入排序折半插入排序2-路插入排序表插入排序希尔排序(三)   交换排序起泡排序快速排序(四)   选择排序简单选择排序堆排序(五)  归并排序(六)   基数排序(七)外部排序计算机组织与体系结构:【总体要求】“计算机组织与体系结构”要求学生掌握单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式,具有完整的计算机系统的整机概念。要求掌握计算机系统层次化结构概念,熟悉硬件与软件之间的界面;掌握计算机数据表示的方法,包括定点数和浮点数的表示;掌握运算器的原理和实现电路;掌握存储层次的概念,会解决Cache存储的一些基本问题;掌握不同类型存储器形式,包括SRAM,DRAM,ROM;掌握磁盘基本原理及RAID;掌握指令集体系结构的基本知识和基本实现方法;掌握中央处理器控制器部分的两种基本设计方法,即硬布线和微程序控制,能够根据模拟中央处理器化简控制信号逻辑或者编写简单微操作流程;熟悉中央处理器的时序逻辑,即指令周期、CPU周期、节拍周期、时钟周期之间的关系;掌握计算机输入输出系统的基本概念,程序查询方式、中断方式和直接内存获取方式;掌握总线的仲裁方式和特点;基本掌握