2017年西南石油大学理学院925数据结构考研题库
● 摘要
一、填空题
1． 顺序栈用
【答案】
存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
2． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
【答案】
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
3． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
【答案】
4． 在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
5． 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m
阶个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；
6． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
树每个结点至多有_____个儿子，除
根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____
7． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）
8． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
9． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
【答案】（1）（2）（3）（4）（5）
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
10．己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
二、判断题