《数据结构》期末考试题及答案6页.doc

2011-2012学年第一学期期末考查数据结构试卷 （答案一律写在答题纸上，在本试卷上做答无效）一、选择（每题1分，共10分）1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D）A.O(0) B.O(1) C.O(n) D.O(n2)2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（ D）A.543612 B.453126 C.346512 D.2341563.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ）A.8 B.9 C.10 D.114.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树