//栈的出栈

int pop(struct Stack * s) { if(s->top != -1) return s->data[s->top--] ; else { printf(\ return -1 ; } }

//栈的入栈

int push(struct Stack *s , int n) { if(MAX -1 != s->top) return s->data[++s->top] = n ; else { printf(\ return -1 ; } }

int main() {

struct Stack s ; char str[MAX] ; int len , i ;

s.top = -1 ;

scanf(\ len = strlen(str) ;

for(i = 0 ; i < len / 2 ; ++i) push(&s , str[i]) ; if(len % 2) ++i ;

for( ; i < len ; ++i) if(pop(&s) != str[i]) break ; if(i == len) printf(\是回文数\ else printf(\不是回文数\ return 0 ; } 4.

Push(1) Pop(1) Push(2) Pop(2) Push(3) Pop(3) 此时输出序列为1 2 3

Push(1) push(2) pop(2) pop(1) push(3) pop(3) 此时输出序列为2 1 3

Push(1) push(2)pop(2) push(3) pop(3) pop(2) pop(3) 此时输出序列为2 3 1 Push(1) push(2) push(3) pop(3) pop(2) pop(1) 此时输出为3 2 1 算法实现就是按上述步骤进行，就省略了 5.

#include #include

#define MAX 100

struct Stack {

char data[MAX] ; int top ; };

//栈的出栈

int pop(struct Stack * s) { if(s->top != -1) return s->data[s->top--] ; else { printf(\ return -1 ; } }

//栈的入栈

int push(struct Stack *s , int n) { if(MAX -1 != s->top) return s->data[++s->top] = n ; else { printf(\ return -1 ; } }

int main() {

struct Stack s ; char str[MAX] ; int i ; char ch ;

s.top = -1 ;

scanf(\

for(i = 0 ; str[i] != '\\0' ; ++i) { if('(' == str[i]) push(&s , str[i]) ; else if(')' == str[i]) {

}

if(-1 == s.top) break ; ch = pop(&s) ; if(ch != '(') break ; } }

if(str[i] != '\\0' || -1 != s.top) printf(\不匹配\\n\else printf(\匹配\\n\return 0 ;

第十章

一、简答题 1、参考161页

2、公式不好写，算法就是根据161页性质4算出深度h，然后根据160页性质1求得叶子节点的个数

3、 根据性质1，我们可以算出完全二叉树的第八层上的节点的最大值应该比8大，所以第八层是最大层，由8个节点推出上一层的叶子节点数，相加即可 4、不好画图，这道题目自己研究一下吧。 5、（1）根节点A，叶子节点CEFHIJKMN非终端节点ABDGL

(2)树的度为3，各节点的度A3，B2，C0，D4，EFHIJKMN为0，G为3，L为1。

（3）树的深度是5，个节点深度A1, BCD2,EFGHIJ3,KLM 4,N5

6、a:011 b: 10 c: 00 d: 010 e: 11 带权路径长度为60 二、填空题 1、参考160页 2、n－1

3、根 前驱节点 后继 4、6 5、6 6、5

7、空二叉树、仅有根节点的二叉树、有子树为空的二叉树、左右子树不为空的二叉树。左子树为空的二叉树

8、2的i－1次方（公式在word里不好写） 9、4 87 10、n-2m+2 11、 n-1 三、改错

1、不能唯一确定

2、大于等于0小于等于2

3、这个说法是正确的 4、是相同的 四、单选 BCDBB DCD 五、算法设计题 1.

写一下思路

利用队列来处理，队列的数据类型为 Struct {

Struct Node * p ; //二叉树的节点 Int floor ; //二叉树的层次 }

设二叉树的根节点为t ， n存储节点的高度,初值置0

EnQueue(t) //树根入队,注意树根节点要存储在上面的结构体中，且floor = 1 While(队列不为空的时候) { Temp = ExQueue() ; //出队

//左孩子入队，入队前判断是否为空 , 左孩子的floor ＝ temp.n ＋ 1 EnQueue(temp->left )

//右孩子入队，入队前判断是否为空左孩子的floor ＝ temp.n ＋ 1 EnQueue(temp->left) //右孩子入队，入队前判断是否为空 }

最后一个出队的节点的n值就是树的高度

2.参考168页总结2下面的例题，参数n应该变成全局变量 3.和第一题一样，第一题就是按照层次遍历的 4.

完全二叉树的定义是最后一层从右到左缺少节点， 所以设flag ＝ 1表示所有的节点都有左右孩子节点

按层次遍历二叉表，当遍历到一个节点时，判断是否有左右孩子节点，此时有如下情况

1. 没有左右孩子节点或只有左节点，则后面的所有节点都应该是叶子节点，

此时flag = 0，之后的每个节点都判断是否为叶子节点，若都是，则为完全二叉树

2. 若只有右节点，则不是完全二叉树

二叉树算法设计题考的最多的应该是递归遍历，所有这几道题看看就可以了

十一章

一、 简答

1、 不唯一，同时存在若干个权值相同的边时 2、 都有关

3、 深度：V1 , v2 , v3 , v5 , v4 , v6 , v7 广度: v1 , v2 , v6, v3,v4,v7,v5 4、 参考181页

5、 参考182页 6、 参考127页 二、 填空题 1、2

2、n－1 2/1*n(n-1) 3、1

4、出 入

5、最小 n-1 6、2e 7、顶点 8、i行为0 9、a,e,b,d,e,f 10、先根 11、层次

12、邻接矩阵 邻接链表 三、改错 1、正确的

2、2n个表节点 3、不等于 4、先根遍历 5、正确的

6、完全有向图对称 四、单选 BBBAC

第十二章

一、 简答题

1. 顺序查找：必须为线性表

折半查找：必须为顺序存储结构，且有序 顺序查找平均查找次数为 n/2

折半查找平均查找次数在194页第四行，因为公式不好写，在书上查吧 2

查3时，4次 查8时，1次 查19时，4次

3. 第一种 7 5 3 1 4 9 8 第二种 7 5 9 8 3 1 4 第三种 7 5 9 3 1 4 8 第四种 7 9 5 3 1 4 8 第五种 7 9 5 8 3 1 4

此题不要背答案，主要理解二叉排序树的构建过程

二、 填空题 1. 6 19 2. O(n)

3. 插入排序