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

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

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

　　一、选择题(24分)

　　1.下列程序段的时间复杂度为( )。

　　i=0，s=0; while (s

　　(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)

　　2.设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列( )存储方式最节省运算时间。

　　(A) 单向链表 (B) 单向循环链表

　　(C) 双向链表 (D) 双向循环链表

　　3.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为( )。

　　(A) s->next=p->next;p->next=-s; (B) q->next=s; s->next=p;

　　(C) p->next=s->next;s->next=p; (D) p->next=s;s->next=q;

　　4.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( )。

　　(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1

　　(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3

　　5.设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为( )。

　　(A) 10 (B) 19 (C) 28 (D) 55

　　6.设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有( )个叶子结点。

　　(A) (B) (C) (D)

　　7. 二叉排序树中左子树上所有结点的值均( )根结点的值。

　　(A) < (B) > (C) = (D) !=

　　8. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为( )。

　　(A) 129 (B) 219 (C) 189 (D) 229

　　9. 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做( )次线性探测。

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

　　10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有( )个结点。

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

　　11.设一组初始记录关键字的长度为8，则最多经过( )趟插入排序可以得到有序序列。

　　(A) 6 (B) 7 (C) 8 (D) 9

　　12.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是( )。

　　(A) F，H，C，D，P，A，M，Q，R，S，Y，X

　　(B) P，A，C，S，Q，D，F，X，R，H，M，Y

　　(C) A，D，C，R，F，Q，M，S，Y，P，H，X

　　(D) H，C，Q，P，A，M，S，R，D，F，X，Y

　　二、填空题(48分，其中最后两小题各6分)

　　1. 1. 设需要对5个不同的记录关键字进行排序，则至少需要比较_____________次，至多需要比较_____________次。

　　2. 2. 快速排序算法的平均时间复杂度为____________，直接插入排序算法的平均时间复杂度为___________。

　　3. 3. 设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。

　　4. 4. 设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查找成功有结点数有_________个。

　　5. 5. 设一棵m叉树脂的结点数为n，用多重链表表示其存储结构，则该树中有_________个空指针域。

　　6. 6. 设指针变量p指向单链表中结点A，则删除结点A的语句序列为：

　　q=p->next;p->data=q->data;p->next=___________;feee(q);

　　7. 7. 数据结构从逻辑上划分为三种基本类型：___________、__________和___________。

　　8. 8. 设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_________;用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。

　　9. 9. 设散列表的长度为8，散列函数H(k)=k % 7，用线性探测法解决冲突，则根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是________。

　　10. 10. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的结果为_____________________。

　　11. 11. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的结果为______________________。

　　12. 12. 设有向图G中的有向边的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，<6，5>}，则该图的一个拓扑序列为_________________________。

　　13. 13. 下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。

　　typedef struct node{int data;struct node *lchild;________________;}bitree;

　　void createbitree(bitree *&bt)

　　{

　　scanf(“%c”,&ch);

　　if(ch=='#') ___________;else

　　{ bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; ________;createbitree(bt->rchild);}

　　}

　　14. 14. 下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。

　　typedef struct node {int data; struct node *next;} lklist;

　　void lklistcreate(_____________ *&head )

　　{

　　for (i=1;i<=n;i++)< p="">

　　{

　　p=(lklist *)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0;

　　if(i==1)head=q=p;else {q->next=p;____________;}

　　}

　　}

　　三、算法设计题(22分)

　　1. 1. 设计在链式存储结构上合并排序的算法。

　　2. 2. 设计在二叉排序树上查找结点X的算法。

　　3. 3. 设关键字序列(k1，k2，…，kn-1)是堆，设计算法将关键字序列(k1，k2，…，kn-1，x)调整为堆。

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

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

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

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