一. 选择题(每题选择一个答案, 将序号填入下划线处,每题2分,共10分)
1. 假定初始序列是递增的,并且按递增序排列,则(  )排序方法花时间最少.
     A.快速    B. shell    C.直接插入     D.冒泡
2. 二维数组 a[0..8, 1..10]按行存放时元素 a[ 8,5 ]的起始地址与按列存放时元素(  )的起始地址相同.
     A. a [8,5]    B. a [3,10]      C. A[5,8]     D. A[0,9]
3. 有一棵平衡二叉树,根结点为A,A的右孩子为B,B的左孩为叶结点C,当A,B二结点的平衡因子分别为(   )时,在结点C下, 插入一个新结点后得到的新树是不平衡的.
     A. 0,0       B. 1,0         C. –1,0        D. 0,1
4.在循环链表中设立一个头结点的理由是(    ).
     A.便于找到链表的首结点         B.可以用头结点记录链表长度
     C.可以使得作插入,删去时不必顾及插入的或删去的结点是否链表的首结点.
     D.可以把首结点与尾结点公开
5.非空的广义表可与有根有序的有向图对应,如果一个有根的有向图中含有回路,那么它对应的广义表是(   )
     A.线性表      B.纯表    C.再入表     D.递归表
二.填空题(每题2分,共10分)
1. 有20个元素的有序表按二分法查找,假定查找每个元素的概率是相等的,则查找成功的平均比较次数为________次.
2. 链接栈的结点有二个域: info, link ,栈顶指针为st, 下列程序段可以把元素x压入栈内:
     new(p); p?.inf=x; ______;
3. 一个好的散列函数的标准是________________.
4. 一个循环队列用数组Q[0..100]存贮其元素, 已知队头,队尾指针分别为80与50, 则当前队列中有_______个元素.
5. 用200个不同的数来构造二叉排序树, 其高度不会超过_______,但也不会少于_______(假定空二叉树的高度为0).
三.算法应用题(每题6分, 共30分)
1. 对下图表示的树林, (1)写出它的后根序序列.(2)画出与它对应的二叉树.
           A        D         G
  
           B       E          H
        
          C       F          I
2. 对序列(26,36,41,38,44,15,68,12,6,51,25)散列存贮于数组A[0..14]中,散列函数为H(R)=Rmod13, 用线性探测法解决冲突,请画出散列表的状况.
3.设有关键码序列: 51(1), 73, 47,95,49,51(2).试写出快速排序(从小到大)与堆排序(从大到小)的最终结果.
4.画出下图的邻接表(要求:出边表中的结点按序号由小到大排列),然后使用该邻接表手工执行深度优先算法(从结点6开始),请写出你得到的遍历序列.
                     1
               2        6
      3               5
             4
5.对下图用用Prim算法从结点6开始构造最小生成树,(1)请用图表示构造的过程.(2)如果从其他结点开始,有没有可能构造出不相同的最小生成树?
(图略)
四.算法设计题(共50分)
1. 求带权有向图中每对结点之间的最短路径的Floyd算法如下:
   (1)(Path数组置初态)
       for I:= 1 to n do
         for j:= 1 to n do
          if adj[I,j]<? then path[I,j]:=(1)
                    else path[I,j]:=(2);
       (2)(求最短路径)
          for k:= 1 to n do
            for I:= 1 to n do
              for j:= 1 to n do
               if adj[I,j]>adj[I,k]+adj[k,j] then
                  begin adj[I,j]:=(3);path[I,j]:=(4) end
请你解答如下问题(1)完成上述算法填空. (2)矩阵adj 的初值是什么?算法结束时,adj[I,j] 和path[I,j]的值表示什么意义?(14分)
2. 写出按对放序线索化以t 为根指针的二叉树的非递归算法.假定用负指针表示线索,并且对栈的基本运算均可调用(12分)
3. 写一算法,重排实型数组R[1..n]中元素的顺序,使得所有负数均排在非负数之前.(要求:不排序,附加空间0(1))(10分)
4. 有一个带有头结点的循环双链表,表头指针为head,结点有四个域,data ,flreg ,llink ,rlink ,其中flreg记录结点数据的访问次数.假定链表的结点已按访问次数不增序排列.(1)画出此链表的结构示意图.(2)写一算法查找链表中是否有值为x的结点,如有,则让该结点的访问次数加1 ,并且要使链表仍保持不增序,如没有,则不作任何工作.(14分)