2016年长春师范大学计算机科学与技术学院数据结构(同等学力及跨学科加试)考研复试题库
● 摘要
一、选择题
1． 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。
A. 选择排序法B. 插入排序法C. 快速排序法D. 堆排序法
答:A
【解析】选择排序的基本思想是：
第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录
和分别变为新的有序区和新的无序区。 和该趟排序交换，使
将它与无序区的第1个记录
2． 将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。
A. 串
B. 树
C. 广义表
D. 栈
答:C
【解析】串、树、栈中的数据元素都是属于非结构的原子类型，元素的值是不可分解的。数组和广义表都是允许带结构的线性表。
3． 数组通常具有的两种基本操作是（ ）。
A. 查找和修改
B. 查找和索引
C. 索引和修改
D. 建立和删除
答:A
【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。根据数组的性质，数组通常具有的两种基本运算是排序和查找。
4． 有关二叉树下列说法正确的是（ ）。
A_二叉树的度为2
B. —棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
答:B
【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，... ，结点n 的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
5． n 个结点的线索二叉树上含有的线索数为（ ）。
答:C
【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n+1个空链域。
6． 线性表是具有n 个（ ）的有限序列（n ＞0）。
A. 表元素
B. 字符
C. 数据元素
D. 数据项E. 信息项
答:C
【解析】一个线性表是n 个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同。
7． 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A. 直接插入排序
B. 起泡排序
C. 基数排序
D. 快速排序
答:C
【解析】C 项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD 三项都依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则不用移动，最坏情况元素反序，则需要移动n （n-1） /2次（
为元素个数）。
8． 求整数阶乘的算法如下，其时间复杂度是（ ）。
A.
B.
C.
D.
相关内容
相关标签