当前位置：文档之家 › 北航数据结构

北航数据结构

  • 格式：pdf
  • 大小：237.39 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

北航考研991考试大纲

北航考研991考试大纲

991数据结构与C语言程序设计考试大纲（2013版）2013年《数据结构与C语言程序设计》考试内容包括“数据结构”与“C语言程序设计”两门课程的内容，各占比例50%，试卷满分为150分。

《数据结构》部分指定参考书：《数据结构教程（第二版）》唐发根编著北京航空航天大学出版社一、概述1．数据的逻辑结构与存储结构的基本概念；2．算法的定义、基本性质以及算法分析的基本概念，包括采用大 形式表示时间复杂度和空间复杂度。

二、线性表1．线性关系、线性表的定义，线性表的基本操作；2．线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和双向链表)的构造原理；3．在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)。

三、堆栈与队列1．堆栈与队列的基本概念与基本操作；2．堆栈与队列的顺序存储结构与链式存储结构的构造原理；3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计；4．堆栈和队列在解决实际问题中应用。

四、树与二叉树1．树与二叉树的基本概念，基本特征、名词术语；2．完全二叉树与满二叉树的基本概念，二叉树的基本性质；3．二叉树与树、树林之间的转换；4．二叉树的顺序存储结构与二叉链表存储结构；5．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，以及在二叉链表基础上各种遍历算法(重点为非递归算法)的设计与应用；6．二叉排序树的基本概念、建立(插入)、查找与平均查找长度ASL的计算；7．哈夫曼(Huffman)树的基本概念，哈夫曼树的构造与带权路径长度(WPL)的计算。

五、图1．图的基本概念、名词术语；2．图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点；3．图的深度优先搜索与广度优先搜索；4．最小(代价)生成树、最短路径、AOV网与拓扑排序以及AOE网与关键路径的基本概念与求解过程。

北航数据结构试题及答案

北航数据结构试题及答案

北航数据结构试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用什么数据结构来实现？A. 链表B. 栈C. 数组D. 树答案：C2. 下列关于二叉树的描述中，错误的是：A. 二叉树的第i层最多有2^(i-1)个节点B. 任意非空二叉树的叶子节点数等于度为2的节点数加1C. 任意非空二叉树的叶子节点数等于度为2的节点数减1D. 任意非空二叉树的叶子节点数等于度为2的节点数答案：C3. 在图的遍历算法中，深度优先搜索（DFS）使用的数据结构是：A. 队列B. 栈C. 链表D. 数组答案：B4. 哈希表的冲突解决方法不包括以下哪种？A. 开放定址法B. 链地址法C. 再散列法D. 排序法答案：D5. 快速排序算法的时间复杂度最坏情况下为：A. O(nlogn)B. O(n^2)C. O(n)D. O(1)答案：B6. 以下排序算法中，时间复杂度为O(nlogn)的是：A. 冒泡排序B. 快速排序C. 选择排序D. 插入排序答案：B7. 以下关于堆的描述中，正确的是：A. 堆是一种特殊的二叉树B. 堆是一种完全二叉树C. 堆是一种平衡二叉树D. 堆是一种链表答案：A8. 在一个长度为n的有序数组中查找一个元素，使用二分查找算法的时间复杂度是：A. O(n)B. O(nlogn)C. O(logn)D. O(1)答案：C9. 以下算法中，不属于动态数据结构的是：A. 链表B. 栈C. 数组D. 哈希表答案：C10. 以下关于图的描述中，错误的是：A. 图是由顶点和边组成的B. 图的顶点可以有0个或多个C. 图的边可以有向或无向D. 图的顶点数一定大于边数答案：D二、多项选择题（每题3分，共15分）1. 下列哪些是线性表的存储结构？A. 顺序存储B. 链式存储C. 索引存储D. 散列存储答案：A, B2. 在图的表示方法中，以下哪些是正确的？A. 邻接矩阵B. 邻接表C. 边表D. 顶点表答案：A, B, C3. 下列哪些排序算法是稳定的？A. 冒泡排序B. 快速排序C. 插入排序D. 选择排序答案：A, C4. 在数据结构中，以下哪些是递归算法的特点？A. 问题可以分解为更小的子问题B. 每个子问题都是原问题的实例C. 存在递归终止条件D. 递归算法的时间复杂度一定比迭代算法高答案：A, B, C5. 在使用链表实现栈时，以下哪些操作是合法的？A. pushB. popC. peekD. clear答案：A, B, C三、简答题（每题5分，共30分）1. 请简述什么是递归，并给出一个递归算法的例子。

北航软件工程基础复习

北航软件工程基础复习

软件工程技术基础复习指南一．数据结构1.术语：1.数据；2.数据元素；3数据结构；4.结构2.数据结构定义：就是具有结构的数据元素的集合。

3.算法的定义：用来解决某个特定课题的指令的集合。

4.算法的性质：输入、输出、有穷性、确定性、有效性5.算法描述：自然语言、程序流程图、具体程序语言6.算法分析：指对算法质量优劣的评价。

（时间复杂度、空间复杂度、可读性、可移植性、易测试性）7.时间复杂度：依据算法编写的程序在计算机中运行时间多少的度量（关键语句之行的次数）O（n）；（O(log2n)（二分检索）<O(n)（比较两个具有n个字符串）<O(nlog2n)<O(n2)<O(n3)（常规矩阵乘）<O(2n)<O(n!)）；O（1）：访问数组中的元素是常数时间操作8.空间复杂度：依据算法编写的程序在计算机中占存储空间多少的度量9.频度统计法：以语句执行的次数的多少作为算法的时间量度的分析方法10.语句的频度：语句被执行的次数11.算法的频度：算法中所有语句的频度之和12.数组：下标与值组成的偶对的有穷集合13.二维数组的存储结构：行序为主序分配方式、列序为主序分配方式、14.特殊矩阵的压缩存储：对称矩阵、对角矩阵、15.线性表：数据元素之间具有的逻辑关系为线性关系的数据元素集合16.线性表的基本操作：创建、索引、存入、插入、删除、排序、17.线性表顺序存储结构：用一组地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过数据元素的存储位置直接反映18.顺序存储结构优点：原理简单、元素存储地址可用简单解析式计算、存储空间开销小19.顺序存储结构缺点：需事先分配连续地址、基本操作时间效率低20.线性链表：用一组地址任意的存储单元(连续的或不连续的)依次存储表中各个数据元素,数据元素之间的逻辑关系通过间接地反映出来21.链式存储结构优点：存储空间动态分布、地址不连续、插入删除操作效率高（O(1)）22.链式存储结构缺点：存储密度小、查找定位效率低O(n)23.堆栈定义：是一种只允许在表的一端进行插入操作和删除操作的线性表。

15秋北航《算法与数据结构》在线作业二100分答案

15秋北航《算法与数据结构》在线作业二100分答案

北航《算法与数据结构》在线作业二单选题一、单选题（共25 道试题，共100 分。

）1. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作A. 条件判断B. 结点移动C. 算术表达式D. 赋值语句-----------------选择：B2. 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。

A. HL=p;p->next=HL;B. p->next=HL;HL=p;C. p->next=HL;p=HL;D. p->next=HL->next;HL->next=p;-----------------选择：B3. 线性表是一个具有n个（）的有限序列。

A. 表元素B. 字符C. 数据元素D. 数据项-----------------选择：C4. 若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为( )。

A. 10，15，14，18，20，36，40，21B. 10，15，14，18，20，40，36，21C. 10，15，14，20，18，40，36，21D. 15，10，14，18，20，36，40，21-----------------选择：A5. 按照二叉树的定义，具有3个结点的二叉树有（）种。

A. 3B. 4C. 5D. 6-----------------选择：C6. 下列有关图遍历的说法中不正确的是（）。

A. 连通图的深度优先搜索是个递增过程B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C. 非连通图不能用深度优先搜索法D. 图的遍历要求每个顶点仅被访问一次-----------------选择：C7. Substr('DATA STRUCTURE'，5，9)=（）。

A. STRUCTURE'B. 'ASTUCTUR'C. 'DATA STRUCTRUE'。

数据结构北航软件技术基础课程ppt

数据结构北航软件技术基础课程ppt


eMail:gaoliansheng@
2020/9/23
liansheng_gao@
软件技术基础
• 第零章 编程的一些问题 • 第五章 二叉树和树
• 第一章 绪 论
• 第六章 图和广义表
• 第二章 线 性 表
• 第七章 排 序
• 第三章 栈和队列
• 第八章 查 找
试，通过测试用例保证每条源代码至少执行一次
2020/9/23
第零章 程序设计的一些问题
• 需求分析-Requ综 结i述 果re： ：m由 测e专 试n门 报t的 告A测n试a人ly员s对is软件进行测试
• 概要设计-Prim12ary测 测试 试D计e划sign
• 详细设计-Detaile条 wda件lDkt：her编osu译gihg、n链接成功，完成单元测试，
2020/9/23
第零章 程序设计的一些问题
• 软件和属性
– 计算机运行中不可缺少的 – 预先编好，能为他人使用 – 商品
• 盘和软件
– 盘是软件的载体
• 软件的分类
– 应用软件 – 系统软件
2020/9/23
第零章 程序设计的一些问题
• 程序设计的几个阶段(软件工程简介)
– 六、七十年代出现了软件危机
2020/9/23
数据元素
• 数据元素是数据的基本单位。 • 它也可以再由不可分割的数据项组成
2020/9/23
数据对象 性质相同的数据元素的集合 。
例：一个班级的成绩表可以看作一个数据对象。 一个图片、声音…..
数据对象是性质相同的数据元素集合。
2020/9/23
数据结构
• 数据元素集合（也可称数据对象） • 各元素之间的关系，即结构。
北航数据结构与程序设计真题2013年北航991真题及答案

北航数据结构与程序设计真题2013年北航991真题及答案

2013年''数据结构与C程序设计〃（代码991）试题一、单项选择题（本题共20分，每小题各2分）1.对于长度为n的线性表，建立其对应的収链表的时间复朵度为（）。

A.0（1）： B・ O（log2n）：・ O（n）： D・ O（n2）n2.一般情况下，在一个双向链表中插入一个新的链结点，（）。

A.需耍修改4个抬针域内的指针：B・需要修改3个指针域内的抬针：C.需要修改2个抬针域内的抬针：D.只需要修改1个指针域内的抬针。

3.假设用单个字母表示中缀表达式中的一个运算数（或称运算对彖）.并利用堆栈产生中缀表达式对应的后缀表达式。

对于中缀表达式A+B^C/D-E）,十从左至右扫描到运算数E时，堆栈中的运算符依次是（）。

（注：不包含表达式的分界符）A.+*/-：B. +*（/-： C・ +*-：・ +*（-o4.若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70,则后序遍历序列为（）。

A. 30,40,20,50,70,60,80：B. 30,40,20,70,60,80,50：C. 70,60,80,50,30,40,20：D. 70,60,80,30,40,20,50.5.分别以6, 3, 8, 12, 5, 7对应叶结点的权值构造的哈夫曼（Huffman）树的深度为（）。

A. 6： B・ 5： C・ 4： D・ 3。

&下列关于图的叙述中，错误的是（）0A.根据图的定义，图中至少有一个顶点：B.根据图的定义.图中至少有一个顶点和一条边（弧）：C.具有n个顶点的无向图最多有n&#61620;（n-l）/2条边:D.具有n个顶点的有向图最多有n&#61620;（n-l）条边（弧）。

7.若在有向图G的拓扑序列中.顶点W在顶点vj之前，则下列4种情形中不可能岀现的是（）。

A.G 中有弧vvi,vj＞：B.G 中没有3ft＜vi r vj＞；c. G中有一条从顶点W到顶点vj的路径：D・G中有一条从顶点vj到顶点vi的路径。

北航数据结构课件 (10)

北航数据结构课件 (10)


（ 1，4，6 ， 12 8，8 12 ， 6，11，… ）
例
49
temp
temp＞K[j] j=0 38 97 76 65 13 27 50
… (若干趟后)
K[j+1]=K[ j ]； j=j−1；
65
38
49
76 65
76 97
65 97
13
27
50
K[j+1]=temp;
38
49
65
76
97
核心思想
首先确定一个元素的间隔数gap。 将参加排序的元素按照gap分隔成若干个子序列 ( 即分别把那些位置相隔为gap的元素看作一个子序 列),然后对各个子序列采用 某一种排序方法 进行排 序；此后减小gap值，重复上述过程，直到gap<1。
一种减小gap的方法：
gap1 = n/2 gapi = gapi-1/2
1.时间性能 —— 排序过程中元素之间的比较次数与元素的
移动次数。 本章讨论各种排序方法的时间复杂度 时主要按照最差情况下所需要的比较次数 来进行。
2.空间性能 —— 除了存放参加排序的元素之外，排序过程
中所需要的其他辅助空间。
3.排序稳定性 —— 对于值相同的两个元素，排序前后的先后
次序不变，则称该方法为稳定性排序方法， 否则，称为非稳定性排序方法。
算 法
泡排序法的排序趟数与原始序列中数 据元素的排列有关，因此，排序的趟数为 一个范围，即[1..n-1]。
什么情况下至少排序一趟 什么情况下要排序n-1趟
O(n
2)
结论
泡排序方法比较适合于 参加排序的序列的原始状态 基本有序的情况
泡排序法是 稳定性排序方法。
北京航空航天大学991数据结构与C语言程序设计历年考研真题专业课考试试题

北京航空航天大学991数据结构与C语言程序设计历年考研真题专业课考试试题


2017年北京航空航天大学991数据 结构与C语言程序设计考研真题
2018年北京航空航天大学991数据 结构与C语言程序设计考研真题
目 录
2010年北京航空航天大学993数据结构与C语言程序设计考研真题 2011年北京航空航天大学991数据结构与C语言程序设计考研真题 2012年北京航空航天大学991数据结构与C语言程序设计考研真题 2013年北京航空航天大学991数据结构与C语言程序设计考研真题 2014年北京航空航天大学991数据结构与C语言程序设计考研真题 2015年北京航空航天大学991数据结构与C语言程序设计考研真题 2016年北京航空航天大学991数据结构与C语言程序设计考研真题 2017年北京航空航天大学991数据结构与C语言程序设计考研真题 2018年北京航空航天大学991数据结构与C语言程序设计考研真题
2014年北京航空航天大学991数据 结构与C语言程序设计考研真题
2015年北京航空航天大学991数据 结构与C语言程序设计考研真题
2016年北京航空航天大学991数据 结构与C语言程序设计考研真题
2010年北京航空航天大学993数据 结构与C语言程序设计考研真题
2011年北京航空航天大学991数据 结构与C语言程序设数据 结构与C语言程序设计考研真题
2013年北京航空航天大学991数据 结构与C语言程序设计考研真题
北航数据结构课件第一章

北航数据结构课件第一章

祝同学们新学期愉快学习进步！课程名称：数据结构教材名称：《数据结构教程》唐发根刘又诚编著北京航空航天大学出版社1996《数据结构》唐发根编著科学出版社1998开设本课程的必要性以及课程的特点：1. 计算机专业重要的专业基础课之一.2. 需要有关“程序设计语言”和“离散数学”的知识作为课程的基础.3. 实践性较强.第一章绪论1.1 什么是数据结构描述客观事物的数字、字符以及一切能够输入到计算机中，并且能够被计算机程序处理的符号的集合。

数据这个集合中的一个一个元素。

具有相同特性的数据元素的集合。

数据元素之间具有的关系(联系)。

数据数据元素数据对象结构一. 名词术语二. 数据结构的定义1.数据元素之间的联系称之为结构，数据结构就是具有结构的数据元素的集合。

2. 数据结构是一个二元组Data-Structure=(D，R)其中，D是数据元素的有限集合，R是D上的关系的集合。

数据元素之间具有的逻辑关系(结构)。

线性关系(线性结构)如线性表、数组、堆栈、队列、串、文件等具有某种逻辑结构的数据在计算机存储器中的存储方式(存储映象)。

物理结构也被称为存储结构。

顺序存储结构链式存储结构用一组地址连续的存储单元依次存放数据元素，数据元素之间的逻辑关系通过元素的地址直接反映。

用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过指针间接地反映。

非线性关系(非线性结构)如树、二叉树、图等物理结构逻辑结构例刘晓光马广生王民…张玉华男男…女男汉回壮…汉161721…25……………姓名性别民族年龄其他逻辑结构：线性结构(线性表)a 1a 2a 3 a 30…d 1d 2 d 3d 4…d 30a 2a 1a 3a 4a 30存储结构:1. 顺序存储结构:2. 链式存储结构:…d 1d 2 d 3d 4a 1a 2a 3a 30∧list…a 2a 1a 4a 3d 4d 1d 5d31.研究数据元素之间的客观联系。

北航计算机考研科目

北航计算机考研科目

北航（北京航空航天大学）计算机考研科目包含以下内容，具体要求可能会有一定的变化，建议在报名前查阅北航的招生信息和考试大纲，以获取最新的考试科目和要求。

1.计算机组成原理：涉及计算机硬件系统的结构和功能，包括数字逻辑、处理器设计、存储器层次结构、输入输出系统等。

2.操作系统：重点学习操作系统的基本原理、进程管理、内存管理、文件系统、设备管理、死锁处理等。

3.数据结构与算法：包括常见数据结构（如数组、链表、栈、队列、树、图等）的基本概念、实现方式和常用算法（如排序、查找、图算法等）的设计与分析。

4.计算机网络：涵盖计算机网络的基本概念、协议体系结构、局域网与广域网技术、传输层协议（如TCP和UDP）、网络安全等。

5.数据库系统：学习数据库的基本概念、关系数据库理论、SQL语言、数据库设计与管理、事务处理与并发控制、数据仓库与数据挖掘等。

6.软件工程：重点涉及软件开发过程、需求分析与建模、软件设计原则与方法、软件测试与质量保证、软件项目管理等。

此外，北航计算机考研还可能包括一些选修科目，如人工智能、机器学习、图像处理、编译原理等。

在备考过程中，您可以参考相关教材和资料，系统学习每个科目的基本概念、原理和应用。

北航《算法与数据结构》在线作业二

北航《算法与数据结构》在线作业二

24. 二叉树上叶结点数等于（）。
A. 分支结点数加1
B. 单分支结点数加1
C. 双分支结点数加1
D. 双分支结点数减1
满分：4 分
25. 某二叉树结点的前序序列为E、A、C、B、D、G、F，中序遍历为A、B、C、D、E、F、G。 该二叉树结点的后序序列为 ( )。
A. B,D,C,A,F,G,E
B. 63
C. 32
D. 31
满分：4 分
15. 如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。下列选项中，（）就是不稳定的排序方法。
A. 起泡排序
B. 归并排序
C. 直接插入法排序
D. 简单选择排序
满分：4 分
D. 'DATA'
满分：4 分
2. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A. 空或只有一个结点高度等于其结点数
B. 任一结点无左孩子
C. 任一结点无右孩子
满分：4 分
3. 设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（）。
C. 附加设施，如为便于运算实现而设置的“哑结点”等等
D. 一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级
满分：4 分
9. n个顶点的连通图至少有（ ）条边。
A. n-1
B. n
C. n+1
D. 0
满分：4 分
10. 排序方法中,从未排序序列中依次取出元素与己排序序列(初始时为空)中的元素进行比较,将其放入己排序序列的正确位置上的方法,称为（）

北航数据结构

四、结果
代码： def qsort(slist,l,r):
if l>r: return -1
t=slist[l] i=l j=r while i!=j:
while slist[j]>=t and i<j: j-=1
while slist[i]<=t and i<j: i+=1
if i<j: slist[i],slist[j]=slist[j],slist[i]
实验报告-快速排序与希尔排序
一、问题描述
快速排序实现中采用了发现逆序和交换记录位置的方法，算法最基本的思想还是划分， 即按某种标准把考虑的记录划分为“小记录”和“大记录”，并通过递归不断划分，最终得到一 个排序的序列。
希尔排序方法又称为缩小增量的插入排序。基本思想：先将整个待排记录序列分割成为 若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行 一次直接插入排序。
三算法的设计与实现
快速排序
1.设两个指针 low 和 high，初值分别为 low 和 high 2.设第一个元素关键字为 pivotkey 3.从 high 所指位置向前搜索找到第一个小于 pivotkey 的记录互相交换，然后从 low 所指位 置起向后搜索，找到第一个大于 pivotkey 的记录互相交换 4.重复 3，直至 low=high 为止。 希尔排序 （1）先取增量 d>1,把全部记录分成 d 个组 （2）对每组进行直接插入排序 （3）逐渐减少增量 d，直到为 1，所有记录在同一组，直接插入排序为止。
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法 因 D.L.Shell 于 1959 年提出而得名。

北航软件工程考研科目

北航软件工程考研科目北航软件工程考研科目多，包括计算机基础、数学知识、算法与数据结构、操作系统、软件工程与软件测试等。

这些科目在考研中具有重要的地位，对于考生来说是不容忽视的。

下面，让我为大家详细介绍一下北航软件工程考研科目。

首先，计算机基础是软件工程考研中的重点科目之一。

它涉及计算机体系结构、计算机网络、操作系统、数据库原理等方面的知识。

在复习这门科目时，我们需要对计算机原理和相关技术有一个全面的了解，同时也要注重理论与实践相结合，能够掌握一些常用的编程语言和开发工具，这样才能更好地应对考试。

其次，数学知识是软件工程考研中的基础科目，也是许多考生觉得比较困难的科目之一。

但是，只要我们在复习时合理安排时间，系统学习数学基础知识，多做一些题目，通过掌握数学思维和解题技巧，相信我们都能够取得不错的成绩。

然后，算法与数据结构也是软件工程考研中的重要科目。

它们是软件开发中最基础的内容，对于提高编程能力和解决实际问题非常重要。

在复习这门科目时，我们需要掌握常用的算法和数据结构，并能够熟练地应用它们解决实际问题。

此外，多做一些算法题目和编程练习也是很有必要的。

此外，操作系统是软件工程考研中的一门重要科目。

它是软件开发中的关键环节，涉及进程管理、内存管理、文件系统等方面的知识。

在复习这门科目时，我们需要理解操作系统的基本原理和设计思想，掌握操作系统的核心概念和常用算法，同时也要熟悉一些实际的操作系统，如UNIX和Windows。

最后，软件工程与软件测试是软件工程考研中的重要科目之一。

它们是软件开发中不可或缺的环节，包括软件需求分析、软件设计、软件测试等方面的知识。

在复习这门科目时，我们需要了解软件工程的基本概念和软件开发过程，同时也要掌握软件测试的基本原理和常用技术，能够灵活运用测试方法和工具进行软件测试。

综上所述，北航软件工程考研科目涉及计算机基础、数学知识、算法与数据结构、操作系统、软件工程与软件测试等方面的知识。

北航信息类大二分科

北航信息类大二分科
北航信息类大二分科有以下几个方向：
1. 计算机科学与技术：主要研究计算机系统、软件技术、计算机网络等方面的知识，培养学生具备计算机系统设计、开发和应用的能力。

具体课程包括操作系统、数据结构与算法、计算机组成原理、数据库原理等。

2. 软件工程：侧重于培养学生掌握软件开发的理论和技术，具备软件需求分析、设计、实现和测试的能力。

相关课程包括软件工程基础、软件质量保证、软件项目管理等。

3. 人工智能：专注于培养学生在人工智能领域的理论和技术能力，包括机器学习、自然语言处理、计算机视觉等方面。

相关课程包括智能计算导论、模式识别、机器学习等。

4. 网络工程：主要研究计算机网络的原理、协议和技术，培养学生具备网络设计、配置和管理的能力。

相关课程包括计算机网络原理、网络安全与管理、网络协议等。

5. 数字媒体技术：注重培养学生在数字媒体制作、图像处理、音视频处理等方面的能力，涉及课程有数字图像处理、计算机动画技术、多媒体技术等。

以上仅列举了北航信息类大二分科的部分方向，学生可以根据自己的兴趣和职业规划选择适合自己的方向进行深入学习。

北航计算机考研参考书

北航计算机考研参考书一、引言随着我国教育事业的发展，越来越多的人选择考研作为进一步提升自己能力的途径。

在北京航空航天大学（北航）的计算机专业考研中，参考书的作用不言而喻。

本文将为大家介绍北航计算机考研的参考书籍，并分析其重要性，以帮助考生们更有效地备考。

二、北航计算机考研参考书概述在北航计算机考研备考过程中，以下书籍被认为是必备参考书：1.数据结构与算法：深入浅出地讲解数据结构与算法的基本概念、原理和应用，对于提高考生的编程能力和解决实际问题具有重要意义。

2.操作系统：该书详细介绍了操作系统的原理、设计与实现，有助于考生掌握操作系统的基本知识和实践技能。

3.计算机网络：该书系统地讲解计算机网络的原理、体系结构和协议，是考生备考计算机网络科目的重要参考资料。

4.计算机组成原理：该书从基本概念出发，深入剖析计算机组成原理，有助于考生理解计算机硬件的基本工作原理。

5.软件工程：该书以实际项目为背景，讲解软件开发的全过程，有助于考生提高软件工程实践能力。

6.计算机基础：涵盖计算机科学基本概念、方法和技术的书籍，对于巩固考生的计算机基础知识具有重要意义。

三、各科目参考书推荐以下是针对北航计算机考研各科目的参考书推荐：1.数据结构与算法：推荐使用《算法导论》、《数据结构与算法分析》等书籍。

2.操作系统：推荐使用《现代操作系统》、《操作系统概念》等书籍。

3.计算机网络：推荐使用《计算机网络》、《TCP/IP详解》等书籍。

4.计算机组成原理：推荐使用《计算机组成与设计》、《计算机组成原理》等书籍。

5.软件工程：推荐使用《软件工程：实践者的观点》、《软件工程教程》等书籍。

6.计算机基础：推荐使用《计算机科学导论》、《计算机科学基础》等书籍。

四、如何高效使用参考书1.制定学习计划：根据自己的实际情况，合理安排学习时间，确保每个科目都能得到充分复习。

2.注重实践与应用：在学习过程中，要注重将所学知识运用到实际问题中，提高解决问题的能力。

北京航空航天大学考研试题


NEXT … … ┇ …
四、 （本题 10 分）根据第三题写一算法，该算法打印系名有 DEPTNAME 的全系教师姓名。 五、 （本题 15） 已知不带头结点的线性链表 list， 链表中结点构造为 其中 data 为数据域，link 为指针域。 请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程 中不得使用除该链表以外的任何链结点空间。 六、 （本题 15 分）已知一具有 n 个结点的二叉树的中序遍历序列与后序遍历序列分别存 放于数组 IN[1:n]和 POST[1:n]中， （设该二叉树各结点的数据值均不相同） 。 请写一建立该二叉树的二叉链表结构的非递归算法.设二叉链表的链结点构造为 , 其中 data 为数据域，lchild 与 rchild 分别为指向该结点左、右孩子的指针域（当孩子 结点不存在时，相应指针域值为空，用 nil 表示） 。

n(n + 1) 中， 则在 B 中确定 aij(i<j)的位置 k 的关系 2 j ∗ ( j − 1) +i 2 j ∗ ( j + 1) (D) +i 2
i ∗ (i − 1) +j 2 i ∗ (i + 1) (C) +j 2
(B)
3.某堆栈的输入序列为 a，b，c，d，下面的四个序列中，_________不可能是它的输 出序列。 (A)a，c，b，d (B)b，c，d，a (C)c，d，b，a (D)d，c，a，b 4.深度为 h 的满 m 叉数的第 k 层有_________个结点。(1≤k≤h) (A)mk-1 (B)mk-1 (C)mh-1 (D)mh-1 5.具有 10 个叶结点的二叉树中有_________个度为 2 的结点。 (A)8 (B)9 (C)10 (D)11 6.要连通具有 n 个顶点的有向图，至少需要_________条边。 (A)n-1 (B)n (C)n+1 (D)2n 7.已知有向图 G=(V，E)，其中 V={v1，v2，v3，v4，v5，v6，v7}，E={<v1，v2>， <v1，v3>，<v1，v4>，<v2，v5>，<v3，v5>，<v3，v6>，<v4，v6>，<v5，v7>， <v6，v7>}，G 的拓扑序列是_________。 (A)v1，v3，v4，v6，v2，v5，v7 (B)v1，v3，v2，v6，v4，v5，v7 (C)v1，v3，v4，v5，v2，v6，v7 (D)v1，v2，v5，v3，v4，v6，v7 8.若查找每个记录的概率均等， 则在具有 n 个记录的连续顺序文件中采用顺序查找法 查找一个记录，其平均查找长度 ASL 为_________ (A)

991“数据结构与C语言程序设计”考试大纲(2019年)北航自命题科目考研

991“数据结构与C语言程序设计”考试大纲（2019版）2019年“数据结构与C语言程序设计”考试内容包括“数据结构”与“C语言程序设计”两门课程的内容，各占比例50%。

试卷满分为150分。

“数据结构”部分一、概述1．数据的逻辑结构与存储结构的基本概念；2．算法的定义、基本性质以及算法分析的基本概念，包括采用大 形式表示时间复杂度和空间复杂度。

二、线性表1．线性关系、线性表的定义，线性表的基本操作；2．线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和双向链表)的构造原理；3．在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)。

三、数组1．一维数组和二维数组的存储；2．矩阵的压缩存储的基本概念；3．对称矩阵、对角矩阵以及三角矩阵的压缩存储。

四、堆栈与队列1．堆栈与队列的基本概念与基本操作；2．堆栈与队列的顺序存储结构与链式存储结构的构造原理；3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计；4．堆栈和队列在解决实际问题中应用。

五、树与二叉树1．树与二叉树的基本概念，基本特征、名词术语；2．完全二叉树与满二叉树的基本概念，二叉树的基本性质及其应用；3．二叉树的顺序存储结构与二叉链表存储结的基本原理；4．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，重点是二叉树在以二叉链表作为存储结构基础上各种遍历算法(包括非递归算法)的设计与应用；5．二叉排序树的基本概念、建立(插入)、查找以及平均查找长度ASL的计算。

六、图1．图的基本概念、名词术语；2．图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点；3．图的深度优先搜索与广度优先搜索；4．最小(代价)生成树、最短路径、AOV网与拓扑排序的基本概念。

七、文件及查找1．顺序查找法以及平均查找长度(ASL)的计算；2．折半查找法以及平均查找长度(ASL)的计算，包括查找过程对应的“判定树”的构造；3．散列(Hash)表的构造、散列函数的构造，散列冲突的基本概念、处理散列冲突的基本方法以及散列表的查找和平均查找长度的计算。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
在集合 U 中放入顶点 v0，v0 到 v0 的距离为 0。 对 V-U 里的每个顶点 v，如果（v0, v）在 E 中（即存在直接的边），则到 v 的已知最短 路径长度设为 w(v0, v), 否则令 v 的已知最短路径长度为 inf。这里的 w(v0, v)是从 v0 到 v 的 边的权值。 反复做： 从 V-U 中选出当时已知最短路径长度最小的顶点 v(min)加入 U，因为这时到 v(min)的 已知最短路径长度 cdis(v0, v(min))就是 v0 到 v(min)的距离。 由于 v(min)的加入，V-U 中某些顶点的已知最短路径可能改变。如果从 v0 经过 v(min) 到 v'的路径比原来已知的最短路径更短，就说明发现了到 v'的新的已知最短路径（及其长 度），该路径经过 v(min)到 v'。在这种情况下更新到 v'的已知最短路径及距离的记录，保证 下面能正确地继续从 V-U 中选择顶点。 反复选择顶点并更新到所有非 U 顶点的最短路径信息，知道从 v0 可达的所有顶点都在集合 U 中为止。如果这时还存在未加入 U 的顶点，就说明被处理的图不连通。
如果这样做不能得到一个包含 G 的所有顶点的连通分量，则原图不连通，没有最小 生成树。算法做出的是 G 的最小连通树林。 rim 算法 从图 G 的顶点集 V 中任取一顶点（例如 v0）放入集合 U 中，这时 U={v0}，令边集合 Er={}， 显然 T=（U，Er）是一棵树（只包含一个顶点且没有边）。
三、算法的设计与实现
Kruskal 算法
设 G=（V，E）是一个网络，其中 IVI=n。 1）初始时取包含 G 中所有 n 个顶点但没有任何边的孤立点子图 T=（V，{}），T 里的每个顶 点自成一个连通分量。下面将通过不断扩充 T 的方式构造 G 的最小生成树。 2）将边集 E 中的边按权值递增的顺序排序，在构造中的每一步顺序地检查这个边序列，找 到下一条（最短的）两端点位于 T 的两个不同连通分量的边 e，把 e 加入 T。这导致两个连 通分量由于边 e 的连接而变成了一个连通分量。 3）每次操作使 T 减少一个连通分量。不断重复这个动作加入新边，直到 T 中所有顶点都包 含在一个连通分量里为止，这个连通分量就是 G 的一棵最小生成树。
p=end l=0 while p>=1 and l<nodes:
road[l]=p p=nodepre[p] l+=1 l-=1 while l>=0: roads.append(road[l]) l-=1 return dis[end],roads def map():
map=[[inf,inf,inf,inf,inf,inf],[inf,inf,inf,6,3,inf,inf,inf],[inf,11, inf,4,inf,inf,7,inf],
return res def prim(self):
res=[] snode=[0] cnode=[i for i in range(1,self.nodenumber)] while len(cnode)>0:
begin,end,min=0,0,99 for i in snode:
for j in cnode: if self.map[i][j]<min: min=self.map[i][j] begin=i
四、结果
Dijkstra
代码 1： class Graph():
def __init__(self,map): self.map=map self.nodenumber=self.nodenumber()
self.edgenumber=self.edgenumber() def nodenumber(self):
一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值 之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的 每一连通分量同样有最小生成树，它们的并被称为最小生成森林。
二、数据结构-图
在数学上，一个图（Graph）是表示物件与物件之间的关系的方法，是图论的基本研究 对象。一个图看起来是由一些小圆点（称为顶点或结点）和连结这些圆点的直线或曲线（称 为边）组成的。如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有 向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个 点也有始点和终点之分。相反，边没有方向的图称为无向图。
检查所有一个端点在集合 U 里而另一个端点在集合 V-U 的边，找出其中权最小的边 e=(u,v) （假设 u 在 U 中，v 在 V-U 中），将顶点 v 加入顶点集合 U，并将 e 加入边集合 Er。易见， 扩充之后的 T=（U，Er）仍是一棵树。 重复上面步骤直到 U=V（所构造的树已经包含了所有顶点）。这时集合 Er 里有 n-1 条边， 子图 T=（U，Er）就是 G 的一棵最小生成树。 Dijkstra 算法 初始：
if nodedis[j]==0 and dis[j]<minn: t=j minn=dis[j]
nodedis[t]=1 #找到最短的一条路径 ,标记 for j in range(nodes+1):
if nodedis[j]==0 and dis[j]>dis[t]+map[t][j]: dis[j]=dis[t]+map[t][j] nodepre[j]=t
实验报告-最小生成树
一、问题描述
最小生成树是一副连通加权无向图中一棵权值最小的生成树。在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即 ），而 w(u, v) 代表此边的权重，若存 在 T 为 E 的子集（即 ）且 (V, T) 为树，使的 w(T) 最小，则此 T 为 G 的最小生成树。 最小生成树其实是最小权重生成树的简称。
end=j res.append([begin,end,min]) snode.append(end) cnode.remove(end) for j in res: j[0]=chr(j[0]+97) j[1]=chr(j[1]+97) return res max=99 row1=[0,5,11,5,max,max,max] row2=[5,0,max,3,9,max,7] row3=[11,max,0,7,max,6,max] row4=[5,3,7,0,max,max,20] row5=[max,9,max,max,0,max,8] row6=[max,max,6,max,max,0,8] row7=[max,7,max,20,8,8,0] map=[row1,row2,row3,row4,row5,row6,row7] graph=Graph(map) print("kruskal") print(graph.kruskal()) print("prim") print(graph.prim()) 代码二： inf=float('inf') def Dijkstra(nodes,edges,graph,start,end): nodepre=[0]*(nodes+1) #记录前驱 nodedis=[0]*(nodes+1) #记录节点遍历状态 dis=[inf for i in range(nodes+1)] #保存最短距离 road=[0]*(nodes+1) #保存最短路径 roads=[] map=graph for i in range(nodes+1):#初始化起点到其他点的距离 if i==start: dis[i]=0 else: dis[i]=map[start][i] if map[start][i]!=inf: nodepre[i]=start else: nodepre[i]=-1 nodedis[start]=1 for i in range(nodes+1):#每循环一次确定一条最短路 minn=inf for j in range(nodes+1):#寻找当前最短路
一个不带权图中若两点不相邻，邻接矩阵相应位置为 0，对带权图（网），相应位置为 ∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶 点建立一个单链表（并按建立的次序编号），第 i 个单链表中的结点表示依附于顶点 vi 的边 （对于有向图是以顶点 vi 为尾的弧）。每个结点由两个域组成：邻接点域（Adjvex），用以指 示与 vi 邻接的点在图中的位置，链域（Nextarc）用以指向依附于顶点 vi 的下一条边所对应 的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域 （Info）。每个顶点的单链表中结点的个数即为该顶点的出度（与该顶点连接的边的总数）。 无论是存储图或网，都需要在每个单链表前设一表头结点，这些表头结点的第一个域 data 用于存放结点 vi 的编号 i，第二个域 firstarc 用于指向链表中第一个结点。
return len(self.map) def edgenumber(self):
cnt=0 for i in range(self.nodenumber):
for j in range(i): if self.map[i][j]>0 and self.map[i][j]<99: cnt+=1
return cnt def kruskal(self):
for i in range(len(gp)): if edge[0] in gp[i]: m=i if edge[1] in gp[i]: n=i
if m!=n: res.append(edge) gp[m]=gp[m]+gp[n] gp[n] =[]
for j in res: j[0]=chr(j[0]+97) j[1]=chr(j[1]+97)