//栈的出栈
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
#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. 插入排序