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

2018年北京市培养单位光电研究院864程序设计之数据结构考研基础五套测试题

  摘要

一、填空题

1. 已知链队列的头尾指针分别是f 和r ,则将值x 入队的操作序列是_____。

【答案】S =(LinkedList*)malloc(sizeof (LNode));s ﹣>data =x ;s ﹣>next =r ﹣>next ;r ﹣>next =s ;r =s ;

【解析】队列采用链式存储结构,先分配一个节点的内存,然后在队尾添加该节点。

2. 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个,进行入栈运算时发生上溢,则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的空间时,应将两栈的_____分别设在内存空间的两端,这样只有当_____时才产生溢出。

【答案】满;空;n ;栈底;两栈顶指针相邻(即值之差的绝对值为1)

3. 堆是一种有用的数据结构。堆排序是一种_____排序,堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时,堆排序的时间复杂度是_____,所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。

【答案】选择;完全二叉树;

4.

【答案】5

5. 设数组数组中任一元素A[i,j]均占内存48个二进制位,从首地址2000开;O(1);满足堆的性质 =_____ 始连续存放在主内存里,主内存字长为16位,那么

(1)存放该数组至少需要的单元数是_____;

(2)存放数组的第8列的所有元素至少需要的单元数_____;

(3)数组按列存储时,元素A[5,8]的起始地址是_____。

【答案】270;27;2204

【解析】数组的元素个数为9*10=90,因为每个元素占内存48个二进制位,即6个字节。故总需要90*6=540个字节,因为主内存字长为16位,即2个字节,所以至少需要540/2=270个单元数。第8列有9个元素,共占9*6=54个字节,因此至少需要54/2=27个单元数。由题知,每个元素占3个单元。按列存储时,A[5,8]的起始地址为2000+[(8﹣1)*9+(5﹣0)]*3=2204。

6. 遍历图的过程实质上是_____,广度优先遍历图的时间复杂度____;深度优先遍历图的时间复杂度_____,两者不同之处在于_____,反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程;0(n+e);0(n+e);访问顶点的顺序不同;队列和栈

【解析】广度优先遍历图使用队列这种数据结构,深度优先遍历图使用栈这种数据结构。

7. 已知;;ASSIGN(S,U) ;ASSIGN(V,SUBSTR(S,INDEX(S,t) ,LEN(t)+1))

:

【答案】

8. 假定查找有序表

【答案】

平均查找次数为

9. 数据结构中评价算法的两个重要指标是_____。

【答案】算法的时间复杂度和空间复杂度

10.高度为4的3阶B-树中,最多有_____个关键字。

【答案】26

【解析】第4层是叶结点,1层至3层每个结点两个关键字,每个节点的关键字达到最大时,关键字最多。

。 中每个元素的概率相等,则进行折半查找时的平均查找长度为_____。,求REPLACE(S,V ,m) =_____。 【解析】折半查找时每个的次数如表所示:

二、判断题

11.数据元素是数据的最小单位。( )

【答案】 ×

【解析】数据项是数据的不可分割的最小单位,而数据元素是数据的基本单位。

12.二叉树是一般树的特殊情形。( )

【答案】×

【解析】树与二叉树是两种不同的树形结构,二叉树中的孩子结点有着严格左右之分的。

13.顺序存储方式的优点是存储密度大,且插入、删除运算效率高。( )

【答案】 ×

【解析】前者正确,后者错误。顺序存储方式在插入、删除元素时需要挪动大量的元素,执

行效率较低。

14.如果数据元素保持有序,则查找时就可以采用折半查找方法。( )

【答案】×

【解析】采用折半查找的条件是数据元素有序且存储方式为顺序存储,对于常见的链式存储,在进行查找时主要依靠指针来操作。

15.负载因子(装填因子) 是哈希表的一个重要参数,它反映哈希表的装满程度。( )

【答案】√

【解析】查找过程中需和给定值进行比较的关键字的个数取决于三个因素:哈希函数,处理冲突的方法和哈希表的装填因子。其中装填因子标志哈希表的装满程度。

16.广义表(((a,b ,C) ,d ,e ,f)) 的长度是4。( )]

【答案】 ×

【解析】长度为1。因为只含一个元素即子表(((a,b ,C) ,d ,e ,f)) 。

17.对两棵具有相同关键字集合的而形状不同的二叉排序树,按中序遍历它们得到的序列的顺序却是一致的。( )

【答案】√

【解析】形状不同的两个二叉排序树(关键字集合相同) ,在中序遍历下是输出排好序的序列,所以顺序是一致的。

18.就平均查找长度而言,分块查找最小,折半查找次之,顺序查找最大。( )

【答案】×

【解析】折半查找最小,分块查找次之,顺序查找最大。分块查找的速度虽然不如折半查找算法,但比顺序查找算法快得多,同时又不需要对全部节点进行排序。当结点很多且块数很大时,对索引表可以采用折半查找,这样能够进一步提高查找的速度。

19.堆是满二叉树。( )

【答案】×

【解析】堆的定义:

n 个关键字序列

①②且且 称为堆,当且仅当该序列满足如下性质(简称为堆性质) : 小根堆:满足第①种情况的堆;

大根堆:满足第②种情况的堆。

因此并不能保证堆是满二叉树。