2017年中央民族大学信息工程学院856计算机学科专业综合之数据结构考研冲刺密押题（一）注意:①本试题所有答案应写在答题纸上,不必抄题,写清题号，写在试卷上不得分；②答卷需用黑色笔（钢笔，签字笔，圆珠笔）书写，用铅笔、红色笔等其他颜色笔答题，试题作废；③答卷上不得做任何与答题无关的特殊符号或者标记，否则按零分处理；④考试结束后试题随答题纸一起装入试题袋中交回。_、选择题1•对矩阵压缩存储是为了（1A方便运算B方便存储C.提高运算速度D.减少存储空间【答案】D［解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。2.在'TCP/IP体系结构中，直接为ICMP提供服务的协议是（1A.PPPB.IPC.UDPD.TCP【答案】B。【解析】首先明确ICMP是网络层的协'议，由于服务必须是下一层向上一层提供服务的，因此选项C项中的UDP和选项D项中的TCP属于传输层，在网络层上面，所以显然错误，而PPP协议是广域网数据链路层协议，直接为网络层，也就是IP层提供服务，ICMP协议是封装在网络层，因此PPP不能直接为ICMP提供服务，ICMP报文直接封装在IP分组中，故答案是B。3.下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（1A直接插入排序B起泡排序C.基数排序D.快速排序【答案】C［解析】C项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD三项都依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则不用移动，最坏情况元素反序，则需要移动n（n-1）/2次（为元素个数％4.浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均含2位符号位）。若有两个数X=27x29/32,Y=25x5/8,则用浮点加法计算X+Y的最终结果是（1A.001111100010B.001110100010C.010000010001D.发生溢出【答案】D［解析】浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤，难点在对阶、规格化、判溢出这三步。X和Y的阶码不同，所以应该先对阶，对阶原则为：小阶向大阶看齐。因此将Y对阶后得到：Y==2'x5/32.然后将尾数相加，得到尾数之和为：34/32。因为这是两个同号数相加，尾数大于1，则需要右规，阶码加1。由于阶码的位数为5位，且含两位符号位，即阶码的表示范围在-8〜+7之间。而阶码本身等于7,再加1就等于8。因此，最终结果发生溢出。5.每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（）个叶子。A.|典2〃］B.C.flog;（«+l）］D.【答案】D［解析］二叉树结点总数村队+叫+垣（no,ni，a分别代表度为0,度为1,度为2的结点数又在非空二叉树中：瞄m+l，且本题所给树为正则二叉树，叫=0,所以n=2*n°-l.因此11|=（04-1）/2O6.现在有一颗无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（1A根节点的度一定为2B.树中最小元素一定是叶节点C.最后插入的元素一定是叶节点D.树中最大元素一定是无左子树【答案】D［解析］二叉树的中序遍历定义是“若二叉树为空，则空操作；否则：①中序遍历左子树；②访问根节点；③中序遍历右子树”。A项错误，当树中仅有一个或者两个结点时，根节点的度就可能不为2；B项错误，树中最小元素是中序遍历时最后访问的节点，当没有右子树时，最后访问的节点是根节点；C项错误，当最后插入的元素破坏树的平衡后，树会进行调整，使其成为中间节点；D项正确，由中序遍历的特点可知，左子树的值大于根节点，所以最大元素一定没有左子树。7.某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微程序，各指令对应的微程序平均由4条微指令组成，采用断定法(下址字段法)确定下条微指令的地址，则微指令中下址字段的位数至少是：()A.5B.6C.8D.9【答案】c【解析】32*4+2=130,27=128<130<2s=256.所以至少需要8位才能表示完130个哽。8.广义表A=(a,b,(c,d),(e,(f,g))),则式子Head(Tail(Head(Tail(Tail(A)))))的值为(XA.(g)B.(d)C.cD.d【答案】D【解析】head操作就是得到广义表中第一个的原子。tail操作就是