2016年信阳师范学院数学与信息科学、计算机与信息技术计算机学科专业基础综合之数据结构复试最后押题五套卷
● 摘要
一、选择题
1．
用户程序发出磁盘是（ ）
A. 用户程序 B. 系统调用处理程序 C. 设备驱动程序 D. 中断处理程序 答:C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的，所以答案选C 。
2． 将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。
A. 串 B. 树 C. 广义表 D. 栈 答:C
【解析】串、树、栈中的数据元素都是属于非结构的原子类型，元素的值是不可分解的。数组和广义表都是允许带结构的线性表。
3． 已知三叉树T 中6个叶结点的权分别是2，3, 4, 5，6，7, T的带权（外部）路径长度最小是（ ）
A.27 B.46 C.54 D.56 答:B
【解析】利用三叉树的6个叶子结点的权构建最小带权生成树，
最小的带权路径长度为
4． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0（n ） B.0（n+e） C.0（n*n） D.0（n*n*n） 答:B
请求后，系统的处理系统的处理流程是：用户程序一系统调用处理程
序一设备骆动程序一中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序
【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0（n+e）
5． 程序段
其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。
答:D
【解析】这个是冒泡排序，最坏的情况下需要进行次交换，即时间复杂度是
6． 将一个的三对角矩阵，按行优先存入一维数组中，A 中元素（即该元素下标
A.198 B.195 C.197 答:B
在B 数组中的位置K 为（ ）。
【解析】将对角矩阵存入三对角矩阵压缩地址计算公式如下：
7． 若磁盘转速为7200转/分，平均寻道时间为8ms , 每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是（ ）。
A. B. C. D. 答:B
【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms , 平均等待时间与磁盘转速有关，
为
因此总的时间为：
磁盘的存取一个扇区的时间
为
8． 用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，则校验位数至少为（ ）
A.2 B.3 C.4 D.5 答:C
【解析】设校验位的位数为k ，数据位的位数为n ，根据海明码编码k 和n
应满足下述关系。
当k=4时，
符合要求，校验位至少是4位，故答案为C 。
9． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入 B. 选择 C. 希尔 D. 二路归并 答:A
【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是：假设待排序的
记录存放在数组
中，排序过程的某一中间时刻，R
被划分成两个子区间
插入到有序区
和
其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨
称其为无序区。将当前无序区的第1
个记录
中适当的位置上。使
变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。
10．组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。
A. B. C. D. 答:B 间下界为
个组分别排序即可，基于比较的排序方法每组的时
【解析】因组与组之间已有序，故将
全部时间下界为
二、填空题
11．对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
答:（1）（2）（3）
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
相关内容
相关标签