全国2001年10月高等教育自学考试

数据结构试题参考答案

课程代码：02331

一、单项选择题（本大题共15小题，每小题2分，共30分）

         1．D      ２．Ｂ              ３．Ｃ            ４．Ｂ              ５．Ｄ                                ６．Ａ    ７．Ｃ    ８，Ｄ    ９，Ａ                   10．Ｃ                                                                             11．Ｄ    12．Ｃ    13．Ｄ    14．Ｃ    15．Ｂ

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

           16．存储（或存储结构）                               17.p－＞next－＞next                                  18．进栈和退栈                      19．12                                                                                                           20．a_4,8                                 21．384                                                                                                 22．abefcdg

           23．快速排序、堆排序、希尔排序

           24．２                                                            25.多关键字

三、解答题（本大题共4小题，每小题5分，共20分）

           26．

               图1               图2

       27．

       28．该图的图形为：                     

深度优先遍历序列为：abdce

广度优先遍历序列为：abedc

29．（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１；

   （２）平均查找长度

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30．  ①S1=S1－>next

      ②s2=s2－>next

      ③s2(或s2!=NULL或s2&&!s1)

      ④s1(或s1!=NULL或s1&&!s2)

      ⑤return 0

31.（1）查询链表的尾结点

   （2）将第一个结点链接到链表的尾部，作为新的尾结点

   （3）返回的线性表为（a₂,a₃,…,a_n,a₁）

32. ①(i＋1)%2(或1－i)

    ②Q－>rear[i]

    ③(Q－>rear[i]＋)%Maxsize

  （2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。

五、算法设计题（本题共10分）

   34．（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。

      （2）int f(int b[],int n)      或   int f(int b[],int n)

              {                       {

   int p,q；                 int p,q；

   p=arrange(b,0,n－1,0)；    p=arrange(b,0,n－1,1)；

   q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)；

   return q－p；             return p－q；

   }                         }