【数据结构】笔试题

1、

某带链的队列初始状态为 front=rear=NULL 。经过一系列正常的入队与退队操作后， front=rear=10 。该队列中的元素个数？

在队列为链栈时，除了初始构造是皆为空外，当这两个指针再次相遇时，这个链队列的元素为一个。注意和循环队列区别。

往队列的队尾插入一个元素为入队，从队列的排头删除一个元素称为退队。初始时front=rear=0，front总是指向队头元素的前一位置，入队一次rear+1，退队一次front+1。队列队头队尾指针相同时队列为空。

而带链的队列，由于每个元素都包含一个指针域指向下一个元素，当带链队列为空时front=rear=Null，插入第1个元素时，rear+1指向该元素，front+1也指向该元素，插入第2个元素时rear+1，front不变，删除1个元素时front+1。即front=rear不为空时带链的队列中只有一个元素。

2、

（判断）在用堆排序算法排序时,如果要进行增序排序,则需要采用"大根堆"？

这个题不是看输出的序列，是看形成的数组。

堆的删除操作：删除操作把堆顶元素和最后一个元素交换，再调整。

最大堆这样一直删，删完了就形成了一个从小到大的数组。

3、

（判断）消除递归不一定需要使用栈？

不是所有的递归转化为非递归都要用到栈。转化为非递归主要有两种方法：对于尾递归或单向递归，可以用循环结构算法代替，如求阶乘；另外一个才是栈的方法。

4、

若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定满足（）

A、结点均无左孩子 B、结点均无右孩子

C、高度为n D、存在度为2的结点

答案选 C 。

原理如下：

先序遍历顺序是：M-L-R;

后序遍历顺序是：L-R-M;

可以看到，只有中间的结点（M）顺序变化了，左右结点相对位置是不变的。那可以推断出，要满足题意的话“二叉树的先序序列与后序序列正好相反”，说明整个二叉树左子树或者右子树有一个没有（遍历就成了，先：M-L ；后：L-M 或者 先：M-R ；后：R-M ）也就是必然是一条链。

5、

在单链表中，增加头结点的目的？

教科书上的原话是: 为了方便在表头插入和删除结点,是的与在其他地方所做的操作相同,需要在表头结点前面增加一个结点把它称之为表头附加节点或者头结点。

6、

已知数组D的定义是int D[4][8];,现在需要把这个数组作为实参传递给一个函数进行处理。下列说明汇总可以作为对应的形参变量说明的是（）。

A、int D[4][] B、int *s[8]

C、int(*s)[8] D、 int D[][8]

答案选 CD 。

首先，二维数组在内存中是连续存储的，他可以通过 arr[i][j]寻址是因为我们定义了这个数组有多少列。假如有N列，这样数组寻址的时候编译器会自动得到 * ( arr + ( i * N ) + j )， 所以传参数的时候列数必须指定，排除 A 选项。

而区分int *p[n]; 和int (*p)[n]; 就要看运算符的优先级了。

int *p[n]; 中，运算符[ ]优先级高，先与p结合成为一个数组，再由int*说明这是一个整型指针数组。

int (*p)[n]; 中( )优先级高，首先说明p是一个指针，指向一个整型的一维数组。