《数据结构与算法》试卷与答案5

1、 PAGE PAGE 9广州大学学年第学期考试卷课程 数据结构与算法考试形式（闭卷，考试）信息学院 系 专业 级 班 学号： 姓名：题次一二三四五六总分评卷人分数评分201010302010100（2 20 分）具有10 个顶点的无向图，边的总数最多为。n0 为哈夫曼树的叶子结点数目，则该哈夫曼树共有 个结点。设有一个10 阶的对称矩阵A，采用压缩存储方式以行序为主序存储 为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85 的址为。A3BAB的度是一个无序序列可以通过构造一棵树而变成一个有序序列，造树的过程即为对无序序列进行排序的过程。法构造的哈希函数肯定不会发生冲突。求从某

2、源点到其余各顶点的Dijkstra算法，当图的顶点数为10，用邻接矩表示图时计算时间约为10ms则当图的顶点数为40时计算时间为ms设一棵后序线索树的高度是结点x 是树中的一个结点其双亲是结点 y 的右子树高度是31x是y的左孩子则确定x的后继最多需经过个中间结点（不含后继及x 本身）对于单向链表，在两个结点之间插入一个新结点时需修改的指共有个。10 .有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,10082 的结点时，经过次比较查找成功。二、单项选择题（每题 1 分，共 10 分）()在一个长度为n 的顺序表中向第i 个元素（0i=n+1）之前插入一新元素时

3、，需向后移动（）个元素n-in-i+1n-i-1i() 设有一个栈，元素的进栈次序为下()是不能的出栈序列A，B，C，D，EB，C，D，E，AE，A，B，C，DE，D，C，B，A() 具有842 个结点的完全三叉树，其叶子结点共有（）个A.421B. 422C.420D.423E.以上都不是4.（）顺序查找方法适用于存储结构为（）的线性表A.压缩存储B. 散列存储C. 顺序存储D. 链式存储E以上都不是5.（）以下序列不是堆的是（） 100，85，98，77，80，60，82，40，20，10，66） B. （100，98，85，82，80，77，66，60，40，20，10） C10，20，

4、40，60，66，77，80，82，85，98，100） 100，85，40，77，80，60，66，98，82，10，20）6（）可采用的查找方法是（）分块查找 B. 顺序查找 C. 折半查找 D. 基于属性（ ）n A1.ni 个结点（i 1 开始用上述方法编号）A中的位置是（ ）A. A2i (2i=n) B.A2i+1 (2i+1=n) C. Ai/2 D.条件不充分，无法确定8（ ）53303712452496）A.45，24，53，12，37，96，30B. 37，24，12，30，53，45，96C. 12，24，30，37，45，53，96D. 30，24，12，37，45，9

5、6，539()在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形可能出现的是()A.G中有弧B.G中有一条从Vi 到Vj 的路径C.G 中没有弧D. G 中有一条从Vj 到Vi 的路径( )FBm 个结点，Bp，p nF中第一棵树的结点个数是( )A.m-nB. m-n-1C. n+1D. 条件不足，无法确定判断题（在括号内填上“”或“1 10 分，做错不倒扣）（）在栈空的情况下，不能做退栈运算，否则产生下溢。() 任何一棵前序线索二叉树，都可以不用栈实现前序遍历。（）就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大（）Shell 方法排序时，若关键字的排列杂乱无序

6、，则效率最高。（）在任何条件下，快速排序的效率总是最好的。（）两叉树是树的一种特殊情况。（）NN-1条边（）拓扑排序是判断一个有向图是否存在回路的唯一方法。（）T中，先删除结点NN，得到新的二叉排序树 T1，则 T 和 T1 相同。（）栈和队列都是限制存取点的线性结构。四、画图/计算/证明 (30 分)1 试说明一棵二叉树进行前序、中序、后序遍历，其叶结点的相对次序是否会发生改变？为什么？（5 分）2n m 节省多少？（设链域占两个单元，数据域占一个单元（5 分）已知一棵二叉树的中序遍历序列为 :BAFDJGCKHLEIMBFJGDKLHMIECA.请完成（6分）构造出这颗二叉树；画出这颗二叉

7、树中序线索化后的结构8 （5 分）(9分) V=a,b,c,d,e,f; E=,请画出该图，并写出邻接矩阵a出发的深度优先和广度优先遍历序列画出由此得到的深度优先和广度优先生成树（或森林）五. 程序填空题 （20 分，每个函数 5 分）用链表表示数据的简单选择排序，结点的域为数据域data，指针域nexthead，链表无头结点。selectsort(head) p=head;while (p) q=p;r=;while ()if ( q-next-data r-data )r=;tmp=q-data;q-data=p-data; p-data=tmp;p=;n个顶点的有向图用邻接矩阵array

8、整。注：图的顶点号从0开始计；indegree是有n个分量的一维数组，放顶点的入度；函数crein用于计算顶点的入度；有三个函数push(data)pop(check(data退栈和测试栈是否为空（不空返回1，否则返回0。# include crein (array, indegree, for (i=0; in; i+)indegreei=;for (i=0; in; i+) for (j=0; jn; indegreei+=array ;topsort( array, indegree, n)count=for (i=0; in; i+)if ()push(i); while (check

9、( )coutvex; count+;for (i=0; in; i+)k=array;if () indegreei-;if ()push(i);latypedef struct Datatype listMaxnum; int num; SeqList;试将下面删除顺序表 la 中所有值为 x 的数据元素的算法补充完整。void DeleteSeqList ( SeqList * la, Datatype x)int j, k;for (j=1; jnum; j+) if ()for (k=j; knum; k+);la-num-;j-;四、编写算法（10 分）n xyzzyx xyzyx

10、 都是中心对称的字符串。试卷答案一、填空题（每空1.5 分，共15 分）1456直接定址2.。7.160ms3 418.31个中间结点4B的度是 49 2个二叉排序10.4 次单项选择题（1.5 15 分1. ( B )2. ( C )ECA5.（D）6.（A）7.（D）8（）9( D)10. ( A)（1.5 15 ）1 （）2( )3 （）4 （）5 （ ）6 （）7 （）8 （ ）9 （ ）10 （ ）四、画图/计算/证明/算法分析 (30 分)叶结点的相对次序是不会发生改变的。2 节 省 n(2m+1)-5n=2n(m-2)3.(1)二叉树为ABCDE(2) (略)4.FGHIMJKLASL=(1+2*2+3*4+4)/8=21/85. (9 分) V=a,b,c,d,e,f; E=,(1) (略)深度优先序列：a b d e c f广度优先序列：a b d e c f深度优先森林：广度优先遍历森林为acacbdfbdefe五. 程序填空题 （15 分，每小题 5 分）10while (p!=NULL)r=p; 或 p-next 或 q while (q-next!=NULL) 或 r!=NULLr=q-next; 或 r-next p=p-next