关于数据结构（C语言）的几个题

1.

随意画几个二叉树就知道了，这里空链域用ε表示，数一数结点个数与ε个数就知道是n+1了

2.

具体过程在图中给出。

3.

第一步将数据（假设为e）放入s的data中；

第二步s的后继指向q的后继节点；

第三步q的后继指向s

4.

查找72只需2步：

第一步：设立low、high与mid指针，将72与mid指向的值即48比较；

第二部：72比48大，low指向mid+1，重新算出mid，指向72，再与72比较，即查找成功。

最多比较次数参考严蔚敏《数据结构》第九章 查找 220页。

5.

例如图中这棵树，假设i=2，2i=4不大于n，2i+1=5大于n，所以2这个结点没有右子树。

6.

顺序栈的类型定义：

typedef struct{
    char *base;        //也可用ElemType，只要定义了就行
    char *top;
    int stacksize;
}SqStackTp;        //注意名字要和主函数里的统一

运行结果：

ABCDEFGHIJKLM

MLKJIHGFEDCBA

结果详解：

在这里将'A'到'A'+12='M'进栈同时输出

 for(ch=’A’;ch<=’A’+12;ch++)

  {  Push(&sq,ch);

printf(“%c”,ch);

   }

在这里将'A'到'M'出栈同时输出

while(!EmptyStack(sq))

{  Pop(&sq,&ch);

   printf(“&c”,ch);

}  printf(“\n”);

由于栈是后进先出，所以就有这样的结果

7.

void converse(int n,int d){
    SqStack S;        //新建一个栈
    InitStack(S);     //初始化栈
    int k,e;
    while(n>0){
        k=n%d;
        push(S,k);
        n=n/d;
    }//将余数进栈
    while(S.top!=S.base){
        pop(S,e);
        printf("%1d",e);
    }//输出结果
}

8.

先序遍历：ABCDEF

中序遍历：BCDAFE

后序遍历：DCBFEA

1）B 2） A 3） 没有选项 4） 7 5）左孩子 右孩子
6）
ABCDEFGHIJKL
LKJIHGFEDCBA
7）

8） 先序： ABCDEF 中：CDBAFE 后 ：DCBFEA