2017年合肥工业大学科研机构和宣城校区848软件工程学科专业基础综合之数据结构考研强化模拟题
● 摘要
一、填空题
1. 表达式
【答案】
2. 在二叉树中,指针p 所指结点为叶结点的条件是_____。
【答案】
【解析】叶子节点的左右孩子都不存在。
3. 设数组的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素为_____。
【答案】9174;8788
【解析】设一个元素的行标为i ,列标为j 。若以行序为主存储顺序,
则它的存储地址为
若以列序为主存储顺序,则它的存储地址为
4. —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端)结点和_____个叶子,该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点,度为0的结点等于度为2的结点个数+1。
5. 对单链表中元素按插入方法排序的C 语言描述算法如下,其中L 为链表头结点指针。请填充算法中标出的空白处,完成其功能。
置空链表,然后将原链表结点逐个插入到有序表中
的后缀表达式是_____。
的存储地址为_____;若以列序为主序顺序存储,则元素的存储地址
【答案】(1)
(2)(3)(4)(5)
当链表尚未到尾,p 为工作指针
查P 结点在链表中的插入位置,这时q 是工作指针
将P 结点链入链表中
是q 的前驱,u 是下个待插入结点的指针
和
每个元素占2个单元,按行优先顺处的元素为_____。
当其值为
6. 设二维数组A 的行和列的下标范围分别为
【答案】
序存储,第一个元素的存储起始位置为b ,则存储位置为
【解析】令这个元素的行标为i ,列标为j 。则它的存储位置是时,则i=2,j=3。
7. 若用n 表示图中顶点数目,则有_____条边的无向图成为完全图。
【答案】n (n-l )/2
【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边,即为n (n-l )。又因为每条边重复出现两次,所有无向完全图的边数为n (n-l )/2。
8. 已知二叉排序树的左右子树均不为空,则_____上所有结点的值均小于它的根结点值,_____上所有结点的值均大于它的根结点的值。
【答案】左子树;右子树 【解析】二叉排序树
或者是一棵空树,或者是具有下列性质的二叉树:①若它
的左子树不空,则左子树上所有结点的值均小于它的根结点的值;②若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;③它的左、右子树也分别为二叉排序树。
9. 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
10.VSAM 系统是由_____、_____、_____构成的。
【答案】索引集;顺序集;数据集
二、判断题
11.串长度是指串中不同字符的个数。( )
【答案】
【解析】不是,串长度是指串中字符的总个数。需要注意的是,在计算字符串的长度时,不要漏掉了空格。
12.顺序存储结构的主要缺点是不利于插入或删除操作。( )
【答案】
【解析】因为顺序表的插入删除会移动大量的元素。
13.外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。( )
【答案】×
【解析】外部排序方法:按可用内存大小,将外存上含n 个记录的文件分成若干长度为z 的子文件或段,依次读入内存并利用有效的内部排序方法对它们进行排序,并将排序后得到的有序子文件重新写入外存,通常称这些有序子文件为归并段或顺串(run )。对这些归并段进行逐趟归并,使归并段(有序的子文件)逐渐由小至大,直至得到整个有序文件为止。一般情况下,外部排序所需总的时间=内部排序(产生初始归并段)所需的时间
外
存信息读写的时间内部归并所需的时间
14.在平衡二又树中,向某个平衡因子不为零的结点的树中插入一新结点,必引起平衡旋转。( )
【答案】×
【解析】不一定,比如一个平衡因子为1的结点,这时往它的右部插入一个新结点,就不会引起平衡旋转
15.在待排数据基本有序的情况下,快速排序效果最好。( )
【答案】×
【解析】在待排数据基本有序的情况下,插入排序效果最好。
16.队列和栈都是运算受限的线性表,只允许在表的两端进行运算。( )
【答案】
【解析】栈只能在一端进行操作,队列可以在表的两端进行运算。
17.数据的逻辑结构是指数据的各数据项之间的逻辑关系。( )
【答案】
【解析】数据的逻辑结构是指数据元素之间的逻辑关系。
18.直接访问文件也能顺序访问,只是一般效率不高。( )
【答案】×
【解析】直接访问文件不能进行顺序访问,只能按关键字随机存取。在ISAM 文件上检索记录时,先从主索引出发找到相应的柱面索引,再从柱面索引找到记录所在柱面的磁道索引,最后从磁道索引找到记录所在磁道的第一个记录的位置,由此出发在该磁道上进行顺序查找直至找到为止。