数据结构考研全真题解.pdf

考研全真题解108数据结构

2002年12月31日10:29:18前沿考试研究室

同济大学1999年试题

阅读下面的程序并写出程序执行结果：

main()

{intx,y,z,w;

z=(x=-1)?(y=-1,y+=x+5):(x=7,y=3);

w=y*a/4;

}

本题的难度并不大，仅需知道C语言的基本知识就可以做对。但是做的时候，很多考生

会得出会得出333的答案，而实际上正确答案为的答案，而实际上正确答案为333，因为大家没有注意到w

的输出格式是的输出格式是。在第一遍审题的时候，可能比较容易看出这里w的输出格式是的输出格式是，但是

在解答过程中，经过若干计算之后，得出了结果为72，心理上很容易发生变化，产生，心理上很容易发生变化，产生好啦！

终于算出来了终于算出来了的一瞬间的想法，并受到前3个都是整数的思维惯性影响，忽视了第4个变量

要转换成字符来输出。这就是这个题目的陷阱，大家一定要重视。

此外，在考试过程中，许多解题技巧在各个学科、各种考试中都是相通的，比如选择题的

代入法、排除法等。下面这个选择题，在无法判断或需很长时间才能判断正确结果的情况下，

一种行之有效的方法就是把备选答案代入到题目中，以验证答案的正确性。

考研全真题解109线性表

2002年12月31日10:32:25网易教育前沿考试研究室

中科院软件所1999年试题

判断正误：

①顺序存储方式只能用于存储线性结构。

②顺序查找法适用于存储结构为顺序或链接存储的线性表。

【分析】

顺序存储方式也可以用来存储树型结构，例如二叉树的数组存储方式和堆排序中的堆。

【解答】

①错误。

②正确。

考研全真题解110线性表

2002年12月31日10:36:29网易教育前沿考试研究室

浙江大学1999年试题

将图1.2所示的s所指结点加到p所指结点之后，其语句应为：

图1.2例题1.10

A．s-next=p+1;p-next=s;

B．(*p).next=s;(*s).next=(*p).next;

C．s-next=p-next;p-next=s-next;D．s-next=p-next;p-next=s;

【分析】

A错在s-next=p+1，由于链表中结点间通常不是顺序存放的，结点间的间隔单元数是不

能确定的，所以用p+1来作为指向于后继结点的地址是不正确的；B错在答案中的两语句的顺

序颠倒了，交换语句顺序后即为正确答案；C错在错在，p-next与s-next同

指向于p的原后继结点，这导致s结点并未真正地插入到链表中。

【解答】

答案为D。

考研全真题解111线性表

2002年12月31日10:40:21网易教育前沿考试研究室

清华大学1992年试题

已知la是带头结点的单链表的头指针，试编写逆序输出表中各元素的递归算法。

【分析】

递归算法的几个主要部分是：

1.何时进行递归，何时结束递归；2.递归的参数传递（即每次的递归调用时应该选用的

参数）；3.如何处理递归参数（即递归体）。

应该指出，递归算法设计是数据结构中相对来说较难理解的部分，因为我们进行递归设计

时多数情况下是在用人脑来模拟计算机的运行求解过程，是用人脑在分析它的执行情况。所

以，在分析和设计递归算法时最好是以，在分析和设计递归算法时最好是按部就班按部就班地来做，一层层地来分解、分析。结合本算法

的分析请见算法注释部分。

【解答】

PROCEDUREreverse(la:linklist);｛主调用过程｝

BEGINReverse_0ut(la);

END;

PROCEDUREReverse_0ut(lb:linklist);

BEGIN

IFlbNILTHEN｛给出递归结束的条件｝

BEGINR