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

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

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

　 一、 单选题(每小题2分，共8分)

　1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的概率都相等)为 ( )。

　　A n B n/2 C (n+1)/2 D (n-1)/2

　2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。

　　A s→link=p→link; p→link=s; B p→link=s; s→link=q;

　　C p→link=s→link; s→link=p; D q →link=s; s→link =p;

　3、 栈的插入和删除操作在( )进行。

　　A 栈顶 B 栈底 C 任意位置 D 指定位置

　　4、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )

　　A 24 B 71 C 48 D 53

　　二、填空题(每空1分，共32分)

　　1、数据的逻辑结构被分为__________、 ___________ 、________和________四种。

　　2、一种抽象数据类型包括______________和_____________两个部分。

　　3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为_________________________________________________。

　　4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为________________和____________________。

　　5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________。

　　6、当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示;当堆栈采用链接存储结构时，栈顶元素的值可用_______________表示。

　　7、一棵高度为5的二叉树中最少含有_________个结点，最多含有________个结点;

　　一棵高度为5的理想平衡树中，最少含有_________个结点，最多含有_________个结点。

　　8、在图的邻接表中，每个结点被称为____________，通常它包含三个域：一是_____________;二是___________;三是_____________。

　　9、在一个索引文件的索引表中，每个索引项包含对应记录的_________和___________两项数据。

　　10、 假定一棵树的广义表表示为A(B(C，D(E，F，G)，H(I，J)))，则树中所含的结点数为_________个，树的深度为_________,树的度为________, 结点H的双亲结点为________,孩子结点为_______________ 。

　　11、 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_________,整个堆排序过程的时间复杂度为________________。

　　12、 在对m阶的B_树插入元素的过程中，每向一个结点插入一个索引项(叶子结点中的索引项为关键字和空指针)后，若该结点的索引项数等于______个，则必须把它分裂为_______个结点。

　　三、 运算题(每小题6分，共24分)

　　1、已知一组记录的排序码为(46，79，56，38，40，80, 95，24)，写出对其进行快速排序的每一次划分结果。

　　2、一个线性表为B=(12，23，45，57，20，03，78，31，15，36)，设散列表为HT[0..12]，散列函数为H(key)= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

　　3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。

　　4、已知一个图的顶点集V各边集G如下：

　　V = {0，1，2，3，4，5，6，7，8，9};

　　E = {(0，1)，(0，4)，(1，2)，(1，7)，(2，8)，(3，4)，(3 ，8)，(5，6)，(5，8)，(5，9)，(6，7)，(7，8)，(8，9)}

　　当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。

　　假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。

　四、 阅读算法，回答问题(每小题8分，共16分)

　　1、假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 –1，请写出输出结果。

　　# include < iostream.h>

　　# include < stdlib.h >

　　consst int stackmaxsize = 30;

　　typedef int elemtype;

　　struct stack {

　　elemtype stack [stackmaxsize];

　　int top;

　　};

　　# include “stack.h”

　　Void main ( )

　　{

　　stack a;

　　initstack(a);

　　int x;

　　cin >>x;

　　while (x! = -1) {

　　push (a, x );

　　cin >>x;

　　}

　　while (!stackempty (a))

　　cout <

　　cout <

　　}

　　该算法的输出结果为：

　　__________________________________________________________.

　　2、阅读以下二叉树操作算法，指出该算法的功能。

　　Templatevoid BinTree：：

　　unknown (BinTreeNode*t) {

　　BinTreeNode< Type> *p =t, *temp;

　　if (p!=NULL) {

　　temp = p→leftchild;

　　p→leftchild = p→rightchild;

　　p→rightchild = temp;

　　unknown(p→leftchild);

　　undnown(p→rightchild);

　　}

　　}

　　该算法的功能是：________________________________

　　 五、 算法填空，在画有横线的地方填写合适的内容(10分)

　　对顺序存储的有序表进行二分查找的递归算法 。

　　int Binsch( ElemType A[ ],int low ,int high,KeyType K )

　　{

　　if (low <= high)

　　{

　　int mid = 1

　　if ( K= = A[ mid ].key )

　　return mid;

　　else if ( K < A[mid].key)

　　return 2

　　else

　　return 3

　　}

　　else

　　return 4

　　 六、 编写算法(10分)

　　编写算法，将一个结点类型为Lnode的单链表按逆序链接，即若原单链表中存储元素的次序为a1，……an-1，an，则逆序链接后变为, an，an-1，……a1。

　　Void contrary (Lnode * & HL)

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

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

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

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