2018年北京师范大学资源学院978数据结构考研核心题库
● 摘要
一、填空题
1． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
2． VSAM(虚拟存储存取方法) 文件的优点是:动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
3． 一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
4． 建立索引文件的目的是_____。
【答案】提高查找速度
5． 当两个栈共享一存储区时，栈利用一维数组stack(1，，1) 表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。
【答案】0；n+1；top[l]+l＝top[2]
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
6． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
7． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH ，中序序列是FEBGCHD ，则它的后序序列是_____。设上述二叉树是由某棵树转换而成，则该树的前序序列是_____
【答案】FEGHDCB ；BEF
【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF 。
8． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
9． 深度为H 的完全二叉树至少有_____个结点:至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】
10．如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，
请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为
其中:left 指向其左孩子，
【答案】
left 指向其前驱；，right 指向其后继。
， right 指向其右孩子，，，
11．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____；而又根据指针的连接方式，链表又可分成_____和_____。
【答案】单链表；双链表；(动态) 链表；静态链表
【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。
12．
给定一组数据以它构造一棵哈夫曼树，则树高为_____，带权路径长度WPL 的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树:
13．外排序的基本操作过程是_____和_____。
【答案】生成有序归并段(顺串) ；归并
14．顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【答案】if(top!＝n)data[++top]＝x ；
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
15．已知二维数组中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是: _____。
【答案】1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4
二、单项选择题
16．算法的计算量的大小称为计算的（ ）。
A. 效率
B. 复杂性
C. 现实性
D. 难度
【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。
17．下列选项中, 不可能是快速排序第2趟排序结果的是（ ）
A.2, 3, 5, 4, 6, 7, 9
B.2, 7, 5, 6, 4, 3, 9
C.3, 2, 5, 4, 7, 6, 9
D.4, 23, 5, 7, 6, 9
【答案】C
【解析】对于快速排序, 每一趟都会使一个元素位于有序时的位置, 而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比, 只有9位于它有序的时候的位置, 显然不是第二趟快速排序的结果
18．当系统发生抖动(thrashing)时, 可以采取的有效措施是（ ）。
Ⅰ. 撤销部分进程
Ⅱ. 增加磁盘交换区的容量
Ⅲ. 提高用户进程的优先级
A. 仅Ⅰ