2016年华北电力大学 软件工程数据结构844大纲

2020年硕士研究生统一入学考试《计算机专业基础》第一部分考试说明一、考试性质计算机专业基础是计算机科学与技术学科（一级学科）、计算机技术工程领域硕士生入学考试的专业基础课。

考试对象为参加东北大学计算机科学与工程学院2020年全国硕士研究生入学考试的准考考生。

二、考试形式与试卷结构（一）答卷方式：闭卷，笔试（二）答题时间：180分钟（三）考试题型及比例简答题20%综合题80%（四）参考书目《数据结构》，严蔚敏，清华大学出版社，2001年。

《C语言程序设计》（第3版），谭浩强,清华大学出版社,2010年。

第二部分考查要点（一）数据结构考查要点1 绪论1.1 数据结构的基本概念和术语1.2 抽象数据类型的表示与实现1.3 算法和算法分析2 线性表2.1 线性表类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现3 栈和队列3.1 栈的类型定义、表示和实现3.2 栈的应用3.3队列的类型定义、表示和实现3.4 队列的应用4 串4.1 串的类型定义、表示和实现4.2串操作应用5 数组和广义表5.1数组的定义、顺序表示和实现5.2特殊矩阵的压缩存储5.3广义表的定义和存储结构6 树和二叉树6.1 树的定义和基本术语6.2二叉树的定义、基本性质和存储结构6.3遍历二叉树和线索二叉树6.4树和森林6.5哈夫曼树及哈夫曼编码7 图7.1 图的定义、基本术语和存储结构7.2图的遍历7.3图的连通性和最小生成树7.4有向无环图、拓扑排序和关键路径。

9 查找9.1 静态查找表9.2 动态查找表9.3 哈希表10 排序10.1 插入排序10.2 快速排序10.3 选择排序10.4 归并排序10.5 基数排序10.6排序方法的比较（二）C语言考查要点1、算法及其描述方法1.1算法的概念、特点1.2算法的描述方法（流程图、N-S流程图）1.3程序设计的三种基本结构；2、数据类型、运算符和表达式2.1变量和常量2.2 预处理命令2.3数据类型（整型、实型、字符型）2.4算术运算符、表达式3、顺序程序设计3.1各种类型数据的格式化输入/输出方法3.2字符数据的非格式化输入/输出方法3.2顺序程序的设计4、选择结构程序设计4.1关系运算符、逻辑运算符和条件运算符4.2 if、switch语句；4.3 if语句的嵌套。

849-软件工程专业基础综合操作系统一、考查目标操作系统是软件工程专业的一门核心专业基础课程，具有较强的理论性和实践性。

该课程的考试内容包括引论、进程管理、内存管理、存储管理（包括文件系统与输入/输出系统）、保护与安全五部分的相关概念、设计原理和实现方法。

考试的具体要求包括：1.了解操作系统在计算机系统中的作用、地位、发展和特点。

2.理解操作系统的基本概念、主要功能、主要组成部分，掌握操作系统各个组成部分的设计方法和实现技术。

3.能够运用所学的操作系统原理、方法和技术对相关问题进行分析和解决。

二、考试的内容1．导论1）操作系统的概念2）计算机系统的操作、存储结构、输入输出结构和计算机系统的体系结构。

3）操作系统的结构组成、操作系统的操作及各部分的功能、高速缓冲存储器CACHE 4）操作系统的分类和运行环境2．操作系统结构1）操作系统提供的服务类型2）操作系统的用户接口类型3）系统调用及类型4）操作系统的设计和实现方法5）操作系统的结构分类及优缺点6）虚拟机的基本概念和原理3．进程1）进程的概念、组织、控制和状态转换2）进程调度的基本概念3）进程的操作，包括进程的生成、终止等4）进程通信4．线程1）线程的概念与动机2）多线程模型5．CPU调度1）调度的基本概念2）调度的时机、切换和过程3）调度的基本准则4）典型调度方法：先来先服务调度算法、最短作业优先调度算法、优先级调度算法、时间片轮转调度算法、多级队列调度算法、多级反馈队列调度算法5）线程调度6）调度算法的性能评估6．进程同步1）进程同步的基本概念2）临界区访问的原则及实现临界区互斥的基本方法：软件实现方法和硬件实现方法3）信号量概念与基本机制4）经典同步问题：生产者－消费者问题、读者－写者问题、哲学家就餐问题和理发师问题。

5）管程的基本概念、原理和实现7．死锁1）死锁的概念及条件2）死锁的处理策略3）死锁的预防及实现方法4）死锁的避免：系统安全状态、资源分配图算法、银行家算法5）死锁的检测方法和解除8．主存1）内存管理的基本概念：程序的装入与链接、逻辑地址与物理地址、内存保护2）交换技术3）内存的分配管理方法：连续分配管理方法、分页管理方法、分段管理方法、段页式管理方法。

2016年南京大学842数据结构、软件工程、操作系统和计算机网络考研真题（回忆版）今年专业课继去年风格大变之后，果然又一次改变了出题方式，不再像前几年的类408风格，感觉有点走回南大08年统考前命题风格，今年一道选择题都没出。

数据结构（45分）总共四道大题，一道计算，三道算法一、计算题1．hash表（软院06年期末题）设散列表长度为11，散列函数H（K）＝（K的第一个字母在英文字母表中的序号，设A的序号为1）%11，若输入顺序为（B，D，M，CI，I，K，TM，X），处理冲突方法为线性探测法，要求：1）构造此散列表。

2）对表中所有键值分别查找1次，求出总的比较次数。

二、算法题1．长度为n的数组a[0…n－1]，编写一个算法在O（n）的时间复杂度内将数组中所有负数放在非负数前面。

2．已知first为不带表头结点的单链表的表头指针（如下图所示），链表中存储的都是整型数据，试写出求所有结点的data域平均值的递归函数。

（软院05年数据结构期末题）3．假设以数组Q[m]存放循环队列中的元素，同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数，试用C＋＋语言写出一个程序，给出该循环队列的类声明，给出队空条件和队满条件，并写出相应的插入元素（Add）和删除（Delete）元素的算法（用类模板，函数模板形式写）（软院04年考研原题）软件工程（45分）两道问答题以及三道大题一、问答题1．软件质量保障常用的是哪三种手段？（5分）2．给了5个需求描述，说出他们分别是哪种类型的需求。

（5分）二、大题1．分析ATM机的取款操作，编写他的用例。

（10分）2．分析下面代码违反了哪个面向对象原则？有什么后果？应如何改进？（10分）3．一道关于契约式设计和防御式编程的代码修改题。

（15分）这道题题目很长，具体我不太记得了，大概就是讲取款的操作，有几个条件：①取款金额必须是100的整数倍；②每次取款金额不能超过3000；③每天的取款金额不能超过两万（具体代码太长我忘了）操作系统（35分）题目比较常规，但是题量很大，全是大题，可是每道题才2、3分的样子1．在一个操作系统，inode节点中分别含有12个直接地址的索引和一、二、三级间接索引。

计算机844考研科目计算机科学与技术（Computer Science and Technology）是计算机科学与技术专业考研的一个重要科目，主要包括以下内容：1. 离散数学与图论（Discrete Mathematics and Graph Theory）：包括图论、逻辑、集合论、代数结构和离散概率等内容。

2. 数据结构与算法分析（Data Structures and Algorithm Analysis）：包括树、图、排序算法、查找算法、动态规划等内容。

3. 计算机组成原理（Computer Organization and Architecture）：包括数字系统、计算机组成、指令集、存储系统、输入输出等内容。

4. 操作系统（Operating System）：包括进程管理、内存管理、文件系统、设备管理等内容。

5. 数据库原理与应用（Database Principles and Applications）：包括数据库设计、关系数据库模型、SQL语言、数据库管理系统等内容。

6. 编程语言原理与编译技术（Principles of Programming Languages and Compiler Technology）：包括编程语言的语法、语义、编译器的构造原理与技术等内容。

7. 计算机网络（Computer Networks）：包括OSI模型、传输层协议、网络层协议、应用层协议等内容。

8. 软件工程（Software Engineering）：包括软件开发方法学、需求工程、软件测试、软件工程管理等内容。

除了以上科目外，还可能包括数值分析、人工智能、计算机视觉、计算机图形学等内容，具体考试科目会根据不同学校和专业的设置而有所差异。

2016年华北电力大学（北京）计算机技术考研专业目录、招生人数、参考书目、历年真题、复试分数线、答题方法、复习经验指导一、2016年华北电力大学（北京）计算机技术专业考研招生目录专业代码、名称及研究方向招生人数考试科目备注004-控制与计算机工程学院085211计算机技术3501.物联网与智能电网02.网络信息安全03.信息系统运行与维护04.数据库与信息系统05.电力企业管理与ERP06.信息处理技术1101思想政治理论2204英语二3302数学二4844数据结构复试科目：2选11数据库原理2计算机组成与结构同等学力加试科目：1高级语言程序设计2操作系统二、2015年华北电力大学（北京）计算机技术专业考研复试分数线考试科目政治外语专业一专业二总分计算机技术38385757280三、2016年华北电力大学（北京）计算机技术专业考研参考书科目名称书名作者出版社844数据结构《数据库概论》萨师煊高等教育出版社四、2013年华北电力大学（北京）计算机技术专业考研真题（回忆版）844数据结构数据结构：1、选择题：10个20分，就是普通的习题集里的选择题类型2、程序填空：8个16分，今年考了两个题：一个是判断一个双向链表是否是对称链表（2空）；一个是将一个二叉树的所有左右子树互换，算是是基于层次遍历二叉树算法（5空）。

3、算法设计题：2个24分（先写数据结构定义，再写算法）①告诉你一个多项表达式用链式存储，关键字coef（多项式系数）和expn（多项式指数），实现算法是求多项式的一阶导数。

②实现将图的邻接矩阵结构存储结构转换成邻接表存储结构。

4、综合应用题：1个15分设计一个电话簿管理系统（主要存储姓名和电话号码），主要进行的操作是检索和查找，简述其主要功能。

五、2016年华北电力大学（北京）计算机技术考研真题答题黄金攻略名师点评：认为只要专业课重点背会了，就能拿高分，是广大考生普遍存在的误区。

而学会答题方法才是专业课取得高分的关键。

（1）841 自动控制原理一、考试形式与试卷结构1、试卷满分及考试时间试卷满分为150分，考试时间为180分钟2、考试方式考试方式为闭卷、笔试3、试卷的题型结构选择填空题，分析计算题，综合设计题二、考察的知识及范围第一章自动控制系统导论内容：（1）自动控制系统的一般性概念和基本工作原理；（2）反馈控制系统的基本组成、分类及对控制系统的基本要求；（3）《自动控制原理》课程研究的主要内容及其发展现状。

重点掌握：自动控制系统的一般性概念和基本工作原理；反馈控制系统的基本组成、分类及对控制系统的基本要求第二章控制系统的数学模型内容：（1）复数和复变函数的基本概念，拉普拉斯变换和拉普拉斯反变换；（2）控制系统研究中几种主要数学模型：微分方程、传递函数和频率特性的内在联系；（3）典型环节的数学模型；（4）常见电气系统和一般机械系统的数学建模；（5）方块图的化简法则；（6）利用梅逊公式求取系统的传递函数。

重点掌握：传递函数的概念、结构图的建立与等效变换、梅逊公式第三章自动控制系统的时域分析内容：（1）系统阶跃响应性能指标；（2）一阶、二阶系统阶跃响应的特点及一阶、二阶系统动态性能；（3）高阶系统动态性能（4）线性系统稳定的充要条件；（5）利用劳斯判剧判别系统的稳定性；（6）稳态误差的定义；（7）稳态误差系数的求取及减小或消除系统稳态误差的方法；重点掌握：稳定性、稳态误差、系统阶跃响应的特点及动态性能与系统参数间的关系等有关概念，有关的计算方法。

第四章根轨迹法内容：（1）根轨迹的定义、幅值和相角条件；（2）根轨迹的绘制法则；（3）利用根轨迹分析系统的特性。

重点掌握：根轨迹的绘制方法，利用根轨迹分析系统的特性。

第五章线性系统的频域分析法内容：（1）频率特性的定义、求法及性质；（2）线性系统极坐标图画法；Nyquist图稳定判据的应用；（3）线性系统伯德图的画法；最小相位系统的定义及性质；（4）利用Bode图求取系统稳态误差；增益裕量和相位裕量的定义、物理意义和求取；重点掌握：正确理解频率响应、频率特性的概念及特点，明确频率特性的物理意义；熟练掌握运用奈奎斯特稳定判据和对数频率判据判定系统稳定性的方法；熟练掌握计算稳定裕度的方法。

上海电力学院840数据结构考研精品资料
一、重点名校考研真题汇编及考研大纲
1．重点名校：数据结构2016-2018年考研真题汇编（暂无答案）
2上海电力学院840数据结构考研大纲
①2021年上海电力学院840数据结构考研大纲。

二、金牌考研上海电力学院840数据结构考研资料
3．严蔚敏《数据结构》考研相关资料
（1）严蔚敏《数据结构》[笔记+课件+提纲]
①上海电力学院840数据结构之严蔚敏《数据结构》考研复习笔记。

②上海电力学院840数据结构之严蔚敏《数据结构》本科生课件。

③上海电力学院840数据结构之严蔚敏《数据结构》复习提纲。

（2）严蔚敏《数据结构》考研核心题库（含答案）
①上海电力学院840数据结构考研核心题库之选择题精编。

②上海电力学院840数据结构考研核心题库之填空题精编。

③上海电力学院840数据结构考研核心题库之算法设计题精编。

（3）严蔚敏《数据结构》考研模拟题[仿真+强化+冲刺]
①金牌考研上海电力学院840数据结构考研专业课六套仿真模拟题。

②上海电力学院840数据结构考研强化六套模拟题及详细答案解析。

③上海电力学院840数据结构考研冲刺六套模拟题及详细答案解析。

三、资料获取VX：ky21985
四、金牌考研研究生入学考试指定/推荐参考书目（资料不包括教材）5．上海电力学院840数据结构考研初试参考书
严蔚敏,吴伟民《数据结构》（C语言版），清华大学出版社，20125
五、金牌考研研究生入学适用院系/专业
6．上海电力学院840数据结构适用院系/专业
计算机科学与技术学院。

2016考研计算机学科专业基础综合考试大纲I考试性质计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的招生质量。

II考查目标计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。

要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

III考试形式和试卷结构一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟。

二、答题方式答题方式为闭卷、笔试。

三、试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分四、试卷题型结构单项选择题80分(40小题，每小题2分)综合应用题70分IV考查内容数据结构【考查目标】掌握数据结构的基本概念、基本原理和基本方法。

掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。

能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。

线性表(一) 线性表的定义和基本操作(二) 线性表的实现1. 顺序存储2. 链式存储3. 线性表的应用二、栈、队列和数组(一) 栈和队列的基本概念(二) 栈和队列的顺序存储结构(三) 栈和队列的链式存储结构(四) 栈和队列的应用(五) 特殊矩阵的压缩存储三、树与二叉树(一) 树的基本概念(二) 二叉树1. 二叉树的定义及其主要特征2. 二叉树的顺序存储结构和链式存储结构3. 二叉树的遍历4. 线索二叉树的基本概念和构造(三) 树、森林1. 树的存储结构2. 森林与二叉树的转换3. 树和森林的遍历(四) 树与二叉树的应用1. 二叉排序树2. 平衡二叉树3. 哈夫曼(Huffman)树和哈夫曼编码四、图(一) 图的基本概念(二) 图的存储及基本操作1. 邻接矩阵法2. 邻接表法3. 邻接多重表、十字链表(三) 图的遍历1. 深度优先搜索2. 广度优先搜索(四) 图的基本应用1. 最小(代价)生成树2. 最短路径3. 拓扑排序4. 关键路径五、查找(一) 查找的基本概念(二) 顺序查找法(三) 分块查找法(四) 折半查找法(五) B树及其基本操作、B+树的基本概念(六) 散列(Hash)表(七) 字符串模式匹配(八) 查找算法的分析及应用六、排序(一) 排序的基本概念(二) 插入排序1. 直接插入排序2. 折半插入排序(三) 气泡排序(bubble sort)(四) 简单选择排序(五) 希尔排序(shell sort)(六) 快速排序(七) 堆排序(八) 二路归并排序(Merge Sort)(九) 基数排序(十) 外部排序(十一) 各种内部排序算法的比较(十二) 排序算法的应用计算机组成原理【考查目标】理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。

计算机844考研科目
一、理论资料
1、算法与数据结构：涉及排序、哈希、图等数据结构，以及对其实
现的算法及其复杂度分析等技术。

2、计算机系统原理：包括汇编语言、体系结构、编译原理、处理器
组成、存储器管理、操作系统等内容。

3、计算机网络原理：涉及计算机网络拓扑、网络协议、网络安全等
内容。

4、软件工程：主要涉及软件开发的知识和方法，包括软件工程过程、软件开发技术、软件测试、软件维护等。

5、数据库：涉及数据库概念、模型、结构、查询语言及数据库管理
等基本知识。

6、编程语言：涉及通用面向对象程序设计、程序设计语言、自动机
理论、计算机性能分析等内容。

二、实际资料
1、综合应用：包括综合技术设计、系统设计、应用系统分析与设计、网站设计、软件开发、系统安全等方面的技术。

2、计算机应用技术：涉及计算机组成原理、计算机维护、网络技术、多媒体技术等内容。

3、编程实践：涉及编程能力的锻炼，使用经典的编程语言，如
C\C++等，加深对基础理论的理解和实际应用。

华北电力大学2016年硕士生入学考试初试科目考试大纲
科目代码：432
科目名称：统计学
一、考试的总体要求
掌握统计学的数据收集、处理和分析的一些基本概念、基本理论和方法，具有正确应用统计的基本理论知识分析和解决实际统计问题的能力。

二、考试的内容
（一）概率论
1.事件及关系和运算；
2.事件的概率；
3.条件概率和全概公式；
4.随机变量的定义；
5.离散型随机变量的分布列和分布函数；离散型均匀分布、二项分布和泊松分布；
6.连续型随机变量的概率密度函数和分布函数；均匀分布、正态分布；
7.随机变量的期望与方差；
（二）统计学
1.调查的组织和实施。

2.概率抽样与非概率抽样。

3.数据的预处理。

4.用图表展示定性数据。

5.用图表展示定量数据。

6.用统计量描述数据的水平：平均数、中位数、分位数和众数。

7.用统计量描述数据的差异：极差、标准差、样本方差。

8.参数估计的基本原理。

9.一个总体参数的区间估计。

10.样本量的确定。

11.假设检验的基本原理。

12.一个总体参数的假设检验。

13.方差分析的基本原理。

14.单因子和双因子方差分析的实现和结果解释。

15.变量间的关系；相关关系和函数关系的差别。

16.一元线性回归的估计和检验。

17.用残差检验模型的假定。

18.多元线性回归模型。

19.多元线性回归的拟合优度和显著性检验；
三、考试的题型
填空题、简答题、计算与分析题。

凯程考研集训营，为学生引路，为学员服务！
第 1 页 共 1 页 2016年华北电力大学电842计算机真题
（完整版）凯程首发
刚考完2016考研初试，凯程教育的电话瞬间变成了热线，同学们兴奋地汇报自己的答题情况，几乎所有内容都在凯程考研集训营系统训练过，所考专业课难度与往年相当，答题的时候非常顺手，相信凯程的学员们对此非常熟悉，预祝亲爱的同学们复试顺利。

考研分笔试、面试，如果没有准备，或者准备不充分，很容易被挂掉。

如果需要复试的帮助，同学们可以联系凯程老师辅导。

下面凯程老师把专业的真题全面展示给大家，供大家估分使用，以及2017年考研的同学使用，本试题凯程首发。

数据结构5个代码题
1删除顺序链表中值在min 和max 之间的数
2二叉链表找空值的点
3新建链表
4判断两点是否存在弧
5判断出栈数列可不可以由该进栈数列得到
操作系统大题就是王道课后的题的形式
磁盘调度 缺页次数 周转时间 逻辑物理第地址转换 pv 信号量。

844程序设计与数据结构
844程序设计与数据结构是一个计算机科学的课程编号，通常用于标识某些大学或学院的计算机科学或软件工程专业的课程。

这个课程通常涵盖了计算机程序设计和数据结构的基本概念和原理。

以下是844程序设计与数据结构可能涵盖的一些主题：
1. 编程语言和工具：介绍一种或多种编程语言（如C、C++、Java 等）和相关的开发工具。

学生将学习如何使用这些语言和工具来编写、调试和测试程序。

2. 数据类型和算法：介绍基本的数据类型（如整数、浮点数、字符等）和算法（如排序、搜索等），以及如何使用这些数据类型和算法来解决实际问题。

3. 控制结构：介绍基本的控制结构（如顺序、选择和循环）以及如何使用这些结构来编写更复杂的程序。

4. 函数和模块：介绍如何将程序分解为函数或模块，以便更好地组织和管理代码。

学生将学习如何定义、调用和传递参数。

5. 数据结构：介绍基本的数据结构（如数组、链表、栈、队列等）以及如何使用这些数据结构来存储和操作数据。

学生将学习如何实现这些数据结构以及如何选择合适的数据结构来解决特定的问题。

6. 算法分析：介绍算法的时间复杂度和空间复杂度分析的基本概念和方法。

学生将学习如何分析算法的效率和性能，以及如何优化算法以获得更好的性能。

7. 软件工程：介绍软件工程的基本概念和方法，包括需求分析、设计、编码、测试和维护。

学生将学习如何使用这些概念和方法来开发软件应用程序。

以上只是844程序设计与数据结构可能涵盖的一些主题，具体的课程内容和重点可能会有所不同，因此建议查阅相关的课程大纲或教材以获得更详细的信息。

声明此文件为参加2015年考研华北电力大学844数据结构初试的考生，根据回忆总结的题目。

相关题目可能与实际考试中的题目有出入，但是难度相当，可以作为备考华电计算机技术专硕的考生做为练习习题使用。

第一题选择，10道题20分，很简单，比王道上的题要简单的多把王道的题做了，选择基本没问题。

第二题填空题10空20分，也很简单。

第3题简答15分5问，第4题算法题55分4道题5小问。

第5题40分两道大题都很简单。

最后给大家些建议：卷子中除了算法题外，其他都很简单。

建议大家多看算法，主要是键表，树，图（主要是深度优先和广度优先遍历算法）。

另外考试大纲上没有写哈西表，但实际会考。

今年有两小题共5分考哈西表。

最后说一句：考研的路很漫长，如果选择了，希望大家坚持到底，尤其到了10份以后更要坚持。

祝学弟们考研成功！华电2015年初试考生2015年4月17日⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0100011101100001011010110011001000110010011011110华北电力大学（北京）2015年硕士研究生入学模拟试题考试科目：844数据结构（闭卷考试，时间120分钟，总分150分）1.数据结构中，与所使用的计算机无关的是数据的（ ）结构； A 、存储 B 、物理 C 、逻辑 D 、物理和存储2.在n 个结点的顺序表中，算法的时间复杂度是O （1）的操作是（ ） A 、访问第i 个结点（1≤i ≤n ）和求第i 个结点的直接前驱（2≤i ≤n ） B 、在第i 个结点后插入一个新结点（1≤i ≤n ） C 、删除第i 个结点（1≤i ≤n ） D 、将n 个结点从小到大排序3.有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。

A 、8 B 、63.5 C 、63 D 、74.线性表L 在（ ）情况下适用于使用链式结构实现。

5.A 、需经常修改L 中的结点值 B 、需不断对L 进行删除插入 C 、L 中含有大量的结点 D 、L 中结点结构复杂 5.不含任何结点的空树( )A 、是一棵树;B 、是一棵二叉树;C 、是一棵树也是一棵二叉树;D 、既不是树也不是二叉树6.从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（ ） A 、希尔排序 B 、归并排序 C 、插入排序 D 、选择排序7.已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是( ) A 、 0 2 4 3 1 6 5 B 、 0 1 3 5 6 4 2C 、 0 1 2 3 4 6 5D 、 0 1 2 3 4 5 6 8.已知完全二叉树有28个结点，则整个二叉树有( )个度为1的结点。

课程编号：842课程名称：数据结构一、考试的总体要求掌握常用数据结构的逻辑结构、存储结构和基本操作，灵活运用所学的数据结构解决实际问题。

二、考试的内容及比例1．基本概念：数据、数据元素、数据对象、数据类型与抽象数据类型、时间复杂度、空间复杂度、线性结构（线性表、栈与队列）、非线性结构（树与二叉树、图）、查找、排序、哈夫曼树、二叉排序树、二叉平衡树、哈希表、AOV网、AOE网。

2．常用数据结构的基本内容：（1）线性表：线性表的特点；顺序表和链表的数据类型描述和基本操作的实现；（2）限定线性表：栈和队列的特点；顺序栈、链栈、循环队列和链队列的数据类型描述和基本操作的实现。

（3）二叉树与树：二叉树和树的特点；二叉树与树、森林的转换；二叉链表、孩子兄弟链表和双亲孩子链表的数据类型描述和基本操作的实现。

（4）图：图的特点；邻接矩阵和邻接表的数据类型描述和基本操作的实现。

3．数据处理技术：（1）查找：静态查找（顺序查找（带岗哨）、折半查找）；动态查找（二叉排序树、二叉平衡树和B-树的查找、插入和删除）；查找算法的性能分析（ASL）（2）内排序：插入类排序（直接插入排序、折半插入排序、希尔排序）、交换类排序（冒泡排序、快速排序）、选择类排序（简单选择排序、堆排序）、归并类排序（二路归并排序）4、基本应用：（1）线性表的应用：一元多项式的计算（2）栈的应用：栈与递归、表达式的计算（3）队列的应用：二叉树的层次遍历和图的广度遍历（4）二叉树和树的应用：哈夫曼树及其编码/解码，用遍历算法框架求解其他问题（5）图的应用：最小生成树、最短路径、拓扑排序、关键路径三、考试的题型概念解释、问题简答、算法与程序设计、综合应用。