17.11　复习题

1．定义一个数据类型包含什么？

2．为什么程序清单17.2中的链表只能沿一个方向遍历？怎样修改struct film的定义才能双向遍历链表？

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

3．什么是ADT？

4．QueuelsEmpty（）函数以一个指向队列的指针为参数，但它本可以编写成接受一个queue结构作为参数。两种方式的优缺点各是什么？

5．栈（stack）是列表家族的另一种数据形式。在栈中进行添加和删除只能在列表的一端进行。项目被描述成“压入”栈顶和“弹出”堆栈。所以，栈是一种LIFO结构，即后进先出（Last In, First Out）。

a．设计一个栈ADT。
b．为栈设计一个C编程接口。

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之后，各个树是什么样子的？