2017年北京联合大学信息无障碍辅助技术803软件基础之数据结构考研题库
● 摘要
一、填空题
1． 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m
阶个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织； 2
．
求REPLACE （S ，V , m ）=_____。
【答案】
3． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
第 2 页，共 57 页
树每个结点至多有_____个儿子，除
根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____
知
已
【答案】
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
4． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
5． 模式串
的next 函数值序列为_____。
【答案】01122312
6． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。
Prior （node , x ） { if（node !=null）
If （ （1） ） *x=node->right；else * x-node->left;
}
next （bt , node, x ）/*bt是二叉树的树根*/ { （2） ;
if （node->rflag）（3）; else {do t=*x；; while （*x==node ）; *x=t; } }
【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）
7． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。
【答案】O （eloge ）; 边稀疏
8． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
9． 索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机
第 3 页，共 57 页
10．栈是_____的线性表，其运算遵循_____的原则。
；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）
二、选择题
11．若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（ ）。
A. 在进程结束时能进行处理机调度 B. 创建新进程后能进行处理机调度 C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度 【答案】C 。
【解析】对于A 、B 、D 显然是可以进行处理机调度的，对于C , 当进程处于临界区时，只要不破坏临界资源的使用规则，是不会影响处理机调度的，比如，通常访问临界资源可能是慢速的，如果在进程访问打印机时，不能处理机调度，那么系统的性能将是非常低的。外设（如打印机）
几种不进行处理机调度的情况如下：①在处理机中断的过程中；②进程在操作系统内核程序临界区中；③其他需要完全屏蔽中断的原子操作过程中。
12．下面关于B 和B+树的叙述中，不正确的是（ ）
A.B 树和B+树都是平衡的多叉树 B.B 树和B+树都可用于文件的索引结构 C.B 树和B+树都能有效地支持顺序检索 D.B 树和B+树都能有效地支持随机检索 【答案】C
【解析】B 树是一种平衡的多分树，通常我们说m 阶的B 树，它必须满足如下条件：①每个结点至多有m 个子结点；②除根结点和叶结点外，其它每个结点至少有个子结点；③若根结点不是叶子结点，则至少有两个子结点；④所有的叶结点在同一层；⑤有k 个子结点的非根结点恰好包含k-1个关键码。B+树是B 树的一种变形树，它与B 树的差异在于：有k 个子结点的结点必然有k 个关键码；非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。其中B 树适合与随即检索，不适合于顺序检索，所以C 项错误。
13．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（ ）型调整以使其平衡
【答案】C
【解析】A 的平衡因子此时为-1，要使插入结点不平衡，必须插在右孩子的左子树上，A 平衡因子变成了-2，则需要进行两次旋转（先右旋后左旋）。
第 4 页，共 57 页