2016年温州大学物理与电子信息工程学院综合卷之数据结构复试笔试最后押题五套卷
● 摘要
目录
2016年温州大学物理与电子信息工程学院综合卷之数据结构复试笔试最后押题五套卷（一） . 2 2016年温州大学物理与电子信息工程学院综合卷之数据结构复试笔试最后押题五套卷（二） . 9 2016年温州大学物理与电子信息工程学院综合卷之数据结构复试笔试最后押题五套卷（三） 18 2016年温州大学物理与电子信息工程学院综合卷之数据结构复试笔试最后押题五套卷（四） 26 2016年温州大学物理与电子信息工程学院综合卷之数据结构复试笔试最后押题五套卷（五） 37
一、选择题
1． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
答:D
【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。
2． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0（n ） B.0（n+e） C.0（n*n） D.0（n*n*n）
答:B
【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0（n+e）
3． 在下列表述中，正确的是（ ）
A. 含有一个或多个空格字符的串称为空格串
B. 对个顶点的网，求出权最小的条边便可构成其最小生成树
C. 选择排序算法是不稳定的
D. 平衡二叉树的左右子树的结点数之差的绝对值不超过1
答:C
【解析】平衡二叉树的左右子树的深度之差的绝对值不超过1。求最小生成树时，每次挑最小权值边，是要求该边的两点都在不同的连通分量上的。
4． 对矩阵压缩存储是为了（ ）。
A. 方便运算
B. 方便存储
C. 提高运算速度
D. 减少存储空间
答:D
【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素
放在一个存储空间，目的就是为了节省空间。
5． 假设磁头当前位于第105道，正在向磁道序号増加的方向移动。现有一个磁道访问请求，序列为35, 45, 12, 68, 110, 180, 170, 195，采用SCAN 调度（电梯调度）算法得到的磁道访问序列是（ ）。
A.110, 170, 180, 195，68, 45, 35，12
B.110，68，45，35，12，170，180，195
C.110，170，180，195，12，35, 45, 68
D.12, 31, 45, 68, 110, 170, 180, 195
答:A
【解析】SCAN 算法类似电梯工作原理，即朝一个固定方向前进，经过的磁道有访问请求则马上服务，直至到达一端顶点，再掉头往回移动以服务经过的磁道，并这样在两端之间往返。因此，当磁头从105道向序号増加的方向移动时，便会服务所有大于105的磁道号（从小到大的顺序）；往回返时又会按照从大到小的顺序进行服务。注意与循环扫描算法的区别，所以SCAN 算法的访问序列是：110, 170，180，195, 68, 45, 35, 12。
6． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N
B.2N-1
C.2N
D.N-1
答:A
【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂 度为
7． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。
A.0（nlogn ）
B.O （logn ）
C.O （n ） D.
答:A
【解析】在内部排序中，最坏情况下的时间复杂度为0（nlogn ）。
已知待排序的n 个元素可分为
大干前一
个组，每个组包含k 个元素，且任一组内的各元素均分别
8． 假定一台计算机的显示存储器用DRAM 芯片实现，若要求显示分辨率为1600x1200, 颜色深度为24位，帧频为85Hz , 显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为（ ）。
A.245Mbps
B.979Mbps C. D.
答:D
【解析】显存的容量=分辨率×色深，带宽=分辨率×色深×帧频，考虑到的时间用来刷新
1600×1200×24×85×2＝7834Mbps 屏幕，故显存总带宽应加倍。所以需要的显存总带宽至少约为：
9． 假定基准程序A 在某计算机上的运行时间为100秒，其中90秒为CPU 时间，其余为时间。若CPU
速度提高
A.55秒
B.60秒
C.65秒
D.70秒
答:D 。
CPU 速度提高【解析】即CRJ 性能提高比为1.5, 改进之后的CPU 运行时间秒。速度不变，仍维持10秒，所以运行基准程序A 所耗费的时间为70秒。
10．对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。
A. 顺序存储方式
B. 链式存储方式
C. 散列存储方式
D. 以上均可以
答:B
速度不变，则运行基准程序A 所耗费的时间是（ ）。
二、填空题
11．执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
答:顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
12．用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。
答
:
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表
相关内容
相关标签