2017年三峡大学计算机与信息学院938数据结构[专业学位]考研冲刺密押题
● 摘要
一、填空题
1． 线性表
【答案】（n －1）/2
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为
2． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
3． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
4． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。
【答案】
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
5． 串是一种特殊的线性表，其特殊性表现在_____; 串的两种最基本的存储方式是_____、_____; 两个串相等的充分必要条件是_____。
【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等
第 2 页，共 48 页
用数组表示，假定删除表中任一元素的概率相同，则删除一个元素
平均需要移动元素的个数是_____。
6． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的 数目。例f （5, 3）=5，有5种表示方式：3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1, 1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
②执行程序，f （6，4）=_____。 【答案】①1; 1; f （m ，n －1）; n ②9
7． 已知一循环队列的存储空间为环队列判满的条件是（ ）
【答案】
8． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
【答案】（1）（2）
链表未到尾就一直进行
将当前结点作为头结点后的第一元素结点插入
其中
队头和队尾指针分别为front 和rear , 则此循
9． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
10．G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
二、选择题
第 3 页，共 48 页
11．已知串
A.0123 B.1123 C.1231 D.1211
【答案】A
其Next 数组值为（ ）。
【解析】KMP 算法的next 数组建立的原则
12．float 型整数据常用IEEE754单精度浮点格式表示，假设两个float 型变量x 和y 分别在32为寄存器
和中，若
A. B. C. D.
且符号相同
且符号不同
且符号相同
且符号不同
则x 和y 之间的关系为：（ ）
【答案】A
【解析】两个数对应的IEEE754的标准形式为；
将IEEE754单精度形式的二进制转化为浮点数公式为由于
的符号位都是1, 所以fl ，f2符号相同，而阶码上
值比f2大，而他们都是负数，所以所以选A
13．为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。
A. 顺序存储 B. 散列存储 C. 链式存储 D. 索引存储 【答案】A
【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。
14．连续存储设计时，存储单元的地址（ ）。
A. 一定连续 B. 一定不连续
第 4 页，共 48 页
所以fl 的绝对
相关内容
相关标签