2018年中国石油大学(北京)地球物理与信息工程学院858计算机科学基础之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
2． 有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)
【答案】3个
【解析】以3，4先出栈的序列有34521、34215、34251共3个。
3． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空:
(_____i)；
＝
_____.
_____
【答案】a ＋l ；n%10
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
4． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，
2
而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。
5． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】O(1)；O(n)
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
6． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
a 中存放待排序的关键字
【答案】
【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
7． 堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。
【答案】选择；完全二叉树；
；O(1)；满足堆的性质
8． 在哈希函数中，p 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
9．
线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。
【答案】(n﹣1)/2
【解析】删除第一个元素需要移动n ﹣1次，以此类推，删除最后一个元素需要移动0次。平均次数为(n﹣l)*n/n/2＝(n﹣l)/2。
10．中缀式(c-d)对应的前缀式为_____，若a=l，b=2, c=3, d=4, 则后缀式运算结果为_____。
【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
的
二、判断题
11．若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【答案】 ×
【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
12．程序一定是算法。（ ）
【答案】 ×
【解析】一个程序不一定满足有穷性。而算法是对问题的解，用程序设计语言来实现来描述，这时算法就是一个程序。
13．一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（ ）
【答案】 √
【解析】树的前序遍历和后序遍历叶子节点的相对次序是不变的，都遵循左右的次序。
14．快速排序和归并排序在最坏情况下的比较次数都是（ ）
【答案】×
【解析】快速排序最坏的情况下比较次数是
15． 若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（ ）
【答案】√
【解析】因为一个有向图的邻接矩阵对角线以下元素均为零，则该图是一个有向无环图，所
相关内容
相关标签