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 个关键字序列
①②且且 称为堆,当且仅当该序列满足如下性质(简称为堆性质) : 小根堆:满足第①种情况的堆;
大根堆:满足第②种情况的堆。
因此并不能保证堆是满二叉树。