2017年济南大学信息科学与工程学院845软件工程专业综合之数据结构考研题库
● 摘要
一、选择题
1． 冯. 诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）。
A. 指令操作码的译码结果
B. 指令和数据的寻址方式
C. 指令周期的不同阶段
D. 指令和数据所在的存储单元
【答案】C
【解析】在冯•诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段（分析取数阶段、执行阶段）取出的是数据。所以，CPU 区分指令和数据的依据是指令周期的不同阶段。
2． 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树
B. 哈夫曼树 C.
D. 堆
【答案】D
【解析】堆的定义：
n 个关键字序列
（1）（2）且且或 称为堆，当且仅当该序列满足如下性质（简称为堆性质）： 树
满足第（1）种情况的堆，称为小顶堆；满足第（2）种情况的堆，称为大顶堆。
由堆的定义可知堆可以满足上述性质。
3． 对给定的关键字序列110, 119, 007, 911，114，120, 122进行基数排序，则第2趟分配收集后得到的关键字序列是（ ） A.
B.
C.
D.
【答案】C
【解析】基数排序的第1趟排序是按照个位数字来排序的，第2趟排序是按然十位数字的大小进行排序的，故答案是C 选项。
4． —棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有（ ）个结点。
A.2h B. C. D.
【答案】B
【解析】此树满足哈夫曼树，除根节点外每层有两个节点。
5． 假定用若干个2Kx4位的芯片组成一个8Kx8位的存储器，则地址0B1FH 所在芯片的最小地址是（ ）。
A.0000H
B.0600H
C.0700H
D.0800H
【答案】D
【解析】由若干芯片构成存储器，采用字和位同时扩展方法。8片2Kx4位的芯片分成4组，每组2个芯片，各组芯片的地址分配分别为：第1组，0000H 〜07FFH ; 第2组，0800H 〜0FFFH ; 第3组，1000H 〜17FFH ; 第4组，1800H 〜1FFFH 。地址0BIFH 处于第2组内，其芯片的最小地址为0800H 。
6． 如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（ ）。
A.1条，1条
B.1条，多条
C. 多条，1条
D. 多条，多条
【答案】A
【解析】所谓递归查询方式就是：如果主机所询问的本地域名服务器不知道被查询域名的IP 地址，那么本地域名服务器就以DNS 客户的身份向其他服务器继续发出查询请求报文，而不是让该主机自行下一步的查询。所以主机只需向本地域名服务器发送一条域名请求，采用递归查询方法，本地域名服务器也只需向上一级的根域名服务器发送一条域名请求，然后依次递归。正确选项为A 。
7． 若元素a ，b , c, d, e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。
A.d ，c ，e ，b ，f ，a
B.c ，b ，d ，a ，e ，f
C.b ，c ，a ，e ，f ，d
D.a ，f ，e ，d ，c ，b
【答案】D
【解析】4个选项所给序列的进、出栈操作序列分别为：
选项A.Push , Push , Push ，Push , Pop, Pop, Push，Pop , Pop, Push , Pop ，Pop
选项B.Push , Push , Push , Pop , Pop , Push, Pop, Pop, Push, Pop , Push, Pop
选项C.Push , Push , Pop , Push , Pop , Pop, Push, Push, Pop, Push , Pop , Pop
选项D.Push , Pop , Push, Push , Push , Push, Push, Pop, Pop，Pop , Pop , Pop
按照题目要求，不允许连续三次进行退栈操作，所以选项D 所给序列为不可能得到的出栈顺序。
8．
用户程序发出磁盘
是（ ）
A. 用户程序
B. 系统调用处理程序
C. 设备驱动程序
D. 中断处理程序
【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的，所以答案选C 。
9． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
【答案】B
【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为
10．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）
。
【答案】B
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：28比72小，不交换；
第二次比较：28比5大，交换，此时为
请求后，系统的处理系统的处理流程是：用户程序一系统调用处理程序一设备骆动程序一中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序