《数据结构作业2.doc》由会员分享，可在线阅读，更多相关《数据结构作业2.doc（8页珍藏版）》请在金锄头文库上搜索。
1、树1 一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有 个结点A）2h B）2h-1 C）2h+1 D）h+12表达式a*(b+c)-d的后缀表达式是 A）abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd 3下面说法正确的为 （1）二叉树按某种方式线索化后，任一结点均有指向前驱和后继的线索 （2）二叉树的前序遍列序列中，任意一个结点均处在子孙结点前 （3）二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值 A）（1）（2）（3） B）（1）（2） C）（1）（3） D）前面的可选答案都不对 5若某二叉树有20个叶子结点，有30个结点仅有一个孩子
2、，则该二叉树的总的结点数是 69 n0=n2+1,n=n0+n1+n26写出一棵满k叉树上的叶子结点数和非叶结点数之间的关系。n0=(k-1)n1+17有n个结点的二叉树，用二叉链表作为存储结构，空指针域有 n+1 81). 写出前序遍历二叉树的递归算法 2). 如图二叉树, 给出按中序, 后序遍历树时的访问次序. 3).画出其先序线索树 E 中序:abcdegfi 后序:acdbgife B F A D G I C9 二叉树的先序和中序遍历序列分别是ABCDEFGH，CBEDFAGH，则后序遍历序列是 A）HGFEDACB B）GHEDFCBA C）CEFDBHGA D）HGAFDEBC 1
3、0假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出该树。11假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该树。 12下面的说法中正确的是 B (1) 任何一棵二叉树的叶结点在三种遍历中的相对次序不变; (2) 按二叉树定义,具有三个结点的二叉树共有6种;A) (1),(2) B)(1) C(2) D)(1),(2)都错13.一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有 B 个结点 A) 2h B)2h-1 C)2h+1 D)h+1 14在有n 个接点的二叉链表中,值为非空的链域的个数为
4、_ A） n-1 B) 2n-1 C) n+1 D) 2n+1 15在一非空二叉树的中序遍历序列中，根结点的右边_ A). 只有右子树上的所有结点 B). 只有右子树上的部分结点C). 只有左子树上的部分结点 D). 只有左子树上的所有结点 16深度为5的二叉树至多有_个结点。 A).16 B).32 C).31 D). 1517前序遍历和后序遍历结果相同的二叉树为 (1) C 前序遍历和中序遍历结果相同的二叉树为 (2) C F 中序遍历和后序遍历结果相同的二叉树为 (3)C E A) 一般二叉树 B) 根结点无左孩子的二叉树 C) 只有根结点的二叉树D) 根结点无右孩子的二叉树 E) 所有
5、结点只有左子数的二叉树F) 所有结点只有右子数的二叉树18在有n 个接点的二叉链表中,值为非空的链域的个数为_ A） n-1 B) 2n-1 C) n+1 D) 2n+119二叉树的先序和中序遍历序列分别是ABCDEFGH，CBEDFAGH，则后序遍历序列是 A）HGFEDACB B）GHEDFCBA C）CEFDBHGA D）HGAFDEBC 20若一棵二叉树具有102片叶子结点，则该二叉树度为2的结点数是 A) 100 B)101 C)102 D)103 211). 写出前序遍历二叉树的递归算法 2). 如图二叉树, 给出按中序, 后序遍历树时的访问次序. 3).画出其先序线索树 E B
6、F A D G I C前序二叉树的递归算法 Void order (tlnode *t) If(t) Coutdata; Order(t-lchild); Order(t-rchild); 22 二叉树的先序和中序遍历序列分别是ABCDEFGH，CBEDFAGH，则后序遍历序列是 A）HGFEDACB B）GHEDFCBA C）CEFDBHGA D）HGAFDEBC 23. 画出有三个结点的所有二叉树和树；写出叉树的五种形式。 24深度为K的完全二叉树至少有 2k-1 个结点,至多有 2K-1 个结点 25在一棵二叉树中，度为0的结点有30个，度为1的结点有40个，则二叉树总的点数有 99 。
7、26一二叉树的先序序列为ABCDEFGH，中序序列为BCADEFGH，则它的左子树结点为 BC ，右子树结点为 DEFGH 。 27找出所有满足下列条件的二叉树：A 它们在先序遍历和中序遍历时，得到的结点访问序列相同；B 它们在后序遍历和中序遍历时，得到的结点访问序列相同；C 它们在先序遍历和后序遍历时，得到的结点访问序列相同；28树的森林如下，试把它转化为二叉树并写出其先序遍历、后序遍历和中序线索二叉树。 A G N / / | / | B C H I K O P Q / | / D E F L M 29 具有1048个结点的完全二叉树的深度为:A. 12 B. 10 C.11 D. 13
8、30有关二叉树的说法正确的是:A. 二叉树的度为2 B. 一棵二叉树的度可以小于2C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度为2 31已知L是无表头结点的单链表，且P结点既不是首元结点，亦不是尾元结点，试从下列提供答案中选择合适的语句序列：a.在P结点后插入S结点的语句序列是 4 1 ；b. 在P结点前插入S结点的语句序列是 7 11 8 4 1 ；c.在表首插入S结点的语句序列是 5 12 ；d. 在表尾插入S结点的语句序列是 9 6 1 ；(1)P-next=S;(2)P-next=P-next-next;(3)P-next=S-next;(4)S-next=P-
9、next;(5)S-next=L;(6)S-next=NULL;(7)Q=P;(8)while(P-next!=Q)P=P-next;(9) while(P-next!=NULL)P=P-next;(10)P=Q;(11)P=L;(12)L=S;(13)L=P; 图 1.设图G用邻接表存储，则拓扑排序的时间复杂度为_ A) O(n) B) O(n+e) C) O(n2) D) O(n*e) 2无向图G=（V，E），其中：V= a,b,c,d,e,f , E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d) 对该图进行深度优先遍历，得到的顶点序列正确的是 A）a
10、,b,e,c,d,f B)a,c,f,e,b,d C)a,e,b,c,f,d D)a,e,d,f,c,b 3图的遍历分为 深度优先遍历 和 广度优先遍历 。 4n个顶点的连通图至少有 n-1 条边。5若用起泡排序对序列10,14,26,29,41,52,5，20从大到小排序,需要多少次比较A15 B. 28 C.3 D.216有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100，当二分查找值为82的数据时要进行多少次比较。 A1 B. 2 C. 4 D. 8 7设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的结点加到表中，用线性哈希表解决冲突，则放入的位置是 A 8 B 3 C 5 D 98对分查找要求 顺序表示 和 元素有序 。
