Question

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

1．在含有n个结点的二叉树二叉链表中有____个空链域。
A. n B. n+1 C. n-1 D.（n+1）/2
2．在双向链表存储结构中，删除p所指的结点时须修改指针______.
A. P—＞next—＞prior=P—＞prior；P—＞prior—＞next=P—＞next；
B. P—＞next=P—＞next—＞next；P—＞next—＞prior =P；
C. P—＞prior—＞next =P；P—＞prior=P—＞prior —＞prior；
P—＞prior =P—＞next—＞next；P—＞next= P—＞prior—＞prior；
3. 在一个不带有头结点的非空单链表中，其结点形式为 (data,next)，若要在指针q所指结点之后插入一个s指向的结点，则需执行下列语句序列：____。
4. 在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为 2 。查找关键字最多比较的次数________。
5. 若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当2i>n,则结点i无___；若2i+1>n，则结点i无____。
6. 完善下列程序中栈的类型定义部分；写出程序的运行结果。
# define sqstack_maxsize 40
(顺序栈的类型定义)
main()
{ SqStackTp sq;
int i;
char ch;
InitStack(&sq);
for(ch=’A’;ch<=’A’+12;ch++)
{ Push(&sq,ch);
printf(“%c”,ch);
}
printf(“\n”);
while(!EmptyStack(sq))
{ Pop(&sq,&ch);
printf(“&c”,ch);
} printf(“\n”);
}
7. 试给出基于以下算法原理的数制转换类C语言程序设计：
N = (N div d)×d + N mod d其中，div是整除运算； mod是取余运算
8. 分别给出下图所示二叉树的先根、中根和后根序列。

sq->top++,sq->data[sq->top]

本人一点都不会，谢谢大家~~大题希望能给出详细过程~~~ （目前只有5分，一会我会去赚分，再追加！！）
第八题不用做~

Answer 1

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

追问

第四题第二问是根据结点数代入log那个式子算得么？第六题定义的部分是写
typedef struct{
char *base;
char *top;
int stacksize;
}SqStackTp; 这部分么？
我上课是真一点没听，所以完全不会。。。麻烦了~~

追答

是的，答题时往里面代就行了。
具有n个结点的判定树的深度为└log2 n┘+1，也就是比较次数不大于(log2 n) +1。
这里有7个数，所以它的判定树具有7个节点，所以比较次数最多为└log2 7┘+1。
这里在严蔚敏《数据结构》220页可以找到。

是的，这里定义一个顺序栈就行了，要注意main函数里进栈的类型是char，所以这里也写char；main函数中用SqStackTp sq;这样声明了一个栈，所以定义的时候也写SqStackTp。
这里在严蔚敏《数据结构》46页可以找到。

追问

那第四题结果就写└log2 7┘+1，不用再计算了么？

追答

两个都行，这里写3也没错，最多查找3次。

Answer 2

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

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

追问

第三题就是一个填空题，第六题一共两问，你只答了第一问。

追答

栈的定义：
struct stack
{
char data;
stack *next;
};

3. s->next=q->next;
q->next=q;

7)