《2018年东北财经大学计算机应用技术806计算机综合之数据结构考研基础五套测试题.doc》由会员分享，可在线阅读，更多相关《2018年东北财经大学计算机应用技术806计算机综合之数据结构考研基础五套测试题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2018年东北财经大学计算机应用技术806计算机综合之数据结构考研基础五套测试题一、单项选择题1 若一棵完全二叉树有768个结点, 则该二叉树中叶结点的个数是（ ）。A.257B.258C.384D.385【答案】C【解析】由和可知, , 即, 显然则384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个性质:最后一个分支结点的序号为, 故非叶子结点数为384, 而叶子结点的个数为) 。 。(表示不大于x 的最大整数, 比如 2 有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（ ）。A.543612B.453126C.346521D.234156【答案】C
2、【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出枝。 3 用哈希(散列) 方法处理冲突(碰撞) 时可能出现堆积(聚集) 现象, 下列选项中, 会受堆积现象直接影响的是（ ）A. 存储效率B. 数列函数C. 装填(装载) 因子D. 平均查找长度【答案】D【解析】哈希方法冲突会使在查找冲突的关键字时, 还要根据冲突处理办法多次比较关键字, 则直接影响了平均查找长度。 4 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要
3、进行多少次探测？（ ）A.k 1次B.k 次C.k+1次 D.【答案】D【解析】至少探测次数。 5 下列选项中，操作系统提供的给应用程序的接口是（ ）.A. 系统调用B. 中断C. 库函数D. 原语【答案】A【解析】操作系统提供给用户应用程序的接口只有两种:命令输入和系统调用. 其中，命令输入又有不同的形式，例如常规的命令行、图形化人机交互接口(GUI)、自然命令用户接口(NUI)等，而系统调用中除了常规的一些传统的系统调用(例如read （ ）) 以外，还有经过扩展的复杂调用(例如多种API) ，以及包含在Lib 库中的各种封装好的过程调用(最终都是通过系统调用陷入到操作系统中去的）等. 6
4、 某计算机主存地址空间大小为256MB , 按字节编址。虚拟地空间大小为4GB , 采用页式存储管理, 页面大小为4KB , TLB(快表) 采用全相联映射, 有4个页表项, 内容如下表所示。次 则对虚拟地址03FFF180H 进行虚实地址变换的结果是（ ）A.0153180HB.0035180HC.TLB 缺失D. 缺页【答案】A【解析】虚拟地址为03FFF180H , 其中页号为03FFFH , 页内地址为180H , 根据题目中给出的页表项可知页标记为03FFFH 所对应的页框号为0153H ,页框号与页内地址之和即为物理地址。 7参考模型的网络层提供的是（ ）。A. 无连接不可靠的数据
5、报服务B. 无连接可靠的数据报服务C. 有连接不可靠的虚电路服务D. 有连接可靠的虚电路服务【答案】A【解析】TCP/IP的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务, 因此答案是A 。 8 设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，A00存放于B0中，那么第i 行的对角元素Aii存放于B 中（ ）处。A.(i3)*i/2B.(i1)*i/2C.(2ni l)*i/2D.(2ni l)*i/2【答案】A【解析】Aii中列标不大于行标，又A00存放在B0中，所以Aii存放的位置为i*(il)/2i l l i*(i3)/2。 9 下列选项
6、中, 不可能是快速排序第2趟排序结果的是（ ）A.2, 3, 5, 4, 6, 7, 9B.2, 7, 5, 6, 4, 3, 9C.3, 2, 5, 4, 7, 6, 9D.4, 23, 5, 7, 6, 9【答案】C【解析】对于快速排序, 每一趟都会使一个元素位于有序时的位置, 而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比, 只有9位于它有序的时候的位置, 显然不是第二趟快速排序的结果 10对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。A.(2，5，12，16)26(60，32，72)B.(5，16，2，12)28(60，32，72)C.(2，16，12，5)28(60，32，72)D.(5，16，2，12)28(32，60，72)【答案】B【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。第一次比较:28比72小，不交换;一、单项选择题考研试题
