2000年10月全国计算机通信工程本科数据结构试卷

数据结构与数据库试题
课程代码：7401

第一部分  选择题（共30分）

一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1、对线性表进行折半查找最方便的存储结构是（）
  A、顺序表     B、有序的顺序表     C、链表      D、有序的链表

2、计算递归函数如不用递归过程通常借助的数据结构是（）
  A、线性表    B、双向队列    C、树     D、栈

3、若串S='goodstudents',其子串的数目是（）
  A、12       B、13      C、78      D、79

4、广义表运算式TAIL[((a,b),(c,d))]结果为（）
  A、c,d      B、(c,d)     C、((c,d))    D、d,c

5、直接存取文件的组织方法是（）
  A、HASH法   B、二分法     C、VSAM法     D、ISAM法

6、深度为5的二叉树其结点数最多为（）
  A、16       B、30        C、31      D、32

7、如果T2是由有序树T转换来的二叉树，则T中结点的后序排列是T2结点的（）
  A、先序排列    B、中序排列    C、后序排列    D、层序排列

8、n个结点的线索二叉树中线索的数目为（）
  A、(n-1)个   B、n个     C、（n+1）个   D、(n+2)个

9、数据库系统的体系结构按照ANSI/SPARC报告可划分为（）
  A、外模式、概念模式、内模式
  B、外模型、概念模型、内模型
  C、模式、模型、视图
  D、关系模型、网状模型、层次模型

10、在数据库技术中，独立于计算机系统的模型是（）
  A、E-R模型
  B、层次模型
  C、关系模型
  D、面向对象的模型

11、关系代数的五个基本操作可直接转换成元组关系演算表达式，它们是：并、差、投影，选择和（）
  A、交     B、笛卡尔积    C、自然连接    D、除法

12、若关系模式R（U，F）属于3NF，则（）
  A、一定属于BCNF    B、消除了插入的删除异常
  C、仍存在一定的插入和删除异常    D、属于BCNF且消除了插入和删除异常

13、对象一般由三个部分组成：一组变量、一线方法和（）
  A、一组属性    B、一组函数    C、一组消息    D、一组实例

14、SQL语言具有的功能是（）
  A、关系规范化，数据操纵，数据控制
  B、数据定义，数据操纵，数据控制
  C、数据定义，关系规范化，数据控制
  D、数据定义，关系规范化，数据操纵

15、为了保证数据的完整性，事务必须具有原子性、一致性，隔离性和（）
  A、可串行性     B、并行性     C、完整性    D、持久性

第二部分  非选择题 （共70分）

二、填空题（本大题共10小题，每小题2分，共20分）不写解答过程，将正确的答案写在每小题的空格内。错填呀不填均无分。

16、算法的时间复杂度和()合称为算法的复杂度。

17、设二维数组A[-2..10,-1..20]按行优先顺序存储，每个元素占4个存储单元，A[-2,-1]的存储地址是1000,则A[5,6]的存储地址是()。

18、图G有n个顶点和e条边，以邻接表形式存储，进行深度优先搜索的时间复杂度为（）。

19、在哈希查找中，冲突是指（）。

20、用索引的方法组织文件时，通常是在文件本身（主文件）之外另外建立一张表，指明逻辑记录和物理记录之间的对应关系。这张表叫做（）。

21、当数据库系统的概念模式改变时（）要作相应的改变，以保证外模式保不变。

22、函数依赖X→Y能由Armstrong推理规则导出的充分必要条件是()。

23、嵌入式SQL需要用（）把集合操作转换成单记录处理方式。

24、在SQL中表达完整性约束的规则有多种形式，其主要约束有（）。

25、客户/服务器体系结构的关键在于（ ）。

三、解答题(本大题共6小题,每小题5分,共30分)

26、设一数列为1,2,3,4,5,6,通过栈操作,要得到顺序为3,2,5,6,4,1和1,5,4,6,2,3的输出序列是否可能,请阐述理由。

27、对于n个顶点的无向图，采用邻接矩阵表示，回答下列问题：
（1）图中有多少条边？
（2）任意两个顶点i和j是否有边连接的条件是什么？

28、请解释什么叫堆(heap)。试说明通常使用一维数组作为堆的存储结构的原因。

29、试述数据库阶段数据管理的特点。

30、试述最小函数依赖集的含义。

31、试说明数据为的并发操作通常会带来哪三类问题。

四、应用题（本大题共4小题，每小题5分，共20分）

32、设有序列30,18,3,61,14,49，请构成一棵二叉排序树，并求其查找成功时的平均查找长度。

33、设某二叉树以二叉链表为存储结构，请写出求其高度的递归算法。

34、设某单位销售产品所需管理的信息有：订单号、客户号、客户名、客户地址、产品号、产品名、产品价格、订购数量、定购日期。一个客户可以有多个订单，一个订单可以订多种产品。
（1）请给出销售信息的E-R模型；
（2）将E-R模型转换成关系模型。

35、设学生选择课数据库中有S、C和SC三个关系模式如下，请分别用SQL语言和关系代数完成下列操作。
检索选修了课程名为DB的学生姓名和所在班级。
S（SNO，SNAME，AGE，CLASS）
C（CNO，CNAME）
SC（SNO，CNO，GRADE）
其中：S是学生关系，SNO：学号，SMAME：姓名，AGE：年龄，CLASS：班级；
     C是课程关系，CNO：课程号，CNAME：课程名；
     SC是学生选课关系，SNO：学生号，CNO：课程号，GRADE：成绩。