目录
北京交通大学计算机与信息技术学院925数据结构考研导师圈点必考题汇编(一).... 2 北京交通大学计算机与信息技术学院925数据结构考研导师圈点必考题汇编(二).. 11 北京交通大学计算机与信息技术学院925数据结构考研导师圈点必考题汇编(三).. 22 北京交通大学计算机与信息技术学院925数据结构考研导师圈点必考题汇编(四).. 30 北京交通大学计算机与信息技术学院925数据结构考研导师圈点必考题汇编(五).. 40
第 1 页，共 48 页
一、填空题
1． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。
【答案】
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。
2． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
3． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
4． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为
5． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。(3在4之前出栈)
【答案】3个
【解析】以3, 4先出栈的序列有34521、34215、34251共3个。
6． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
第 2 页，共 48 页
.
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
7． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
8． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
9． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
10．设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
11．从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m
阶个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；
12．已知一循环队列的存储空间为环队列判满的条件是( )
【答案】
13．外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段(顺串)
14．下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
第 3 页，共 48 页
树每个结点至多有_____个儿子，除
根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____
其中队头和队尾指针分别为front 和rear , 则此循
【答案】
【解析】快速排序(quicksort )的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
15．循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
二、选择题
16．对线性表进行折半查找时，要求线性表必须( )。
A. 以顺序方式存储B. 以顺序方式存储，且数据元素有序 C. 以链接方式存储D. 以链接方式存储，且数据元素有序 【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
17．在一个文件被用户进程首次打开的过程中，操作系统需做的是( )
A. 将文件内容读到内存中 B. 将文件控制块读到内存中 C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程 【答案】B
第 4 页，共 48 页
北京交通大学计算机技术导师目录 北京交通大学计算机与信息技术学院925数据结构考研导师圈点必考题汇编...
