2017年北方民族大学计算机应用技术832C语言程序设计与数据结构之数据结构考研仿真模拟题
● 摘要
一、填空题
1． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。
Prior （node , x ） { if（node !=null）
If （ （1） ） *x=node->right；else * x-node->left;
}
next （bt , node, x ）/*bt是二叉树的树根*/ { （2） ;
if （node->rflag）（3）; else {do t=*x；;
while （*x==node ）; *x=t; } }
【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）
2． 关键码序列（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 ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
3． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
4．
每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。
【答案】
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。
5． 实现字符串拷贝的函数strcpy 为：
【答案】
6． VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
7． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
8． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
9． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
10．二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历
.
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
序列相同，则任何结点都没有左子树。
二、判断题
11．树中的结点和图中的顶点就是指数据结构中的数据元素。（ ）
【答案】√
【解析】树中的结点和图中的顶点就是指数据结构中的数据元素，而它们的边指的是元素之间的关系。
12．快速排序和归并排序在最坏情况下的比较次数都是
【答案】×
【解析】快速排序最坏的情况下比较次数是 13．设模式串的长度为m , 目标串的长度为n ，当
【答案】
【解析】因为两个字符串的长度几乎相等，因此，在进行相应的匹配时，只需要定位父串的前几位即可。
14．若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（ ）
【答案】√
【解析】二叉排序树对于每一个结点，它的左子树的所有结点的值都小于这个结点的值，而它的右子树的所有结点的值都大于这个结点的值。而采用中序遍历，遍历顺序为左根右，因此可以得到按增序排列的关键码序列。
15．外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（ ）
【答案】×
【解析】外部排序方法：按可用内存大小，将外存上含n 个记录的文件分成若干长度为z 的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串（run ）。对这些归并段进行逐趟归并，使归并段（有序的子文件）逐渐由小至大，直至得到整个有序文件为止。一般情况下，外部排序所需总的时间=内部排序（产生初始归并段）所需的时间 存信息读写的时间内部归并所需的时间
16．通常使用队列来处理函数或过程的调用。（ ）
【答案】
【解析】经常使用栈来处理函数或过程的调用。
（ ）
且处理只匹配一次的模式时，朴素的匹配（即
子串定位函数）算法所花的时间代价可能会更为节省。（ ）
外