2017年西北工业大学电子信息学院880数据库、数据结构与程序设计之数据结构考研仿真模拟题
● 摘要
一、选择题
1． 设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，
储地址为1，每个元素占一个地址空间，则
A.13
B.33
C.18
D.40
【答案】B
【解析】对于对称矩阵，的地址为（ ）。 为第一元素，其存为了节省存储空间，为多个相同的元素只分配一个存储空间。
时，当时，其对于对称矩阵，元素下表之间的对应关系为：当
中k 相当于地址空间的标号，i 为行号，j 为列号。因为第一个元素存储地址为1，所以最后计算
的k 需要加1。所以
的存储位置为
2． —个进程的读磁区操作完成后，操作系统针对该进程必做的是（ ）
A. 修改进程状态为就绪态
B. 降低进程优先级
C. 进程分配用户内存空间
D. 增加进程的时间片大小
【答案】A
【解析】进程等待的操作完成便会从等待状态转移到就绪状态。
3． 主机甲通过1个路由器个路由器（存储转发方式）与主机乙互联，两段链路的数据传输速率均为10Mbps ，主机甲分别采用报文交换和组大小为10kb 的分组交换向主机乙发送1
个大小为
的报文。若忽略链路传播延迟、分组头开销和拆装时间，则两种交换方式完成该
报文传输所需的总时间分别为（ ）
A.800ms> 1600ms
B.801ms 、1600ms
C.1600ms 、800ms
D.1600ms 、801ms
【答案】D
【解析】不进行分组时，发送一个报文的时延是
的时延也是800ms 共计1600ms 。进行分组后发送一个报文的时延是在接收端接收此报文件接收一个报文的时延也是1ms ，但是在发送第二个报文时，第一个报文已经开始接收。共计有800个分组，
总时间为801 ms。
4． 将森林F 转换为对应的二叉树T , F中叶结点的个数等于（ ）
A.T 中叶结点的个数
B.T 中度为1的结点个数
C.T 中左孩子指针为空的结点个数
D.T 中右孩子指针为空的结点个数
【答案】C
【解析】森林转化为对应的二叉树是‘孩子-兄弟’存储的，即左孩子指针指向当前节点的孩子节点，右孩 子指针指向当前节点的兄弟节点，所以在T 中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以 选C
5． 若需在0（nlog2n ）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序
【答案】C
【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。不稳定排序有：快速排序、堆排序、shell 排序。时间复杂度平均为的有：归并排序、堆排序、shell 排序、快速排序。
6． 在一个文件被用户进程首次打开的过程中，操作系统需做的是（ ）
A. 将文件内容读到内存中
B. 将文件控制块读到内存中
C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程
【答案】B
【解析】概念
7． 对同一待排序列分别进行折半插入排序和直接插入排序， 两者之间可能的不同之处是（ ）。
A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数
【答案】D 。
【解析】折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，
而记录的移动次数不变。折半插入排序的时间复杂度仍为
所以两者之间的不同只可能是元素之间的比较次数。
8． 用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（ ）
A. 存储效率
B. 数列函数
C. 装填（装载）因子
D. 平均查找长度
【答案】D
【解析】哈希方法冲突会使在查找冲突的关键字时，还要根据冲突处理办法多次比较关键字，则直接影响了平均查找长度。
9． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。
A.4
B.5
C.6
D.7
【答案】C
【解析】设度为0的结点数为x 则度为3的树总结点数n=度为0的结点数+度为1的结点数+度为2的结点数+度为3的结点数从每个结点所指向的结点数的和的角度来计算度
为3
的树总结点数两种方法所计算出来的n 相等，所以
10．某CPU 主频为1.03GHz , 采用4级指令流水线，每个段的执行需要1个时钟周期。假定CPU
执行了100条指令，在其执行过程中没有发生任何流水线阻塞，此时流水线的吞吐率为（ ）
A.
B.
C.
D.
【答案】C
【解析】采用4级流水线执行100条指令，在执行过程中共用
条指令/秒，故答案为C 。
个时钟周期。CPU 的主频是1.03GHz , 也就是说每秒钟有1.03G 个时钟周期。流水线的吞吐率
为条指令/秒
条指令/秒
条指令/秒
条指令/秒
二、填空题
相关内容
相关标签