for (i = n;i>0; i--)

　　　for (j = i+1; j<n; j++)

　　　　product *=j;

17．已知指针p指向单链表中某个结点，则语句p -> next =p -> next -> next的作用是________________。

18．假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为________________，不可能得到的出栈序列为________________。

19．若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为________________。

20．右图表示的广义表为________________。

21．若一棵满三叉树中含有121个结点，则该

树的深度为________________。

22．若以邻接矩阵表示有向图，则邻接矩阵上

　第i行中非零元素的个数即为顶点v_i的________________。

23．若希望只进行8趟排序便能在4800个元素中找出其中值最小的8个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用________________排序方法。

24．在含20个关键字的3阶B树（2－3树）上查找一个关键字，至多需要访问___________次外存。

25．文件上的两类主要操作为________________和________________。

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

26．设栈S1的入栈序列为1 2 3 4（每个数字为13个元素），则不可能得到出栈序列3142。但可通过增设栈S2来实现。例如，按下图中的箭头指示，依次经过栈S1和S2，便可得到序列3 1 4 2。

如果用H1和H2分别表示栈S1和S2的进栈操作，用P1和P2分别表示两个栈的出栈操作，则得到3 1 4 2的一个操作步骤为

　　H1，H1，H1，P1，H2，P2，P1，H2，P1，H2，P2，H1，P1，H2，P2，P2

　　　请仿照上例写出利用两个栈从1 2 3 4得到4 1 3 2的操作步骤。

27．已知树如右图所示，

　（1）写出该树的后序序列；

    （2）画出由该树转换得到的二叉树。

28．为关键字（17，33，31，40，48）构造一个长度为7的散列表，设散列函数为h(key)=key%7,用开放定址法解决冲突的探查序列是

　hi = (h(key) + i(key%5+1))%7      0≤i≤6

（1）画出构造所得的散列表；

（2）求出在等概率情况下查找成功时的平均查找长度。

29．已知R［1..8］中的元素依次为（12，5，9，20，6，31，24，27），写出按算法MergeSortDC　对R进行自顶向下的二路归并排序过程中，前5次调用函数Merge(R, low, mid, high)时参数 low, mid 和high的值。

 void MergeSortDC (int R[], int low, int mid, int high )

 {

        int mid;

        if (low<high)

        {

               mid = (low +high)/2;

               MergeSortDC (R, low, mid);

              MergeSortDC (R, mid+1, high);

               Merge (R, low, mid, high);

        }

 } // MergeSortDC

　（1）第一次调用时的参数值；

　（2）第二次调用时的参数值；

    （3）第三次调用时的参数值；

（4）第四次调用时的参数值；

（5）第五次调用时的参数值；

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

30．下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。

　void union (LinkList La, LinkList Lb)

    {

        //本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中

        LinkList pre = La, q;

        LinkList pa = La -> next;

        LinkList pb = Lb -> next;

        free (Lb);

        while (pa && pd)

        {

               if (pa -> data <pb -> data)

               {  pre = pa; pa = pa -> next;}