2018年北京市培养单位自动化研究所863计算机学科综合(专业)之数据结构考研基础五套测试题
● 摘要
一、填空题
1． 在一个具有n 个单元的顺序栈中，假定以地址高端(即下标为n 的单元) 作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top ＝_____。
【答案】top ﹣1
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以top ﹣1。
2． —个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
3． 一个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
4． 空格串是指_____，其长度等于_____。
【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数
5． 在有n 个顶点的有向图中，每个顶点的度最大可达_____。
【答案】2(n－1)
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n －1。
6． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
7． VSAM(虚拟存储存取方法) 文件的优点是:动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
8． 高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】
。当最后一层只有【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为
一个元素时，此时堆的元素个数最少，元素个数为。
9． 在二叉树中，指针p 所指结点为叶结点的条件是_____。 【答案】
【解析】叶子节点的左右孩子都不存在。
10．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录的_____。
【答案】比较；移动
二、判断题
11．折半查找与二元查找树的时间性能在最坏的情况下是相同的。（ ）
【答案】×
【解析】不是，当二元查找树是一棵单支树时，时间性能是O(n)。而折半查找依然是
12．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为O(1)（ ）。
【答案】 √
【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操作的时间复杂度是O(1)。
13．用希尔(Shell)方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）
【答案】×
【解析】希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
14．一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第k ﹣1层具有的最多结点数为余下的
【答案】 √
【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为k ﹣1层全满时，此时从根结点到第k ﹣1层具有最大的结点数为
15．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。（ ）
【答案】×
【解析】单链表不能使用折半查找方法。折半查找主要用于数据元素有序且存储方式为顺序
个结点在第k 层的任一位置上。（ ）
存储的表。
16．若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（ ）
【答案】√
【解析】二叉排序树对于每一个结点，它的左子树的所有结点的值都小于这个结点的值，而它的右子树的所有结点的值都大于这个结点的值。而釆用中序遍历，遍历顺序为左根右，因此可以得到按增序排列的关键码序列。
17．抽象数据类型与计算机内部表示和实现无关。（ ）
【答案】 √
【解析】抽象数据类型只表示数据的逻辑结构，与计算机内部表示和实现无关。
18．广义表(((a，b ，C) ，d ，e ，f)) 的长度是4。（ ）]
【答案】 ×
【解析】长度为1。因为只含一个元素即子表(((a，b ，C) ，d ，e ，f)) 。
19．3阶的B-树是平衡的3路搜索树。反之，一棵平衡的3路搜索树是3阶B-树。（ ）
【答案】×
【解析】3路搜索树并不具有3阶B-树的性质。因此一棵平衡的3路搜索树不一定是3阶B-树。
20．外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（ ）
【答案】×
【解析】外部排序方法:按可用内存大小，将外存上含n 个记录的文件分成若干长度为2的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串(run)。对这些归并段进行逐趟归并，使归并段(有序的子文件) 逐渐由小至大，直至得到整个有序文件为止。一般情况下，外部排序所需总的时间=内部排序(产生初始归并段) 所需的时间m*tIS+外存信息读写的时间
需的时间
。 内部归并所三、算法设计题
21．有n 个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法(注:双向起泡排序即相邻两趟排序向相反方向起泡) 。
【答案】算法如下:
相关内容
相关标签