2017年上海市培养单位上海高等研究院866计算机原理之数据结构考研冲刺密押题
● 摘要
目录
2017年上海市培养单位上海高等研究院866计算机原理之数据结构考研冲刺密押题（一）.... 2
2017年上海市培养单位上海高等研究院866计算机原理之数据结构考研冲刺密押题（二）.. 14
2017年上海市培养单位上海高等研究院866计算机原理之数据结构考研冲刺密押题（三）.. 27
2017年上海市培养单位上海高等研究院866计算机原理之数据结构考研冲刺密押题（四）.. 39
2017年上海市培养单位上海高等研究院866计算机原理之数据结构考研冲刺密押题（五）.. 51
一、填空题
1． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。 【答案】
2． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
3． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。 【答案】
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
4． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。
【答案】O （eloge ）; 边稀疏
5． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。 【答案】
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
6． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
7． 在循环队列中，队列长度为n ，存储位置从0到，
【答案】 编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。
8． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____（表示为n 的函数）。
【答案】1＋（1＋2）＋（1＋2＋3）＋"•＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6，即
【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了1＋2次。当i=3时，赋值语句被执行了1＋2＋3次。可以推出赋值语句总共被执行了1＋（1＋2）＋（1＋2＋3）＋…＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6次。
9． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
10．在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
11．数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
12．N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。
【答案】2（N-1）
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。
二、选择题
13．由3个结点可以构造出多少种不同的有向树？（ ）
A.2
B.3
C.4
D.5
【答案】A
【解析】满足以下条件的有向图称为有向树：①有且仅有一个结点的入度为0; ②除树根外结点的入度为1; ③从树根到任一结点有一有向通路。
14．float 类型（即IEEE754单精度浮点数格式）能表示的最大正整数是（ ）。
A.
B.
C.
D.
【答案】D 。
【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示，且阶码用移码表示的浮点数。规格化的短 浮点数的真值为：S 为符号位，E 的取值为f 为23位；
故float 类型能表示的最大整数是
15．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）
。
【答案】B
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：28比72小，不交换；
第二次比较：28比5大，交换，此时为
第三次比较：16比28小，不交换；
第四次比较：32比28大，交换，此时为
第五次比较：28比2大，交换，此时为
第六次比较：28比12大，不交换；
第七次比较：28比60小，交换，此时为
一次划分结束。
16．y 的机器数分别为某字长为8位的计算机中，已知整型变量x 、
若整型变量
A.11000000
B.00100100
C.10101010
D. 溢出
【答案】A
y 右移一位， 【解析】将x 左移一位，两个数的补码相加的机器数为1 1000000, 故答案选择A 。
则z 的机器数为（ ）