当前位置:问答库>考研试题

2017年电子科技大学自动化工程学院820计算机专业基础之数据结构考研强化模拟题

  摘要

一、选择题

1. 执行( )操作时,需要使用队列做辅助存储空间。

A. 查找哈希(Hash )表

B. 广度优先搜索网

C. 前序(根)遍历二叉树

D. 深度优先搜索网

【答案】B

【解析】查找哈希表不需要辅助存储空间,前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间,广度优先搜索树需要队列做辅助存储空间。

2. 用有向无环图描述表达式(A+B)*(,至少需要顶点的数目为( )(A+B)/A)。

A.5 B.6 C.8 D.9

【答案】A

6条边【解析】一共5个结点

3. 以太网交换机进行转发决策时使用的PDU 地址是( )。

A. 目的物理地址

B. 目的IP 地址

C. 源物理地址

D. 源IP 地址

【答案】A

【解析】交换机会监测发送到每个端口的数据帧,通过数据帧中的有关信息(源结点的MAC 地址、目的结点的MAC 地址), 就会得到与每个端口所连接结点的MAC 地址, 并在交换机的内部建立一个“端口-MAC 地址”映射表。建立映射表后,当某个端口接收到数据帧后,交换机会读取出该帧中的目的结点的MAC 地址,并通过“端口-MAC 地址”的对应关系,迅速将数据帧转发到相应的端口,注意这里的交换机工作在数据链路层,因此关于IP 地址的选项是不对的,因此答案为A 。

4. 在一株高度为2的5阶B 树中,所含关键字的个数最少是( )

A.5

B.7

C.8

D.14

第 2 页,共 49 页

【答案】A

【解析】根据B 树的定义可知,跟结点最少含有个关键字,高度为2的阶B 树最少有(5-1)+1=5个关键字,其中根节点含有个关键字,第2层结点含有1关键字。

5. 下列选项中,描述浮点数操作速度指标的是( )。

A.MIPS

B.CPI

C.IPC

D.MFLOPS

【答案】D

【解析】表示每秒执行多少百万次浮点

. 表示每秒执行多少百万条指令。对于一个给定的程序,

MIPS 定义为

这里所说的指令一般是指加、减运算这类短指令。

就是每条指令执行所用的时钟周期数。由于不同指令的功能不同,

造成指令执行时间不同,也即指令执行所用的时钟数不同,所以CPI 是一个平均值。

每个时钟周期执行的指令数。

6. 下列因素中,不会影响信道数据传输速率的是( )

A. 信噪比

B. 频率宽带

C. 调制速率

D. 信号传播速度

【答案】D

【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。

7. 将森林转换为对应的二叉树,若在二叉树中,结点u 是结点v 的父结点的父结点,则在原来的森林中,u 和v 可能具有的关系是( )。

I. 父子关系

II. 兄弟关系

III.u 的父结点与v 的父结点是兄弟关系

A. 只有I

B.I 和II

C.I 和III

第 3 页,共 49 页 运算,用来描述计算机的浮点运算速度,适用于衡量处理机的性能。

D.I 、II 和III

【答案】B

【解析】首先,在二叉树中,若结点U 是结点v 的父结点的父结点,那么u*v的关系有如下4种情况:

接下来,根据森林与二叉树的转换规则,将这4种情况还原成森林中结点的关系。其中:

,在原来的森林中U 是V 的父结点的父结点; 情况(1)

,在森林中u 是v 的父结点; 情况(2)

,在森林中u 是v 的父结点的兄弟; 情况(3)

,在森林中u 与v 是兄弟关系。 情况(4)

由此可知,题目中的I 、II 是正确的。

8. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( )存储方式最节省运算时间。

A. 单链表

B. 仅有头指针的单循环链表

C. 双链表

D. 仅有尾指针的单循环链表

【答案】D

【解析】仅有尾指针的单循环链表,在最后插入元素和删除第一个元素都会用到这个尾指针。

9. 由3个结点可以构造出多少种不同的有向树?( )

A.2

B.3

C.4

D.5

【答案】A

【解析】满足以下条件的有向图称为有向树:①有且仅有一个结点的入度为0; ②除树根外结点的入度为1; ③从树根到任一结点有一有向通路。

10.若需在0(nlog2n )的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是( )。

A. 快速排序

B. 堆排序

第 4 页,共 49 页