电子科技大学820计算机基础考试大纲

考试科目820计算机专业基础考试形式笔试(闭卷)考试时间180分钟考试总分1５0分本科目包括《数据结构》与《计算机操作系统》两门课程,总分１50分,两门课程各占75分《数据结构》一、总体要求　 《

考试科目 820计算机专业基础 考试形式 笔试(闭卷) 考试时间 180分钟 考试总分 1５0分 本科目包括《数据结构》与《计算机操作系统》两门课程,总分１50分,两门课程各占75分 《数据结构》 一、总体要求 《数据结构》就就是计算机程序设计得重要理论技术基础,就就是计算机科学与技术学科 得核心课程。要求学生通过数据结构课程得学习,能够针对具体得应用与算法策略选择与设计恰当 得数据结构，并能编程实现。 二、内容及比例 《数据结构》部分主要考试内容(带下划线文字表示重点部分): 1、数据结构及算法得相关概念与术语 重点:数据结构及算法得概念；数据得逻辑结构与存储结构;算法得定义及特性;算法时间复 杂度与空间复杂度得分析方法。 ２、线性表（包括栈、队列与数组)得存储结构、基本运算及应用 重点:线性表、栈与队列得存储结构及其存储特点;线性表得基本操作在顺序存储及链式存 储上得实现;各种变形链表(循环链表、双向链表、带头结点得链表等)得表示与基本操作得实现； 递归过程得特点及实现方法;循环队列得判满、判空方法;稀疏矩阵得存储方法（三元组、十字链表) 与基本运算得实现(转置、矩阵加法等)。 3、广义表得存储结构、基本运算及应用 重点:广义表得基本概念、基本操作及存储结构。 4、树与二叉树得存储结构、遍历算法及应用 重点:二叉树与树得递归定义、基本术语、基本性质;满二叉树与完全二叉树得概念及特征; 二叉树、树及森林得顺序存储及链式存储，以及相互转换算法;线索二叉树、二叉排序树得构建； 各种遍历算法;哈夫曼树与哈夫曼编码得构建与应用。 5、图得存储结构、遍历算法及应用 重点:图得基本概念与术语;图得基本存储方法:邻接矩阵、关联矩阵、邻接表、逆邻接表、 十字链表;图得遍历算法:深度优先搜索算法与广度优先搜索算法；图得基本应用:最小生成树、最 短路径,拓扑排序与关键路径。 6、静态查找表、动态查找表与哈希表(包括二叉排序树、AVＬ树) 重点:静态查找表、动态查找表与哈希表上得查找方法;哈希函数得基本构造方法,解决地址 冲突得基本策略;理解各查找算法得时间复杂度与空间复杂度。 7、五类内部排序算法得算法思想、时间特性及稳定性 重点:插入排序、交换排序、选择排序、归并排序与基数排序等五类排序算法得算法思想与时 间复杂度;五类排序算法得特性与适用情形。 三、题型及分值 单项选择题:1０% 填空题：1０% 简答题:50% 算法题：30％ 分为阅读、修改与编写算法三类: 阅读算法:阅读指定算法，回答使用得数据结构、算法实现得功能或执行得结果; 修改算法:阅读指定算法,指出算法得错误并修正;指出算法得不足并改进;按给定功能填写算法 空缺部分; 编写算法:根据算法功能要求与选定得数据结构,用程序设计语言(Ｃ与Pascaｌ均可）编写算