程序员习题
1） 经过以下栈运算后，x的值是_____________。
InitStack(s); Push(s,a); Push(s,b); Pop(s,x); GetTop(s,x); A.a
B.b C.1
D.0 2) 经过以下栈运算后，StackEmpty(s)的值是___________。
A.st.top==-1;
B.st.top!= -1;
C.st.top!=Maxsize; D.st.top==Maxsize; 13) 判定一个顺序栈st为（元素个数最多为Maxsize）满的条件为______________.
A.st.top!=-1;
B.st.top= = -1;
C.t.top!=Maxsize-1; D.st.top== axsize-1; 14)递归模型f(n=f(n-1)+n (n>1)的递归出口是___________.
A..f(1)=0 B.f(1)=1 C.f(0)=1 D.f(n)=n
InitStack(s); Push(s,a); Push(s,b); Pop(s,x); Pop(s,y);
A.a
B.b
C.1
D.0 3) 设一个栈的输入序列为A,B,C,D, 则借助一个栈所得到的输出序列不可能是___________.
A).A.B.C.D
B) D.C.B.A
C).A.C.D.B
D).D.A.B.C 4) 一个栈的进栈序列是a.b.c.d.e, 则栈的不可能的输出序列是___________’
A.edcb B.decba
C.dceab D.abcde 5) 已知一个栈的进栈序列是 1,2,3,……,n,其输出序列的第一个元素是i，则第j个出栈元素是_______________’
A.j
B.n-I
C.z-i+1
D.不确定 6） 已知一个栈的进栈序列是1,2,3,…..,n, 其输出序列是p1,p2,……,pn, 若p1=n, 则p1的值是_____________.
A.I
Bn-I
Cn-i+1
D 不确定 7） 设n个元素的进栈序列为p1,p2,p3,……,pn, 其输出序列为1,2,3,……,n, 若pn=1,则pi(1
A.n-i+1 B.I
C.I
D.有多种可能 8） 栈是一种具有_________________特性的线性表。
9) 顺序栈和链栈的区别仅在于_____________的不同？
10) 如果栈的最大长度难以估计，那么最好使用__________________栈。
11）一个栈的输入序列是12345，则栈的输出序列12345可不可能出现。 12）判定一个顺序栈st为（元素个数最多为Maxsize）空的条件为_____________.15) 经过以下队列运算后，队头的元素是____________.
InitQuue(qu); enQueue(qu,’a’); enQueue(qu,’b’); enQueue(qu,’c’); deQueue(qu);
A.a
B.b
C.1 D.0
16) 元素A,B,C,D顺序连续进入队列qu后，队头元素是____________,队尾元素是_______.
A.A
B.B
C.C
D.D
17) 一个队列的入列序列为1234，则队列可能的输出序列是______________.
A.4321 B.1234 C.1432 D.3241
18) 队列是一种具有___________特性的线性表。
19）顺序队和连队的区别仅在于______________的不同。
20）如果队列的最大长度难以估计，则最好使用_____________.
21）环形队列qu的队满条件是_______________.
A.(qu.rear+1)%maxSize == (qu.front+1)%MaxSize
B.(qu.rear+1)%MaxSize==qu.front+1;
C.(qu.rear+1)%MaxSize==qu.front+1;
D.qu.rear==qu.front
22) 最适合用作列队的列表是__________.
A.带队首指针和队尾指针的循环单连表
B.带队首指针和队尾指针的非循环单链表
C.只带队首指针的循环单链表 D.只带队尾指针的循环单链表 23）最不合适用做链队的链表是
A.只带队首指针的非循环双链表。 B．只带队首指针的循环双链表。 C.只带队尾指针的循环双链表。 D.只带队尾指针的循环单链表。 24）.假设一个练队的队尾和队首指针分别为rear front则判断队空的条件是
A front==rear B front!==NULL C rear!==NULL D front==NULL 25)用单链表表示的链队的队头在链表的_______位置 A.链头
B．链尾 C．链中
D．以上都可以
26）用单链表表示的链队的队尾在链表的_______位置
A.链头 C．链中
B．链尾D．以上都可以
27）对于链队在进行删除操作时 A 仅修改头指针 B仅修改尾指针
C 头尾指针都要修改 D头尾指针可能都要修改 填空题
1． 若用带表头结点的单链表表示则队列为空的标志是_______.2． 若用不带表头结点的单链表表示则创建一空队列的所要执行的操作是_______.3． 若用带头结点的单链表表示则创建一空队列的所要执行的操作是_______.4． 已知链队的头尾指针分别是f和r则将值x如队的操作是
P=(QNode *)malloc (sizeof(QNode));p->data=x;
_____________;________;_________; 5． 表达式23+（（12*3-2）/4+34*5/7）+108/9的后缀表达式是_____________________ 6． ; 程序：
1． 有如下算法：
Void print (int w) {
Int i;
If (w!=0)
{
Print(w-1);
For (i=1;i
Printf(“%d”,w);
Printf(“\\n”);
}}
调用语句print（4）的结果_______。 2．有如下递归过程：
Void reverse（int m） {printf(“%d”,n%10);
If (n/10!=0) reverse(n/10); }
调用语句reverse(582)的结果是________。
3.递归函数sum(int a[], int n)的返回值是数组a[]的前n个元素之和。
Int sum(int a[], int n)
{if(n>0) return_______;
Else ________; }
4.递归函数int dec(int a[], int n)判断数组a[]的前n个元素是否递增， 递增返回0；
int dec(int a[], int n)
{if(n
Else ________; }
5.递归函数invert (int a[], int k)将指定数组中的前k 个元素逆置
Void invert (int a[], int k)
{int t;
If(_______){invert(____________);
T=a[0];
A[0]=a[k-1];a[k-1]=t;
} }
6.int dec(int n)的功能是计算n!.如调用dec(6)后函数的反回值是120
int dec(int n){if (n
else return(________);
} 7.递归函数 int fib(int n)的功能是计算fibonacci 数列的第n 项
int fib(int n){ if (n==0)________;
else if(_________) return 1;
else _________;
} 判断：
1） 栈低元素是不能删除的元素。 2） 顺序栈中元素值的大小是有序的。 3） 在n个元素进栈后，他们的出栈顺序和进栈顺序正好相反。
4） 栈顶元素和栈底元素有可能是同一元素。
5） 若用s[1]~s[m]表示顺序栈的存储空间，则对栈的进栈，出栈操作最多只能进行m次。
6） 栈是一种对进栈，出栈操作总次数做了限制的线性表。
7） 对顺序栈进行进栈，出栈操作，不涉及元素的前后移动问题。 8） 栈是一种对进栈，出栈操作的次序做了限制的线性表。 9） 空栈没有栈顶指针。
10) 栈和队列都是限制存取端的线性表。 11）队列是一种对进队列，出队列操作的次序做了限制的线性表。
12）n个元素进队列的顺序和出队列的顺序总是一致的。
13）顺序队中有多少元素，可以根据队首指针的值和队尾指针的值来计算。
14）若用“队首指针的值和队尾指针的值相等”作为环形顺序队为空的标志，则在设置一个空队时，只需给队首指针和队尾指针赋同一个值，不管什么值都可以。
15）无论是顺序队还是链队，进队，出队操作的时间复杂度都是 O(1).解答题：
1） 设有一个数列的输入顺序为123456，若采用栈结构，并以A和D分别表示进栈和出栈操作，试问通过进栈和出栈操作的合法序列。
（1） 能否得到输出序列为325641的序列？
（2） 能否得到输出序列为154623的
序列？
2）说说线性表，栈和队列的异同。
3）设栈s和队列q的初始状态都为空，元素 a,b,c,d,e和f依次通过栈s，一个元素出栈后既进入队列q，若6个元素出队的序列是bdcfea, 则栈s的容量至少应该存多少个元素？ 程序题：
1> 写出下列程序字段的输出结果（栈的元
素类型SElemType为char） Void main() {Stack S; Char x,y; InitStack(S); X=’c’;y=’k’;
Push(S,x);
push(S,’a’); push(S,y); Pop(S,x);
push(S,’t’); push(S,x); Pop(S,x);
push(S,’s’);
While(!StackEmty(S)){pop(S,y);printf(y);} Printf(x); }
2> 简述以下算法的功能（栈的元素类型
SElemType为int） Status algo2(Stack S,int e) {Stack T;int d; InitStack(T);
While(!StackEmpty(S)) {pop(S,d);
If(d!=e)push(T,d); }
While(!StackEmpty(S)) {pop(T,d); Push(S,d); } }
3> 写出以下程序段的输出结果（队列中元
素类型QElemType为char） Void main()
{Queue Q; InitQueue(Q); Char x=’e’,y=’c’; EnQueue(Q,’h’); EnQueue(Q,’r’); EnQueue(Q,y);
DeQueue(Q,x); EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,’a’); While(!QueueEmpty(Q)){DeQueue(Q,y);
Printf(y);
}
Printf(x); } 4>函数MultibaseOutput(long n,int B)的功能是：将一个无符号十进制数n转换成B（2
Int InitSack(Stack *s,int n) {S->elem=(int * )malloc(n*sizeof(int)); If(S->elem==NULL) return -1; S->max=n; _____________=0; Return 0; } ` Int push(Stack *S,int item )/*将整数item压入栈中*/ {if(S->top==S->max){printf(*Stack is full!\\n);
Return -1; } _____________=irem;
Return 0; }
Int StackEmpty(Stack S) {
Return(!S.top)?1:0;/*判断栈是否为空*/ }
Int pop(Stack *S)栈顶元素出栈*/ {
If(S->top){printf(“pop an empty stack!\\n”);
Return -1;
}
Return __________;
}
Void MultibaseOutput(long n,int B) {
Int m;Stack S;
If(InitStack(&S,MAXSIZE)){printf(“Failure!\\n”);
Return;
}
Do{if(push(&S,________)){printf(“Failure!\\n”);
Return;}
N=________;
}while(n!=0);
While(!StackEmpty(S))/*输出B进制数*/ {m=pop(&S);
If(m
Else printf(“%c”,m+55);/*大于或等于10，输出相应的字符*/ }
Printf(“\\n”);}
