北京邮电大学2018年807软件工程考研真题
- 格式：pdf
- 大小：269.91 KB
- 文档页数：8
邮学，北邮考研辅导领军者
1 北京邮电大学
2018年硕士研究生入学统一考试试题
考试科目：软件工程专业综合
请考生注意：①所有答案（包括选择题和填空题）一律写在答题纸上，否则不计成绩
②不允许考生使用计算器。
本试题包含数据结构，数据库和操作系统三个科目。请考生在答题时注明答题科
目。数据结构总分90分，为必选部分。其他两部分总分各为60分，是二选一科目。
必选科目数据结构（90分）
一、选择题（每小题2分，共20分）
1．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点 （1≤i≤n）
C． 删除第i个结点（1≤i≤n）
D． 将n个结点从小到大排序
2 ．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1, p2, p3, …, pn ，若p1=n，则
pi为：
A．i B．n-i C．n-i+1 D．不确定
3．设有两个串p和q，求q在p中首次出现的位置的运算称作：
A．连接 B．模式匹配 C．求子串 D．求串长
4．二叉排序树的前序遍历和中序遍历序列如下：前序遍历：EFHIGJK，中序遍历：HFIEJKG。
该二叉树的根的右子树的根是：
A．E B．F C．G D．H
5．已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是：
A．0321 B．0123 C．0132 D． 0312
6．下列二叉排序树中查找效率最高的是：
A．平衡二叉树 B．排序二叉树
C．没有左子树的排序二叉树 D．没有右子树的排序二叉树
7．要尽可能快的对序列进行稳定的排序，则应该选择：
邮学，北邮考研辅导领军者
2 A．快速排序 B．归并排序 C．冒泡排序 D．堆排序
8．哈希表的地址区间是0到16，哈希函数为H（K）=K mod 17，采用线性探测法处理冲突，
并将关键字序列26，25，72，38，8，18，59依次存储到哈希表中。则元素59存放在哈希表
中的地址是：
A．8 B．9 C．10 D．11
9．如果线性表用链表实现，下面所列的算法中哪一种算法对线性表排序速度最快：
A．简单选择排序 B．归并排序 C．插入排序 D．快速排序
10．设矩阵A是某个有向图的邻接矩阵（0-1矩阵），矩阵B是m个A相乘，即B=Am=[bjk]。
关于bjk下面的哪个陈述是正确的？
A．如果bjk =0，则不存在顶点Vj到Vk的通道
B．如果bjk =1，则存在一条从顶点Vj到Vk的通道
C．如果bjk ≠0，则有m条从Vj到Vk的通道
D．从Vj到Vk的长度为m的通道有bjk条
二、简答题（每小题10分，共40分）
11．下面是计算Fibonacci数的递归实现：
int fib( int n ) {
if ( n <=1 ) return n;
return f(n-1)+f(n-2);
}
用n度量问题规模的大小，求其时间复杂度和空间复杂度。
12．简述堆调整的算法，并且用此算法将数组9，8，7，6，5，4，3，2，1，0调整为小根堆，
写出4个中间状态和最终状态。
13．已知一个无向图如图所示，要求分别用Prim和Kruskal算法生成最小生成树（假设以0为
起点，给出构造过程）。
邮学，北邮考研辅导领军者
3 14．用链表实现的线性表通常要添加一个头结点。请解释添加头结点作用。而带头结点的链表
通常实现成循环的链表，请解释此做法的原因。
三、编程题（每小题15分，共30分）
15．n次Legendre次多项式Pn(x)的递归定义是：
0
1
n-1n-2()1
();
()(21/) P(x)-(1-1/n) P(x) (n>1)nPx
Pxx
Pxnx=
=
=−
请编写函数double legendre(double x,int n)。它按照上面的定义用非递归的方式求n次
Legendre多项式在x处的值。
16．现有两个按元素值 递增有序排列的单链表A和B。请编写算法，将A表和B表归并成一
个按元素值递减有序排列的单链表C。要求利用原表空间。
请考生注意：以下题目分为数据库和操作系统两部分。考生在这两个科目中选择
一个答题即可。如果出现两科目都答题情况则随机选取一科目计分。两门科目的
总分均为60分。请考生注明选择科目。
二选一科目数据库（60分）
四、选择题（每小题2分，共20分）
1．数据库系统的数据独立性体现在 。
A．不会因为数据的变化而影响到应用程序
B．不会因为系统数据存储结构与数据逻辑结构的变化而影响应用程序
C． 不会因为存储策略的变化而影响存储结构
D． 不会因为某些存储结构的变化而影响其他的存储结构
2．下面的选项不是关系数据库基本特征的是 。
A．不同的列应有不同的数据类型 B．不同的列应有不同的列名
C．与行的次序无关 D．与列的次序无关
3．用二维表来表示实体及实体之间联系的数据模型称为 。
A．实体—联系模型 B．层次模型
C．关系模型 D．网状模型
4．关系模型中有三类完整性约束，定义外部关键字实现的是哪一类完整性 。
A．实体完整性 B．用户自定义完整性 邮学，北邮考研辅导领军者
4 C．实体完整性、参照完整性 D．参照完整性
5．在SQL语言中，视图是数据库体系结构中的 。
A．内模式 B．模式
C．物理模式 D．外模式
6．关系代数中的投影操作是指从关系中 。
A．抽出特定记录 B．抽出特定字段
C．建立相应的影像 D．建立相应的图形
7．数据库服务器、数据库和表的关系，正确的说法是 。
A．一个数据库服务器可以管理多个数据库，一个数据库可以包含多个表
B．一个数据库服务器只能管理一个数据库，一个数据库只能包含一个表
C．一个数据库服务器只能管理一个数据库，一个数据库可以包含多个表
D．一个数据库服务器可以管理多个数据库，一个数据库只能包含一个表
8．约束“年龄限制在18～30岁之间”属于DBMS的 功能。
A．安全性 B．恢复
C．并发控制 D．完整性
9．在并发操作中可能产生若干数据库不一致性，除了丢失修改、不能重复读以外，还
有 。
A．读“脏”数据 B．不可串行化
C．事务内部故障 D．活锁和死锁
10．在数据库的安全性控制中，授权的数据对象的 ，授权子系统就越灵活。
A．范围越小 B．约束越细致
C．范围越大 D．约束范围大
五、简答题（每小题5分，共15分）
11．试述SQL的数据定义功能。
12．试述数据库安全性的目的和措施。
13．解释调度、可串行、不可串行的概念。
六．计算题（每小题3分，共15分）
运动会数据库由项目表、运动员表和参加表组成：
项目表projects(pid,name,best)，分别表示项目号、名称、最好成绩；
运动员表emplyoees(eid,name,unit,sex,age)，分别表示运动员编号、姓名、单位、性别、年龄； 邮学，北邮考研辅导领军者
5 参加表works(pid,eid,date,score)，表示参加项目号、运动员编号、日期和成绩。
14．检索“中央电视台”单位的运动员参加的比赛项目号、名称、最好成绩，写出关系代数表
达式。
15．检索没有参加任何项目的运动员姓名，写出其关系代数表达式。
16．画出15关系代数表达式的语法树。
17．写出SQL语句：检索姓名为李刚的运动员参加的项目名称和成绩。
18．写出SQL语句：检索参加“短跑”比赛的运动员编号、姓名、单位、性别、年龄，按照
年龄降序排列。
七、设计题（每小题5分，共10分）
某电脑公司是一家专门销售计算机整机、外围设备和零部件的公司。该公司有3个部门：市场
部、技术部和财务部。市场部有18位业务员，负责采购和销售业务；技术部有14位工程师，
负责售后服务、保修等技术性的工作；财务部有12位工作人员、1位会计和1位出纳，负责财
务业务。公司需要将所有经营的客户、销售、维修（服务、保修）、职工等信息都存储在数据
库中。
19．试分析该公司关系模式（部门编号，部门名称，职工编号，职工姓名，性别，岗位，业务
编号，业务名称，客户编号，客户姓名，订单号）的函数依赖，并指明其主码；将该关系模式
分解到3NF。
20．设计该数据库的E—R图，将该E—R图转化为关系模式结构。
二选一科目操作系统（60分）
八、判断题（每小题1分，共10分）
请考生在答题纸上标记所给出判断题题目的题，并在题号后给出正确与否的选择，标注方式
采用“对”/“错”，或者“True”/“False”，或者“T”/“F”形式。
1．如果多个作业需要调入内存但没有足够的内存，那么系统必须在这些作业中做出选择，这
样的决策过程被称为CPU调度。
2．程序的并发执行是指同一时刻有两个以上的程序，它们的指令在同一处理器上执行。
