2016年河北工程大学信息与电气工程学院数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 某计算机处理器主频为50MHz ，采用定时查询方式控制设备A 的I/0, 查询程序运行一次所用的时钟 周期数至少为500。在设备A 工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU 用于设备A 的I/0的时间占整个CPU 时间的百分比至少是（ ）。
A.0.02%
B.0.05%
C.0.20%
D.0.50%
答:C
【解析】对于设备A ，每秒中查询至少200次，每次查询至少500个时钟周期，总的时钟周期数为100000, 又因为处理器主频为50MHz 。所以CPU 用于设备A 的I/0的时间占整个CPU 时间的百分比至少为100000/50=0.20%。
2． 折半查找的时间复杂性为（ ）。
答:D
【解析】顺序查找的事件复杂度为因为折半查找是查找效率最高的算法，它的事件复杂 度为
3． 一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A.107
B.108
C.214
D.215
答:B
【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有
以
4． 下列选项中的英文缩写均为总线标准的是（ ）。
A.PCI 、CRT 、USB 、EISA
B.ISA 、CPI 、VESA 、EISA
C.ISA 、SCSI 、RAM 、MIPS
D.ISA 、EISA 、PCI 、PCI-Express
答:D
【解析】选项A 中的CRT 和USB 、选项B 中的CPI 、选项C 中的RAM 和MIPS 均不是总线
第 2 页，共 42 页 所
也就是说若对其进行哈夫曼编码，共能得到108个码字。
标准的英文缩写，只有选项D 中的英文缩写均为总线标准。
5． 如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（ ）。
A.1条，1条
B.1条，多条
C. 多条，1条
D. 多条，多条
答:A
【解析】所谓递归查询方式就是：如果主机所询问的本地域名服务器不知道被查询域名的IP 地址，那么本地域名服务器就以DNS 客户的身份向其他服务器继续发出查询请求报文，而不是让该主机自行下一步的查询。所以主机只需向本地域名服务器发送一条域名请求，采用递归查询方法，本地域名服务器也只需向上一级的根域名服务器发送一条域名请求，然后依次递归。正确选项为A 。
6． 从堆中删除一个元素的时间复杂度为（ ）。
答:B
【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为
7． 设无向图的顶点个数为m 则该图最多有（ ）条边。
A.n-1
B.n （n-l ）/2
C.n （n+l）/2
D.0
E.n2
答:B
【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。因此边数最多时，构成的是无向完全图。此时的边数为n （n-l ）/2。
8． TCP/IP参考模型的网络层提供的是（ ）。
A. 无连接不可靠的数据报服务
B. 无连接可靠的数据报服务
C. 有连接不可靠的虚电路服务
D. 有连接可靠的虚电路服务
答:A
【解析】TCP/IP的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务，因此答案是A 。
第 3 页，共 42 页
9． 数据序列
结果。
A. 选择排序
B. 起泡排序
C. 插入排序
D. 堆排序
答:C 只能是下列排序算法中的（ ）的两趟排序后的
【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。
10．设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2, 再建立F1的硬链接文件F3, 然后删除F1。此时，F2和F3的引用计数值分别是（ ）。
A.0、1
B.1、1
C.1、2
D.2、1
答:B
【解析】为了使文件实现共享，通常在使用该形式文件系统的文件索引节点中设置一个链接计数字段，用来表示链接到本文件的用户目录项的数目（引用计数值），这是共享的一种方法。当新文件建立时，一般默认引用计数值为1。硬链接可以看作是已存在文件的另一个名字，新文件和被链接文件指向同一个节点，引用计数值加1。当删除被链接文件时，只是把引用计数值减1，直到引用计数值为0时，才能真正删除文件。软链接又叫符号链接，在新文件中只包含了被链接文件的路径名，新文件和被链接文件指向不同的节点。建立软链接文件时，文件的引用计数值不会增加。在这种方式下，当被链接文件删除时，新文件仍然是存在的，只不过是不能通过新文件的路径访问被链接文件而已。因此，在本题中，当建立F2时，F1和F2的引用计数值都为1。当再建立F3时，F1和F3的引用计数值就都变成了2。当后来删除F1时，F3的引用计数值为2-1=1。F2的引用计数值仍然保持不变，所以F2和F3的引用计数值分别是：1, 1。
二、填空题
11．假定查找有序表
答:37/12
【解析】折半查找时每个的次数如表所示：
表
中每个元素的概率相等，则进行折半查找时的平均查找长度为_____
第 4 页，共 42 页