2015年考研：计算机数据结构测试题（六）

　　2015年计算机考研专业课考试科目为：计算机组成原理、数据结构、操作系统以及计算机网络等，需要大家记忆的东西很多，但是更重要的还是要理解，融会贯通才能够把题做好，把问题解决。新东方在线小编分享计算机数据结构测试题和参考答案，希望广大考生在复习之余能够认真做题，不断检验和查漏补缺，争取全面提高。

　　下面请看2015年考研：计算机数据结构测试题（六）

　　一、选择题(30分)

　　1.数据的最小单位是( )。

　　(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

　　2.设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为( )。

　　(A) 40，50，20，95 (B) 15，40，60，20

　　(C) 15，20，40，45 (D) 45，40，15，20

　　3.设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为( )。

　　(A) 15，25，35，50，20，40，80，85，36，70

　　(B) 15，25，35，50，80，20，85，40，70，36

　　(C) 15，25，35，50，80，85，20，36，40，70

　　(D) 15，25，35，50，80，20，36，40，70，85

　　4.函数substr(“DATASTRUCTURE”，5，9)的返回值为( )。

　　(A) “STRUCTURE” (B) “DATA”

　　(C) “ASTRUCTUR” (D) “DATASTRUCTURE”

　　5.设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为( )。

　　(A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)

　　6.设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=( )。

　　(A) Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm

　　(C) N2+2N3+3N4+……+(m-1)Nm (D) 2Nl+3N2+……+(m+1)Nm

　　7.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较( )次。

　　(A) 25 (B) 10 (C) 7 (D) 1

　　8.设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为( )。

　　(A) abedfc (B) acfebd (C) aebdfc (D) aedfcb

　　9.设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是( )。

　　(A) n-i (B) n-1-i (C) n+1-i (D) 不能确定

　　10 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是( )。

　　(A) 40，42，45，55，80，83 (B) 42，40，45，80，85，88

　　(C) 42，40，45，55，80，85 (D) 42，40，45，85，55，80

　　二、填空题(共30分)

　　1. 1. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。

　　2. 2. 在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。

　　3. 3. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素(包括对角线上元素)存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。

　　4. 4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表;队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。

　　5. 5. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。

　　6. 6. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。

　　7. 7. 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。

　　8. 8. 设一组初始记录关键字序列(k1，k2，……，kn)是堆，则对i=1，2，…，n/2而言满足的条件为_______________________________。

　　9. 9. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。

　　void bubble(int r[n])

　　{

　　for(i=1;i<=n-1; i++)

　　{

　　for(exchange=0,j=0; j<_____________;j++)< p="">

　　if (r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}

　　if (exchange==0) return;

　　}

　　}

　　10. 10. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。

　　struct record{int key; int others;};

　　int bisearch(struct record r[ ], int k)

　　{

　　int low=0,mid,high=n-1;

　　while(low<=high)< p="">

　　{

　　________________________________;

　　if(r[mid].key==k) return(mid+1); else if(____________) high=mid-1;else low=mid+1;

　　}

　　return(0);

　　}

　　三、应用题(24分)

　　1. 1. 设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。

　　2. 2. 设无向图G(如右图所示)，给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。

　　3. 3. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。

　　4. 4. 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。

　　四、算法设计题(16分)

　　1. 1. 设计判断两个二叉树是否相同的算法。

　　2. 2. 设计两个有序单链表的合并排序算法。

2015年考研：计算机数据结构测试题（六）答案

　　实践是检验真理的唯一标准，做题时检验自身的重要途径，新东方在线小编希望每一位考生都能够把握理论基础，注重实践应用，真正做到统筹全局，整体提升。在这里预祝大家2015年考研，取得一个好成绩，加油!

　　温馨提示：要学好一门专业课，选好参考书是非常有必要的。向大家推荐：严蔚敏的数据结构、白中英的计算机组成、西安电子科技大的操作系统、谢希仁的网络等书。另外，推荐我们新东方在线的【赢在起点——2015考研全科备考攻略系列公开课】辅助大家进行复习备考。如需参加培训课程，请进入新东方在线首页选课中心http://kaoyan.koolearn.com/ 进行选课，我们有2015考研计算机考点精讲班、2015考研计算机全程班、2015考研政英数计算机全科签约联报班等课程供大家选择。

　　了解更多2015年计算机考研信息关注新东方在线，更多资料下载，更多备考指导，更多经验分享~~~