2017年中国石油大学(北京)地球物理与信息工程学院858计算机科学基础之数据结构考研题库
● 摘要
一、填空题
1． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
【答案】（1）（2）
链表未到尾就一直进行
将当前结点作为头结点后的第一元素结点插入
2． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
3． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; （10，7，-9，0，47，23，1，8，98，36）
4．
【答案】5
5． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
6． 二进制地址为011011110000，大小为
【答案】011011110100；011011100000
011011110000是块的起始地址，【解析】大小分别为
第 2 页，共 39 页
=_____
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
，
则结点
和
在同一层上的条件是
和块的伙伴地址分别为：_____ 和
其伙伴块的起始地址计算公
式如下：
当大小为4时，起始地址
为当大小为16时，起始地址为
：
7． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
8． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
9． 关键码序列（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 ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
10．在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
二、判断题
11．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为
【答案】
第 3 页，共 39 页
（ ）。
【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操 作的时间复杂度是
12．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）
【答案】×
【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。
13．对磁带机而言，ISAM 是一种方便的文件组织方法。（ ）
【答案】×
【解析】ISAM 是一种专为磁盘存取设计的文件组织方式。
14．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ）
【答案】
【解析】算法的健壮性是指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果。
15．—棵树中的叶子数一定等于与其对应的二叉树的叶子数。（ ）
【答案】×
【解析】一颗树的叶子树与它对一个的二叉树的叶子树没有直接联系。不妨举例：假设一个有三个结点的二叉树，层数为2。则它的叶结点数为2。将其按规则转为对应的二叉树时，则它的叶结点数为1。
16．一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第的最多结点数为
【答案】√
【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为
层全满时，
此时从根结点到第
层具有最大的结点数为
17．由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。（ ）
【答案】×
【解析】希尔排序把序列分成很多小序列，对于直接插入排序，记录少时的效率会大大提高。并且序列在基本有序的情况下，直接插入排序也会提高。
18．在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ）
【答案】√
第 4 页，共 39 页
层具有
余下的个结点在第k 层的任一位置上。（ ）
相关内容
相关标签