1 2011-2012 学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题 1 分，共 10 分） 1.长度为n的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法时间复杂度为（ ） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1 的顺序入栈，下列哪一个是合法的出栈序列？（ ） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4 的结点个数分别是4、2、1、2，则树中叶子个数为（ ） A.8 B.9 C.10 D.11 4.设森林 F 对应的二叉树B 有 m 个结点，B 的右子树结点个数为n，森林 F 中第一棵树的结点个数是（ ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有 10 个度为2 的结点，5 个度为1 的结点，则度为0 的结点个数是（ ） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（ ） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7 层有 10 个叶子结点的完全二叉树不可能有（ ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（ ） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90 ） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84 则采用的排序方法是（ ） 2 A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（ ） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 C.以链接方式存储 D.以链接方式存储，且数据元素有序 二、填空（每空 1 分，共 15 分） 1.数据结构中评价算法的两个重要指标是 、空间复杂度。 2.在单链表中，指针 P 所指结点有后继的条件是 。（结点构成：data 和 nex t） 3.栈的特点是 。 4.判断循环队列是否队满的条件表达式是 。 5.完全二叉树中的结点个数为 n，则编号最大的分支结点的编号为 。 6.如果 A 有7 个兄弟，而 B 是A 的双亲，则 B 的度是 。 7.如果二叉树中有20 个叶子节点，30 个度为 1 的结点，则该二叉树的总结点...
