2018年西藏大学工学院825计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 对一组数据(2, 12, 16, 88, 5, 10) 进行排序, 若前三趟排序结果如下:
第一趟:2, 12, 16, 5, 10, 88
第二趟:2, 12, 5, 10, 16, 88
第三趟:2, 5, 10, 12, 16, 88
则采用的排序方法可能是（ ）。
A. 起泡排序
B. 希尔排序
C. 归并排序
D. 基数排序
【答案】A
【解析】题目中所给的三趟排序过程, 显然是使用起泡排序方法, 每趟排序时从前往后依次比较, 使大值“沉底”。希尔排序的基本思想是:先对序列进行“宏观调整”, 待序列中的记录“基本有序”时再进行直接插入排序。宏观调整的方法是:通过某种规则将大的待排序序列分割为若干小的待排序序列, 再依次对这些小的序列直接插入排序。宏观调整可以多次, 每次分割的序列数逐渐增多, 而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序列合并为一个大的有序序列, 然后“逐趙归并”, 直至整个序列为有序为止。基数排序是分配排序的一种, 这类排序不是通过关键字比较, 而是通过“分配”和“收集”过程来实现排序的。本题中, 很容易看出大值逐渐“沉底”, 显然使用的是起泡排序法。
2． 计算机算法指的是解决问题的步骤序列，它必须具备（ ）三个特性。
A. 可执行性、可移植性、可扩充性
B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性
D. 易读性、稳定性、安全性
【答案】B
【解析】计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述，也就是解决问题的步骤序列。一个算法通常需要具备五大特性:有穷性；确定性；可执行性；输入一个算法有零个或多个输入；输出一个算法有零个或者多个输出。
3． 稀疏矩阵一般的压缩存储方法有两种，即（ ）。
A. 二维数组和三维数组
B. 三元组和散列
C. 三元组和十字链表
D. 散列和十字链表
【答案】C
【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组(行标，列标，值) 。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。
4． 设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，a 11为第一元素，其存储地址为1，每个元素占一个地址空间，则a 85的地址为（ ）。
A.13
B.33
C.18
D.40
【答案】B
【解析】对于对称矩阵，为了节省存储空间，为多个相同的元素只分配一个存储空间。对于对称矩阵，元素下表之间的对应关系为:当i ＞＝j 时，k ＝i(i﹣l)/2＋j ﹣l ；当i ＜＝j 时，k ＝j(j﹣l)/2＋i ﹣l 。其中k 相当于地址空间的标号，i 为行号，j 为列号。因为第一个元素存储地址为1，所以最后计算的k 需要加1。所以a 85的存储位置为8*(8﹣1)/2＋5＝33。
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． 设有向图G=(V, E) , 顶点集
边集,
,
若从顶点V0开始对图进行深度优先遍历, 则可能得到的不同遍历序列个数是（ ）。
A.2
B.3
C.4
D.5
【答案】D
【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索, 所以可能得到的不同遍历序列分别是: ①
④
' ; ②; ⑤; ③。
体系结构中, 直接为ICMP 提供服务的协议是（ ）。 ; 7． 在
A.PPP
B.IP
C.UDP
D.TCP
【答案】B 。
【解析】首先明确ICMP 是网络层的协议, 由于服务必须是下一层向上一层提供服务的, 因此选项C 项中的UDP 和选项D 项中的TCP 属于传输层, 在网络层上面, 所以显然错误, 而PPP 协议是广域网数据链路层协议, 直接为网络层, 也就是IP 层提供服务, ICMP 协议是封装在网络层, 因此PPP 不能直接为ICMP 提供服务, ICMP 报文直接封装在IP 分组中, 故答案是B 。
8． 主机甲与主机乙之间使用后退N 帧协议(GBN)传输数据, 甲的发送窗口尺寸为1000, 数据帧长为1000字节, 信道宽带为100Mbps , 乙每收到一个数据帧立即利用一个短帧(忽略其传输延迟) 进行确认, 若甲乙之间的单向传播延迟是50ms , 则甲可以达到的最大平均数据传输速率约为（ ）
A.10Mbps
B.20Mbps
C.80Mbps
D.100Mbps
【答案】C 【解析】
9． 在子网
A.0
B.1
C.2 中, 能接收目的地址为的IP 分组的最大主机数是（ ）。