2017年华北电力大学(北京)控制与计算机工程学院842数据结构与操作系统之数据结构考研题库
● 摘要
一、填空题
1． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
2． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
【答案】（1）（2）
链表未到尾就一直进行
将当前结点作为头结点后的第一元素结点插入
3． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】
完全二叉树的高度
4． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
5． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
6． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
7． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
【答案】
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
8． 设有两个算法在同一机器上运行，其执行时闻分别为_____。
【答案】15 【解析】当
时，
而，
时，
要使前者快于后者，n 至少为
9． 在循环队列中，队列长度为n ，存储位置从0到，
【答案】
编号，以rear 指示实际的队尾元素，现
要在此队列中插入一个新元素，新元素的位置是（ ）。
10．关键码序列（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 ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
11．中缀式运算结果为_____。
【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
12．假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】的次数最小。总次数为
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测
对应的前缀式为_____，若则后缀式的
二、选择题
13．在缺页处理过程中，操作系统执行的操作可能是（ ）。
I. 修改页表 II. 磁盘I/O III. 分配页框 A. 仅 I 、II B. 仅II C. 仅III D.I 、II 和III 【答案】D