27-复习题

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

1．定义一种数据类型涉及哪些内容？

2．为什么程序清单17.2只能沿一个方向遍历链表？如何修改 struct film 定义才能沿两个方向遍历链表？

3．什么是ADT？

4． QueueIsEmpty() 函数接受一个指向 queue 结构的指针作为参数，但是也可以将其编写成接受一个 queue 结构作为参数。这两种方式各有什么优缺点？

5．栈（stack）是链表系列的另一种数据形式。在栈中，只能在链表的一端添加和删除项，项被“压入”栈和“弹出”栈。因此，栈是一种LIFO（即后进先出last in,first out）结构。

a．设计一个栈ADT

b．为栈设计一个C编程接口，例如 stack.h 头文件

6．在一个含有3个项的分类列表中，判断一个特定项是否在该列表中，用顺序查找和二叉查找方法分别需要最多多少次？当列表中有1023个项时分别是多少次？65535个项是分别是多少次？

7．假设一个程序用本章介绍的算法构造了一个存储单词的二叉查找树。假设根据下面所列的顺序输入单词，请画出每种情况的树：

a．nice food roam dodge gate office wave

b．wave roam office nice gate food dodge

c．food dodge roam wave office gate nice

d．nice roam office food wave gate dodge

8．考虑复习题7构造的二叉树，根据本章的算法，删除单词 food 之后，各树是什么样子？