2018年大连海事大学信息科学技术学院810数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 已知二维数组
【答案】1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4
2． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
3． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。
【答案】（ ）；(（ ）) ；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
4． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则的地址为l ＋2＋... ＋i ﹣l ＋j ＝i(i﹣l)/2＋j 。若i ＜j 。则的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。
5． 有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)
【答案】3个
【解析】以3，4先出栈的序列有34521、34215、34251共3个。
6． 索引顺序文件既可以顺序存取，也可以 _____存取。
【答案】随机
中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是: _____。
7． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。 【答案】
【解析】哈夫曼树只有度为0和2的节点。
8．
＝_____
【答案】5
9． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉树。故结点个数为。
10．组成串的数据元素只能是_____。
【答案】字符
二、判断题
11．有n 个数顺序(依次) 入栈，出栈序列有Cn 种，
【答案】 √
12．若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（ ）
【答案】√
【解析】二叉排序树对于每一个结点，它的左子树的所有结点的值都小于这个结点的值，而它的右子树的所有结点的值都大于这个结点的值。而釆用中序遍历，遍历顺序为左根右，因此可以得到按增序排列的关键码序列。
13．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（ ）
【答案】 ×
【解析】后序遍历、中序遍历也可以遍历一维数组存储的二叉树。
14．串长度是指串中不同字符的个数。（ ）
【答案】 ×
【解析】不是，串长度是指串中字符的总个数。需要注意的是，在计算字符串的长度时，不要漏掉了空格。
15．数据结构的抽象操作的定义与具体实现有关。（ ）
【答案】 ×
【解析】数据结构抽象操作定义取决于客观存在的一组逻辑特性，与其在计算机内具体表现
（ ）
和实现无关
16．如果完全二叉树从根结点开始按层次遍历的输序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。（ ）
【答案】×
【解析】不是，2，3作为1的左右孩子，由于左节点2比1大，所以不具有二叉排序树的性质。
17．—个有向图的邻接表和逆邻接表中的结点个数一定相等。（ ）
【答案】√
【解析】图的邻接表表示法类似于树的孩子链表示法。对于图G 中的每个顶点，该方法把所以邻接于顶点
的链接成一个带头。在有向图中，为图中每个顶点建立一个入边表的方法称为逆邻接表示法。
18．拓扑排序的有向图中，最多存在一条环路。（ ）
【答案】×
【解析】要进行拓扑排序，需要满足一个条件为:若顶点A 在序列中排在顶点B 的前面，则在图中不存在顶点B 到顶点A 的路径。如果是一个有环图，则不能满足这个条件，所以拓扑排序的有向图中不能存在环路。
19．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）
【答案】×
【解析】例如起泡排序是稳定排序，将4， 3， 2，1按起泡排序排成升序序列，第一趟变成3， 2，1，4，此 时3就朝向最终位置的相反方向移动。
20．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
【答案】√
【解析】堆排序:基本思想先将原始序列构造成一个堆(初始堆) ，使其n 个元素的最大(小) 值处于序列的第 —个位置；然后交换序列第一个元素与最后一个元素的位置。
三、算法设计题
21．假设串的存储结构如下所示，编写算法实现串的置换操作。
【答案】算法如下:
相关内容
相关标签