当前位置:问答库>考研试题

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 文件上检索记录时,先从主索引出发找到相应的柱面索引,再从柱面索引找到记录所在柱面的磁道索引,最后从磁道索引找到记录所在磁道的第一个记录的位置,由此出发在该磁道上进行顺序查找直至找到为止。