2009级数字数据结构试卷

1、。装。订。线。2005年2006年第 2 学期数据结构试卷 B 卷时间共 120 分钟一、填空题（每题 1 分，共 15 分）1、对于顺序的线性表，当随机或删除一个元素时，约需平均移动表长的个元素。2、对于长度为 n 的顺序表，或删除元素的时间复杂度为；对于顺序栈或队列，或删除元素的时间复杂度为。3、在具有 n 个单元顺序的循环队列中，队满时共有个元素。4、在哈希表中的查找中，评判一个哈希函数优劣的两个主要条件是和。6、具有 N 个顶点的完全无向图的弧数为。7、设有一空栈，栈顶指针为 top，现有输入序列 1，2，3，4，5，经过 push, push,pop, push, pop , pus

2、h,push后，输出序列为。8、后序序列和中序序列相同的二叉树为。9、采用堆排序、快速排序、冒泡排序，对初态为有序的表，则最省时间的是。10、有 N 个球队参加的足球联赛按主客场制进行比赛，共需进行场比赛。11、在一棵高度为 H 的理想平衡二叉树中，最少含有个结点，最多含有个结点。12、对广义表 A=（x,(a,b),c,d)），运算 head(head(tail(A)的结果是。13、在具有 n 个结点的图中，其生成树含有条边。二、选择题（每题 1 分，共 15 分）1、一棵二叉排序树中，按（）遍历，得到的是一个有序序列。A. 先 序B. 中 序C. 后 序D、层次2从一个长度为 n 的顺序表

3、中删除第 i 个元素（1in），需向前移动个元素。A. n-iB. n-i+1C. n-i-1D. i3、若进栈序列为 1、2、3、4，进栈过程中可随意出栈，则（）不可能是一个出栈序列。A. 3、4、2、1B. 2、4、3、1C. 1、4、2、3D. 3、2、1、44、在具有 n 个单元的顺序的队列中，假定 front 和 rear 分别为队首指针和队尾指针，则判定队列为空的条件是（）。A. front=rear+1B. front+1=rearC. front=rearD. front=05、数组 A（1.5,1.6）的每个元素占 5 个单元，将其按行优先次序在起始地址为 1000 的连续单

4、元中，则元素 A5，5的地址为（）。A、1140B、1145C、1120D、1125）。6、线索二叉树中某结点 D，没有左孩子的主要条件是（得分阅卷人得分阅卷人题号12345678910总分得分阅卷人A、D-Lchild=NullB、D-ltag=1C、D-Rchild=NullD、D-ltag=07、设字符串 S1=ABCDEFG，S2=PQRST.则运算 S=CONCAT（SUB（S1,2,LENGTH（S2）,SUB(S1,LENGTH（S2），2）后结果为（）。A、BCQRB、BCDEFC、CDEFGD、BCDEFEF8、若给定的关键字集合为20，15，14，18，21，36，40，1

5、0，一趟快速排序结束时，键值的排列为（）。A、10，15，14，18，20，36，40，21B、10，15，14，18，20，40，36，21C、10，15，14，20，18，40，36，21D、15，10，14，18，20，36，40，219、设有 100 个元素，用折半查找时，最大比较次数是（）。A、25B、7C、10D、110、在计算递归函数时，如不用递归函数，应借助于（）数据结构。A、线性表B、栈C、队列D、双向队列11、在文件“局部有序”或文件长度较小的情况下，最佳排序的方法是（）。A、直接排序 B、起泡排序C、简单选择排序D、堆排序12、若数组 S1.n作为两个栈 S1 和 S2

6、的空间，对任何一个栈，只有当1.n全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（）。A、S1 的栈底位置为 0，S2 的栈底位置为 n+1B、S1 的栈底位置为 0，S2 的栈底位置为 n/2C、S1 的栈底位置为 1，S2 的栈底位置为nD、S1 的栈底位置为 1，S2 的栈底位置为 113、给定权的集合15，3，14，2，6，9，16，17，所构造出的树的带权路径长度为（ ）。A、129B、219C、189D、22914、假设有 n个关键字，它们具有相同的哈希函数值，用线性探测法把这 n 个关键字存入到哈希地址空间中要做（）次探测。A、n2B、n(n+1)+1)/2D、n(n-

7、1)/215、在直接选择排序中，的比较次数为（）数量级。A、nB、log2nC、n2D、nlog2n三、判断题（每题 1 分，共 10 分）1、完全二叉树的某结点若无左孩子，则它必是叶结点。（）2、用向量和单链表表示的线性表，均可用折半查找来提高查找速度。（）3、m 叉树是出度最小为 m 的树。()4、若一个广义表的表头为空表，则此广义表亦为空表。（）5、在 N 个结点的无向图中，若边数N-1，则该图必是连通图。（）6、在任意一棵非空二叉排序树，删除某个结点后又将其，则所得的二叉树与删除前原二叉排序树相同。7、二叉树是度数为 2 的有序树。（）8、若某二叉树的叶子结点数为 1，则其先序序列和后

8、序序列一定相反。9、如果有向图 G=的拓扑序列不唯一，则图中必有两条弧和。 （）10、只有在初始数据表为逆序时，冒泡排序所执行的比较次数最多。 （）得分阅卷人四、简答题（每题 5 分，共 15 分）1、简述算法的五个重要特性。答：2、树和二叉树有何区别？答：3、快速排序、堆排序、排序和归并排序，哪一种排序方法所需的辅助空间最大？请简单说明。答：五、应用题（共 35 分）1、假设用于通讯的电文由 a,b,c,d,e,f,g,h 等 8 个字母组成，字母在电文中出现的频率分别为 0.07，0.19，0.02，0.06，0.32，0.03，0.21 和 0.10。试为这些字母设计蔓编码,并求出带权路

9、径长度。（8 分）2、已知哈希表地址空间为 0.8，哈希函数为 H（key）=k mod 7，采用线性探测法处理。将下面数据序列 100，20，21，35，3，78，99，45 依次存入该哈希表中，并求出在等概率下的平均查找长度。（8 分）3、已知一棵二叉树如右图，请分别写出其先、中、后序遍历序列。（7 分）D先序序列：RI中序序列：CWFB后序序列：EH4、写出下图分别按深度、广度优先搜索遍历得到的序列。（6 分）V1深度优先搜索：V4V3V2广度优先搜索：V5V6V75、设二叉树的前序遍历序列为 ABCDEFGHI，中序遍历的序列为 BCAEDGHFI，写出其后续序列。（6 分）后续序列：六、算法题（共 10 分）1、假设用一个单循环链表表示队列（也称循环队列），该