2018年天津大学软件学院901数据结构与程序设计之数据结构考研核心题库
● 摘要
一、填空题
1． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
2． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】O(m＋n)
3． 在基于关键字比较且时间为
【答案】归并；堆
4． 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _____；_____；
【答案】py ﹣＞next ＝px ﹣＞next ；px ﹣＞next ＝py
5． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
6． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
第 2 页，共 59 页
_ 的排序中，若要求排序是稳定的，则可选用_____
排序；若要求就地排序(及辅助空间为O(1))，则可选用_____排序。
a 中存放待排序的关键字
【答案】
【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
7． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【答案】if(top!＝n)data[++top]＝x ；
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
8． 以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。
【答案】
第 3 页，共 59 页
9． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉树。故结点个数为。
10．已知有序表为(12，18，24，35，47，50，62，83，90，115，134) 当用二分法查找90时，需次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2; 4; 3
【解析】二分法查找元素次数列表
查找100是找到115就停止了。 11．_____；串是一种特殊的线性表，其特殊性表现在_____；串的两种最基本的存储方式是_____、两个串相等的充分必要条件是_____。
【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等
12．试利用下列栈和串的基本操作完成下述填空题。
initstack(S)置S 为空栈； push(S，X) 元素X 入栈； pop(S)出栈操作； gettop(S)返回栈顶元素； sempty(S)判栈空函数； setnull(St)置串St 为空串； length(st)返回串st 的长度；
equal(S1，S 2) 判串S 1并S 2是否相等的函数； concat(S1，S 2) 返回联接S 1和S 2之后的串； sub(S，i ，1) 返回S 中第i 个字符； empty(st)判串空函数
FUNCinvert(pre:string ；V ARexp :string) :boolean ；
{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true ，否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。
)
第 4 页，共 59 页