2016年北京科技大学计算机与通信工程学院547软件综合之数据结构考研复试题库
● 摘要
目录
2016年北京科技大学计算机与通信工程学院547软件综合之数据结构考研复试题库（一） ... 2
2016年北京科技大学计算机与通信工程学院547软件综合之数据结构考研复试题库（二） ... 9 2016年北京科技大学计算机与通信工程学院547软件综合之数据结构考研复试题库（三） . 17 2016年北京科技大学计算机与通信工程学院547软件综合之数据结构考研复试题库（四） . 24 2016年北京科技大学计算机与通信工程学院547软件综合之数据结构考研复试题库（五） . 33
一、选择题
1． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便地进行插入与删除
C. 为了能方便地找到双亲
D. 使二叉树的遍历结果唯一
答:A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
2． 先序序列为a , b，c , d的不同二叉树的个数是（ ）。
A.13
B.14
C.15
D.16
答:B
【解析】二叉树的先序遍历定义为：若二叉树为空，则空操作；否则，访问根节点，然后先序遍历左子树，最后先序遍历右子树。本题中，结点a 为二叉树的根节点，左右子树的先序遍历可能存在下面四种情况：①左子树为空，bed 为右子树；②b 为左子树，cd 为右子树；③be 为左子树，d 为右子树；④bed 为左子树，右子树为空。然后将左右子树继续分解，如第①种情况的右子树先序遍历（bed ）可能有：a. 左子树为空，右子树为cd ；b. 左子树为c ，右子树为d ；c. 左子树为cd ，右子树为空。按照这种方法继续分解左右子树，直到不能再分解为止，可得第①和④种情况各包含5种不同情况，第②和③种情况各包含2种情况，因此总共有14种不同的二 叉树。
3． 若将关键字1，2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）
A.0
B.1
C.2
D.3
答:D
【解析】将图中给定的关键字序列依次插入到平衡树中，构成的平衡树如下图所示，由图可知平衡因子为0的分支结点为3个叶子结点，故答案为D 。
4． 下列关于闪存（FlashMemory ）的叙述中，错误的是（ ）。
A. 信息可读可写，并且读、写速度一样快
B. 存储元由MOS 管组成，是一种半导体存储器
C. 掉电后信息不丢失，是一种非易失性存储器
D. 采用随机访问方式，可替代计算机外部存储器
答:A 。
【解析】考查闪存的特性，闪存是EEPROM 的进一步发展，可读可写，用MOS 管的浮栅上有无电荷来存储信息，它依然是ROM 的一种，故写速度比读速度要慢不少。闪存是一种非易失性存储器，它采用随机访问方式，现在常见的SSD 固态硬盘就是由flash 芯片组成的，故答案为A 。
5． 在参考摸型中，下列功能需由应用层的相邻层实现的是（ ）
A. 对话管理
B. 数据格式转换
C. 路由选择
D. 可靠数据传输
答:B
【解析】应用层的相邻层即为表示层，表示层负责管理数据的压缩、加密与解密、格式装换等，故答案为B 。
6． —
组记录的关键码为
准得到的一次划分结果为（ ）。
答:C
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：46比84小，不交换；
第二次比较：40比46小，交换，此时为
第三次比较：46比79小，交换，此时为
第四次比较：38比46小，交换，此时为
则利用快速排序的方法，以第一个记录为基