18．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是_________。

    typedef struct{

    DataType data[100]；

         int top；

    }SeqStack；

    DataType f18(SeqStack*S)

    {    if(StackEmpty(S))

    Error(”Stack is empty”)；

    return S->data[S->top]；

    }

19．在串匹配中，一般将主串称为目标串，将子串称为_________。

20．已知广义表C=(a(b，c)，d)，则：tail(head(tail(C)))= _________。

21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为_________。

22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是_________。

23．对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是_________。

24．高度为3的3阶B-树最少的关键字总数是_________。

25．VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是_________。

三、解答题(本大题共4小题，每小题5分，共20分)

26．假设二叉树的RNL遍历算法定义如下：

  若二叉树非空，则依次执行如下操作：

    (1)遍历右子树；

  (2)访问根节点；

  (3)遍历左子树。

已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。

27．已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表示如下所示。

请回答下列问题：

(1)请画出对应的图G。

(2)画出图G的邻接表存储结构。

28．已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请给出初始建堆后的序列。

29．已知一棵二叉排序树如图所示。

    请回答下列问题：

    (1)画出插入元素23后的树结构；

(2)请画出在原图中删除元素57后的树结构。

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

30．已知下列程序，Ls指向带头结点的单链表。

 Typedefstruct node  {

         DataType  data;

      struct node * next;

 } * LinkList;

 void f30( LinkList Ls )

{   LinkList p, q;

      q = Ls->next;

      if ( q && q->next ) {

           Ls->next = q->next;

           p=q

           while ( p->next )

                p = p->next;

           p->next = q;

           q->next = NULL;

}

}

请回答下列问题：

(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。

(2)请简述算法的功能。

31．已知字符串处理函数f31程序如下。

    int f31(char*strl，char*str2)

    {  while(*strl==*str2&&(*strl!=’＼0’)){

    strl++；

    str2++；

  }

    return(*strl-*str2 ? l∶0)；

    }

    请回答下列问题：

    (1)若调用语句是f31(”abcde”，”abcdf’)，则函数的返回值是什么?若调用语句是    f31(”abcde”，”abcde”)，则函数的返回值是什么?

    (2)简述该函数的功能。

32．数组A[]中存储有n个整数，请阅读下列程序。

    void f32(intA[]，int n)

    {  inti，j，k，x；

    k=n-l；

        while(k>0){

    i=k；  k=0；

    for(j=O；j<i；j++)

    if(A[j]>A[j+1]){

    x=A[j]；

    A[j]=A[j+l]；

  &n