2018年天津大学理学院901数据结构与程序设计之数据结构考研基础五套测试题
● 摘要
一、填空题
1． 实现字符串拷贝的函数strcpv 为:
(_____)
【答案】s++＝*t++或(*s++＝*t++)!＝'\0‟
2． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。
【答案】15
2n
【解析】当时，100n2>2n，而，时，100n ＜2
3． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录
的_____。
【答案】比较；移动
4． 索引顺序文件既可以顺序存取，也可以 _____存取。
【答案】随机
5． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
。当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为一个元素时，此时堆的元素个数最少，元素个数为。
6． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
7． 有向图G=(V, E) ，其中权d 。E(G)为
第 2 页，共 60 页
，用三元组表示弧及弧上的
，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。
【答案】50；4
8． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
h 为附加头结点指针
(_____)
_____；
【答案】(1)p!＝NULL //链表未到尾就一直进行 (2)q //将当前结点作为头结点后的第一元素结点插入
9． 在循环队列中，队列长度为n ，存储位置从0到，n ﹣1编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是_____。
【答案】
10．设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。在下面的算法中，free_tree(T)在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点
；
，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下
处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。
【答案】
11．文件由_____组成；记录由_____组成。
【答案】记录；数据项
第 3 页，共 60 页
12．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增 量序列) 依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; (10，7，-9，0，47，23，1，8，98，36)
13．栈是_____的线性表，其运算遵循_____的原则。
【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出
14．已知t) ，LEN(t)＋1))
:
【答案】
；
；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，，求REPLACE(S，V ，m) ＝_____。
15．在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是
。
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
二、单项选择题
16．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表 C. 双链表
D. 仅有尾指针的单循环链表 【答案】D
【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。
17．一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个 【答案】C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A
第 4 页，共 60 页