1、定义一个数据类型包含什么？
包含数据本身的定义及其操作的定义。
2、为什么程序清单17.2中的链表只能沿一个方向遍历？怎样修改struct film的定义才能双向遍历链表？
每个节点只记录了下一个节点的地址。
strcut film
{ char title[TSIZE];
int rating;
struct film *previous; //指向前序节点
struct film *next;
}
3、什么是ADT?
抽象数据模型，用户自定义的数据类型，包括数据的存储、组合方式以及可实现的操作。
4、QueueIsEmpty()函数以一个指向队列的指针为参数，但它本可以编写成接受一个queue结构作为参数。两张方式的优缺点各是什么？
指针作为参数，需要加const关键词进行限制，函数实质是对实参队列在进行判断；如果以结构作为参数，函数是对实参队列的副本进行判断。
5、栈是列表家族的另外一种数据形式。在栈中进行添加删除只能在列表一端进行。项目被描述成“压入栈顶”和“弹出堆栈”。即LIFO结构（Last in First out).请设计一个栈ADT，并为其设计C接口。
typedef int Item; typedef struct node{ Item item; struct node *next;}Node; typedef struct stack{ Node *top; Node *bottom; int items;}Stack;/*函数原型 *//*操作：初始化堆栈 */void InitializeStack(Stack *ps){ ps->top=NULL; ps->bottom=NULL; ps->items=0;}/*操作：判断堆栈是否为空 *//*操作前：ps指向一个已初始化的队列 *//*操作后：若空返回true,否则返回false */int StackIsEmpty(const Stack *ps){ return ps->items==0;} /*操作：判断Stack是否满 */int StackIsFull(const Stack *ps){ return ps->items==MAXQUEUE;}/*操作：确定堆栈中项目数量 */int StackItemCount(const Stack *ps){ return ps->items;}/*操作：在堆栈顶部添加新项目 *//*操作前：ps指向一个已初始化的堆栈,item是要被添加的项目 *//*操作后：如果添加成功，返回true,否则返回false */int PushStack(Item item,Stack *ps){ Node *pnew; if(StackIsFull(pq)) return 0; pnew=(Node*)malloc(sizeof(Node)); if(pnew==NULL) return 0; pnew->item=item; if(StackIsEmpty(ps)) { ps->top=pnew; pnew->next=NULL; } else { pnew->next=ps->top; ps->top=pnew; } ps->items++; return 1;}/*操作：从堆栈顶部删除项目 *//*操作前：ps指向一个已初始化的队列 *//*操作后：如果堆栈非空，顶部项目被复制到*pitem *//* 并被从堆栈中删除，函数返回true;如果这个操作使队列为空 *//* 则把堆栈重置为空队列；如果堆栈开始就为空，返回false */int DeStack(Item *pitem,Stack *ps){ Node *temp; if(StackIsEmpty(ps)) return 0; *pitem=ps->top->item; temp=ps->top; ps->top=ps->top->next; free(temp); ps->items--; if(ps->items==0) ps->bottom=NULL; return 1;} /*操作： 清空堆栈 *//*操作前：ps指向一个已初始化的堆栈 *//*操作后：堆栈为空 */void EmptyTheStack(Stack *ps){ Item *pitem; while (!StackIsEmpty(ps)) DeStack(pitem,ps);}
6、当在一个含有3个项目的列表中判断某一特定项目在不在该列表中时候，顺序搜索和折半搜索需要进行的比较次数最多分别为多少次？当列表中有1023个项目时呢？有65536个项目时呢？
3次、2次；
1023次、log2^1024;
65536、log2^65536+1;
7、假设某程序使用本章介绍的算法构建了一个存储单词的二叉搜索树。假设单词按照下列顺序输入，画出每种情况的树：
a.nice food roam dodge gate office wave
nice
food roam
dodge gate office wave
8、考虑复习题7构建的二叉树，依照本章算法，删除单词food后，各个树分别是什么样？
nice
dodge roam
gate office wave