发布时间 : 星期一 文章数据结构习题（95页）更新完毕开始阅读
是_____________H。设栈为顺序栈，每个元素占4个字节。 【答案】（1）23 （2）100CH
【解析】PUSH为入栈操作，POP为出栈操作。根据栈的性质，经过PUSH,PUSH,POP运算之后，栈中存在元素1，输出数据为2，然后经过PUSH,POP，3入栈，3出栈，然后经过PUSH,PUSH之后4，5入栈，此时出栈序列为2，3，栈中元素为1，4，5；每个元素占4个字节，所以栈顶指针的值为1000H+3*4=100CH（十六进制数）
3．循环队列的引入，目的是为了克服_____________。 【答案】假溢出时大量移动数据元素。
4．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_____________。 【答案】先进先出
5．已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_____________。 【答案】
s=(LinkList)malloc(sizeof(LNode)); s->data=x;
s->next=r->next; r->next=s; r=s;
【解析】根据队列的性质，新插入的元素永远插在队尾。
8．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M=_____________。 【答案】(M+1)% N；
【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。
9．当两个栈共享一存储区时，栈利用一维数组stack[1..n]表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_____________，栈2空时，top[2]为_____________，栈满时为_____________。 【答案】（1）0 （2）n+1 （3）top[1]+1=top[2]
【解析】为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的栈底分别设在这片内存空间的两端,这样,当两个栈的栈顶在栈空间的某一位置相遇时，才产生上溢，即top[1]+1=top[2]。
10．在作进栈运算时应先判别栈是否_____________；在作退栈运算时应先判别栈是否 _____________；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_____________。
为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____________分别设在内存空间的两端，这样只有当______________时才产生溢出。 【答案】（1）满 （2）空 （3）n （4）栈底 （5）两栈顶指针相邻 13．无论对于顺序存储还是链式存储的栈和队列来说，进行插入和删除运算的时间复杂度均相同为_____________。 【答案】O(1)
【解析】对于栈用栈顶指针表示栈顶，而栈的插入和删除操作均在栈顶进行。对于队列用队头和队尾指针分别表示允许插入和删除的一端。
14．在顺序队列中，当尾指针等于数组的上界，即使队列不满，再作入队操作也会产生溢出，这种现象称为_____________。
13
【答案】假溢出
【解析】产生该现象的原因是，被删元素空间在该元素被删除后就永远得不到使用。为了克服这种现象，采用循环队列来实现。
3.5 程序设计题
1．设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。)
【算法分析】判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。 【算法源代码】 int EXYX (char E[]){
/*E[]存放字符串表达式，以‘#’结束*/
char s[30]; /*s是一维数组，容量足够大，用作存放括号的栈*/ int top=0,i; /*top用作栈顶指针*/
s[top]='#'; /*‘#’先入栈，用于和表达式结束符号‘#’匹配*/ i=0; /*字符数组E的工作指针*/
while(E[i]!='#') /*逐字符处理字符表达式的数组*/ switch (E[i])
{case '(': s[++top]= '('; i++ ; break ;
case ')': if(s[top]=='('){top--; i++; break;}
else{printf(\括号不配对\ case '#': if(s[top]=='#'){printf(\括号配对\\n\
else {printf(\括号不配对\\n\括号不配对*/ default : i++; /*读入其它字符，不作处理*/ }
}/*算法结束*/
2．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。 【算法分析】
根据队列的先进先出的性质，队列的入队操作在队尾进行，出队操作在队头进行。而题目所采用的数据结构是只设一个尾指针的循环链表。我们可以根据循环链表的特点找到头指针。 【算法源代码1】
void EnQueue (LinkList rear, ElemType x)
/* rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾*/ { s=(LinkList)malloc(sizeof(LNode)); /*申请结点空间*/
s->data=x; s->next=rear->next; /*将s结点链入队尾*/ rear->next=s; rear=s; /*rear指向新队尾*/ }
【算法源代码2】
void DeQueue (LinkList rear)
/* rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息*/
{ if(rear->next==rear) {printf(\队空\\n\
s=rear->next->next; /*s指向队头元素*/ rear->next->next=s->next; /*队头元素出队*/ printf (\出队元素是:%d\
if(s==rear) rear=rear->next; /*空队列*/ free(s); }
14
3．设整数序列a1，a2，?，an，给出求解最大值的递归程序。 【算法分析】根据题意，本题的函数定义为：
a[1] n=1 maxvalue(a,n)= a[n] a[n]>maxvalue(a,n-1)
maxvalue(a,n-1) a[n] int MaxValue (int a[],int n) /*设整数序列存于数组a中，共有n个，本算法求解其最大值*/ {int max; if (n==1) max=a[1]; else if (a[n]>MaxValue(a,n-1)) max=a[n]; else max=MaxValue(a,n-1); return(max); } 4．试将下列递归函数改写为非递归函数。 void test(int *sum) { int x; scanf(\if(x==0) *sum=0 ; else {test(&sum); (*sum)+=x;} printf(\} 【算法分析】 该函数是以读入数据的顺序为相反顺序进行累加问题，可将读入数据放入栈中，等输入结束时，将栈中数据退出进行累加。累加的初值为0。 【算法源代码】 int test() { int x,sum=0,top=0,s[30]; scanf(\while (x!=0) {s[++top]=a; scanf(\printf(\while (top) {sum+=s[top--]; printf(\ } 5．编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。 【算法分析】 利用两个临时栈s1和s2。先将s栈中的内容移到s1栈中，再将s1栈中的内容移到s2栈中，最后将s2栈中的内容移到s栈中，即可实现。 【算法源代码】 reverse(SqStack *s) {SqStack *s1,*s2; /*s,s1,s2均为栈类型 ElemType x; /*栈中元素的类型，用于存储从栈中取出元素的临时变量*/ initstack(s1); /*栈的初始化*/ initstack(s2); while(!stackempty(s)) /*如果栈不空，将s栈中的内容移到s1栈中*/ {pop(s,x); /*取栈顶元素放入变量x中*/ push(s1,x); /*将变量x入栈*/ } while(!stackempty(s1)) /*如果栈不空，将s1栈中的内容移到s2栈中*/ 15 {pop(s1,x); push(s2,x); } while(!stackempty(s2)) /*如果栈不空，将s2栈中的内容移到s栈中*/ {pop(s2,x); push(s,x); } } 6．假设循环队列中只设rear和length来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。 【算法分析】 该题的关键问题是如何确定头指针，根据为指针rear和元素个数length很容易确定头指针。front=(rear-length+MAXSIZE)%MAXSIZE 【算法源代码】 #define MAXQSIZE 100 //最大队列长度 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; //队列存储空间 int rear; //尾指针，若队列不空，指向队列尾元素 int length; //队列内含元素的个数 }CyQueue; int FullQueue( CyQueue *Q) {/*判队满,队中元素个数等于空间大小*/ return Q->length==Maxsize; } void EnQueue( CyQueue *Q, ElemType x) {/* 入队 if(FullQueue( Q)) {printf(\队已满，无法入队\ Q->Data[Q->rear]=x; Q->rear=(Q->rear+1)%MAXSIZE /*在循环意义上的加1*/ Q->length++; } ElemType DeQueue( CyQueue *Q) {/*出队*/ int front; /*设一个临时队头指针*/ if(Q->length==0) Error(\队已空，无元素可出队\ front=(Q->rear + MAXSIZE - Q->length)%MAXSIZE; Q->length --; return Q->Data[front]; } 7．一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。 【算法分析】 双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。 【算法源代码】 void InitStack( DuStack *S )/*初始化双向栈*/ {S->top[0] = -1; S->top[1] = STACKSIZE; } 16