2020江西国家电网校园招聘考试：数据结构与算法自测（9）

1.队列是一种（   ）的线性表。
A.先进先出  B.先进后出 
C.只能插入  D.只能删除
 
2.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（   ）比较大小，查找结果是失败。
A.20，70，30，50       B.30，88，70，50      
C.20，50      D.30，88，50
 
3.元素3,1,2一次全部进入一个栈陆陆续续出栈操作，得到的很出栈序列为（   ）。
A.321 B.312
C.123 D.213
 
4.把一棵树转换为二叉树后，这棵二叉树的形态是（   ）。
A.唯一的                          
B.有多种  
C.有多种，但根结点都没有左孩子    
D.有多种，但根结点都没有右孩子
 
5.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（   ）。
A.M1           B.M1+M2       
C.M3            D.M2+M3  
 
1.【答案】A。解析：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
2.【答案】A。解析：首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
3.【答案】D。解析：栈的特点是先进后出，而题干中的三个元素是一次性全部入栈（注意入栈顺序为3、1、2），所以出栈时也是三个元素一次出栈，根据特点可知，出栈顺序为2、1、3。
4.【答案】A。解析：树转换成二叉树，根节点是没有右孩子的，这由转换规则应该不难理解，且转换规则是唯一的，所以转换成的二叉树是唯一的。
5.【答案】D。解析：第一棵树构成根和左子树,因此右子树上的结点个数就是M2 + M3。