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

一、填空题

1． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。

【答案】n －1

【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。

2． 组成串的数据元素只能是_____。

【答案】字符

3． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，

请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为

其中:left 指向其左孩子，

【答案】

left 指向其前驱；，right 指向其后继。

， right 指向其右孩子，，，

4． 在循环队列中，队列长度为n ，存储位置从0到，n ﹣1编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是_____。

【答案】

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

【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数

6． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 【答案】

【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N－1) 个非零元素。

二、单项选择题

7． 若需在

（ ）。

A. 快速排序

B. 堆排序

C. 归并排序

D. 直接插入排序

【答案】C

【解析】稳定排序有:插入排序、起泡排序、归并排序、基数排序。不稳定排序有:快速排序、

堆排序、shell 排序。时间复杂度平均为的有:归并排序、堆排序、shell 排序、快速排序。

8． 某网络拓扑如下图所示, 路由器R1

只有到达子网的路由。为使R1可以将IP 分组正确地路由到图中所有子网, 则在R1中需要增加一条路由(目的网络, 子网掩码, 下一跳) 是（ ）。

的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是

A.

B.

C.

D.

【答案】D

因此是 【解析】首先从题目给出的路由表项可以确定下一跳肯定是路由器R1直接相连的R2的地址, , 此时可以排除A 和B 两个选项了。进而分析路由器R2所连接的网络特点, 注意

和, 但答案选项中只有一条信息, 因此这里其连接了2

个网络分别是

用到了超网的概念, 超网是与子网类似的概念一IP 地址根据子网掩码被分为独立的网络地址和主机地址。但是, 与子网把大网络分成若干小网络相反, 它是把一些小网络组合成一个大网络一超网,

这里

和前24位是相同的, 因此所构成的超网就是

, 那么子网掩码就是即, 因此答案是D 。

9． 假设某计算机按字编址, Cache 有4个行, Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空, 采用2路组相联映射方式和LRU 替换算法, 当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4, 8时, 命中Cache 的次数是（ ）。

A.1

B.2

C.3

D.4

【答案】C 。

【解析】Cache 有4个行, 2路组相联, 即Cache 被分成2组, 每组2行。主存地址为0〜1、4〜5、8〜9可映射到第0组Cache 中, 主存地址为2〜3、6〜7可映射到第1组Cache 中。Cache 初始为空, 采用LRU 替换算法, 当访问主存的10个地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4, 8时, 命中Cache 的次数共有3次, 分别发生在第7、8和10步时。

10．下列给出的指令系统特点中, 有利于实现指令流水线的是（ ）。

Ⅰ. 指令格式规整且长度一致

Ⅱ. 指令和数据按边界对齐存放

Ⅲ. 只有Load/Store指令才能对操作数进行存储访问

A. 仅Ⅰ、Ⅱ

B. 仅Ⅱ、Ⅲ

C. 仅Ⅰ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

【答案】D

【解析】特点Ⅰ和Ⅲ都是RISC 机的特征, 而特点Ⅱ则有利于指令和数据的存放, 所以以上三个特点都有利于实现指令流水线。

11．采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。

A. 数据元素过多

B. 负载因子过大

C. 哈希函数选择不当

D. 解决冲突的算法选择不好

【答案】D

【解析】开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。