单项选择题（本大题共15小题，每小题2分，共30分）二、填空题（本大题共10小题，每小题2分，共20分）三、判断题（本大题共4小题，每小题1分，共4分）四、解答题（本大题共4小题，每小题5分，共20分）五、算法阅读题（本大题共2小题，每小题3分，共6分）六、算法设计题（本大题共2小题,本大题20分）第一部分一、单项选择题2.以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈8．对于栈操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序9.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。A.不确定B.n-i+1？C.iD.n-i10.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是A.i-j-1B.i-jC.j-i+1D.不确定的11.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.23415612.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）。A.23415B.54132？C.23145D.1543213.设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。A.51234B.45132C.43125D.3215414.栈在（）中应用。A.递归调用B.子程序调用C.表达式求值D.A，Ｂ，Ｃ15.一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分16.表达式a*(b+c)-d的后缀表达式是()。A．abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd17算术表达式a+b*（c+d/e）转为后缀表达式后为（）A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++18.设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A．线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈19.用链接方式存储的队列，在进行删除运算时（）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改20.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m21.栈和队都是（）A．顺序存储的线性结构B.链式存储的非线性结构C.限制存取点的线性结构D.限制存取点的非线性结构22．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定23．具有10个叶结点的二叉树中有（）个度为2的结点。A．8B．9C．10D．ll24．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250B．500C．254D．505E．以上答案都不对（501）25.设给定权值总数有n个，其哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-126.有n个叶子的哈夫曼树的结点总数为（）。A．不确定B．2nC．2n+1D．2n-127.有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为228．二叉树的第I层上最多含有结点数为（）A．2IB．2I-1-1C．2I-1D．2I-129.一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间30．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点A．2hB．2h-1C．2h+1D．h+131．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定32．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是A．acbedB．decabC．deabcD．cedba34．由3个结点可以构造出多少种不同的二叉树？（）A．2B．3C．4D．5二、填空题1．对于给定的n个元素,可以构造出的逻辑结构有（1），（2），（3），（4）四种。2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。3．在一个长度为n的顺序表