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

一、填空题

1． 在有n 个顶点的有向图中，每个顶点的度最大可达。

【答案】2（n-l ）

【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。

2． 已知一循环队列的存储空间为其中队头和队尾指针分别为front 和rear , 则此循环队列判满的条件是（ ）

【答案】

3． 在n 个顶点的非空无向图中，最多有_____个连通分量。

【答案】n

【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。

4． 空格串是指_____，其长度等于_____。

【答案】由空格字符（

值32）所组成的字符串；空格个数

5． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。

【答案】4; 2 6． 中缀式运算结果为_____。

【答案】

【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。

7． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为

8． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若

则的地址为

若

对应的前缀式为_____，若

则后缀式

的

，）则 的地址为_____。

则

的地址为

9． 在一棵m 阶的个数是_____。

【答案】

将代入得33。

树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的

关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字

最少

【解析】m 阶树除根结点和叶子结点外，结点中关键字个数最多是

10．阅读下列程序说明和裎序，填充程序中的_____。

本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：

（1）把根结点放入堆栈。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）

存放还没有转换过的结点，它的栈顶指针为

。

（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。

（1）

{（2）

If （ （3） ）

} }}

【答案】

【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。

11．执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。

【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储

12．设数组储，则元素为_____。

【答案】9174；8788

的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存

的存储地址为_____；若以列序为主序顺序存储，则元素

的存储地址

【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，

则它的存储地址为

若以列序为主存储顺序，则它的存储地址为

二、选择题

13．对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。

A.4

B.3 C.2 D.1

【答案】B

【解析】拓扑排序的步骤为：

（1）在有向图中选一个没有前驱的顶点并且输出它；

（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑棑序序列，分别为abced ，abecd ，aebcd 。

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

中继器

集线器

网桥

路由器 A. 仅和 B. 仅D. 仅

C. 仅和【答案】D

【解析】中继器和集线器工作在物理层，不能抑制网络风暴。为了解决冲突域的问题，提高共享介质的利用率，通常利用网桥和交换机来分隔互联网的各个网段中的通信量，以建立多个分离的冲突域。但是，当网桥和交换机接收到一个未知转发信息的数据帧时，为了保证该帧能被目的结点正确接收，将该帧从所有的端口广播出去。于是可以看出，网桥和交换机的冲突域等于端口的个数，广播域为1。因此网桥不能抑制网络风暴。