2018年武汉工程大学计算机科学与工程学院835数据结构之数据结构考研基础五套测试题
● 摘要
一、判断题
1． 在待排数据基本有序的情况下，快速排序效果好。（ ）
【答案】×
【解析】在待排数据基本有序的情况下，插入排序效果好。
2． 在平衡二又树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（ ）
【答案】×
【解析】不一定，比如一个平衡因子为1的结点，这时往它的右部插入一个新结点，就不会引起平衡旋转
3． 倒排文件的目的是为了多关键字查找。（ ）
【答案】√
【解析】多关键字文件的特点是，在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。常见的多关键字文件为:多重表文件和倒排文件。
4． 在初始数据表已经有序时，快速排序算法的时间复杂度为
【答案】×
【解析】当初始数据表有序，此时快速排序所需要比较的次数最多，快速排序算法的时间复杂度为。
5． 哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念（ ）
【答案】×
【解析】哈希文件是使用一个函数(算法) 来完成一种将关键字映射到存储器地址的映射，根据用户给出的关键字，经函数计算得到目标地址，再进行目标的检索。哈希表是根据关键码值而直接进行访问的数据结构。
6． 在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（ ）
【答案】√
第 2 页，共 42 页 。（ ）
【解析】最佳适配法:将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户；最先适配法:从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户；从适配法选择上可以看出最佳适配法会增加闲置空间。
二、单项选择题
7． 算法的计算量的大小称为计算的（ ）。
A. 效率
B. 复杂性
C. 现实性
D. 难度
【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。
8． 设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作（ ）。
A. 求子串
B. 判断是否相等
C. 模型匹配
D. 连接
【答案】C
【解析】常用的串的基本操作有七种，INDEX(s，t) 是其中的定位函数，这种运算就是所说的模式匹配。
9． 对于循环队列（ ）。
A. 无法判断队列是否为空
B. 无法判断队列是否为满
C. 队列不可能满
D. 以上说法都不是
【答案】D
【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断:①另设一个布尔变量来区别队列是空还是满；②队满时，
(rear+1)
font 。
第 3 页，共 42 页
10．假定变量i 、f 和d 的数据类型分为int 、float 和double(int用补码表示, float 和double 分别用IEEE754单精度和双精度浮点数格式表示) , 已知
器中执行下列关系表达式, 则结果为“真”的是（ ）。
(Ⅰ)
(Ⅱ)
(Ⅲ)
(Ⅳ)
A. 仅Ⅰ和Ⅱ
B. 仅Ⅰ和Ⅲ
C. 仅Ⅱ和Ⅲ
D. 仅Ⅲ和Ⅳ
【答案】B
【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。Ⅱ中, f 的数据类型从float 转换为int 时, 小数点后面4位会丢失, 故Ⅱ的结果不为真; Ⅳ中, d+f时需要对阶, 对阶后f 的尾数有效位被舍去而变为0, 故d+f仍然为d , 再减去d 后结果为0, 故Ⅳ的结果也不为真。
Ⅰ和Ⅱ进行数据类型的转换的时候并没有改变其值。
11．用户程序发出磁盘请求后, 系统的处理系统的处理流程是:用户程序一系统调用处理程序—设备骆动程序一中断处理程序。其中, 计算数据所在磁盘的柱面号、磁头号、扇区号的程序是（ ）
A. 用户程序
B. 系统调用处理程序
C. 设备驱动程序
D. 中断处理程序
【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的, 所以答案选C 。
12．设文件F1的当前引用计数值为1，先建立F1的符号链接(软链接) 文件F2，再建立F1的硬链接文件F3，然后删除F1. 此时，F2和F3的引用计数值分别是（ ）.
A.0、1
B.1、1
C.1、2
D.2、1
【答案】B
【解析】为了使文件实现共享，通常在使用该形式文件系统的文件索引节点中设置一个链接计数字段，用来表示链接到本文件的用户目录项的数目(引用计数值) ，这是共享的一种方法. 当新
第 4 页，共 42 页 。若在32位机
相关内容
相关标签