《2018年武汉科技大学856数据结构(C语言版)[专业硕士]考研基础五套测试题.doc》由会员分享,可在线阅读,更多相关《2018年武汉科技大学856数据结构(C语言版)[专业硕士]考研基础五套测试题.doc(4页珍藏版)》请在金锄头文库上搜索。
1、2018年武汉科技大学856数据结构(C语言版)专业硕士考研基础五套测试题-一、单项选择题1 已知串A.0123B.1123C.1231D.1211【答案】A【解析】KMP 算法的next 数组建立的原则其Next 数组值为( )。 2 下列选项给出的是从根分别到达两个叶节点路径上的权值序列, 能属于同一棵哈夫曼树的是( )。A.24, 10, 5和24, 10, 7B.24, 10, 5和24, 12, 7C.24, 10, 10和24, 14, 11D.24, 10, 5和24, 14, 6【答案】D【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中, 第二个被访问
2、的两个结点的权值要么相等, 要么和为根节点的权值, 故B 项错误。同理, 通过第三个被访问的节点排除A 项。C 项, 由两条路径可推出三个叶子节点的权值分别是:3、10和11, 而根据哈夫曼树的定义可知, 权值为3的节点应该和权值为10的结点结合, 故C 项错误。D 项, 反推出有四个叶子节点, 权值分别为:5、5、6和8, 满足哈夫曼树的条件。 3 下列给出的指令系统特点中, 有利于实现指令流水线的是( )。. 指令格式规整且长度一致. 指令和数据按边界对齐存放. 只有Load/Store指令才能对操作数进行存储访问A. 仅、B. 仅、C. 仅、D. 、【答案】D【解析】特点和都是RISC
3、机的特征, 而特点则有利于指令和数据的存放, 所以以上三个特点都有利于实现指令流水线。 4 执行完下列语句段后,f 值为( )。 A.2B.4C.8D. 无限递归【答案】B【解析】该程序使用了递归调用,由题知,:f(0)2;f(l)l*f(0)2;f(2)2*f(l)4;所以结果为4。 5 为提高散列(Hash)表的查找效率, 可以采用的正确措施是( )。. 增大装填(载) 因子. 设计冲突(碰撞) 少的散列函数. 处理冲突(碰撞) 时避免产生聚集(堆积) 现象A. 仅B. 仅C. 仅、D. 仅、【答案】D【解析】散列表的查找效率(比较次数) 取决于:散列函数、处理冲突的方法和散列表的装填因子
4、。标志着散列表的装满程度, 通常情况下, 越小, 发生冲突的可能性越小; 反之, 越大, 表示已填入的记录越多, 再填入记录时, 发生冲突的可能性越大。因此选项错误, 越是增大装填因子, 发生冲突的可能性就越大, 查找效率也越低。选项正确。选项正确。采用合适的处理冲突的方法避免产生聚集现象, 也将提高查找效率。例如, 用拉链法解决冲突时不存在聚集现象, 用线性探测法解决冲突时易引起聚集现象。 6 下列选项中会导致进程从执行态变为就绪态的事件是( )。A. 执行P(wait)操作B. 申请内存失败C. 启动设备D. 被高优先级进程抢占【答案】D【解析】D 项, 被高优先级进程抢占, 进程会由执行
5、态变为就绪态。ABC 三项, 程序由于缺少资源而由执行态转为阻塞态。 7 将森林转换为对应的二叉树,若在二叉树中,结点u 是结点v 的父结点的父结点,则在原来的森林中,u 和v 可能具有的关系是( ).(1)父子关系(2)兄弟关系(3)U的父结点与V 的父结点是兄弟关系A. 只有(1)B.(1)和(2)C.(1)和(3)d.(1)、(2)和(3)【答案】B【解析】首先,在二叉树中,若结点U 是结点v 的父结点的父结点,那么u 和v 的关系有如下4种情况: 接下来,根据森林与二叉树的转换规则,将这4种情况还原成森林中结点的关系. 其中: 情况(1),在原来的森林中u 是v 的父结点的父结点;情况(2),在森林中u 是v 的父结点;情况(3),在森林中u 是v 的父结点的兄弟;情况(4),在森林中u 与v 是兄弟关系.由此可知,题目中的(1)、(2)是正确的. 8 在采用中断方式控制打印输出的情况下, CPU 和打印控制接口中的息不可能是( )。A. 打印字符B. 主存地址C. 设备状态D. 控制命令【答案】B端口之间交换的信-一、单项选择题-考研试题-