当前位置：问答库＞考研试题

一、填空题

1．

每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是

中序序列是

前庁序列是_____。 【答案】

【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。

2． 二进制地址为011011110000，大小为【答案】011011110100；011011100000

011011110000是块的起始地址，【解析】大小分别为式如下：

当大小为4时，起始地址

为当大小为16时，起始地址为

：

3． 在单链表L 中，指针P 所指结点有后继结点的条件是_____ 【答案】

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

4． 二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。

5． 数据结构中评价算法的两个重要指标是_____。

【答案】算法的时间复杂度和空间复杂度

6． 已知如下程序段：

第 2 页，共 70 页 .

，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的和块的伙伴地址分别为：_____ 和其伙伴块的起始地址计算公

语句1执行的时间复杂度为_____；语句2执行的时间复杂度为_____；语句3执行的时间复杂度为_____；语句4执行的时间复杂度为_____。

【答案】（1）n ＋1

（2）n

（3）n （n ＋3）/2

（4）n （n ＋l ）/2

【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋（n ＋l ）加起来就是n （n ＋3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n （n ＋l ）/2。

7． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用三元组表示弧及弧上的权d 。 E （G ）为 E （G= {<0，5, 100>, <0，2，10>, <1，2，5>，<0，4, 30>，<4, 5, 60>，<3，5, 10>，<2. 3，50>， <4, 3, 20>}，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。

【答案】50; 4

8． 建立索引文件的目的是_____。

【答案】提高查找速度

9． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）

10．设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的

数目。例f （5, 3）=5，有5种表示方式：3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1, 1＋1＋1＋1＋1。

①以下是该函数的程序段，请将未完成的部分填入，使之完整。

第 3 页，共 70 页

②执行程序，f （6，4）=_____。

【答案】①1; 1; f （m ，n －1）; n ②9

二、选择题

11．给定二叉树如下图所示。设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树，若遍历后的节点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）

A.LRN

B.NRL

C.RLN

D.RNL

图

【答案】D

【解析】对“二叉树”而言，一般有三条搜索路径；

①先上后下的按层次遍历；

②先左（子树）后右（子树）的遍历；

③先右（子树）后左（子树）的遍历；

其中第1种路径的搜索方式就是常见的层次遍历，第2种搜索路径方式包括常见的NLR 、中序遍历LNR 、后序遍历LRN , 第3种搜索路径方式则是不常使用的NRL 、RNL 、RLN 。本题考查的是第3种搜索路径方式的一种情况。根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D 。

12．下列网络设备中，能够抑制广播风暴的是（ ）。

中继器

集线器

网桥

路由器

A.

仅

和

B.

仅

C.

仅

D. 仅 和

第 4 页，共 70 页