2018年郑州大学产业技术研究院945软件工程专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 下列说法不正确的是（ ）。
A. 图的遍历是从给定的源点出发每个顶点仅被访问一次
B. 遍历的基本方法有两种:深度遍历和广度遍历
C. 图的深度遍历不适用于有向图
D. 图的深度遍历是一个递归过程
【答案】C
【解析】图的遍历是指从图中的某一个顶点出发，按照某种搜索算法沿着图中的边对图中的所有顶点访问一次且仅访问一次。图的深度遍历类似于树的先序遍历，不仅适合无向图，也适合于有向图。
2． 对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次釆用的增量是（ ）。
A.1
B.4
C.3
D.2
【答案】B
【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的增量是4。
3． 采用指令Cache 与数据Cache 分离的主要目的是（ ）
A. 减低Cache 的缺失损失
B. 提高Cache 的命中率
C. 减低CPU 平均访问时间
D. 减少指令流水线资源冲突
【答案】D
【解析】指令流水线不会断流, 预取过来的都是指令
4． 算法的计算量的大小称为计算的（ ）。
A. 效率
B. 复杂性
C. 现实性
D. 难度
【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。
5． 在一棵度为4的树T 中, 若有20个度为4的结点, 10个度为3的结点, 1个度为2的结点, 10个度为1的结点, 则树T 的叶结点个数是（ ）。
A.41
B.82
C.113
D.122
【答案】B
【解析】根据二叉树的性质3的推广公式:
式, 即
。
树T 的叶子结点的个数是82。
6． 就平均性能而言，目前最好的内排序方法是（ ）排序法。
A. 起泡
B. 希尔插入
C. 交换
D. 快速
【答案】D
【解析】快速排序的平均时间复杂度是nlogn 所需要的辅助存储为
间复杂度也是
注意仅仅表示的是一个量级，比如和的量级都为，虽然堆排序的时。之所以说，所需要的辅助存储为O(1)，看似堆排序比快速排序的性能好，但是需要可直接在将数据带入公快排最好，是在综合考虑的情况下。
7． 下面关于哈希(Hash，杂凑) 查找的说法正确的是（ ）。
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B. 除留余数法是所有哈希函数中最好的
C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可
【答案】C
【解析】若数据结构中存在关键字和K 值相等的记录，则必定在f(K)的存储位置上，由此，不需要进行比较便可直接取得所查记录。在此，称这个对应关系f 为哈希(Hash)函数，哈希函数的
选择要视具体情况而定。
8． 在子网中, 能接收目的地址为
A.0
B.1
C.2
D.4
【答案】C 的IP 分组的最大主机数是（ ）。
【解析】每个子网中忽略子网内全为0和全为1的地址剩下的就是有效主机地址, 本题中由于子网的比特数是30, 因此用于主机的只有2位, 即00, 01, 10, 11, 有效主机地址是2个,
这里
显然是其广播地址, 因此答案是C 。
9． 对进行基数排序，一趟排序的结果是:（ ）
A. 05， 46， 13， 55， 94， 17， 42 B.
C. 42，13， 94，05， 55， 46，17
D. 05，13， 46，55，17，42，94
【答案】C
【解析】基数排序有两种:最低位优先和最高位优先。
①最低位优先的过程
先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是 根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。
②以r 为基数的最低位优先排序的过程 假设线性表由结点序列
成，
其中
分配:开始时，把
收集:把构成，每个结点的关键字由d 元组。在排序过程中，使用r 个队列组。排序过程就是对i=0， 1，... ，d －1，依次做一次“分配”和“收集”。 各个队列置成空队列，然后依次考察线性:
表中的每一个结点各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的。如果的关键字k=k，就把放进Q k 队列中。
线性表。
10．某计算机使用4体交叉存储器, 假定在存储器总线上出现的主存地址(十进制) 序列为8005, 8006, 8007, 8008, 8001, 8002, 8003, 8004, 8000, 则可能发生发生缓存冲突的地址对是（ ）。
A.8004, 8008
B.8002、8007
C.8001、8008
D.8000、8004