2016年浙江工商大学信息与通信工程、工程硕士程序设计之数据结构(同等学力加试)考研复试题库
● 摘要
一、选择题
1． 对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。
A. 顺序存储方式
B. 链式存储方式
C. 散列存储方式
D. 以上均可以
答:B
2． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
答:D
【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。
3． 某计算机主频为1.2GHz ，其指令分为4类，它们在基准程序中所占比例及CPI 如下表所示。
该机的MIPS 数是（ ）
A.100
B.200
C.400
D.600
答:C
【解析】基准程序的该机器的
第 2 页，共 42 页 计算机的主频为为1200MHz ，
4． 对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）。
A. 每次分区后，先处理较短的部分
B. 每次分区后，先处理较长的部分
C. 与算法每次分区后的处理顺序无关
D. 以上三者都不对
答:A
【解析】令递归函数为f ，第一次进行递归函数认为递归深度为1，以后从深度为n 的递归函数f 中再调用递归函数f ，此时深度为整个f 的最大深度为递归深度。
5． 4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7
B.-8
C.15
D.16
答:C
【解析】Hanoi 问题总移动次数为：次。
6． 程序P 在机器M 上的执行时间是20秒，编译优化后，P 执行的指令数减少到原来的CPI 増加到原来的1.2倍，则P 在M 上的执行时间是（ ）
A.8.4 秒
B.11.7 秒
C.14 秒
D.16.8 秒
答:D 【解析】
7． 在下面的排序方法中，辅助空间为
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
答:D
8． 主机甲与主机乙之间使用后退N 帧协议（GBN ）传输数据，甲的发送窗口尺寸为1000, 数据帧长为1000字节，信道宽带为100Mbps ，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间 的单向传播延迟是50ms ，则甲可以达到的最大平均数据传输速率约为（ ）
A .10 Mbps
B. 20 Mbps
第 3 页，共 42 页 而的是（ ）。
相关内容
相关标签