数据结构(C语言版)第三四章习题答案.doc

第3章 栈和队列
习题
1．选择题
（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。
A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1
（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。
A．i B．n-i C．n-i+1 D．不确定
（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。
A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n
（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。
A．x=top->data;top=top->link； B．top=top->link;x=top->link；
C．x=top;top=top->link； D．x=top->link；
（5）设有一个递归算法如下
        int fact(int n) {  //n大于等于0
             if(n<=0) return 1;
             else return n*fact(n-1);        }
则计算fact(n)需要调用该函数的次数为（ ）。 
A． n+1       B． n-1      C． n      D． n+2
（6）栈在 （ ）中有所应用。
A．递归调用 B．函数调用 C．表达式求值 D．前三个选项都有
（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A．队列 B．栈 C． 线性表 D．有序表
（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）。
A．2 B．3 C．4 D． 6
（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（　）。
A．top不变 B．top=0 C．top-- D．top++
（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（　）数据结构最佳。
A．线性表的顺序存储结构 B．队列
C. 线性表的链式存储结构 D. 栈
（11）用链接方式存储的队列，在进行删除运算时（　）。
A. 仅修改头指针 B. 仅修改尾指针
C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
（12）循环队列存储在数组A[0..m]中，则入队时的操作为（　）。
A. rear=rear+1 B. rear=(rear+1)%(m-1)
C. rear=(rear+1)%m D. rear=(rear+1)%(m+1)
（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（　）。
A. (rear+1)%n==front B. rear==front
C．rear+1==front D. (rear-l)%n==front
（14）栈和队列的共同点是（　）。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
（15）一个递归算法必须包括（　）。
A. 递归部分 B. 终止条件和递归部分
C. 迭代部分 D. 终止条件和迭代部分

（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 
根据提示，算法可设计为：
　//以下为顺序栈的存储结构定义
　#define StackSize 100 //假定预分配的栈空间最多为100个元素
　typedef char DataType;//假定栈元素的数据类型为字符
　typedef struct{
　　DataType data[StackSize];
　　int top;
　}SeqStack; 

　int IsHuiwen( char *t)
　　{//判断t字符向量是否为回文，若是，返回1，否则返回0
　　　SeqStack s;
　　　int i , len;
　　　char temp;
　　　InitStack( &s);
　　　len=strlen(t); //求向量长度
　　　for ( i=0; i<len/2; i++)//将一半字符入栈
　　　　Push( &s, t[i]);
　　　while( !EmptyStack( &s))
　　　　{// 每弹出一个字符与相应字符比较
　　　　　temp=Pop (&s);
　　　　　if( temp!=S[i])  return 0 ;// 不等则返回0
　　　　　else i++;
　　　　} 
　　　return 1 ; // 比较完毕均相等则返回 1
　　}
（3）设从键盘输入一整数的序列：a1, a2, a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。
#define maxsize 栈空间容量
void InOutS(int s[maxsize])
//s是元素为整数的栈，本算法进行入栈和退栈操作。
{int top=0; //top为栈顶指针，定义top=0时为栈空。
for(i=1; i<=n; i++) //n个整数序列作处理。
{scanf(“%d”,&x); //从键盘读入整数序列。
if(x!=-1) // 读入的整数不等于-1时入栈。
if(top==maxsize-1){printf(“栈满\n”);exit(0);}else s[++top]=x; //x入栈。
else //读入的整数等于-1时退栈。
{if(top==0){printf(“栈空\n”);exit(0);} else printf(“出栈元素是%d\n”,s[top--])；}}
}//算法结束。

（4）从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$。
[题目分析]逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND,对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。
float expr( )
//从键盘输入逆波兰表达式，以‘$’表示输入结束，本算法求逆波兰式表达式的值。
｛float OPND[30]; // OPND是操作数栈。
　init(OPND); //两栈初始化。
float num=0.0; //数字初始化。
scanf (“%c”,&x);//x是字符型变量。
while(x!=’$’)
{switch
{case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’) //拼数
if(x!=’.’) //处理整数
{num=num*10+（ord(x)-ord(‘0’)）; scanf(“%c”,&x);}
else //处理小数部分。
{scale=10.0; scanf(“%c”,&x);
while(x>=’0’&&x<=’9’)
{num=num+(ord(x)-ord(‘0’)/scale;
scale=scale*10; scanf(“%c”,&x); }
}//else
push(OPND,num); num=0.0;//数压入栈，下个数初始化
case x=‘ ’:break; //遇空格，继续读下一个字符。
case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break;
case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;
case x=‘*’:push(OPND,pop(OPND)*pop(OPND));break;
case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;
default: //其它符号不作处理。
}//结束switch
scanf(“%c”,&x);//读入表达式中下一个字符。
}//结束while（x！=‘$’）
printf(“后缀表达式的值为%f”,pop(OPND));
}//算法结束。
[算法讨论]假设输入的后缀表达式是正确的，未作错误检查。算法中拼数部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符，认为是数。这种字符的序号减去字符‘0’的序号得出数。对于整数，每读入一个数字字符，前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点，认为数的整数部分已完，要接着处理小数部分。小数部分的数要除以10（或10的幂数）变成十分位，百分位，千分位数等等，与前面部分数相加。在拼数过程中，若遇非数字字符，表示数已拼完，将数压入栈中，并且将变量num恢复为0，准备下一个数。这时对新读入的字符进入‘+’、‘-’、‘*’、‘/’及空格的判断，因此在结束处理数字字符的case后，不能加入break语句。

（5）假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
①下面所示的序列中哪些是合法的？
A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO
②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

①A和D是合法序列，B和C 是非法序列。
②设被判定的操作序列已存入一维数组A中。
int Judge(char A[])
//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。
{i=0; //i为下标。
j=k=0; //j和k分别为I和字母O的的个数。
while(A[i]!=‘\0’) //当未到字符数组尾就作。
{switch(A[i])
{case‘I’: j++; break; //入栈次数增1。
case‘O’: k++; if(k>j){printf(“序列非法\n”)；exit(0);}
}
i++; //不论A[i]是‘I’或‘O’，指针i均后移。}
if(j!=k) {printf(“序列非法\n”)；return(false);}
else {printf(“序列合法\n”)；return(true);}
}//算法结束。
[算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘\0’），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。
(6）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。 
算法如下：
　//先定义链队结构:
　typedef struct queuenode{
　　　Datatype data;
　　　struct queuenode *next;
　　}QueueNode; //以上是结点类型的定义

　typedef struct{
　　　queuenode *rear;
　　}LinkQueue; //只设一个指向队尾元素的指针

　(1)置空队
　　void InitQueue( LinkQueue *Q)
　　　{ //置空队：就是使头结点成为队尾元素
　　　　QueueNode *s;
　　　　Q->rear = Q->rear->next;//将队尾指针指向头结点
　　　　while (Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队
　　　　　{s=Q->rear->next;
　　　　　　Q->rear->next=s->next;
　　　　　　free(s);
　　　　　}//回收结点空间
　　　}

　(2)判队空 
　　int EmptyQueue( LinkQueue *Q)
　　　{ //判队空
　　　　//当头结点的next指针指向自己时为空队
　　　　return Q->rear->next->next==Q->rear->next;
　　　}

　(3)入队
　　void EnQueue( LinkQueue *Q, Datatype x)
　　　{ //入队
　　　　//也就是在尾结点处插入元素
　　　　QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点
　　　　p->data=x; p->next=Q->rear->next;//初始化新结点并链入
　　　　Q-rear->next=p; 
　　　　Q->rear=p;//将尾指针移至新结点
　　　}

　(4)出队
　　Datatype DeQueue( LinkQueue *Q)
　　　{//出队,把头结点之后的元素摘下
　　　　Datatype t;
　　　　QueueNode *p;
　　　　if(EmptyQueue( Q ))
　　　　　　Error("Queue underflow");
　　　　p=Q->rear->next->next; //p指向将要摘下的结点
　　　　x=p->data; //保存结点中数据
　　　　if (p==Q->rear)
　　　　　{//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点
　　　　　　Q->rear = Q->rear->next; Q->rear->next=p->next;}
　　　　else 
　　　　　　Q->rear->next->next=p->next;//摘下结点p
　　　　free(p);//释放被删结点
　　　　return x;
　　　}
（7）假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。
【解答】
循环队列类定义
#include <assert.h>
template <class Type> class Queue { //循环队列的类定义
public:
Queue ( int=10 );
~Queue ( ) { delete [ ] Q; }
void EnQueue ( Type & item );
Type DeQueue ( );
Type GetFront ( );
void MakeEmpty ( ) { front = rear = tag = 0; } //置空队列
int IsEmpty ( ) const { return front == rear && tag == 0; } //判队列空否
int IsFull ( ) const { return front == rear && tag == 1; } //判队列满否
private:
int rear, front, tag; //队尾指针、队头指针和队满标志
Type *Q; //存放队列元素的数组
int m; //队列最大可容纳元素个数
}
构造函数
template <class Type>
Queue<Type>:: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) {
//建立一个最大具有m个元素的空队列。
Q = new Type[m]; //创建队列空间
assert ( Q != 0 ); //断言: 动态存储分配成功与否
}
插入函数
template<class Type>
void Queue<Type> :: EnQueue ( Type &item ) {
assert ( ! IsFull ( ) ); //判队列是否不满，满则出错处理
rear = ( rear + 1 ) % m; //队尾位置进1, 队尾指针指示实际队尾位置
Q[rear] = item; //进队列
tag = 1; //标志改1，表示队列不空
}
删除函数
template<class Type>
Type Queue<Type> :: DeQueue ( ) {
assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理
front = ( front + 1 ) % m; //队头位置进1, 队头指针指示实际队头的前一位置
tag = 0; //标志改0, 表示栈不满
return Q[front]; //返回原队头元素的值
}
读取队头元素函数
template<class Type>
Type Queue<Type> :: GetFront ( ) {
assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理
return Q[(front + 1) % m]; //返回队头元素的值
}

(8）如果允许在循环队列的两端都可以进行插入和删除操作。要求：
① 写出循环队列的类型定义；
② 写出“从队尾删除”和“从队头插入”的算法。
[题目分析] 用一维数组 v[0..M-1]实现循环队列，其中M是队列长度。设队头指针 front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。
（1）#define M 队列可能达到的最大长度
typedef struct
{ elemtp data[M];
int front,rear;
} cycqueue;
（2）elemtp delqueue ( cycqueue Q)
//Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。
{ if (Q.front==Q.rear) {printf(“队列空”); exit(0);}
Q.rear=(Q.rear-1+M)%M; //修改队尾指针。
return(Q.data[(Q.rear+1+M)%M]); //返回出队元素。
}//从队尾删除算法结束
void enqueue (cycqueue Q, elemtp x)
// Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。
{if (Q.rear==(Q.front-1+M)%M) {printf(“队满”; exit(0);)
Q.data[Q.front]=x; //x 入队列
Q.front=(Q.front-1+M)%M; //修改队头指针。
}// 结束从队头插入算法。

（9）已知Ackermann函数定义如下:

① 写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程。
② 写出计算Ack(m,n)的非递归算法。
int Ack(int m,n)
{if (m==0) return(n+1);
else if(m!=0&&n==0) return(Ack(m-1,1));
else return(Ack(m-1,Ack(m,m-1));
}//算法结束
（1）Ack(2,1)的计算过程
Ack(2,1)=Ack(1,Ack(2,0)) //因m<>0,n<>0而得
=Ack(1,Ack(1,1)) //因m<>0,n=0而得
=Ack(1,Ack(0,Ack(1,0))) // 因m<>0,n<>0而得
= Ack(1,Ack(0,Ack(0,1))) // 因m<>0,n=0而得
=Ack(1,Ack(0,2)) // 因m=0而得
=Ack(1,3) // 因m=0而得
=Ack(0,Ack(1,2)) //因m<>0,n<>0而得
= Ack(0,Ack(0,Ack(1,1))) //因m<>0,n<>0而得
= Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因m<>0,n<>0而得
= Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因m<>0,n=0而得
= Ack(0,Ack(0,Ack(0,2))) //因m=0而得
= Ack(0,Ack(0,3)) //因m=0而得
= Ack(0,4) //因n=0而得
=5 //因n=0而得
（2）int Ackerman( int m, int n)
{int akm[M][N];int i,j;
for(j=0;j<N;j++) akm[0][j];=j+1;
for(i=1;i<m;i++)
{akm[i][0]=akm[i-1][1];
for(j=1;j<N;j++)
akm[i][j]=akm[i-1][akm[i][j-1]];
}
return(akm[m][n]);
}//算法结束

（10）已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法：
① 求链表中的最大整数；
② 求链表的结点个数；
③ 求所有整数的平均值。
#include <iostream.h> //定义在头文件"RecurveList.h"中
class List;
class ListNode { //链表结点类
friend class List;
private:
int data; //结点数据
ListNode *link; //结点指针
ListNode ( const int item ) : data(item), link(NULL) { } //构造函数
};
class List { //链表类
private:
ListNode *first, current;
int Max ( ListNode *f );
int Num ( ListNode *f );
float Avg ( ListNode *f, int& n );
public:
List ( ) : first(NULL), current (NULL) { } //构造函数
~List ( ){ } //析构函数
ListNode* NewNode ( const int item ); //创建链表结点, 其值为item
void NewList ( const int retvalue ); //建立链表, 以输入retvalue结束
void PrintList ( ); //输出链表所有结点数据
int GetMax ( ) { return Max ( first ); } //求链表所有数据的最大值
int GetNum ( ) { return Num ( first ); } //求链表中数据个数
float GetAvg ( ) { return Avg ( first ); } //求链表所有数据的平均值
};

ListNode* List :: NewNode ( const int item ) { //创建新链表结点
ListNode *newnode = new ListNode (item);
return newnode;
}

void List :: NewList ( const int retvalue ) { //建立链表, 以输入retvalue结束
first = NULL; int value; ListNode *q;
cout << "Input your data:\n"; //提示
cin >> value; //输入
while ( value != retvalue ) { //输入有效
q = NewNode ( value ); //建立包含value的新结点
if ( first == NULL ) first = current = q; //空表时, 新结点成为链表第一个结点
else { current->link = q; current = q; } //非空表时, 新结点链入链尾
cin >> value; //再输入
}
current->link = NULL; //链尾封闭
}

void List :: PrintList ( ) { //输出链表
cout << "\nThe List is : \n";
ListNode *p = first;
while ( p != NULL ) { cout << p->data << ' '; p = p->link; }
cout << ‘\n’;
}

int List :: Max ( ListNode *f ) { //递归算法 : 求链表中的最大值
if ( f ->link == NULL ) return f ->data; //递归结束条件
int temp = Max ( f ->link ); //在当前结点的后继链表中求最大值
if ( f ->data > temp ) return f ->data; //如果当前结点的值还要大, 返回当前检点值
else return temp; //否则返回后继链表中的最大值
}

int List :: Num ( ListNode *f ) { //递归算法 : 求链表中结点个数
if ( f == NULL ) return 0; //空表, 返回0
return 1+ Num ( f ->link ); //否则, 返回后继链表结点个数加1
}
float List :: Avg ( ListNode *f , int& n ) { //递归算法 : 求链表中所有元素的平均值
if ( f ->link == NULL ) //链表中只有一个结点, 递归结束条件
{ n = 1; return ( float ) (f ->data ); }
else { float Sum = Avg ( f ->link, n ) * n; n++; return ( f ->data + Sum ) / n; }
}
#include "RecurveList.h" //定义在主文件中
int main ( int argc, char* argv[ ] ) {
List test; int finished;
cout << “输入建表结束标志数据 ：”;
cin >> finished; //输入建表结束标志数据
test.NewList ( finished ); //建立链表
test.PrintList ( ); //打印链表
cout << "\nThe Max is : " << test.GetMax ( );
cout << "\nThe Num is : " << test.GetNum ( );
cout << "\nThe Ave is : " << test.GetAve () << '\n';
printf ( "Hello World!\n" );
return 0;
}

第4章 串、数组和广义表
习题
1．选择题
（1）串是一种特殊的线性表，其特殊性体现在（ ）。
A．可以顺序存储 B．数据元素是一个字符
C．可以链式存储 D．数据元素可以是多个字符若
（2）串下面关于串的的叙述中，（ ）是不正确的？
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
（3）串“ababaaababaa”的next数组为（ ）。
A．012345678999 B．012121111212 C．011234223456 D．0123012322345
（4）串“ababaabab”的nextval为（ ）。
A．010104101 B．010102101 C．010100011 D．010101011
（5）串的长度是指（ ）。
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
（6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（ ）。
A．808 B．818 C．1010 D．1020
（7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（ ）。
A．BA+141 B．BA+180 C．BA+222 D．BA+225
（8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一