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

1.B  2.D  3.C  4.C  5.A
6.C  7.B  8.C  9.A  10.A
11.B  12.C  13.C  14.B  15.D

二、填空题（本大题共10小题，每小题2分，共20分）

16.空音复杂度
17.100+(7×22+7)×4=1644 (可直接填写1644)
18.O(n+e)
19.不同关键字记录映射到同一地址.
20.索引表
21.模式/外模式的映象
22.
23.游标机制
24.主键约束,外健约束,属性值约束
25.功能分布(或功能划分)

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

26、(1)3,2,5,6,4,1是可能的,但1,5,4,6,2,3不可能.(2分)
(2)因为5在4,2,3之前出栈,那么5出栈时,栈内状态为:5,4,3,2。
  根据先进后出原则,其次序只能是5,4,3,2,不可能出现5,4,2,3,想出2时,2却被3压在下面,2不能比3先出栈,所以不可能出现1,5,4,6,2,3这种序列.(3分)

27、（1）图中边数等于邻接矩阵的非零元不比个数之和的一半。 (2分)
    （2）i，j有边相连的条件是A[i,j]<>0,且A[j<i]<>0. (3分)

28、堆定义为:n个元素的序列(K1K2,…,Kn)当且仅当

用一维数组存储,可与完全二叉树相对应,很容易确定二叉树中任一结点i的左、右儿子位置，而不需要使用指定域空间，因此常用一维数组存储堆阵。（3分）

29、数据库阶段的数据管理方式具有以下特点：（共5分，每个特点1分）
（1）采用复杂的数据模型表示数据结构。
（2）有较高的数据独立性。
（3）为用户提供了方便的用户接口，用户可以使用查询语言或程序方式操纵数据库。
（4）系统提供了数据库恢复，并发控制，完整性约束和数据安全性的数据控制功能。
（5）对数据的操作可以记录为单位，也可以以数据项为单位，增加了系统灵活性。

30、如果函数依赖集F满足：
  （1）F中每个函数依赖的右部都是单属性；（1分）
  （2）F中的任一函数依赖X→A,其F-{X→A}与F不等价;(2分)
  （3）F中的任一函数依赖X→A,Z为X的子集,(F-{X→A})∪{Z→A}与F不等价。则称F为最小函数依赖集。(2分)

31、(1)丢失更新问题(2分)
两个事务T1和T2读入同一数据并修改,T2提交的结果破坏了T1提交的结果,T1的修改被丢失;
(2)数据不一致(2分)
事务T1读某一数据,事务T2读取并修改了同一数据,若T1再读此数据,得到了不同结果;
(3)读“脏数据”(1分)
事务T1修改了某一数据,事务T2读取同一数据,而T1由于某种原因被撤消,则T2读到的数据为"脏'数据。

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

32、二叉排序树:  (3分)

平均查找长度=1/6 (1+2×2+3×2+4)  (2分)
          =2.5  

33、void BTdepth (BinTree BT,int h)
  { int hr, h1;
    if(BT==null)  h=0;    (1分)
    else
    { BTdepth (BT→lchild,h1);      2分
      BTdepth (BT→rchild,hr);
      if(h1>=hr)
         h=h1+1;                    2分
      else
         h=hr+1;
     }
  }

34、E-R模型(3分)

关系模型:(2分)
客户(客户号,客户名,客户地址)
产品(产品号,产品名,产品价格)
订单(订单号,产品号,订购日期)
订购(订单号,产品号,订购数量)

35、SQL语言：（3分）
SELECT SNAME, CLASS FROM S
        WHERE SNO IN （SELECT SNO FROM SC，C
            WHERE SC.SNO=C.CNO AND CNAME='DB'）
关系代数:(2分)

(该题有多种答案,仅供参考)