2018年武汉工程大学计算机科学与工程学院835数据结构之数据结构考研核心题库
● 摘要
目录
2018年武汉工程大学计算机科学与工程学院835数据结构之数据结构考研核心题库（一） ... 2
2018年武汉工程大学计算机科学与工程学院835数据结构之数据结构考研核心题库（二） ... 9 2018年武汉工程大学计算机科学与工程学院835数据结构之数据结构考研核心题库（三） . 17 2018年武汉工程大学计算机科学与工程学院835数据结构之数据结构考研核心题库（四） . 27 2018年武汉工程大学计算机科学与工程学院835数据结构之数据结构考研核心题库（五） . 35
第 1 页，共 41 页
一、判断题
1． 内排序要求数据一定要以顺序方式存储。（ ）
【答案】×
【解析】由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类:一类 是内部排序；另一类是外部排序。因此，内部排序没有要求数据一定是以顺序方式存储。
2． 最小生成树的Krusakl 算法是一种贪心法。（ ）
【答案】√
【解析】在构建最小生成树常见的有三种贪心算法:
3． 完全二叉树肯定是平衡二叉树。（ ）
【答案】×
【解析】从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。
4． AOE 网一定是有向无环图。（ ）
【答案】×
【解析】在带权的有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称这种有向图表示活动的网络，简称为AOE 网。因此对AOE 网是否是有向无环图没有要求。
5． 程序一定是算法。（ ）
【答案】 ×
【解析】一个程序不一定满足有穷性。而算法是对问题的解，用程序设计语言来实现来描述，这时算法就是一个程序。
6． 哈夫曼树无左右子树之分。（ ）
【答案】×
【解析】哈夫曼树就是一棵二叉树。
第 2 页，共 41 页 。
二、单项选择题
7． 对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储
B. 以顺序方式存储，且数据元素有序
C. 以链接方式存储
D. 以链接方式存储，且数据元素有序
【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
8． 某网络的IP 地址空间为采用定长子网划分，子网掩码为
网络的最大子网个数、每个子网内的最大可分配地址个数分别是（ ）.
A.32， 8
B.32， 6
C.8， 32
D.8， 30
【答案】B
【解析】子网号为5位，在CIDR 中可以表示2＝32个子网，主机号为3位，除去全0和全5则该
1的情况可以表示6个主机地址，答案为B.
9． 浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤. 设浮点数的阶码
7和尾数均采用补码表示，且位数分别为5位和7位(均含2位符号位). 若有两个数X ＝2×29/32，Y
＝2×5/8，则用浮点加法计算X ＋Y 的最终结果是（ ）.
A.001111100010
B.001110100010
C.010000010001
D. 发生溢出 5
【答案】D
【解析】浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤，难点在对阶、规格化、判溢出这三步.X 和Y 的阶码不同，所以应该先对阶，对阶原则为：小阶向大阶
7看齐. 因此将Y 对阶后得到：Y ＝2×5/32，然后将尾数相加，得到尾数之和为：34/32.因为这是两
个同号数相加，尾数大于1，则需要右规，阶码加1. 由于阶码的位数为5位，且含两位符号位，即阶码的表示范围在之间. 而阶码本身等于7，再加1就等于8. 因此，最终结果发生溢出.
10．单链表中，增加一个头结点的目的是为了（ ）。
A. 使单链表至少有一个结点
第 3 页，共 41 页
B. 标识表结点中首结点的位置
C. 方便运算的实现
D. 说明单链表是线性表的链式存储
【答案】C
【解析】单链表中增加一个头结点的目的是为了方便运算的实现，使得对第一个元素的操作与其它元素的操作相同。
11．若对如下无向图进行遍历, 则下列选项中, 不是广度优先遍历序列的是（ ）
A.h , c , a , b , d , e , g , f
B.e , a , f , g , b , h , c , d
C.d , b , c , a , h , e , f , g
D.a , b , c , d , h , e , f , g
【答案】D
【解析】根据广度优先遍历的定义, 可知选项A 、B 、C 都为广度优先遍历, 而选项D 是深度优先遍历而不是广度优先遍历, 故答案为D 。
12．在一棵度为4的树T 中, 若有20个度为4的结点, 10个度为3的结点, 1个度为2的结点, 10个度为1的结点, 则树T 的叶结点个数是（ ）。
A.41
B.82
C.113
D.122
【答案】B
【解析】根据二叉树的性质3的推广公式:
式, 即
。
树T 的叶子结点的个数是82。
13．假设某计算机按字编址, Cache 有4个行, Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空, 采用2路组相联映射方式和LRU 替换算法, 当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4, 8时, 命中Cache 的次数是（ ）。
A.1
B.2
C.3
第 4 页，共 41 页 可直接在将数据带入公
相关内容
相关标签