设图G如题28图所示题28图回答下列问题。

(1)图G是否是有向无环图?

(2)给出图G所有的拓扑排序序列。

已知带有头结点的单链表定义如下:

typedef struct node

{    char ch;

      struct node *next;

} ListNode;

typedef ListNode *LinkList;

请编写函数int f34( LinkList h, char string[]);根据输入的字符串,建立不含重复字符的链表

阅读程序,写出执行结果。

void f33(int a[], int n)

{    int i;

      for(i=(n-1)/2; i>=0; i--)

      Sift(a, i, n-1);

}

   void Sift( inta[], int i, int h)

 {    int j, temp *a[i];

      j=2*i+1;

     while(j<=h)

{  if((j

      j++;

      if( temp=>=a[j])

     break;

     a[i]=a[j];

      i=j;

       j=2*i+1;

}

 a[i]=temp;

}

int main()

{          int i, a[10]={10,20,5,23,25,62,21,1,32,39};

          f33(a,10);

          for(i=0; i<10; i++)

            printf(“%d,”,a[i]);

      printf(“\n”);

       return 0;

}

执行结果:

已知二叉树T如题32图所示。

阅读程序f32,写出执行f32(T)的输出结果。

typedef char DataType

typedef struct node

{      DataType data;        //data是数据域

struct node * lchild, * rchild;     //分别指向左右孩子

} BinTNode;

typedef BinTNode * BinTree;

void f32( BinTree bt)

{      if(bt!=NULL)

   {   f32(bt->rchild);

 printf(“%c”, bt->data);

 f32(bt->lchild);

 }

}

执行结果：

程序f31是将输入的m行n列的二维数组a变换为三元组表形式存储在数组b中。请在空白处填上适当内容将算法补充完整。

#define MAXSIZE 100

typedef int DataType;

typedef struct {

       int i, j;                 //1非零元素行列下标

      Data Type v;      //非零元素值

} TriTupleNode;

typedef struct {

     TriTupleNode data[MAXSIZE];         //存储三元组数组

     int m, n, t;             //m:矩阵的行,n:矩阵的列,t非零元素数量

} TSMatrix;

    void f31(TSMatrix *b, int*a, int m, int n)          

    //将m行n列的矩阵a变换为三元组表形式存储在b中

{     int i, j, k=0;

      for(i=0; i

       for(j=0; j

         {    b->data k].i=i;

                b->data k].j=j;

                b->data[k].v=____(1)____;

              ____(2)____;

          }

         b->m=m;

         b->n=n;

          b->t=____(3)____;

}

设图G如题28图所示题28图回答下列问题。

(1)图G是否是有向无环图?

(2)给出图G所有的拓扑排序序列。

设关键字序列为:53,15,72,52,48,67,63,23。已知散列表地址空间为0~11,散列函数为H(k)=kmod11,采用线性探查再散列法解决冲突。

(1)将所给关键字数据依次填入该散列表中;

(2)计算等概率下查找成功的平均查找长度。

已知队列的基本操作定义如下,请在空白处填写适当的语句,完成指定的功能。#define QueueSize 100

typedef struct {        //队列定义

       char data[QueueSize];

        int front, rear;

 } CirQueue;

 CirQueue Q;

void Init Queue( CirQueue *Q)     //队列初始化

{      Q->front=Q->rear=0;;

}

 int Queue Empty( CirQueue *Q)       //判队列是否空

{ return ____(1)____;

}

int Queue Full( CirQueue * Q)         //判队列是否满

{    return(Q->rear+ 1)% QueueSize==Q->front;

 }

 char EnQueue( CirQueue *Q, char c)      ///入队操作

{     if (QueueFulk(Q))

     return ‘\0’;        //^操作失败

    else

 {     Q->data[ Q->rear]=c;

      Q->rear=____(2)____;

    retum c;       //操作成功

 }

}

 char DeQueue(CirQueue *Q)       //出队列操作

{     char x;

    if( Queue Empty(Q))

    return ‘\n’;        //操作失败

    else

 {     x=Q->data[[Q->font];

    O->front=____(3)____;

   retum x;      //操作成功

   }

}

两个栈共享数组空间data[m](定义如下),它们的栈底分别设在数组的两端(初始化后topl=-1,top2=m).

typedef struct{

DataType data[m];

int top1, top2;

}SeqStack;回答下列问题。

(1)编写判断栈满的函数 int stackfull( SeqStack *s);

(2)编写进栈函数 void push( SeqStack *s, int si, DataType x);其中,si取值为0、1,分别表示栈底为0或m-1的栈。

已知二叉树T中含有元素A,B,C,D,E,F,G,H,T的前序遍历序列、中序遍历序列和后序遍历序列如下,其中符号____表示未知元素。试写出①到⑩所代表的正确元素值。

前序遍历序列 A B D ① E F G ②

中序遍历序列 ③ B A ④ C G F ⑤

后序遍历序列 ⑥ ⑦ ⑧ ⑨ H F C ⑩

对箱排序的改进和推广的排序算法是_________。