2009 级《数据结构》期末试题 A 卷
一、判断题(5*2 分)
1. 算法的优劣与所用的计算机无关。但是与算法描述的语言有关。
2. 根据算法的时间复杂性,人们常常把算法分成两类:多项式阶算法、指数阶
算法。当 n 很大时,可以证明有如下关系:
O(1)<O(loglog n)<O(log n)<O(n*log n)<O(n)<O(n^2)<O(2^n)
3. 分析排序算法的最好和最坏时间复杂性时,当排序文件已经是排好序时,则
算法对此文件执行排序具有最好时间复杂性;当排序文件是逆排列时,算法
对此文件执行排序具有最坏时间复杂性。
4. N 个结点的有向图,若它有 N(N-1)条边,则它一定是强连通的。在 n 个结点
的无向图中,若边数大于 N-1,则该图必是连通图。
5. 中序遍历一棵二叉查找树可以得到一个排好序的结点序列。
二、单选题(7*2 分)
1.一棵左右子树均不空的二叉树在后序线索化后,其空指针域的个数为____。
A.0 B.1 C.2 D.3
2.下列排序算法中,某一趟排序后未必能选出一个元素放在最终位置上的是____。
A.堆排序 B.直接插入排序 C.分划交换排序 D.冒泡排序
3.一棵具有 N个顶点,K条边的无向图是一个森林(N>K),则该森林必有____棵树。
A.K B.N C.N-K D.1
4.若一组记录关键字为(34,60,55,30,32,85),则利用堆排序的方法建立的初始堆为
____。
A.{60,34,55,30,32,85} B.{85,60,55,30,32,34}
C.{85,60,55,34,32,30} D.{85,55,60,32,34,30}
5.在下述结论中正确的有____个。
1)只有一个结点的二叉树的度为 0
2)二叉树的度为 2
3)二叉树的左右字数可任意交换
4)深度为 K 的完全二叉树的结点个数小于或等于深度相同的二叉树
5)有 4 个不同关键字的结点可以构成 14 种不同的二叉树
A. 1 B. 2 C. 3 D.4
6.在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的____倍。
A.1 B.2 C.1.5 D.不能确定
7.设有数组 A[i,j],数组的每一个元素长度为三个字节,i 的值为 1 到 8,j 的值为
1 到 10,数组从内存首地址 S 开始顺序存放,当按列优先存放时,元素 A[5,8]的
存储首地址为____。
A.S+141 B.S+180 C.S+222 D.S+225
三、简答题(46 分)
1. 说明顺序存储和链式存储的区别及各自的优缺点。(4 分)
2. 将表达式(a+b)*c+d/(e*f-g)-h 改写成前缀和后缀表达式。(6 分)