祝同学们
新学期愉快
学习进步！
课程名称：数据结构
教材名称：《数据结构教程》
唐发根刘又诚编著
北京航空航天大学出版社1996
《数据结构》
唐发根编著
科学出版社1998
开设本课程的必要性以及课程的特点：
1. 计算机专业重要的专业基础课之一.
2. 需要有关“程序设计语言”和“离散数学
”
的知识作为课程的基础.
3. 实践性较强.
第一章绪论
1.1 什么是数据结构
描述客观事物的数字、字符以及一切能够输入到计算机中，并且能够被计算机程序处理的符号的集合。数据这个集合中的一个一个元素。具有相同特性的数据元素的集合。数据元素之间具有的关系(联系)
。
数据
数据元素数据对象结构
一. 名词术语
二. 数据结构的定义
1.数据元素之间的联系称之为结构，数据结构就是具有结构的数据元素的集合。
2. 数据结构是一个二元组
Data-Structure=(D，R)
其中，D是数据元素的有限集合，R是D上的关系的集合。
数据元素之间具有的逻辑关系(结构)。
线性关系(线性结构)
如线性表、数组、堆栈、队列、串、文件等
具有某种逻辑结构的数据在计算机存储器中的
存储方式(存储映象)。
物理结构也被称为存储结构。
顺序存储结构
链式存储结构
用一组地址连续的存储单元依次存放数据元素，数据元素之间的逻辑关系通过元素的地址直接反映。用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过指针间接地反映。
非线性关系(非线性结构)
如树、二叉树、图等
物理结构逻辑结构
例
刘晓光马广生
王民…
张玉华
男
男…
女
男汉回
壮
…
汉
1617
21
…
25
…
…………姓名
性别
民族
年龄
其他逻辑结构：线性结构(线性表)a 1a 2a 3 a 30
…
d 1
d 2 d 3
d 4
…
d 30
a 2
a 1
a 3
a 4
a 30
存储结构:
1. 顺序存储结构
:
2. 链式存储结构:
…
d 1
d 2 d 3
d 4
a 1
a 2
a 3
a 30
∧
list
…
a 2
a 1
a 4
a 3
d 4
d 1
d 5
d
3
1.研究数据元素之间的客观联系。
2. 研究具有某种逻辑关系的数据在计算机存储器内的存储方式。
3. 研究如何在数据的各种结构(逻辑的和物理的)的基础上对数据实施一系列有效的基本操作。三. 数据结构课程研究的主要内容
(算法)
(逻辑结构)(存储结构)
1.2 算法及其描述
输入一个完整的算法应该满足下面五个基本标准：确定性有穷性输出一. 算法及其性质
(2).算法是由人们组织起来准备加以实施的一系
列有限的基本步骤。
1.算法的定义
2.算法的性质
(1).算法
是用来解决某个特定课题的指令的集合。
二. 算法的描述
1. 采用自然语言来描述
问题：求两个正整数M与N的最大公因子。
(1) M除以N，将余数送中间变量R；
(2) 测试余数R是否等于零？
a) 若R等于零，求得的最大公因子为当前N
的值, 算法到此结束。
b) 若R不等于零，将N送入M，将R送N，重
复算法的(1)和(2)。
2. 采用程序流程图的形式来描述
M 除以N 的余数送R
余数R 为0否？
将N 送M 将R 送N
输出N 的值
结束
开始
yes
no
采用某种具体程序语言来描述3.
COMFACTOR( M, N )
int M, N;
{
int R;
while( 1 )
{
R=M % N;
if (R==0)
return N;
M=N;
N=R;
}
}
4. 设计一种既脱离某种具体的程序设计语言，
又具有各种程序设计语言的共同特点的形
式化语言来描述
SPARKS语言，一种类Pascal
一. 算法格式
一个完整的用SPARKS语言编写的算法必须具有以下两种格式之一。
procedure算法名(参数表)语句串
end function算法名(参数表)语句串
end
1.3 SPARKS
语言简介
二. 语句
1.赋值语句：(1) if 条件then [ 语句串](2) if
条件then [ 语句串1 ]
else
[ 语句串2 ]
V←E
2. 条件语句(两种)
3.循环语句(四种)
while 循环条件do
语句串
end
repeat
语句串
until 循环结束条件for v←e
1
to/downto e2 by e3do 语句串
end
loop
语句串
forever
return
return (表达式)
call 算法名(参数表)变量名←算法名(参数表)
case
：条件1：语句串1：条件2：语句串2
... ...... ...：条件n ：语句串n ：else ：语句串n+1end
4. 分情况语句
5. 算法调用语句
6.返回语句
goto 语句标号
stop
// 注释内容//
exit
read(参数表)print(参数表)
7. 转移语句
8. 出口语句
9. 输入/输出语句
10. 停止语句
11.
注释
数据库期末试题2010级 友情提醒：闭卷考试，有一定难度，英文，考试时间2小时，需要好好复习。建议好好做那份样卷（即09年试卷），大题目题型和那上面差不多，选择改为了判断，我们这届没有简答题。 题型：判断（10题），简答题（5题） 判断题没有记录，主要考基本概念。 简答题： （1）事务，串行化调度，两阶段锁协议 （2）Sql语句和关系代数语句写出查询 （3）ER图设计并写出关系主键，外键等 （4）给出函数依赖，并且推断属于何种范式（BCNF，第三范式） （5）题目给出关系表与关系代数表达式，求出运算结果
班号学号姓名成绩 《数据库系统概论》期末考试卷 注意事项：1、考试时间2小时； 2、答案写在答题纸上 题目： 一、……………………………………………………………( 分) 二、……………………………………………………………( 分) 三、……………………………………………………………( 分) 四、……………………………………………………………( 分) 五、……………………………………………………………( 分) 六、……………………………………………………………( 分)
一：单选题(本大题共12小题，每小题3分，共36分) 1. 对现实世界进行第一层抽象的是【 D 】 A. 用户数据模型 B. 物理数据模型 C. 逻辑数据模型 D. 概念数据模型 2. 以下不属于集合运算的是________。【 C 】 A. 并 B. 广义笛卡尔积 C. 除 D. 差 3. 若一个关系有函数依赖集（AB→CD, A→D），则可确定它最高属于：【 A 】 A. 1NF B. 2NF C. 3NF D. BCNF 4. 以下哪个SQL语句没有语法错误【 A 】 A. Grant select on TableA to User1 with grant option B. select count(a) from b where count(a)>3 C. insert into TableA set a=1, b=2 D. drop TableA where a=1 5. 定义学生对象来表示张三、李四等学生个体，这种抽象方法被称为【A】 A. 分类 B. 聚集 C. 类比 D. 概括 6. 哪一级封锁协议解决了读脏数据问题？【B】 A. 一级封锁协议 B.二级封锁协议 C. 三级封锁协议 D. 以上都不是 7. 工资表（职工号，岗位级别，岗位工资）中有如下约束：岗位级别低的职工的岗位工资 应低于岗位级别高的职工的岗位工资。这种约束属于什么约束类型？【 E】 A. 静态列级约束 B. 动态列级约束 C. 静态元组约束 D. 动态元组约束 E. 静态关系约束 F. 动态关系约束 8. 设有关系R（A，B，C）的值如下：
北京航空航天大学现代远程教育 2015年3月份《数据库原理及应用》课程考试试卷 注意事项： 1、本试卷满分100分；考试时间：90分钟；考试形式：开卷 2、请将答案一律写在答题纸上，试卷上作答无效 3、考试结束后，考生将试卷及答题纸一并交回 4、请将条形码贴在答题纸的指定位置 学习中心______________姓名____________学号____________ 一、单项选择题（本大题共20小题，每小题1.5分，共30分） 1、第一代数据模型是指（）。 A．关系模型B．网络模型 C．面向对象模型D．人工智能模型 2、SQL语言中授权的操作是通过（）语句实现的。 A．CREATE B．REVOKE C．GRANT D．INSERT 3、SQL Server是一个基于（）。 A．层次模型的DBMS B．网状模型的DBMS C．关系模型的应用程序D．关系模型的DBMS 4、一个m:n联系转换为一个关系模式。关系的码为（）。 A．某个实体的码B．各实体码的组合 C．n端实体的码D．任意一个实体的码 5、手工处理阶段是（）。 A．计算机数据处理技术发展的初级阶段 B．计算机数据管理技术发展的初级阶段 C．计算机数据处理技术发展的中级阶段 D．计算机数据管理技术发展的中级阶段 6、在DBS中，DBMS和OS之间的关系是（）。 A．相互调用B．DBMS调用OS C．OS调用DBMS D．并发运行7、数据库保护的几个方面中，不包括的是（）。 A．控制数据冗余B．并发控制 C．完整性保护D．故障恢复 8、（）是长期存储在计算机内的有组织、可共享的数据集合。 A．数据库管理系统B．数据库系统 C．数据库D．文件组织 9、数据库系统包括（）。 A．DB、DBMS B．DB、DBA C．DB、DBMS、DBA、计算机硬件 D．DB、DBMS、DBA、OS、计算机硬件 10、SQL语言具有（）的功能。 A．关系规范化、数据操纵、数据控制 B．数据定义、数据操纵、数据控制 C．数据定义、关系规范化、数据控制 D．数据定义、关系规范化、数据操纵 11、部分匹配查询中有关匹配符“_”的正确的叙述是（）。 A．“_”代表任意单个字符 B．“_”可以代表零个或多个字符 C．“_”不能与“%”一同使用 D．“_”代表一个字符 12、规范化过程主要是为了克服数据库逻辑结构中的插入异常、删除异常以及（）的缺陷。 A．数据的不一致性B．结构不合理 C．冗余度大D．数据丢失 13、SQL 语言集数据查询、数据操作、数据定义和数据控制功能于一体，语句INSERT、DELETE、UPDATA实现下列（）功能。 A．数据查询B．数据操纵 C．数据定义D．数据控制 14、下列命题中不正确的是（）。 A．数据库减少了不必要的数据冗余 B．数据库中不存在冗余数据
2013年''数据结构与C程序设计〃（代码991）试题 一、单项选择题（本题共20分，每小题各2分） 1.对于长度为n的线性表.建立其对应的做链表的时间复杂度为（）。 A.0（1）： B. O（log2n）：? O（n）： D? O（n2）。 2.一般情况下，在一个双向链表中插入一个新的链结点，（）o A.需要修改4个抬针域内的指针： B.需要修改3个指针域内的指针： C.需要修改2个指针域内的抬针：D?只需要修改1个指针域内的指针。 3.假设用单?个字母表示中缀表达式中的一个运算数（或称运算对&）?并利用堆栈产生中缀表达式对应的后缀表达式。对于中缀表达式A+B*（C/D-E）,十从左至右扫描到运算数E时，堆栈中的运算符依次是（）。（注：不包含表达式的分界符） A.+*/-： B. +*（/-： C? +*-：? +*（-o 4.若某二叉排序树的前序遍历序列为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, 5Z 7对应叶结点的权值构造的哈夫曼（Huffman）树的深度为（）。 A. 6： B. 5： C? 4： D? 3。 &下列关于图的叙述中，错误的是（）0 A.根据图的定义，图中至少有一个顶点： B.根据图的定义.图中至少有一个顶点和一条边（弧）： C.具有n个顶点的无向图最女有n（n-l）/2条边； D.具有n个顶点的有向图最多有n（n-l）条边（弧）。 7.若在有向图G的拓扑序列中，顶点vi在顶点vj之前，则下列4种情形中不可能出现的是（）》 A.G中有弧 B.G中没有弧vvi,vj＞： C.G中有一条从顶点vi到顶点vj的路径： D?G中有一条从顶点vj到顶点vi的路径。 8.下列关于査找操作的叙述中.错误的是（）。 A.在顺序表中査找元素可以采用顺序查找法，也可以采用折半査找法： B.在链表中査找结点只能采用顺序査找法，不能采用折半査找法： C.一般情况下，顺序査找法不如折半查找法的时间效率商： D.折半査找的过程可以用一棵称之为''判定树"的二叉树來描述。 9.在一棵m阶B?树中，除根结点之外的任何分支结点包含关键字的个数至少是（）。 A. m/2-1： B? m/2： C? m/2-l： D? m/2° 10.若对序列（49, 38, 65, 97, 76, 13, 27f 49J进行快速排序，则第一趙排序结束（即确定了第1个分界元素的最终位宜）时.序列的状态是（）。 A. （13, 27, 49； 38, 49, 76, 97, 65）： B. （13, 38, 27, 49； 49, 76, 97, 65）： C. （13, 38, 49； 27, 49, 97, 76, 65）： D. （13, 38, 49；27t 49z 76, 97, 65）。 二、填空题（本题共20分，每小题各2分）
2011 年硕士研究生入学考试 “数据结构与C语言程序设计”(科目代码:991)试题与答案 一、单项选择题(本题共20分，每小题各2分) 1．下列关于线性表的存储结构的叙述中，错误的是。 A．线性表的顺序存储结构中隐式地存储了数据元素之间的逻辑关系 B．线性表的顺序存储结构一定需要占用一片地址连续的存储空间 C．线性表的链式存储结构通过指针来反映数据元素之间的逻辑关系 D．线性表的链式存储结构占用的存储空间一定不连续 2．若front 和rear 分别表示链接队列的队头指针与队尾指针，则向队列中插入一个由p 指的新元素的过程是依次执行。 A．rear=p; front=p; B．front=p; rear=p; C．rear->link=p; rear=p; D．front->link=p; rear=p; 3．下列关于二叉树的叙述中，正确的是。 A．二叉树的度可以小于2 B．二叉树的度等于2 C．二叉树中至少有一个结点的度为2 D．二叉树中每一个结点的度都为2 4．若某二叉树有40个叶结点，则该二叉树的结点总数最少是。 A．78 B．79 C．80 D．81 5．若采用邻接矩阵存储一个有向图，且邻接矩阵主对角线以下元素均为0，则该有向图的拓扑序列。 A．存在且惟一B．存在但可能不惟一 C．不存在D．无法确定 6．下面关于AOE 网的叙述中，正确的是。 A．AOE 网是一个带权的连通图 B．AOE 网是一个带权的强连通图 C．AOE 网是一个带权的无回路的连通图 D．AOE 网是一个带权且无回路的有向图 7．下列关于线性表查找方法的叙述中，错误的是。 A．顺序查找法适合于采用顺序存储结构和链式存储结构的线性表的查找 B．对于相同元素，顺序查找法一定能够查找到表中首次出现的元素 C．对于相同元素，折半查找法一定能够查找到表中首次出现的元素 D．对于相同元素，折半查找法不一定能够查找到表中首次出现的元素 8．在二叉排序树中进行查找的平均时间效率主要与下列因素之一有关，该因素是。A．二叉排序树的深度B．二叉排序树中结点的个数的多少 C．被查找结点的度D．二叉排序树的存储结构 9．下列4 种排序方法中，每一趟排序结束时不一定能够确定一个元素排序最终位置的是。 A．插入排序B．快速排序 C．堆积(Heap)排序D．二路归并排序 2 10．下列4 种排序方法中，当待排序的序列中元素初始时已经按值有序，排序所花费的
一、单选题（共 25 道试题，共 100 分。）V 1. 数据库物理存储方式的描述称为( ) A. 外模式 B. 内模式 C. 概念模式 D. 逻辑模式 满分：4 分 2. DB、DBMS和DBS三者之间的关系是( ) A. DB包括DBMS和DBS B. DBS包括DB和DBMS C. DBMS包括DB和DBS D. 不能相互包括 满分：4 分 3. 在关系模型中，实现"关系中不允许出现相同的元组"的约束是通过______。 A. 候选键 B. 主键 C. 外键 D. 超键 满分：4 分 4. 数据库中只存放视图的 A. 操作 B. 对应的数据 C. 定义 D. 限制 满分：4 分 5. 从一个数据库文件中取出满足某个条件的所有记录形成一个新的数据库文件的操作是（）操作。 A. 投影 B. 连接 C. 选择 D. 复制 满分：4 分 6. 在SQL中，删除视图用______。 A. DROP SCHEMA命令 B. CREATE TABLE命令 C. DROP VIEW命令 D. DROP INDEX命令 满分：4 分 7. DBAS指的是______。 A. 数据库管理系统 B. 数据库系统 C. 数据库应用系统 D. 数据库服务系统 满分：4 分 8. 设有关系模式W(C,P,S,G,T,R),其中各属性的含义是：C课程,P教师,S学生,G成绩,T
时间,R教室，根据定义有如下数据依赖集：D={C→G，(S,C)→G,(T,R)→C,(T,P)→R,(T,S)→R}关系模式W的一个关键字是__，W的规范化程度最高达到__（）。 A. (S,C),1NF B. (T,R),3NF C. (T,P),4NF D. (T,S),2NF 满分：4 分 9. 设有关系R1和R2，经过关系运算得到结果S，则S是______。 A. 一个关系 B. 一个表单 C. 一个数据库 D. 一个数组 满分：4 分 10. （）是控制数据整体结构的人，负责三级结构定义和修改 A. 专业用户 B. 应用程序员 C. DBA D. 一般用户 满分：4 分 11. 数据库设计属于（）。 A. 程序设计范畴 B. 管理科学范畴 C. 系统工程范畴 D. 软件工程范畴 满分：4 分 12. 下述（）不是DBA数据库管理员的职责。 A. 完整性约束说明 B. 定义数据库模式 C. 数据库安全 D. 数据库管理系统设计 满分：4 分 13. 对象标识具有唯一性，其唯一性的范围是在____ A. 对象内 B. 类内 C. 类层次内 D. 系统内 满分：4 分 14. 已知关系R（P，Q，M，N），F是R上成立的函数依赖集，F={（P→Q，Q→M）}，则R 的侯选码是（）。 A. P B. Q C. PQ D. PN 满分：4 分
北航《算法与数据结构》在线作业二 单选题 一、单选题（共25 道试题，共100 分。） 1. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作 A. 条件判断 B. 结点移动 C. 算术表达式 D. 赋值语句 -----------------选择：B 2. 在一个单链表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; -----------------选择：B 3. 线性表是一个具有n个（）的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 -----------------选择：C 4. 若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为( )。 A. 10，15，14，18，20，36，40，21 B. 10，15，14，18，20，40，36，21 C. 10，15，14，20，18，40，36，21 D. 15，10，14，18，20，36，40，21 -----------------选择：A 5. 按照二叉树的定义，具有3个结点的二叉树有（）种。 A. 3 B. 4 C. 5 D. 6 -----------------选择：C 6. 下列有关图遍历的说法中不正确的是（）。 A. 连通图的深度优先搜索是个递增过程 B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C. 非连通图不能用深度优先搜索法 D. 图的遍历要求每个顶点仅被访问一次 -----------------选择：C 7. Substr('DATA STRUCTURE'，5，9)=（）。 A. STRUCTURE' B. 'ASTUCTUR' C. 'DATA STRUCTRUE'
北航2002年程序设计与数据结构试题 一、简答题（10’） 1. 数据结构课程是计算机专业的基础课还是专业课，或者专业基础课？（2’） 2. 学习数据结构课程需要哪些课程作为它的基础（举例两门课程）？若没有这些知识，对学习数据 结构课程可能会产生哪些影响？请举例说明（不超过100字）。（4’） 3. 数据结构课程将为那些课程学习奠定必要的基础？请举例说明哪些课程（举例两门课程）用到了 数据结构课程的哪些知识（不超过100字）。（4’） 二、（5’） 请推导出结论：具有0n 个叶结点的哈夫曼树（Huffman ）的分支总数为02(1)n -。 三、单项选择题（2’×15） 1. 线性链表中各链接点之间的地址________。 A. 必须连续 B. 部分地址必须连续 C. 不一定连续 D. 连续与否无所谓 2. 在非空线性链表中由p 所指的链接点后面插入一个由q 所致的链接点的过程是依次执行动作 ________。 A. link(q)←p; link(p)←q; B. link(q)←link(p); link(p)←q; C. link(q)←link(p); p ←q; D. link(p)←q; link(q)←p; 3. 在非空双向循环链表中由q 所指的那个链接点前插入一个p 指的链接点的动作对应的语句依次为 rlink(p)←q, llink(p)←llink(q), llink(q)←p, ________。（空白处为一条赋值语句） A. rlink(q)←p B. rlink(llink(q))←p C. rlink(llink(p))←p D. rlink(rlink(p))←p 4. 在初始为空的堆栈中依次插入元素f, e, d, c, b, a 以后，连续进行了三次删除操作，此时栈顶元素是 ________。 A. c B. d C. b D. e 5. 若某堆栈的输入序列为1, 2, 3, …, n ，输出序列的第1个元素为n ，则第i 个输出元素为________。 A. i B. n i - C. 1n i -+ D. 哪个元素无所谓 6. 求字符串T 在字符串S 中首次出现的位置的操作称为________。 A. 求串的长度 B. 求子串 C. 串的模式匹配 D. 串的连接 7. 若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为 4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，该树一共有________个叶结点。 A. 35 B. 28 C. 77 D. 78 8. 若一棵二叉树有1001个结点，且无度为1的结点，则叶结点的个数为________。 A. 498 B. 499 C. 500 D. 501 9. 已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为ABCDEFGH ，该完全二叉 树的后序遍历序列为________。
北航10秋学期《算法与数据结构》模拟题一 一、单项选择题（本大题共15小题，每小题2分，共30分） 1、顺序表是线性表的（） A．链式存储结构 B．顺序存储结构 C．索引存储结构 D．散列存储结构 2、循环链表主要优点是（） A．不再需要头指针了 B．已知某个结点的位置后，能够容易找到它的直接前趋 C．在进行插入、删除运算时，能更好地保证链表不断开 D．从表中任一结点出发都能扫描到整个链表 3、根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是（） A．集合中任何两个结点之间都有逻辑关系但组织形式松散 B．线性结构中结点按逻辑关系依次排列形成一条"锁链" C．树形结构具有分支、层次特性，其形态有点像自然界中的树 D．图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接 4、以下说法错误的是（） A．求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B．顺序存储的线性表可以随机存取 C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 D．线性表的链式存储结构优于顺序存储结构 5、以下说法错误的是（） A．每个存储结点只能存放一个数据元素 B．数据元素之间的关联方式可由存储结点之间的关联方式直接表达 C．一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级 D．语言级描述可经编译自动转换成机器级因此也可以看成是一种机内表示 6、对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（）方法 A．归并排序 B．直接插入排序 C．直接选择排序 D．快速排序。 7、在文件局部有序或文件长度较小的情况下，最佳的排序方法是（） A．直接插入排序 B．冒泡排序 C．直接选择排序 D．归并排序 8、对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由（）式确定. A．Loc[i,j]=A[m,n]+[(n+1)*i+j]*k B．Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C．Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D．Loc[i,j]=[(n+1)*i+j]*k
2013年“数据结构与C程序设计”(代码991)试题 一、单项选择题（本题共20分，每小题各2分） 1．对于长度为n的线性表，建立其对应的单链表的时间复杂度为( )。 A．O(1)；B．O(log2n)；．O(n)；D．O(n2)。 2．一般情况下，在一个双向链表中插入一个新的链结点，( )。 A．需要修改4个指针域内的指针；B．需要修改3个指针域内的指针； C．需要修改2个指针域内的指针；D．只需要修改1个指针域内的指针。 3．假设用单个字母表示中缀表达式中的一个运算数(或称运算对象)，并利用堆栈产生中缀表达式对应的后缀表达式。对于中缀表达式A+B*(C/D-E)，当从左至右扫描到运算数E时，堆栈中的运算符依次是( )。(注：不包含表达式的分界符) A．+*/-；B．+*(/-；C．+*-；．+*(-。 4．若某二叉排序树的前序遍历序列为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。 6．下列关于图的叙述中，错误的是( )。 A．根据图的定义，图中至少有一个顶点； B．根据图的定义，图中至少有一个顶点和一条边(弧)； C．具有n个顶点的无向图最多有n(n-1)/2条边； D．具有n个顶点的有向图最多有n(n-1)条边(弧)。 7．若在有向图G的拓扑序列中，顶点vi在顶点vj之前，则下列4种情形中不可能出现的是( )。 A．G中有弧
北航《数据库原理及应用》在线作业二 单选题 一、单选题（共25 道试题，共100 分。） 1. 若用如下的SQL语句创建了一个表S ：CREATE TABLE S(S# CHAR(6) NOT NULL, SNAME CHAR(8) NOT NULL, SEX CHAR(2), AGE INTEGER) 今向S表插入如下行时，哪一行可以被插入 A. ('991001','李明芳',女，'23') B. ('990746','张为',NULL,NULL) C. (NULL,'陈道一'，'男',32) D. ('992345',NULL,'女',25) -----------------选择：B 2. 下列有关数据库的恢复的说法中不正确的是（） A. 应定期将数据库做成档案文件 B. 在进行事务处理过程时数据库更新的全部内容写入日志文件 C. 发生故障时用当时数据内容和档案文件更新前的映象，将文件恢复到最近的检查点文件状态。 D. 数据库恢复，还可用最新的档案文件和日志文件的更新映象，将文件恢复到最新的检查点文件状态。 -----------------选择：C 3. 在命令窗口执行SQL命令时，若命令要占用多行，续行符是______。 A. 冒号(:) B. 分号(;) C. 逗号(,) D. 连字符(-) -----------------选择：D 4. 事务的执行不被其它事务干扰，这个性质称为事务的（） A. 原子性 B. 隔离性 C. 持久性 D. 一致性 -----------------选择：B 5. 规范化理论是关系数据库进行逻辑设计的理论依据。根据这个理论，关系数据库中的关系必须满足其每一属性都是（） A. 互不相关的 B. 不可分解的 C. 长度可变的 D. 互相关联的 -----------------选择：B 6. SQL语言中，删除一个表的命令是（）。 A. CLEAR TABLE
991“数据结构与C语言程序设计”考试大纲（2017版） 2017年“数据结构与C语言程序设计”考试内容包括“数据结构”与“C语言程序设计”两门课程的内容，各占比例50%。试卷满分为150分。 “数据结构”部分 一、概述 1．数据的逻辑结构与存储结构的基本概念； 2．算法的定义、基本性质以及算法分析的基本概念，包括采用大O形式表示时间复杂度和空间复杂度。 二、线性表 1．线性关系、线性表的定义，线性表的基本操作； 2．线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和双向链表)的构造原理； 3．在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)。 三、数组 1．一维数组和二维数组的存储； 2．矩阵的压缩存储的基本概念； 3．对称矩阵、对角矩阵以及三角矩阵的压缩存储。 四、堆栈与队列 1．堆栈与队列的基本概念与基本操作； 2．堆栈与队列的顺序存储结构与链式存储结构的构造原理； 3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计； 4. 循环队列的基本概念； 5．堆栈和队列在解决实际问题中应用。 五、树与二叉树 1．树与二叉树的基本概念，基本特征、名词术语； 2．完全二叉树与满二叉树的基本概念，二叉树的基本性质及其应用；
3．二叉树的顺序存储结构与二叉链表存储结的基本原理； 4．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，重点是二叉树在以二叉链表作为存储结构基础上各种遍历算法(包括非递归算法)的设计与应用； 5．二叉排序树的基本概念、建立(插入)、查找以及平均查找长度ASL的计算。 六、图 1．图的基本概念、名词术语； 2．图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点； 3．图的深度优先搜索与广度优先搜索； 4．最小(代价)生成树、最短路径、AOV网与拓扑排序以及AOE网与关键路径的基本概念与求 解过程。 七、文件及查找 1．顺序查找法以及平均查找长度(ASL)的计算； 2．折半查找法以及平均查找长度(ASL)的计算，包括查找过程对应的“判定树”的构造； 3．B-树和B+树的基本概念，B-树的插入与查找； 4．散列(Hash)表的构造、散列函数的构造，散列冲突的基本概念、处理散列冲突的基本方法以及散列表的查找和平均查找长度的计算。 八、内排序 1．排序的基本概念，各种内排序方法的基本原理和特点，包括排序过程中进行的元素之间的比较次数，排序总趟数、排序稳定性以及时间复杂度与空间复杂度计算； 2．插入排序法(含折半插入排序法)； 3．选择排序法； 4．(起)泡排序法； 5．谢尔(Shell)排序法； 6．快速排序法； 7．堆积(Heap)排序法，包括堆积的定义与构造； 8．二路归并排序法。 “C语言程序设计”部分
北京航空航天大学2012年硕士研究生入学考试试题 “数据结构与C语言程序设计”（科目代码：991） 一、填空题(本题共20分，每小题各2分) 1．从总体上说，“数据结构”课程主要研究三个方面的内容。 2．若对某线性表最常用的操作是在表中插入元素或者删除表中元素，则对于顺序存储结构和链式存储结构这两种存储结构而言，线性表应该采用。 3．在长度为n的非空队列中进行插入或者删除操作的时间复杂度用大O符号表示 为。 4．若一棵度为4的树中度为1、2、3和4的结点个数分别为4、2、1和1，则该树中叶结点的个数为。 5．若某二叉树的中序遍历序列为B,A,F,D,G,C,E，按层次遍历序列为A,B,C,D,E,F,G，则该二叉树的后序遍历序列为。 6．将一棵结点总数为n、且具有m个叶结点的树转换为一棵二叉树以后，该二叉树中右子树为空的结点有个。 7．对于图G=(V,E) 与G^=(V^,E^)，若有V^包含于V，E^包含于E，则称G^是G的。8．在顺序表(6,15,30,37,65,68,70,72,89,99)中采用折半查找法查找元素37，与表中进行过比较的元素依次是。 9．若已知n个关键字值具有相同的散列函数值，并且采用线性探测再散列法处理冲突，那么，将这n个关键字值全部散列到初始为空的地址空间中，发生散列冲突的次数是。10．若长度为n的序列K=(k1,k2,…,kn)当且仅当满足ki≤k2i并且ki≤k2i+1(1≤i≤n/2)时，则称该序列为一个小顶堆积(Heap)。根据该定义，序列(26,5,77,1,61,11,59,48,15,19)对应的小顶堆积是。 二、简答题(本题共20分，每小题各5分) 1．如果一个具有100个顶点、200条边的有向图采用邻接矩阵存储，该邻接矩阵是否是稀疏矩阵？为什么？（这里我们假设：当矩阵中非零元素的数目小于整个矩阵总元素的数目的5%时认为该矩阵为稀疏矩阵） 2．一般情况下，建立散列表时难以避免出现散列冲突，常用处理散列冲突的方法之一是开放定址法，该方法的基本思想是什么？ 3．若对序列(2,12,16,88,5,10)按值从小到大进行排序，前三趟排序的结果分别为： 第1趟排序的结果：(2,12,16,5,10,88) 第2趟排序的结果：(2,12,5,10,16,88) 第3趟排序的结果：(2,5,10,12,16,88) 请问：该结果是采用了选择排序法还是采用了(起)泡排序法得到的？为什么？ 4．快速排序法的排序过程是递归的。若待排序序列的长度为n，则快速排序的最小递归深度与最大递归深度分别是多少？ 三、综合题(本题共20分，每小题各5分) 1．若非空双向循环链表中链结点结构为llink data rlink，则依次执行下列4条语句的目的是在该链表中由q指的结点后面插入一个由p指的结点，其中1条语句有错误，请找出该语句，并写出正确的语句。
北航《管理信息系统》复习题二一、单选题（本大题共20小题，每题1.5分，共30分） 1．对于“指针”和“链”，下面的说法正确的是（） A．它们是数据物理组织的两种形式 B．它们是数据逻辑组织的两种形式 C．它们是数据物理组织的两种基本工具 D．它们是数据逻辑组织的两种基本工具 2．绘制信息系统流图基础是新系统的（） A．业务流程图B．数据流程图 C．表格分配图D．处理流程图 3．管理信息系统的特点是（） A．数据集中统一，应用数学模型，有预测和控制能力，面向操作人员B．数据集中统一，应用人工智能，有预测和决策，面向高层管理人员C．数据集中统一，应用数学模型，有预测和控制能力，面向管理和决策D．应用数学模型，有预测和决策能力，应用人工智能，面向管理人员4．与概念级数据库对应描述的是（） A．物理结构B．全局逻辑结构 C．局部逻辑结构D．用户数据结构 5．对控制职能起着举足轻重作用的是信息的充分、准确和（）A．完整B．有效 C．定量化D．及时传递 6．从本质上讲，信息系统的开发方法可以划分为两大类，即（）A．结构化生命周期法和战略数据规划方法 B．预先严格定义的方法和原型化方法 C．预先严格定义的方法和战略数据规划方法 D．企业系统规划方法和战略数据规划方法 7．对数据文件的维护包括（） A．数据库的正确性保护、转储与恢复；数据库的重组和重构 B．对数据文件的安全性、完整性控制；数据库的重组和重构
C．对数据文件的安全性、完整性控制；数据库的正确性保护、转储与恢复；数据库的重组和重构 D．对数据文件的安全性、完整性控制；数据库的正确性保护、转储与恢复 8．信息的使用在深度上大体可分为三个阶段，即（） A．EDP阶段、MIS阶段、DSS阶段 B．提高工作效率阶段、信息及时转化为价值阶段、支持决策阶段 C．提高工作效率阶段、信息及时转化为价值阶段、寻找机会阶段 D．提高工作效率阶段、提高组织效益阶段、寻找机会阶段 9．信息资源管理（IRM）起源于（） A．管理信息系统、决策支持系统、事务处理系统、电子数据处理 B．管理信息系统、图书情报管理、数据库行政管理 C．图书情报管理、数据库行政管理、事务处理系统、电子数据处理 D．图书情报管理、事务处理系统、电子数据处理等领域 10．I是一种战略资源，II则是一种战略武器、这里I和II分别是（） A．I 是信息，II是信息技术B．I是信息技术，II信息系统 C．I是能源，II信息技术D．I是信息资源，II是信息系统 11．决策支持系统通过它的输出接口产生报告、数据库查询结构和模型的模拟结果，这些结果又提供了对决策过程中（）的支持。 A．方案设计、方案选择、评价B．情报收集、方案设计、方案设计、评价C．情报收集、方案设计、方案选择D．方案设计、方案选择 12．LKP框架结构的DSS包含（）等几部分，其中最后一部分是DSS求解问题的核心。 A．语言系统、知识系统、问题处理系统、模型库系统 B．语言系统、知识系统、，模型库系统、问题处理系统 C．语言系统、知识系统、问题处理系统 D．语言系统、问题处理系统、知识系统 13．在DSS的DDM结构中，决策支持系统的核心是（） A．数据库B．模型库和数据库 C．模型库和方法库D．对话生成管理系统 14．电子数据处理系统（EDP）、管理信息系统（MIS）、决策支持系统（DSS），一般来讲它
北京航空航天大学 2015 ～2016 学年第 2 学期 《软件技术基础》 考试B试卷 班级：__________；学号：______ ； 姓名：__________；成绩：______ ； 2016年6 月16 日
一、选择题（每题2分，共20分） 1、若五个元素的出栈序列为1、 2、 3、 4、5，则进栈序列可能是（） A.2,4,3,1,5 C.3,1,4,2,5 B.2,3,1,5,4 D.3,1,2,5,4 1、若从无向图的任意一个顶点出发一次深度优先搜索便可以访问该图的所有顶点，则该图一定是一个（）图。 A.非连通 C.强联通 B.连通 D.完全 3、算法分析的目的是（)。 A.研究算法的输入与输出之间的关系C.分析算法的效率，以求改进 B.找出数据结构的合理性 D.分析算法的可读性 4、下面那个不是数据结构的基本研究内容（）。 A.数据的逻辑结构 C.数据的存储结构 B.语法 D.算法 5、若变量list是带头结点的循环链表的头结点指针，则该链表最后那个链接点的指针域中存放的是（）。 A.变量list的地址 C.变量list指的链结点的值
B.变量list的内容 D.链表第一个链结点的地址 6、对于一个不带权的无向图的邻接矩阵而言，（）。 A.矩阵中非零元素的数目等于图中边的数目 B.矩阵中非全零的行的数目等于图中顶点的数目 C.第i行的非零元素的数目与第i列非零元素的数目相等 D.第i行与第i列的非零元素的总数等于第i个顶点的度数 7、在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列空的条件是（）。 A.front==rear+1 C.front==rear B.rear==front+1 D.front==0 8、在所学过的排序方法中，排序趟数与序列原始状态有关的方法是（）。 A.选择排序法 C.冒泡排序法 B.谢尔排序法 D.快速排序法 9、数据库DBNS能实现对数据库中数据的查询、插入、修改和删除操作，该功能称为（）。 A.数据定义功能 C.数据操纵功能 B.数据存储功能 D.数据控制功能
北航《算法与数据结构》在线作业 北航“算法与数据结构”在线作业1 1，单题(25题，100分)) 1。下面的陈述是错误的() a .线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置b上不一定是相邻的.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置c上不一定是相邻的.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定是相邻的.d线性表的链式存储结构的特点是用一组任意的存储单元来存储带满分的线性表的数据元素:4点 2。头节点的单链表的头为空的判定条件() A。头=空b头->下一个=空c头->下一个=头d头！=人头满分:4分3。有一个10，000个元素的无序序列。我希望尽快选出前10个最大元素。在不改变现有算法结构 的前提下，()是以下内部排序算法中最合适的 A。选择排序方法b .快速排序方法c .堆排序方法d .冒泡排序方法满分:4分 4。在以下堆栈的基本操作中，那些不是处理操作的是()。 A。倒推，倒推，倒推，倒空，满分:4分
5。让矩阵a是一个对称矩阵(aij=aji，1 next = head d . p = head full score:4 points 11。设置一个有n个节点的二叉树。其深度为 a . n-1 b . n c . 5 floor(log2n) d .无法确定满分:4分 12。当堆栈存储在大小为N的数组序列中时，假设top = = N用于指示堆栈为空， 会在移除堆栈时修改top指针with()语句 a . to p ++ b . top = 0 c . top- d . top = n满分:4分法 A，块b，序列c，二进制d，哈希满分:4分 13。如果要求线性表能够快速查找并满足动态变化的要求，可以使用()finder 14。使用二进制搜索方法查找长度为n的线性表时，每个元素的平均搜索长度为()
单项选择题 第1题一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。如果按层次顺序从1开始对全部结点编号，问编号为n的结点的父结点（若存在）的编号是多少？（） A、2n-1 B、Kn-1 C、K D、1+2+3+…+K 答案：B 第2题下一段程序实现的功能是打印以h为头节点的单链表中的所有节点，哪一段程序是正确的：（）。 A、p = h while ( p != NULL ) {printf(p->data) p = p->next} B、while ( h != NULL ) {printf(h->data)h = h->next} C、p = h while ( p!= NULL ) {p = p->next printf(p->data)} D、p = h while ( p－>next!= NULL ) {p = p->next printf(p->data)} 答案：A 第3题文件的基本组织方式有：（）。 A、顺序组织、索引组织、散列组织和链接方式 B、磁盘组织、磁带组织 C、数据库组织 D、关键字与非关键字 答案：A 第4题设n为正整数。试确定下列程序段中带标号@的语句的频度。 X=91; Y=100; While(y>0) @If(x>100){ X=x–10; Y=y–1; }else x=x+1; ：（）。 A、无穷多次 B、1100 C、9100 D、100
答案：B 多项选择题 第5题下述陈述中哪一项是正确 的(): A、文件是由记录组成的集合 B、记录是文件存取的基本单位 C、文件是由数据项组成的 D、数据项有时也被称之为字段 答案：B|D 第6题下列排序算法中哪些是不稳定 的(): A、昌泡排序 B、选择排序 C、快速排序 D、堆排序 答案：B|C|D 判断题 第7题在单向链表中，在X指向的结点后插入结点，对应的方法与X是否是头指针无关。 正确 错误 答案：错误
北航《算法与数据结构》复习题 单选题（每小题2分，总分10分） 1、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（D ） A、必需是联系的 B、部分地址必须是连续的 C、一定是不连续的 D、连续不连续都可以 2、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以什么为标准操作（B） A、条件判断 B、结点移动 C、算术表达式 D、赋值语句 3、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B ） A、p->next=s;s->next=p->next; B、s->next=p->next;p->next=s; C、p->next=s;p->next=s->next; D、p->next=s->next;p->next=s; 4、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（C ） A、(2,5,12,16)26(60,32,72) B、(5,16,2,12)28(60,32,72) C、(2,16,12,5)28(60,32,72) D、(5,16,2,12)28(32,60,72) 5、稀疏矩阵的压缩存储方法是只存储（A ） A、非零元素 B、三元组（i,j, aij） C、aij D、i,j 1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（A）排序法。 A、插入 B、选择 C、希尔 D、二路归并 2、用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（D ） A、一定都是同义词 B、一定都不是同义词 C、都相同 D、不一定都是同义词 3、将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为（D ） A、42 B、40 C、21 D、20 4、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B ） A、不确定 B、n-i+1 C、I D、n-i 5、设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（C）个 A、k+1 B、2k C、2k-1 D、2k+1 判断题（每小题1分，总分10分）(A==对，B==错) 6、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。（B） 7、就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大（B） 8、任何一棵二叉树都可以不用栈实现前序线索树的前序遍历（A） 9、在一棵具有n个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。（B ） 10、线索二叉树中的每个结点通常包含有5个数据成员。（A ） 11、从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为选择排序（B ） 12、在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终的排序算法是冒泡排序（A ） 13、不是所有的AOV网都有一个拓朴序列（A ） 14、对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树（A ）