1、自考人网校专本套读 2018 春季招生进行中，零学历 2.5 年拿本科，支持学费分期，0 利率 0 手续费！应用市场搜索“自考人”下载自考 APP 神器，随时随地无忧备考，自测练习强化巩固，考试重点轻松装进口袋！浙江省 2001 年 10 月数据结构与数据库试题课程代码：07401一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题 2 分，共 26 分)1.设函数 f(n)=25n3+5000n2，则它的渐进时间复杂度为 ( )A. O(1) B. O(n) C. O(n2) D. O(n3)2.在顺序存储的线性表(a 1,a2,an)中，删
2、除一个结点所需移动结点的平均次数为( )A. n B. n/2 C. (n1)/2 D. (n+1)/23.设用一维数组 A1.n来表示一个栈， An为栈底。用整型变量 T 指示当前栈顶位置，AT为栈顶元素。往栈中推入(PUSH) 一个元素时， T 的值( )A.加 1 B.减 1 C.不变 D.清 04.对称矩阵的元素满足( )A. aij=aji(0 i,jn1) B. aij=aji，a ii=0(0i,jn1)C. aij=aji，a ii=1(0i,j n1) D. aij=-aji(0i,j n1)5.设结点 x 和结点 y 是二叉树 T 中的任意两个结点，若在前序排列中 x 在
3、y 之前，而在后序排列中 x 在 y 之后，则 x 和 y 的关系是( )A. x 是 y 的左兄弟 B. x 是 y 的右兄弟C. x 是 y 的祖先 D. x 是 y 的后代6.具有 n 个顶点的有向图，其邻接矩阵为 A，则第 i 个顶点的出度为( )A. B.Aijj(,)1 jjn,)1C. D.ijjni(,)1 jijni(,)1自考人网校专本套读 2018 春季招生进行中，零学历 2.5 年拿本科，支持学费分期，0 利率 0 手续费！应用市场搜索“自考人”下载自考 APP 神器，随时随地无忧备考，自测练习强化巩固，考试重点轻松装进口袋！7.一组记录的关键字经一趟二路归并排序后得到
4、含有 5 个长度为 2 的有序表如下：25，48 ， 16，35 ，79，82 ， 23，40 ， 36，72 ，在此基础上按二路归并排序方法再对该序列进行一趟归并后的结果为( )A. 16，25，35，48，23， 40，79，82，36，72B. 16，25，35，48，23，40 ，79，82，72，36C.16，25，48，35，79，82 ，23，36，40，72D.16，25，35，48，79，23 ，36，40，72，828.关系模型中，表示实体间 nm 联系是通过增加一个( )实现。A.关系 B.属性C.关系或一个属性 D.关系和一个属性9.商店可经营多种商品，一种商品可由多家
5、商店经营，商店和商品之间属于( )联系。A. M1 B. MN C. 1M D. 1110.设有以下关系：合同(合同号，用户号，用户名，用户地址) ，合同号是唯一的，则这个关系的范式等级是( )A. 1NF B. 2NF C. 3NF D. BCNF11.数据库逻辑设计阶段主要输出信息不包括( )A.DBMS 可处理的模式 B.子模式C.应用程序设计指南 D.独立于 DBMS 的概念模式12.数据库的并发操作有可能带来的三个问题中包括( )A.数据独立性降低 B.无法读出数据C.权限控制 D.丢失更新13.从功能上看，DDBMS(分布式数据库管理系统)不包括( )A.查询子系统 B.完整性子系
6、统C.调度子系统 D.安全性子系统二、填空题(每空 2 分，共 20 分)1.顺序表的存储空间是_( 填“静态”或“动态”) 分配的，在程序执行之前必须明确规定它的存储规模。2.栈的修改是按照_的原则进行的。3.已知有三个串：A=“This is a test.” ，B=“This ”,C=“is”，B 在 A 中的位置是 1，则 C 在 A 中的位置是_。4.广义表 B=(x,(a,b),y)，tail(B)=_。5.用索引的方法组织文件时，通常是在文件本身(主文件)之外另外建立一张表，指明逻辑记录和物理记录之间的对应关系，这张表叫做_。6.在嵌入式 SQL 中用游标机制的目的是_。7.数据
7、按外模式的描述提供给用户，按内模式的描述存储在磁盘中，而_提供了连接这两级的相对稳定的中间观点，并使得两级的任何一级的改变都不受另一级的牵制。8.关系模型是由若干个关系模式组成的集合，其主要特征是用二维表格结构表达实体集，用_表示实体间联系。9.分布式数据库系统分层的体系结构有三个显著的特征：数据分布独立性、数据冗余的显式控制以及_。10.继承性是数据间的泛化/细化联系，可分为单继承性和_。三、简答题(每小题 5 分，共 30 分)1.设有两个算法在同一机器上运行，其执行时间分别为 10n2 和 2n，要使前者快于后者，问题规模 n 至少要多大?2.设长度为 n 的链队列用单循环链表表示，若只
8、设尾指针，则入队和出队操作的时间复杂度分别是多大?3.解释串匹配中“有效位移”和“无效位移”两个术语。4.已知关系模式 R 和 S，计算 24 (RS)R: S:A B C D E4 5 6 6 47 9 10 10 513 15 16自考人网校专本套读 2018 春季招生进行中，零学历 2.5 年拿本科，支持学费分期，0 利率 0 手续费！应用市场搜索“自考人”下载自考 APP 神器，随时随地无忧备考，自测练习强化巩固，考试重点轻松装进口袋！5.试述死锁的概念及消除死锁的方法。6.已知顾客基本表的关系模式为(顾客号，姓名，地址，电话) 。(1)请用 SQL 更新语句增加一名新顾客，其值为(
9、330102，王伟，北京，0105128934)。(2)请用 SQL 更新语句将 (1)中新增的顾客姓名改为 王 南 。四、应用题(每小题 6 分，共 24 分)1.试写出二分查找的递归算法 int BinSearch(Seqlist R,int low,int high,KeyType k)。2.看懂下列两段程序，完成关键字序列 R=52,23,34,101,33,26,15,98的建立大根堆的过程。已给出初始的完全二叉树，要求画出每次调用 Heapify()后的完全二叉树。void Heapify(SeqList R,int low,int high) int large;RecType
10、temp=Rlow;for(large=2*low;large=Rlarge.key)break;Rlow=Rlarge;Low=large;Rlow=temp;void BuildHeap(SeqList R) int i;for(i=n/2;i0;i-)Heapify(R,i,n);3.设某学校教学所需管理的信息有：课程号，课程名，学号，学生姓名，教师号，教师名，选用教材，成绩。一个教师可以讲授多门课程，特定的一门课程规定只能由一位教师讲授；一名学生可以选修多门课程。(1)请给出教学信息的 E-R 模型；(2)将 E-R 模型转换成等效的关系模式。4.设教学数据库中有三个关系：学生关系 S
11、(S，SNAME，AGE，SEX)学习关系 SC(S，C，GRADE)课程关系 C(C，CNAME，TEACHER)其中：S 关系中，S ：学号，SNAME：姓名，AGE ：年龄，SEX：性别；C 关系中，C：课程号，CNAME ：课程名，TEACHER：教师；SC 关系中，S：学号，C：课程号，GRADE：成绩。自考人网校专本套读 2018 春季招生进行中，零学历 2.5 年拿本科，支持学费分期，0 利率 0 手续费！应用市场搜索“自考人”下载自考 APP 神器，随时随地无忧备考，自测练习强化巩固，考试重点轻松装进口袋！请分别用 SQL 语言和关系代数表达式完成下列操作：检索所学课程包含学生 S6 所学课程的学生学号。
