2016年常州大学信息学院、数理学院数据结构(同等学力加试)复试笔试最后押题五套卷
● 摘要
一、选择题
1． 折半查找的时间复杂性为（ ）。
答:D
【解析】顺序查找的事件复杂度为
因为折半查找是查找效率最高的算法，它的事件复杂
度为
2． 设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，储地址为1，每个元素占一个地址空间，则
A.13 B.33 C.18 D.40 答:B
【解析】对于对称矩阵，
的地址为（ ）。
为第一元素，其存
为了节省存储空间，为多个相同的元素只分配一个存储空间。
时，
当
时，
其
对于对称矩阵，元素下表之间的对应关系为：当
中k 相当于地址空间的标号，i 为行号，j 为列号。因为第一个元素存储地址为1，所以最后计算 的k 需要加1。所以
的存储位置为
3． 若X 是后序线索二叉树中的叶结点， 且X 存在左兄弟结点Y ，则X 的右线索指向的是（ ）
A.X 的父结点
B. 以Y 为根的子树的最左下结点 C.X 的左兄弟结点Y
D. 以Y 为根的子树的最右下结点 答:A
【解析】根据后续线索二叉树的定义，X 结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后续遍历的方式可知X 结点的后继是其父结点，即其右线索指向的是父结点。
4． 若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组
中，则在B 中确定
的位置k 的关系为（ ）。
答:B
【解析】将n 阶对称矩阵存人一维数组中，一维数组的大小需为
第 2 页，共 43 页
对n 阶对称矩阵
A
以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组
中，当
时，i 与k 的关系为
5． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素，则关键字的比较次数最多是（ ）。
A.4 B.5 C.6 D.7 答:B
【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为（l 〇g2n ）在本题中，n=16, 故比较次数最多为5。
6． 串的长度是指（ ）。
A. 串中所含不同字母的个数 B. 串中所含字符的个数 C. 串中所含不同字符的个数 D. 串中所含非空格字符的个数 答:B
【解析】串中字符的数目n 称为字符的长度，不必考虑其中单个字符是否相等。
7． 已知串其Next 数组值为（ ）。
A.0123 B.1123 C.1231 D.1211 答:A
【解析】KMP 算法的next 数组建立的原则
8． 下列序列中，（ ）是执行第一趟快速排序后所得的序列。
答:C
【解析】快速排序将数据划分成两部分，其中一部分关键字比另一部分关键字小。
9． 动态存储管理系统中，通常可有（ ）种不同的分配策略。
第 3 页，共 43 页
+1，
答:C
【解析】动态存储管理系统中有以下三种：首次拟合法、最佳拟合法、最差拟合法。①首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。②最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n 且最接近n 的空闲块进行分配。③最差拟合法，将可利用空间表中不小于n 且是链表中最大的空闲块的一部分分配给用户。
10．对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（ ）
A. B. C. D.
答:D
【解析】拓扑排序方法如下：
（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它； （2）从图中删去该顶点，并且删去从该顶点发出的全部有向边； （3）重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。 对于此有向图进行拓扑排序所有序列为：
和
所以选D
二、填空题
11．线性表
答:（n －1）/2
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为
12．数据结构中评价算法的两个重要指标是_____。
答:算法的时间复杂度和空间复杂度
13．VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。
答:分配和释放存储空间；重组；对插入的记录
第 4 页，共 43 页
用数组表示，假定删除表中任一元素的概率相同，则删除一个元素
平均需要移动元素的个数是_____。
相关内容
相关标签