2002自考数据结构与数据库试题.doc

浙江省2002年1月高等教育自学考试数据结构与数据库试题课程代码：07401一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题2分，共26分)1设函数f(n)=n2+5000nlgn,则它的渐进时间复杂度为( )。 A.O(1) B.O(n) C.O(nlgn) D.O(n2)2.设用一维数组A1.n来表示一个栈，An为栈底。用整型变量T指示当前栈顶位置，A为栈顶元素。从栈中抛出(POP)一个元素时，T的值( )。 A.加1 B.减1 C.不变 D.清03.一个串A=“the length of”，则strlen(A)的结果为( )。 A.11 B.13 C.14 D.34.广义表A(b,(c,d,(e,f,g)的长度为( )。 A.1 B.2 C.3 D.65.深度为5的二叉树其结点数最多为( )。 A.16 B.30 C.31 D.326.一个无向连通图的生成树是含有该连通图的全部顶点的( )。 A.极小连通子图 B.极小子图 C.极大连通子图 D.极大子图7.若待排序列已基本有序，要使它们完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是( )。 A.归并排序 B.直接插入排序 C.直接选择排序 D.快速排序8.一个关系中的候选键( )。 A.必须一个 B.可多个 C.必须多个 D.至少3个9.SQL语言具有的功能是( )。 A.关系规范化，数据操纵，数据控制 B.数据定义，数据操纵，数据控制 C.数据定义，关系规范化，数据控制 D.数据定义，数据操纵，关系规范化10.下列说法中不正确的是( )。 A.任何一个包含两个属性的关系模式一定满足3NF B.任何一个包含两个属性的关系模式一定满足BCNF C.任何一个包含三个属性的关系模式一定满足3NF D.任何一个关系模式都一定有关键码11.假如采用关系数据库系统来实现应用，在数据库设计的( )阶段，需将E-R模型转换为关系数据模型。 A.概念设计 B.物理设计 C.逻辑设计 D.运行阶段12.实体完整性要求主属性不能取空值，这一点通常是通过( )。 A.定义外键来保证 B.定义主键来保证 C.用户定义的完整性来保证 D.关系系统自动保证13.对象一般由三个部分组成：一组变量、一组方法和( )。 A.一组属性 B.一组函数 C.一组消息 D.一组实例二、填空题(每小题2分，共20分)1.假设顺序表中每个结点占用c个存储单元，其中第i个结点的存储地址是si，那么第j(ji)个结点的存储地址sj可以用sj=si+_来计算。2.链队列是链式存储的队列，它的删除操作限制在_处进行。3.一个5的下三角矩阵A中的元素aij(ij,1i5,1j5)按行存于一个一维数组B1.15中，对其中的任一元素aij,若在B中的位置为k，则k=_。4.线索化是对二叉树_使其变成线索二叉树的过程，其中线索是指向前驱或后继而非指向孩子的指针。5.一个无向图的邻接表表示中，若表结点的个数是m，则无向图中边的条数是_条。6.一个班级有多个学生，一个学生只能属于一个班级，班级与学生之间属于_联系。(填1：M，M：N，M：1或1：1)7.在SQL中，外模式一级数据结构的基本单位是_。8.设R是一关系模式，分解成关系模式=R1,R2,Rk,F是R上的一个函数依赖集。如果对R中满足F的每一个关系r都有：r=R1(r)Rk(r)，则称这个分解相对于F是_。即r为它在Ri上的投影的自然联接。9.为了使全局应用的用户能集中精力于数据库应用的逻辑上，而不必关心数据的物理位置的分配，分布式数据库系统提供了各种透明性，主要包括位置透明性和_。10.在_数据模型基础上，提供元组、数组、集合一类更为丰富的数据类型以及处理新的数据类型操作的能力，这样形成的数据模型，称为“对象关系数据模型”。三、简答题(每小题5分，共30分)1.假设二叉树包含的结点数据为1，3，7，2，12。画出一棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。2.为什么在单循环链表中设置尾指针比设置头指针更好?3.命题“在二叉排序树中添加新结点时，新结点总是叶子”对不对，为什么?4.已知关系模式R和S，计算24(RS) R： S： A B C D E 3 6 7 7 3 9 11 13 13 6 14 18 205.教学数据库中有基本表S、SC、C，分别是学生、选课和课程表，其关系模式如下： C(C#，CNAME，TEACHER)，其中属性含义分别为课程号，课程名，教师； SC(S#，C#，GRADE)，其中属性含义分别为学号，课程号，成绩； S(S#，SNAME，SEX)，其中属性含义分别为学号，姓名。 试用SQL更新语句进行以下操作： (1)当DB课的成绩低于该门课程平均成绩时，提高3%。 (2)创建视图“EXCL”，可在其中直接得到学生的学号、姓名、课程名、成绩等信息。6.试述数据库体系结构中两级映象的概念及其作用。四、应用题( 每小题6分，共24分)1.初始输入序列的键值如下： 62 63 61 13 84 06 05 58 38 09 试采用二路归并排序法进行从小到大的排序，写出该序列在每遍扫描时的合并过程。2.设将a,b,c,d依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序入其中，Push(x)表示x进栈，Pop()表示出栈，请分析a,b,c,d的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。3.现有某个应用，涉及两个实体集，相关的属性为： 实体集R(R#，R1，R2，R3)，实体集S(S#，S1)，其中R#和S#分别表示相应实体集的码；从实体集R到S是一对多(1：M)的联系，联系具有两个属性T1和T2。 试画出相应的E-R图，并将E-R图转换成等价的关系模式。4.现有如下关系： 学生(学号，姓名，性别，专业，出生日期) 教师(教师编号，姓名，所在部门，职称) 课程(课程编号，课程名称，学分) 授课(教师编号，学号，课程编号，选用教材，成绩) 请分别用关系代数表达式和SQL语言完成下列操作： 查找教师“李红”所教过的学生中成绩为85分以上(包括85分)的学生学号，姓名和专业。浙江省2002年1月高等教育自学考试数据结构与数据库试题参考答案课程代码：07401一、单项选择题(每小题2分，共26分) 1.D 2.A 3.B 4.B 5.C 6.A 7.B 8.B 9.B 10.C 11.C 12.B 13.C二、填空题(每小题2分，共20分) 1.(j-1)*c 2.表头 3.i(i-1)/2+j 4.以某种次序遍历 5.m/2 6.1：M 7.视图 8.无损联接分解 9.复制透明性 10.关系三、简答题(每小题5分，共30分)1.(注：答案不唯一，给出一个正确的答案即可。上边列举出两个，只要满足：“12为根，3和7在中间一层，1和2在最底层并且同是中层靠左边这个结点(3或7)的儿子”就可以了) 2.很多实际问题中，表的操作常常是在表的表尾位置上进行，用尾指针表示单循环链表，查找开始结点和终端结点都很方便，查找时间都是O(1)。 3.对。二叉排序树的定义以及它的插入算法我们知道，要插入一个新结点，总要一直搜索到树的叶结点处，才确定了插入的位置，所以插入的结点总是叶子。一个特殊情况是原树为空，这种情况下我们依然可以认为，后来得到的这个只有一个结点的树的根结点也是叶子。 4. A B C D E 3 6 7 7 3 3 6 7 13 6 9 11 13 13 6 5.(1)UPDATE SC SET GRADE=1.03GRADE WHERE C#=DB AND GRADE85 AND 教师.姓名=李红 或者SELECT 学号