郑州大学现代远程教育《数据结构》

1、郑州大学现代远程教育数据结构 郑州大学远程教育彩赋学习中心 郑州大学现代远程教育数据结构 真题 2015版客观题 客观题部分 一、单项选择题：（每空2分，共20分） 1. 单链表是线性表的一种_的存储结构。 a. 顺序存取 b. 随机存取 c. 索引存取 2. 栈和队列的共同点是_。 a. 都是后进先出 b. 都是先进先出 c. 都是只允许在端点处插入和删除元素 d.无共同点 3. 设s=。则 index(s,t,5)的返回值是_。 a. 4 b. 5 c. 6 d. 9 e. 10 4. 串是一种特殊的线性表，其特殊性体现在_。 a. 可以顺序存储 b. 数据元素是一个字符 c. 可以链接存

2、储 d. 数据元素可以是多个字符 5树最适合用来表示_。 a. 有序数据元素 b. 无序数据元素 c元素之间具有分支层次关系的数据 d. 元素之间无关联的数据 64个顶点的无向完全图有_条边。 a. 6 b. 12 c. 16 d. 20 7散列表的装填因子越大，则发生冲突的可能性就_。 a. 越小 b. 越大 c. 不确定 8. 在长度为n的有序表中折半查找一个元素的平均查找长度是_。 a.o(n2) b.o(nlogn) c.o(n) d. o(logn) 9. 下列方法中，_是不稳定的排序方法。 a. 折半插入排序 b. 直接插入排序 c. 冒泡排序 d. 堆排序 10_二叉排序树可得到

3、一个关键字的有序序列。 郑州大学远程教育彩赋学习中心 a. 先序遍历 b. 中序遍历 c. 后序遍历 d. 层序遍历 二、是非题：（每题1分，共10分）（说明：正确的选“a”,错误选“b” ） 1 线性表的顺序存储结构优于链式存储结构。 （ ） 2 空串和空格串是相同的。 （ ） 3 图结构中，每个结点的前驱和后续都可以有任意多个。 （ ） 4 快速排序算法在待排序数据有序时最不利于发挥其长处。 （ ） 5 连通的最小生成树是唯一的。 （ ） 6 栈是fifo的线性表。 （ ） 7 由二叉树的先序和后序遍历序列不能唯一确定这棵二叉树。（ ） 8 若从无向图的一个顶点出发进行广度优先遍历可访问到

4、图中的所有顶点， 则该图一定是连通图。 （ ） 9 折半查找方法要求查找表必须是关键字的有序表，但是对存储结构没有限 制。 （ ） 10 在一棵非空二叉树的中序遍历序列中，根结点的右边只有其右子树上的 所有结点。 （ ） 主观题部分 一、简答题：（50分） 1. 若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构（顺序或链式结构）？为什么？（10分） 2.将下图所示森林转化为二叉树并在其上标出中序全线索。（10分） 3.已知如右图所示的有向图，写出该图的: (1)邻接矩阵 (2）一个可能的拓扑有序序列。 （10分） 郑州大学远程教育彩赋学习中心 4设散列函数h(key)=ke

5、y mod 7,用线性探测再散列法解决冲突。对关键字序列 13，28，72，5，16，8，7，9，11，29 在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。（10分） 5对于序列 26，33，35，29，19，12，22 ， （1）判断它是否是堆，若是，写出其是大顶堆还是小顶堆；若不是，把它调整为堆，写出调整的过程和调整后的序列。 （5分） （2）写出对该序列进行直接插入排序每一趟结束时的关键字状态。（5分） 二、算法设计题：（20分） 1、编写递归算法，计算二叉链表存储的二叉树的结点数目。（10分） 2、基于图的深度优先遍历策略写一算法，判断以邻

6、接表方式存储的无向图中连通分量的个数。 （10分） 郑州大学远程教育彩赋学习中心 数据结构答案 一、单项选择题： 1.a 2.c 3.d 4.b 5.c 6.a 7. b 8.d 9.d 10.b 二、判断题： 1.b 2.b 3.a 4.a 5.b 6.b 7.a 8.a 9.b 10.a 主观题部分： 一、简答题： 1.应采用顺序结构。因为顺序表是随机存取的存储结构，在顺序表中存取任何元素所花的时间都一样。而链表是顺序存取的存储结构。 2. ?0?0?03.?0?0?01000100100000010010000000?0?0? 0?1?0?可能的拓扑序列为：156234 （注意4一定是最

7、后一个，2一定在1和5之后） 4. asl=(1+1+1+2+5+1+1+4)/8 =16/8=2 郑州大学远程教育彩赋学习中心 5. (1) 该序列不是堆。 原始序列： 26，33，35，29，19，12，22 交换26和35，建大顶堆：35，33，26，29，19，12，22 （2）直接插入排序过程： 原始序列： （26），33，35，29，19，12，22 i=2： （26，33），35，29，19，12，22 i=3： （26，33，35），29，19，12，22 i=4： （26，29，33，35），19，12，22 i=5： （19，26，29，33，35），12，22 i=6： （12，19，26，29，33，35），22 i=7： （12，19，22，26，29，33，35） 二、算法设计题： 1. int nodes(bitree t) if(!t) return 0; return nodes(t-lchild)+nodes(t-rchild)+1; 2. int count (algraph g) int i, sum; for (i=0; i for (i=0; ivoid dfs (algraph g