《2016年长春师范大学计算机科学与技术学院数据结构(同等学力及跨学科加试)复试笔试仿真模拟题.doc》由会员分享，可在线阅读，更多相关《2016年长春师范大学计算机科学与技术学院数据结构(同等学力及跨学科加试)复试笔试仿真模拟题.doc（3页珍藏版）》请在金锄头文库上搜索。
1、2016年长春师范大学计算机科学与技术学院数据结构(同等学力及跨学科加试)复试笔试仿真模拟题一、选择题1 在采用中断I/O方式控制打印输出的情况下，CPU 和打印控制接口中的I/O端口之间交换的信息不可能是（ ）。A. 打印字符 B. 主存地址 C. 设备状态 D. 控制命令 【答案】B【解析】I/O接口的功能包括：选址功能；传送命令功能；传送数据功能；反映I/O设备工作状态功能。A 项为数据，C 项为设备状态，D 项为命令。B 项，主存地址在中断方式控制下是不需要的，因此，它不可能是CPU 和打印控制接口中的I/O端口之间交换的信息。2 G=V E ，已知有向图（），其中G 的拓扑序列是（
2、）。 【答案】A【解析】设G=（V ，E ）是一个具有n 个顶点的有向图，V 中顶点序列能被称，则在序列中顶点Vi 为拓扑序列的条件：若是图中的边（即从顶点V i 到V j 有一条路径）必须排在顶点Vj 之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列是 3 若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是（ ）。A.1, 2.3.4 B.2，3, 4.1 C.3, 2, 4, 1 D.4, 3, 2, 1【答案】C【解析】题目中的二叉树的先序序列和后序序列正好相反，这样的二叉树每层只有一个结点。该二叉树的形态如下图所
3、示。 从左至右，这8棵二叉树的中序序列分别为： （1）4. 3. 2. 1， （2）3, 4, 2, 1 （3）2, 4, 3, 1 （4）2, 3, 4，1 （5）1，4，3, 2 （6）1, 3, 4, 2 （7）1，2, 4, 3 （8）1, 2, 3, 4显然选项C 的中序序列不会出现。4 已知一棵有2011个结点的树，其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。A.115 B.116 C.1895 D.1896 【答案】D【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点（因为一个非终端结点，另外，树根结点转至少有一个孩子结点，其最右边的孩子结点转
4、换成二叉树后一定没有右孩子）换成二叉树后也没有右孩子。题目中树的总结点数是2011，叶结点个数是116, 则非终端结点个数是2011-116=1895, 则该树对应的二叉树中 无右孩子的结点个数是1895+1=1896。 5 在OSI 参考模型中，直接为会话层提供服务的是（ ）A. 应用层 B. 表示层 C. 传输层 D. 网络层 【答案】C【解析】OSI 参考模型中，下层直接为上层提供服务，而会话层的下层为传输层。6 程序P 在机器M 上的执行时间是20秒，编译优化后，P 执行的指令数减少到原来的CPI 増加到原来的1.2倍，则P 在M 上的执行时间是（ ）A.8.4 秒 B.11.7 秒
5、C.14 秒 D.16.8 秒 【答案】D【解析】 7 链表不具有的特点是（ ）。A. 插入、删除不需要移动元素 B. 可随机访问任一元素 C. 不必事先估计存储空间 D. 所需空间与线性长度成正比 【答案】B而【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置，线性表中的任一数据元素都可随机存取。 8 知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。A.CBEFDA B.FEDCBA C.CBEDFA D. 不定【答案】A【解析】由前序结果可知A 为根节点，再由中序遍历结果知BC 为A 的左孩子，且C 为B 的左孩子结点，到此可排除B 项，按照这种逻辑依次推理，便可得出结果对于该类型题目，可以先根据前序遍历结果和中序遍历结果画出二叉树，然后后序遍历二叉树得到后序遍历序列。 9 算法的计算量的大小称为计算的（ ）。A. 效率 B. 复杂性 C. 现实性 D. 难度 【答案】B【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。 一、选择题考研试题
