2016年天津职业技术师范大学信息技术工程学院数据结构复试笔试最后押题五套卷
● 摘要
目录
2016年天津职业技术师范大学信息技术工程学院数据结构复试笔试最后押题五套卷（一） . .... 2 2016年天津职业技术师范大学信息技术工程学院数据结构复试笔试最后押题五套卷（二） . .. 10 2016年天津职业技术师范大学信息技术工程学院数据结构复试笔试最后押题五套卷（三） . .. 19 2016年天津职业技术师范大学信息技术工程学院数据结构复试笔试最后押题五套卷（四） . .. 26 2016年天津职业技术师范大学信息技术工程学院数据结构复试笔试最后押题五套卷（五） . .. 35
第 1 页，共 42 页
一、选择题
1． 若无向图G= （V , E）中含7个顶点，则保证图G 在任何情况下都是连通的，则需要的边数最少是（ ）。
A.6 B.15 C.16 D.21 答:C
【解析】要保证无向图G 在任何情况下都是连通的，即任意变动图G 中的边，G 始终保持连通。首先需要图G 的任意6
个结点构成完全连通子图然后再添加一条边将第7个结点与
需
条边，
连接起来，共需16条边。本题非常容易错误地选择选项A ，
主要原因是对“保证图G 在任何情况下都是连通的”的理解，分析选项A ，在图G 中，具有7个顶点6条边并不能保证其一定是连通图，即有n-1 条边的图不一定是连通图。分析选项D ，图G 有7个顶点21条边，那么图G —定是无向完全图，无向完全图能 保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。
2． 站点A 、B 、C 通过CDMA 共享链路，A 、B 、C 的码片序列（chipping sequence
）分别是
和
C 收到A 发送的数据是（ ）
A.000 B.101 C.110 D.111 答:B
【解析】用A 的码片与信息做内积运算
3． 设哈希表
长哈希函
数
再哈希法解决冲突，关键字为49的结点的地址是（ ）。
答:D
【解析】15，38，61，84用哈希函数为5，发生冲突，用二次探测再散列法解决冲突：
仍然发生冲突。
仍然发生冲突。
第 2 页，共 42 页
若C 从链路上收到的序列是则
表中已有4个结点
：其余地址为空，如用二次探测
计算后得地址：4，5，6，7。49计算后
不再发生冲突。
4． 循环队列存储在数组中，则入队时的操作为（ ）。
A. B. C. D. 答:D
5．
用户程序发出磁盘请求后，系统的处理系统的处理流程是：用户程序一系统调用处理程序一设备骆动程序一中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是（ ）
A. 用户程序 B. 系统调用处理程序 C. 设备驱动程序 D. 中断处理程序 答:C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的，所以答案选C 。
6． 下列因素中，不会影响信道数据传输速率的是（ ）
A. 信噪比 B. 频率宽带 C. 调制速率 D. 信号传播速度 答:D
【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。
7． 对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。
A. 顺序存储方式 B. 链式存储方式 C. 散列存储方式 D. 以上均可以 答:B
8． —个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms 到达。它们的计算和P1:计算60ms ，作顺序如下：
计算
计算
计算
虑调度和切换时间，则完成两个作业需要的时间最少是（ ）。
A.240ms
第 3 页，共 42 页
操
若不考
B.260ms C.340ms D.360ms 答:B 。
【解析】考查处理系统的性能计算，由于P2比PI 晚5ms 到达，PI 先占用CPU ，根据PI 和P2的执行过程，作业运行的甘特图如下所示，故答案为B 。
9． 将一个（即该元素下标
A.198 B.195 C.197 答:B
的三对角矩阵，按行优先存入一维数组在B 数组中的位置K 为（ ）。
中，A 中元素
【解析】将对角矩阵存入三对角矩阵压缩地址计算公式如下：
10．假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
答:D
【解析】至少探测次数
二、填空题
11．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
答:3; （10，7，-9，0，47，23，1，8，98，36）
12．顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
答:物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
第 4 页，共 42 页