习　题　3

一、分析题

1.写出下列程序段的输出结果。

2.写出以下程序段的输出结果。

3.设有一个栈,元素进栈的次序为a,b,c。问经过栈操作可以得到哪些输出序列？

二、编程题

1.编写一个算法,将读入的一列字符（以“＃”结尾）,按逆序打印出来（不包括“＃”）。

2.二阶广义Fibonacci序列定义如下:1,1,2,3,5,8,13,…即:

试分别编写递归与非递归算法计算Fibonacci序列的第n项的值。

3.试编写一个判别表达式中正、反括号是否正确配对出现的算法。

4.假设以数组cir[m]存放循环队列的元素,同时设置变量rear和length分别指示循环队列中队尾元素的位置和队列中所含元素的个数。试给出此循环队列队满的条件,并写出相应的插入和删除元素的算法。

5.用一个无表头结点的循环单链表表示一个循环队列,该队列只设一个队尾指针rear,不设队首指针,编写函数实现下列功能。

（1）向循环队列中插入一个元素。

（2）从循环队列中删除一个元素。

6.假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点而不设头指针,试编写相应的队列初始化、入队列和出队列的算法。

7.如果用一维数组q[m]表示一个循环队列,该队列只有一个头指针front和记录队列长度的计数器count,而不设尾指针,头指针比队列实际第一个元素超前一个位置,则:

（1）编写函数分别实现队列的置空、判断队列是否为空、读取队首元素、将新元素插入到队尾列和从队列里删除元素五种运算。

（2）问队列中最多能容纳多少个元素？