2017年大连海事大学信息科学技术学院810数据结构考研仿真模拟题
● 摘要
一、填空题
1． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
2． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
【答案】（1）（2）（3）（4）（5）
3． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
4． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
5． 空格串是指_____，其长度等于_____。
【答案】由空格字符（
6． 模式串
7． 设数组
值32）所组成的字符串；空格个数
的next 函数值序列为_____。
【答案】01122312
数组中任一元素
均占内存48个二进制位，从首地址2000开始
连续存放在主内存里，主内存字长为16位，那么
（1）存放该数组至少需要的单元数是_____；
（2）存放数组的第8列的所有元素至少需要的单元数_____； （3）数组按列存储时，元素【答案】270; 27; 2204 【解析】
数组的元素个数为需要
第8列有9个元素，共占
因为每个元素占内存48个二进制位，即6个字节。故总
个单元数。
个字节，因此至少需要
个单元数。由题知，每个元素占3
个字节，因为主内存字长为16位，即2个字节，所以至少需要
的起始地址是_____。
个单元。按列存储时，的起始地址为
8． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
9． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
的元素，如该元素已在哈希表中，报告出错。
【答案】
【解析】本题是在哈希表ht[]中插入值为
10．在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
二、判断题
11．从逻辑结构上看，n 维数组的每个元素均属于n 个向量。（ ）
【答案】√
【解析】对于每一维，都有一个向量共用这个元素，比如我们最常见的二维数组，对于每个元素，在行和列都有一个向量共用这个元素。
12．通常使用队列来处理函数或过程的调用。（ ）
【答案】
【解析】经常使用栈来处理函数或过程的调用。
13．数据元素是数据的最小单位。（ ）
【答案】
【解析】数据项是数据的不可分割的最小单位，而数据元素是数据的基本单位。
14．哈希表的结点中只包含数据元素自身的信息，不包含任何指针。（ ）
【答案】×
【解析】哈希表的结点中可以包括指针，指向其元素。如哈希链表。
15．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为
【答案】
【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操作的时间复杂度是
16．—个稀疏矩阵
【答案】×
【解析】稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。
17．基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（ ）
【答案】×
【解析】如果用字符串为关键字，可以将其中的字符串的每一位用Ascn 码进行比较。
（ ）。
采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m
的转置运算。（ ）
和n 的值互换，则就完成了
相关内容
相关标签