《2017年西南交通大学信息科学与技术学院959数据结构[专业学位]考研题库.doc》由会员分享，可在线阅读，更多相关《2017年西南交通大学信息科学与技术学院959数据结构[专业学位]考研题库.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年西南交通大学信息科学与技术学院959数据结构专业学位考研题库一、选择题1 设有数组数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内的存储首地址为（ ）。 【答案】B【解析】在计算中，可以考虑按照列存放时，址。比如顺序存放时，它是第 在内存的位置，比较容易计算元素的首地个元素，由于首地址为BA ，所以它的存储首地址为存首地址BA 开始顺序存放，当用以列为主存放时，元素 2 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）。A. 仅修改队头指针 B. 仅修改队尾指针C. 队头、队尾指针都可能要修改 D. 队头、
2、队尾指针都要修改 【答案】C【解析】用不带头结点的单链表存储队列，一般删除操作仅修改队头指针，但当队列中只有一个结点时，进行删除操作要将队头、队尾指针都修改成NULL 。 3 以下数据结构中，（ ）是非线性数据结构。A. 树 B. 字符串 C. 队 D. 栈 【答案】A【解析】非线性结构是指存在一对多或者多对一的关系。常见的非线性结构有树结构和图结构。 4 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。 【答案】B【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。第一次比较：28比72小，不交换； 第二
3、次比较：28比5大，交换，此时为第三次比较：16比28小，不交换； 第四次比较：32比28大，交换，此时为第五次比较：28比2大，交换，此时为第六次比较：28比12大，不交换； 第七次比较：28比60小，交换，此时为 一次划分结束。5 知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。A.CBEFDA B.FEDCBA C.CBEDFA D. 不定【答案】A【解析】由前序结果可知A 为根节点，再由中序遍历结果知BC 为A 的左孩子，且C 为B 的左孩子结点，到此可排除B 项，按照这种逻辑依次推理，便可得出结果对于该类型题目，可以先根据前序遍历结果
4、和中序遍历结果画出二叉树，然后后序遍历二叉树得到后序遍历序列。 6 在一棵具有15个关键字的4阶B 树中，含关键字的结点数最多是（ ）A.5 B.6 C.10 D.15【答案】D【解析】m 阶B 树非根结点含关键字个数 4阶B 树非根结点含关键字1?3个，所以要使关键字结点数量最多，那么每个结点只有一个关键字，一共有15个关键字那么最多有15个含有关键字的结点 7 一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（ ）。A.11 B.12 C.13 D.14【答案】B8 下列选项中的英文缩写均为总线标准的是（ ）。A.PCI 、CRT 、USB 、EISA B.ISA 、C
5、PI 、VESA 、EISA C.ISA 、SCSI 、RAM 、MIPS D.ISA 、EISA 、PCI 、PCI-Express 【答案】D【解析】选项A 中的CRT 和USB 、选项B 中的CPI 、选项C 中的RAM 和MIPS 均不是总线标准的英文缩写，只有选项D 中的英文缩写均为总线标准。 9 某设备中断请求的相应和处理时间为100m ，每400ns 发出一次中断请求，中断相应所容许的最长延迟时间为50ns , 贝U 在该设备持续工作过程中CPU 用于该设备的百分比至少是（ ）A.B.C.D. 【答案】B【解析】每400m 响应一次中断并且用100m 进行处理，所以该设备的时间占
6、用CPU 时间百分比为中断响应容许的延迟时间对此没有影响，属于干扰条件。 10将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。A.4 B.5 C.6 D.7【答案】C【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个全二叉树的高度为叉树的高度为 或或 结点的完由完全二叉树类推到完全三叉树可知，n 个结点的完全三时间占整个CPU 时间二、填空题11外排序的基本操作过程是_和_。；归并 【答案】生成有序归并段（顺串）12已 求REPLACE （S ，V , m ）=_。【答案】 13对n 个记录的表rl.n进行简单选择排序，所需进行的关键字间的比较次数为_。【答案】n （n-1）/2【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+.+l=n（n-l ）知一、选择题考研试题
