10. 对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是(C )。
a) n b) (n-1)*(n-1) c) n-1 d) n2
11. 在一个具有n个顶点的有向完全途中,所含有的边数是( A )。 a) n b) n*(n-1) c) n(n-1)/2 d) n(n+1)/2
12. 含有n个顶点e条边得无向连通图,利用Prim算法生成的最小生成树其时间复杂度为( C )。
a) O(e*n) b) O(elog2e) c) O(n2) d) O(nlog2n) 二. 填空题(本大题共7小题,每空2分,共16分)
13. 在数据结构中,从逻辑上可以把数据结构分成 线性结构 和 非线性结构 。
14. 从栈顶指针为top的链栈中删除一个结点,并将被删除结点的值保存在x中,其操作步骤为 x=top->data top=top->next 。
15. 对n个元素进行冒泡排序时,最少比较次数是 n-1 。
16. 在一棵具有10个叶子结点的二叉树中,度为2的结点个数为 9 个。 17. 对一棵二叉搜索树进行 中序 遍历,可得到一个关键字递增有序序列。
18. 已知有向图的邻接矩阵,要计算第i号顶点的出度,计算方法是将 第i个 元素累加。
19. 用深度优先搜索策略来遍历一个图类似于树的 先序 遍历。 三、应用题(本大题共4小题,每小题10分,共40分)
20. 对于图1所示的树:画出其转换成相应的二叉树树型。写出相应二叉树的中序遍历。
21. 已知关键字序列(25,89,12,34,76,45,9,56),采用直接插入排序法关键字递增(从小到大)排序,给出每一趟排序的结果。
22. 已知闭散列表的长度为10(散列地址空间为0?9),散列函数H(k)=k%8,采用线性重新散列技术解决冲突。将下列一组数据(25,16,38,47,79,82,5,39)依次插入散列表中,请画出插入这组数据后的散列表。
23. 用克鲁斯卡尔(Kruskal)算法求图2所示的无向带权连通图的最小生成树,请依次画出生成最小生成树的过程,并计算最小生成树的权。
24. 算法设计题(本大题共2小题,每小题10分,共20分) 请将答案填写在答题纸相应的位置上。
25. 阅读下面程序,假设以两个元素递增(从小到大)有序排列的线性表A和B分别表示两个集合,且同一表中无相同元素,现要求另辟空间构成一个线性表C,其元素为A和B中元素的交集,C同样以元素递增方式排序。集合的链表结点结构定义如下,请完善下列程序。
Typedef struct LNode{ElemType data; struct LNode *next;}*LinkList;
LinkList Intersect(LinkList A,LinkList B) {
LNode *p,*q,*r,*s; LinkList C;
C = (LNode)*malloc(sizeof(LNode)); C->next = NULL; r=C;p=A;q=B;
while( (1) ) {
if(p->data
s=(LNode*)malloc(sizeof(LNode)); s->data = p->data; r->next = s; r = s;
(3) ; q=q->next; } else
(4) ; }
r->next = NULL; C=C->next;
return (5) ; }
26. 对于二叉树以二叉链表为存储结构,其根指针为root,树结点结构定义如下,请写出求二叉树的深度(设根的深度为1)的算法。 typedef int TreeItem;
typedef struct btnode *btlink; struct btnode {
TreeItem element; btlink left; btlink right; }Btnode;
第三部分 关系数据库与sql语言(共100分)
一、单项选择题(本大题共20小题,每小题2分,共40分)
在每小题列出的四个备选项中,只有一个是符合题目要求的,请将正确答案代码填写在答题纸相应位置上。
1. 数据库管理系统的英文缩写是:C
a) DB b) DBS c) DBMS d) DBRS
2. 要在表中插入新记录,需要使用以下哪个语句?A
a) Insert b) Select c) Update d) Delete
3. 数据管理技术的发展经过了三个阶段,以下哪个不是这三个阶段之中的?B
a) 人工管理阶段 b) 高级语言阶段 c) 文件系统阶段 d) 数据库系统阶段 4. 数据库系统的模式/内模式映像,确保了数据的什么独立性?D
a) 软件独立性 b) 存取独立性 c) 逻辑独立性 d) 物理独立性 5. 以下哪种模型不是数据库系统中的数据模型?A
a) 还原模型 b) 层次模型 c) 网状模型 d) 关系模型
6. 如果一个关系R∈1NF,并且每一个非主属性都完全函数依赖于码(键),则称关系R 于:A
a) 2NF b) 3NF c) 4NF d) BCNF
7. 现有学生表S(Sno,Sname)和选课表SC(Sno,Cno,G),其中Sno表示学号,Sname表示姓名,Cno表示课程号,G表示成绩。要查询学生李琳选修的所有课程的成绩,下列关系代数表达式中正确的是:B
a) πG(σS.Sno = SC.Sno(S∞SC)) b) πG(σS.Sname = ‘李琳’(SxSC)) c) πG(σS.Sname = ‘李琳’(S∞SC)) d) πG(σS.Sname = ‘李琳’(S)xSC))
8. 如果R属于第三范式,则下列描述哪一项是错误的?B a) R中不存在非主属性部分依赖于码(键)的情况 b) R不属于第二范式
c) R中不存在非主属性传递依赖于码(键)的情况 d) R属于第一范式
9. SQL中,“DELETE FROM 表名“表示:A a) 从基本表中删除所有元组 b) 从基本表中删除所有属性 c) 从数据库中撤销这个基本表 d) 从基本表中删除重复元组
10. 将E-R图转换为关系模型是,关于实体的转换原则,下列描述错误的是:B a) 一个实体转换为一个关系模型 b) 两个实体转换为一个关系模式 c) 实体的键就是关系的键 d) 实体的属性就是关系的属性
11. 下述SQL语句中,修改表中数据的命令是:C a) ALTER b) CREATE c) UPDATE d) INSERT 12. 在SQL语句中,与“MIN d) 13. 设有关系模型R(A,B,C,D),F是R上成立的函数依赖集,F={B->C,C->D},则R的候选码(候选键)为:B a) BCD b) AB c) CD d) BC 14. 在select语句中,指定选择条件的是哪个子句? C a) Select b) From c) Where d) Group by 15. 数据库管理系统提供的DML语言是:D a) 数据定义语言 b) 数据备份语言 c) 数据控制语言 d) 数据操纵语言 16. 数据库在磁盘上的基本组织形式是:B a) 模型 b) 文件 c) 二维表 d) 二叉树 17. 设有关系R(A,B,C)的值如下:A A B C 2 2 3 2 3 4 3 3 5 a) 函数依赖A->B在上述关系中成立 b) 函数依赖BC->A在上述关系中成立 c) 函数依赖B->A在上述关系中成立 d) 函数依赖A->BC在上述关系中成立 18. 以下哪一个不属于数据库的三级模式结构?D a) 外模式 b) 模式 c) 内模式 d) 组合模式 19. 以下描述正确的是:B a) 交运算可以用并运算来表示 b) 交运算可以用差运算来表示 c) 并运算可以用差运算来表示 d) 并运算可以用交运算来表示 20. 五种基本关系代数运算是:A a) ∩,-,Ⅹ,π和σ b) ∪,-,∞,π和σ c) ∪,∩,Ⅹ,π和σ d) ∪,∩,∞,π和σ 二、 填空题(本大题共8小题,每空2分,共20) 21. 关系的 实体 完整性约束:说明了键的属性列值必须唯一,其值不能为空或者部分为空。 22. 关系模型可以形式化地表示为R(U,D,DOM,F),其中R表示关系名,U表示属性名集合,D表示属性来自的域,DOM表示属性向域的映像集合,F表示属性间 集合。 23. SQL(Structured Query Language)的中文是 数据结构化 语言,是关系数据库的标准语言。 24. 两个实体型之间的联系有三种类型:一对一联系、一对多联系、 多对多 联系。 25. 关系R和关系S的 并 运算,由属于R或属于S的元组组成。关系R和关系S的交运算,由 属于R且属于S 的元组组成。 26. 数据 是长期存储在计算机内,有组织的,可共享的数据集合。 27. 设有两个关系R(A,B,C)和S(C,D,E),关系代数表达式,πA,E(σB=D(R∞S)),用SQL查询语句可以表达为:select A.E From R,S where R.C=S.C and B=D 。 28. CREATE CLUSTERED INDEX text ON student(sno)这个语句中student表的sno列上建立了一个 集簇 索引。 三、根据题意,写出实现以下查询的SQL语句(本大题共25分) 请将答案写在答题纸相应位置上。 29. 现有某校学生数据库,其中有如下三个基本表: 学生表:Student(SNo,SName,SSex,Sage,SDept) 各属性分别表示:学号,姓名,性别,年龄,系; 课程表:Course(CNo,CName,CPno,CCredit) 各属性分别表示:课程号,课程名,先修课程号,学分; 成绩表:SC(SNo,CNo,Grade) 各属性分别表示:学号,课程号,成绩。 表的结构如图表示: 用SQL语言实现以下各小题: (1).在Student表中,查询年龄在18到21岁学生信息(包含18岁和21岁)。(3分) Select *from student where sage bewtten 18and21 (2).在Student表中,查询学生的信息,按照年龄从大到小排序。(3分) Select*from student where sage order by desc; (3).修改Course表中的数据,凡是学分小于等于2分的课程,将其学分修改为3分(3分) Update course set ccridit=3 where ccridit<=2 (4).在Student表中,查询姓刘的学生的学号和姓名。(4分) Select sno,sname from student where sname like ‘刘%’ (5).从Stuendt表中删除姓名为张三的学生的信息。(3分) Detele SNo,SName,SSex,Sage,SDept from student where sname=’张三’ (6).在Student表和SC表中,查询所有学生的姓名、课程号和成绩(使用连接查询)。(4分) Select * from sc where student.sno=sc.cno (7).在SC表的基础上建立一个视图MIN_VIEW,用以实现查询每门课程的最低分。(5分) 四、计算题(本大题共2小题,共15分) 30. 请将答案写在答题纸相应的位置上。 已知关系模式R(A,B,C,D),F={B->D,D->B,AB->C} (1).求R的候选码;(4分) (2).判断R最高属于第几范式。(4分) 31. 某个医院管理系统中有两个实体:病人、医生。 其中“病人“的属性有:病人编号、病人姓名、性别、出生年月。 “医生“的属性有:医生编号、医生姓名、职称、科室。 一个病人可以找多个医生看病,一个医生可以给多个病人看病。 病人每次看病,医生会给出诊断结果。 (1).根据上述语义设计E-R模型,画出E-R图。(4分) (2).将E-R模型转换成关系数据模型,并指出每个关系的主键和外键(如果存在)。(3分)