2016年重庆交通大学信息科学与工程学院数据结构(同等学力加试)考研复试题库
● 摘要
目录
2016年重庆交通大学信息科学与工程学院数据结构（同等学力加试）考研复试题库（一） . .... 2
2016年重庆交通大学信息科学与工程学院数据结构（同等学力加试）考研复试题库（二） . .... 9
2016年重庆交通大学信息科学与工程学院数据结构（同等学力加试）考研复试题库（三） . .. 17
2016年重庆交通大学信息科学与工程学院数据结构（同等学力加试）考研复试题库（四） . .. 25
2016年重庆交通大学信息科学与工程学院数据结构（同等学力加试）考研复试题库（五） . .. 32
第 1 页，共 39 页
一、选择题
1． 程序P 在机器M 上的执行时间是20秒，编译优化后，P 执行的指令数减少到原来的CPI 増加到原来的1.2倍，则P 在M 上的执行时间是（ ）
A.8.4 秒
B.11.7 秒
C.14 秒
D.16.8 秒
答:D 【解析】
2． 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。
答:B
【解析】二分查找的时间复杂度为在一个用N 个元素的有序单链表中查找具有给定关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，
因此时间复杂度为
3． float 类型（即IEEE754单精度浮点数格式）能表示的最大正整数是（ ）。 A.
B.
C.
D.
答:D 。
【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示，且阶码用移码表示的浮点数。规格化的短 浮点数的真值为：S 为符号位，E 的取值为f 为23位；
故float 类型能表示的最大整数是
4． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
第 2 页，共 39 页 而
D. 单循环链表
答:A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进
行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
5． 在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
答:D
【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为：双亲表示法、孩子链表示法、孩子兄弟表示法。
6． 若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。
A. 单链表
B. 双向链表
C. 单循环链表
D. 顺序表
答:D
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素。
7． 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A. 直接插入排序
B. 起泡排序
C. 基数排序
D. 快速排序
答:C
【解析】C 项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD 三项都依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则不用移动，最坏情况元素反序，则需要移动n （n-1） /2次（
为元素个数）。
第 3 页，共 39 页
相关内容
相关标签