算法与数据结构试题电信061-2

1、班级 学号 2008 年2009 年第 1 学期算法与数据结构试题(B)（除第一题选择题外，所有一、单项选择题(从下列各题四个备选写在答题纸上，写在其它地方无效）中选出一个正确,将其代号 (A,B,C,D)写在下表中,答题写在其它地方无效；每小题 1 分,共 10 分)1.A.B.C.D.2.关于线性表的表述正确的是（）每个元素都有一个直接前趋和一个直接后继线性表中至少要有一个元素表中元素的排列顺序必须是由小到大或者由大到小除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前趋和直接后继一般情况下，将递归算法转换成等价的非递归算法应该设置（）A.堆栈 B.队列 C.堆栈或队列 D.数

2、组3.A.4.A.5.设栈的输入序列为 1.2.3.n，若输出序列的第一个元素是 n，则第 i 个输出元素是（）不确定 B. ni+1C.iD. ni若广义表满足 Head（A）Tail（A），则 A 为（）（）B. （）C.（），（） D.（），（），（）设有 13 个值，用它们组成一棵树，则该树共有（）个结点。A13B. 12C.26D.256.A.C.7.下面几个符号编码集合中，不是前缀编码的是（）（0，10，110，1111）B. （11，10，001，101，0001）（00，010，0110，1000） D.（B,C,AA,AC,ABA,ABB,ABC）在一棵度为 3 的树中，度为

3、 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2 个，则度为 0 的结点数为（）个。A.8.A.9.4B.5C.6D.7为了方便对图状结构的数据进行存取操作，则其中数据结构应该采用（）B. 链式C. 索引D. 散列顺序对有 18 个元素的有序表做二分（折半）查找，则查找 A3的比较序列的下标为（）A. 1.2.3B. 9.5.2.3C. 9.5.3D. 9.4.2.310. 对任意的 7 个关键字进行排序，至少进行（）次关键字之间的两两比较。A.13B.14C.15D.17二、填空(每空 1 分,共 20 分)1.算法的基本特性是(),(),(),(),()。在

4、从被调用函数返回调用函数之前，系统也需要做如下三件事情：（）；（）；（）。二叉树的第 i 层上至多有（）个结点。带权的图称作（）。5. 哈希表的检索平均检索长度取决于（）、（）和（）这三个。题号12345678910任何递归定义必须同时满足如下两个条件：（）；（）。两个串相等的充要条件是（），并且（）。队列的操作原则是（），栈的操作原则是（）。9.线性表的链式结构为（）。三、判断题 (每小题 1 分,共 10 分)1.串是由有限个字符的连续序列，串长度为串中字符的个数。（）KMP 算法的最大特点是指示主串的指针不需要回溯。（）若一个广义表的表头为空表，则此广义表亦为空表。（）二叉树就是结点度为

5、 2 的树。（）存在这样的二叉树，对它采用任何次序的遍历，结果相同。（）6.二叉树中不存在度大于 2 的结点，当某个结点只有一棵时无所谓左右之分。（）不使用递归也能实现二叉树的前序，中序和后序遍历。（）强连通分量是有向图中的极大强连通子图。（）有回路的图不能进行拓扑排序。（）所有的排序算法都是不稳定的。（）四、证明计算题(共 10 分)1.证明对任意一棵二叉树，若终端结点数为 n0，度为 2 的结点数为 n2，则 n0=n2+1。（6分）2.模式“abaabcac”的 next 函数值为：（4 分）五、作图题 (共 15 分)二叉树有哪几种基本形态? 画图说明之。（5 分）试将森林 F= T1

6、,T2,T3,T4 转换为一棵二叉树。（5 分）3.数组 A1.2,0.2 的以列序为主序的顺序六、问答题 (共 20 分)结构。（5 分）一只一棵树边的集合为(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c),请回答以下问题：（1）（2）（3）（4）（5）（6）（7）（8）哪个是根节点？ 哪些是叶子结点？哪些是结点g 的双亲？哪些是结点g 的祖先？哪些是结点g 的孩子？哪些是结点e 的子孙？哪些是结点e 的兄弟？那些是结点f 的兄弟？结点 b 和结点 n 的层次号分别是多少？j12345678模式串abaabcacNextj（9） 树的深度是多