2017年山东师范大学管理科学与工程学院836数据结构A考研导师圈点必考题汇编
● 摘要
目录
2017年山东师范大学管理科学与工程学院836数据结构A 考研导师圈点必考题汇编（一） . .. 2 2017年山东师范大学管理科学与工程学院836数据结构A 考研导师圈点必考题汇编（二） . 10 2017年山东师范大学管理科学与工程学院836数据结构A 考研导师圈点必考题汇编（三） . 17 2017年山东师范大学管理科学与工程学院836数据结构A 考研导师圈点必考题汇编（四） . 24 2017年山东师范大学管理科学与工程学院836数据结构A 考研导师圈点必考题汇编（五） . 31
一、填空题
1． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
【答案】
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
2． 以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。
void leafchain（BiTree Abt）
{p={BiTree）malloc （sizeof （BiTNode ））;
If （!p ）{print£（“OVERFLOW\n”; exit （1）; } head=p; top=0; if （bt ）
{top++; stack[top]=bt; while （top ）
{t=stack[top]; top--;
if （it->Lchild && !t->Rchild）{ （1） ; （2） ; （3） ; } else {if（ （4） ）{top++; stack[top]= （5） ; } if （ （6） ）{top++; stack[top]= （5） ; } } }
（8） ; （9） ; } } 【答案】
p->Rchild=t:t->Lchild=p:p=t: t->Rchild!=null:t->Rchild: t->Lchild!=null: t->Lchild: p->Rchild=head:head->Lchild=p 3． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为
4． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
5． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
6． 设广义表
则
是_____tail（L ）是_____；L 的长度是_____；深度是_____。
；；2；2 【答案】（ ）（（ ））
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
7． 关键码序列（Q ，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X ），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。
【答案】（Q ，A ，C ，S ，Q ，D ，F ，×，R ，H ，M ，Y ）; （F ，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X ）
【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接
插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
8． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
9． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
10．属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
二、算法设计题
11．已知一具有n 个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组
和
中（设该二叉树各结点的数据值均不相同）。请写一建立该二叉树的二叉链表结构的非
递归算法。该二叉链表的 链结点结构为（lchild ，data , rchild ）, 其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域 （当孩子结点不存在时，相应指针域为空，用nil 表示）。
【答案】算法如下：
//由二叉树的中序序列IN[]和后序序列POSTt[]建立二叉树
分别是中序序列和后序序列第一和最后元素的下标，初始调用时
，
相关内容
相关标签