1. 假定有一个程序，它读取一系列名字，但必须以反序将它们打印出来。哪种ADT更适合完成这个任务？
解析：
堆栈。堆栈的特性是先进后出，后进先出，所以适合完成这个任务。
#include "stack.h"
#include
#include
int main( void ){
int ch;
int counter;
counter = 0;
printf( "input name you want:n" );
while( (ch = getchar()) != EOF ){
push( ch );
++counter;
}
printf( "print name you input:n" );
while( --counter >= 0 ){
ch = top();
putchar( ch );
pop();
}
return EXIT_SUCCESS;
}
#define STACK_TYPE char
void push( STACK_TYPE value );
void pop( void );
STACK_TYPE top( void );
int is_empty( void );
int is_full( void );
#include "stack.h"
#include
#define STACK_SIZE 100
static STACK_TYPE stack[ STACK_SIZE ];
static int top_element = -1;
void
push( STACK_TYPE value ){
assert( !is_full() );
top_element += 1;
stack[ top_element ] = value;
}
void
pop( void ){
assert( !is_empty() );
top_element -= 1;
}
STACK_TYPE
top( void ){
assert( !is_empty() );
return stack[ top_element ];
}
int
is_empty( void ){
return top_element == -1;
}
int
is_full( void ){
return top_element == STACK_SIZE - 1;
}
2. 在超级市场的货架上摆放牛奶时，使用哪种ADT更为合适？既需要考虑顾客购买牛奶，也需要考虑超级市场新到货一批牛奶的情况。
解析：
假如为了保证所有的牛奶不过期能尽量卖完，肯定是旧的牛奶摆放在前面，新的牛奶摆放在后面，这适合使用队列这种数据结构。
3.在堆栈的传统接口中，pop函数返回它从堆栈中删除的那个元素的值。在一个模块中是否有可能提供两种接口？
解析：
传统接口和替代形式的借口很容易共存。top函数返回栈顶元素值，但并不实际移除它，pop函数移除栈顶元素并返回它。希望使用传递方式的用户可以用传统的方式使用pop函数。如果希望使用替代方案，用户可以用top函数获得栈顶元素的值，而且在使用pop函数时忽视它的返回值。
4. 如果堆栈模块具有一个empty函数，用于删除堆栈中的所有值，模块的功能是不是变得更加明显更为强大？
解析：
模块的功能变得更为强大了，不过这可能提高它跟其他函数名发生冲突的几率和实现跟堆栈中其它函数相同的功能。
5.在push函数中，top_element在存储之前先增值。但是pop函数中，它却在返回栈顶值后再减值。如果弄反这两个次序，会发生什么后果。
解析：在push函数中，如果top_element先存储值后增值可能会造成数组溢出。在pop函数中，如果top_element先减值再返回栈顶值则可能提前触发assert宏。
6.如果在一个使用静态数组的堆栈模型中删除所有的断言，会产生什么后果？
解析：
会导致数组发生溢出，导致一些意料之外的结果。
7.在堆栈的链式实现中，为什么destroy_stack函数从堆栈中逐个弹出元素？
解析：
由于它们中的每一个都是用malloc函数单独分配的，因此逐个将它们弹出可以保证每个元素均被释放。用于释放它们的代码在pop函数中已经存在，所以调用pop函数比复制那些代码更好。
8.链式堆栈实现的pop函数声明了称为first_node的局部变量。这个变量可不可以省略？
解析：
first_node局部变量是用来表示当前需要删除的内存的地址，是不可以省略的。之前我们已经有过实验了，假如在stack = stack->next之前使用了free(stack)可能会导致stack->next的值发生改变。
9.当一个循环数组已满时，front和rear值之间的关系和堆栈为空是是一样的。但是空和满是两种不同的状态。从概念上说，为什么会出现这种情况？
解析：
考虑一个具有5个元素的数组，它可以出现6种不同的状态：它可能为空，也可能分别包含1个、2个、3个、4个或5个元素。但front和rear始终必须指向数组中的5个元素之一。所以对于任何给定值的front，rear只可能出现5中不同的情况：它可能等于front、front+1、front+2、front+3、front+4（记住front+5实际上就是front，因为它已经环绕到这个位置）。我们不可能用只能表示5个不同状态的变量来表示6种不同的状态。
10.有两种方法可用于检测一个已满的循环数组：始终保留一个数组元素不用；另外增加一个变量，记录数组中元素的个数。哪种方法更好一些？
解析：
始终保留一个数组元素会浪费一个数组元素的空间。但不用增加额外的一个变量，假如数组元素占用的空间大于增加一个变量所占的空间， 而你的内存又比较小时，考虑使用增加一个变量的方法。假如数组元素占用的空间小于增加一个变量 所占的空间，而你的内存又比较小时，考虑使用始终保留一个数组元素不用。
12.队列既可以使用单链表也可以双链表实现。那个更合适？
解析：
假定拥有一个指向链表尾部的指针，单链表就完全可以达到目的。由于队列绝不会反向遍历，而双链表具有一个额外的链字段开销，因为它用于这个场合并无优势。
13.画一棵树，它是根据下面的顺序把这些值一次插入到一棵二叉搜索树而形成的：20,15,18,32,5,91,-4,76,33,41,34
,21,90。
解析：
*/
14.按照升序或降序把一些值插入到一棵二叉搜索树将导致树不平衡。在这样一棵树中查找一个值的效率如何？
解析：
效率较低，查找效率为N。N为数组元素中的元素个数。
15.在使用前序遍历时，下面这棵树各节点的访问次序是怎么样的？中序遍历呢？后序遍历呢？层次遍历呢？
解析：
前序遍历：54 36 22 16 25 41 40 51 72 61 80 73
中序遍历：16 22 25 36 40 41 51 54 61 72 73 80
后序遍历：16 25 22 40 51 41 36 61 73 80 72 54
16.改写do_pre_order_traversal函数，用于执行树的中序遍历。
#include
#include
#include "tree.h"
int main( void ){
TREE_TYPE values[] = { 54, 36, 72, 22, 41, 61, 80, 16, 25, 40, 51, 73 };
int len;
int i;
len = sizeof(values) / sizeof(*values);
for( i = 0; i < len; ++i ){
insert( values[i] );
}
printf( "the sequence of preorder traversal:n" );
pre_order_traverse( print );
printf( "n" );
printf( "the sequence of inorder traversal:n" );
in_order_traverse( print );
printf( "n" );
printf( "the sequence of postorder traversal:n" );
post_order_traverse( print );
printf( "n" );
return EXIT_SUCCESS;
}
#define TREE_TYPE int
void print( TREE_TYPE value );
void insert( TREE_TYPE value );
TREE_TYPE *find( TREE_TYPE value );
void pre_order_traverse( void (*callback)( TREE_TYPE value ) );
void in_order_traverse( void (*callback)( TREE_TYPE value ) );
void post_order_traverse( void (*callback)( TREE_TYPE value ) );
#include "tree.h"
#include
#include
#define TREE_SIZE 100
#define ARRAY_SIZE ( TREE_SIZE + 1 )
static TREE_TYPE tree[ ARRAY_SIZE ];
static int
left_child( int current ){
return current * 2;
}
static int
right_child( int current ){
return current * 2 + 1;
}
void print( TREE_TYPE value ){
printf( "%d ", value );
}
void
insert( TREE_TYPE value ){
int current;
assert( value != 0 );
current = 1;
while( tree[ current ] != 0 ){
if( value < tree[ current ] ){
current = left_child( current );
}else{
assert( value != tree[ current ] );
current = right_child( current );
}
assert( current < ARRAY_SIZE );
}
tree[ current ] = value;
}
TREE_TYPE *
find( TREE_TYPE value ){
int current;
current = 1;
while( current < ARRAY_SIZE && tree[ current ] != value ){
if( value < tree[ current ] ){
current = left_child( current );
}else{
current = right_child( current );
}
}
if( current < ARRAY_SIZE ){
return tree + current;
}else{
return 0;
}
}
static void
do_pre_order_traverse( int current, void (*callback)( TREE_TYPE value ) ){
if( current < ARRAY_SIZE && tree[ current ] != 0 ){
callback( tree[ current ] );
do_pre_order_traverse( left_child( current ), callback );
do_pre_order_traverse( right_child( current ), callback );
}
}
void
pre_order_traverse( void (*callback)( TREE_TYPE value ) ){
do_pre_order_traverse( 1, callback );
}
static void
do_in_order_traverse( int current, void (*callback)( TREE_TYPE value ) ){
if( current < ARRAY_SIZE && tree[ current ] != 0 ){
do_in_order_traverse( left_child( current ), callback );
callback( tree[ current ] );
do_in_order_traverse( right_child( current ), callback );
}
}
void
in_order_traverse( void (*callback)( TREE_TYPE value ) ){
do_in_order_traverse( 1, callback );
}
static void
do_post_order_traverse( int current, void (*callback)( TREE_TYPE value ) ){
if( current < ARRAY_SIZE && tree[ current ] != 0 ){
do_post_order_traverse( left_child( current ), callback );
do_post_order_traverse( right_child( current ), callback );
callback( tree[ current ] );
}
}
void
post_order_traverse( void (*callback)( TREE_TYPE value ) ){
do_post_order_traverse( 1, callback );
}
17.改写do_pre_order_traversal函数，用于执行树的后序遍历。
解析：
答案参考问题16。
18. 二叉搜索树的那种遍历方法可以以升序依次访问树中的所有节点？那种方法可以降序依次访问树中的所有节点？
解析：
中序遍历可以以升序访问一棵二叉搜索树的各个节点。没有一种预定义的遍历方法以降序访问二叉树的各个节点，但可以对中序遍历稍作修改，使它先遍历右子树然后再遍历左子树可以实现这个目的。
19.destroy_tree函数是通过释放所有分配给树中节点的内存来删除这棵树，这意味着所有树节点必须以某个特定的次序进行处理。哪种类型的遍历最适合这个任务。
解析：
后序遍历最适合这个任务。因为后序遍历的顺序是先遍历左子树，然后再遍历右子树，最后遍历根节点。
#include
#include
#include "tree.h"
int main( void ){
TREE_TYPE values[] = { 54, 36, 72, 22, 41, 61, 80, 16, 25, 40, 51, 73 };
int len;
int i;
len = sizeof(values) / sizeof(*values);
for( i = 0; i < len; ++i ){
insert( values[i] );
}
printf( "the sequence of preorder traversal:n" );
pre_order_traverse( print );
printf( "n" );
printf( "the sequence of inorder traversal:n" );
in_order_traverse( print );
printf( "n" );
printf( "the sequence of postorder traversal:n" );
post_order_traverse( print );
printf( "n" );
post_order_traverse( destroy_tree );
return EXIT_SUCCESS;
}
#define TREE_TYPE int
typedef struct TREE_NODE{
TREE_TYPE value;
struct TREE_NODE *left;
struct TREE_NODE *right;
} TreeNode;
void print( TREE_TYPE value );
void insert( TREE_TYPE value );
TREE_TYPE *find( TREE_TYPE value );
TreeNode *find_2( TREE_TYPE value );
void destroy_tree( TREE_TYPE value );
void pre_order_traverse( void (*callback)( TREE_TYPE value ) );
void in_order_traverse( void (*callback)( TREE_TYPE value ) );
void post_order_traverse( void (*callback)( TREE_TYPE value ) );
#include "tree.h"
#include
#include
#include
static TreeNode *tree;
void print( TREE_TYPE value ){
printf( "%d ", value );
}
void
insert( TREE_TYPE value ){
TreeNode *current;
TreeNode **link;
link = &tree;
while( (current = *link) != NULL ){
if( value < current->value ){
link = ¤t->left;
}else{
assert( value != current->value );
link = ¤t->right;
}
}
current = (TreeNode *)malloc( sizeof( TreeNode ) );
assert( current != NULL );
current->value = value;
current->left = NULL;
current->right = NULL;
*link = current;
}
TREE_TYPE *
find( TREE_TYPE value ){
TreeNode *current;
current = tree;
while( current != NULL && current->value != value ){
if( value < current->value ){
current = current->left;
}else{
current = current->right;
}
}
if( current != NULL ){
return ¤t->value;
}else{
return NULL;
}
}
TreeNode *find_2( TREE_TYPE value ){
TreeNode *current;
current = tree;
while( current != NULL && current->value != value ){
if( value < current->value ){
current = current->left;
}else{
current = current->right;
}
}
return current;
}
void destroy_tree( TREE_TYPE value ){
TreeNode *p = find_2( value );
if( p ){
printf( "%d ", p->value );
}
free( p );
}
static void
do_pre_order_traverse( TreeNode *current, void (*callback)( TREE_TYPE value ) ){
if( current != NULL ){
callback( current->value );
do_pre_order_traverse( current->left, callback );
do_pre_order_traverse( current->right, callback );
}
}
void
pre_order_traverse( void (*callback)( TREE_TYPE value ) ){
do_pre_order_traverse( tree, callback );
}
static void
do_in_order_traverse( TreeNode *current, void (*callback)( TREE_TYPE value ) ){
if( current != NULL ){
do_in_order_traverse( current->left, callback );
callback( current->value );
do_in_order_traverse( current->right, callback );
}
}
void
in_order_traverse( void (*callback)( TREE_TYPE value ) ){
do_in_order_traverse( tree, callback );
}
static void
do_post_order_traverse( TreeNode *current, void (*callback)( TREE_TYPE value ) ){
if( current != NULL ){
do_post_order_traverse( current->left, callback );
do_post_order_traverse( current->right, callback );
callback( current->value );
}
}
void
post_order_traverse( void (*callback)( TREE_TYPE value ) ){
do_post_order_traverse( tree, callback );
}
暑期编程PK赛 得CSDN机械键盘等精美礼品！
