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

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

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

　　一、选择题(30分)

　　1. 1. 字符串的长度是指( )。

　　(A) 串中不同字符的个数 (B) 串中不同字母的个数

　　(C) 串中所含字符的个数 (D) 串中不同数字的个数

　　2. 2. 建立一个长度为n的有序单链表的时间复杂度为( )

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

　　3. 3. 两个字符串相等的充要条件是( )。

　　(A) 两个字符串的长度相等 (B) 两个字符串中对应位置上的字符相等

　　(C) 同时具备(A)和(B)两个条件 (D) 以上答案都不对

　　4. 4. 设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择( )。

　　(A) 99 (B) 97 (C) 91 (D) 93

　　5. 5. 在二叉排序树中插入一个关键字值的平均时间复杂度为( )。

　　(A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2)

　　6. 6. 设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。

　　(A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4]

　　(C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4]

　　7. 7. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为( )。

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

　　8. 8. 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有( )个度数为0的结点。

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

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

　　(A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc

　　10. 10. 队列是一种( )的线性表。

　　(A) 先进先出 (B) 先进后出 (C) 只能插入 (D) 只能删除

　　二、判断题(20分)

　　1. 1. 如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。( )

　　2. 2. 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。( )

　　3. 3. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( )

　　4. 4. 二维数组和多维数组均不是特殊的线性结构。( )

　　5. 5. 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。( )

　　6. 6. 如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。( )

　　7. 7. 非空的双向循环链表中任何结点的前驱指针均不为空。( )

　　8. 8. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。( )

　　9. 9. 图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。( )

　　10. 10. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。( )

　　三、填空题(30分)

　　1. 1. 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为_____________________________。

　　2. 2. 下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。

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

　　void bstinsert(bitree *&t,int k)

　　{

　　if (t==0 ) {____________________________;t->data=k;t->lchild=t->rchild=0;}

　　else if (t->data>k) bstinsert(t->lchild,k);else__________________________;

　　}

　　3. 3. 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next; _________________;。

　　4. 4. 设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________(设结点中的两个指针域分别为llink和rlink)。

　　5. 5. 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为__________。

　　6. 6. 完全二叉树中第5层上最少有__________个结点，最多有_________个结点。

　　7. 7. 设有向图中不存在有向边，则其对应的邻接矩阵A中的数组元素A[i][j]的值等于____________。

　　8. 8. 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为_____________________________。

　　9. 9. 设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。

　　10. 10. 设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与___________相互交换即可。

　　四、算法设计题(20分)

　　1. 1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。

　　2. 2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

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

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

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

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