数据结构期末考试题04~05

    A．n      B．n一1    C．n+l    D．2*n   

2．在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为( B )。

    A．O(n)     B．O(1)    C．O(n2)    D．O(log2n)

3．设输入序列为1,2,3,4,5，借助一个栈不可能得到的输出序列是（   C   ）。

A. 1,2,3,4,5    B. 1,4,3,2,5      C. 4,1,3,2,5       D. 1,3,2,5,4

4．树中所有结点的度等于所有结点数加(  C  )。

    A．0       B．1     C．一1    D．2

5．设单链表中结点的结构为(data，link)。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*P之间插入结点*s，则应执行下列哪一个操作?( B )

    A．s一>1ink＝p一>1ink；p一>1ink＝s

    B．q一>1ink＝s；s一>link＝p

    C．p一>1ink：s一>1ink;s一>1ink＝p

    D．p一>1ink＝s；s一>1ink＝q 6．首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为( C  )

A. 前序遍历      B. 后序遍历     C. 中序遍历      D. 层次遍历

7．在无向图中定义顶点vi与vj之间的路径为从vi到达vj的一个( A  )。

    A．顶点序列    B．边序列    C．权值总和    D．边的条数

8．如果只想得到1024个元素组成的序列中的前5个最小元素，那么用( D  )方法最快。

    A．起泡排序    B．快速排序    C．堆排序      D．直接选择排序

9.已知完全二叉树有30个结点，则整个二叉树有（ B ）个度为1的结点。 

A. 0      B. 1       C. 2     D. 不确定

10.设计一个判断表达式中左右刮号是否匹配的算法，采用（ B）数据结构最佳

A. 顺序表       B. 栈         C. 队列         D. 单链表

二、填空题(每小题2分，共20分) 

    11．在程序运行过程中不能扩充的数组是_静态_分配的数组。这种数组在声明它时必须指定它的大小。

    12．将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。对于任意给定数组元素A[I][J]，如果它能够在数组B中找到，则它应在__2*I+J _位置。

    13．链表适用于__顺序_查找。

    14．队列的插入操作在_队尾_进行，删除操作在_队头_进行。

    15．设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少应为_3_。

    16．广义表A((a，b，c)，(d，e，f))的表尾为_((d，e，f)) _。

    17．在一棵树中，_根_结点没有前驱结点。

    18．一棵树的广义表表示为a(b(c，d(e，f)，g(h))，i(j，k(x，y)))，结点k的所有祖先的结点数为_2_个。

  19.已知五个元素ABCDE的进栈次序为ABCDE，若C为第一个出栈元素，则下一个出栈的元素不可能是  A  

三、判断题(每小题1分，共5分)

21．二维数组可以视为数组元素为一维数组的一维数组。  (  对   )

    22．二叉排序树的中序遍历序列按关键字递增有序。  (  对  )

    23．栈是一种后进先出的线性表，因此，元素的进栈序列和出栈序列不可能相同。  (  错 )

    24．单链表必须从第一个数据元素开始访问表中的其它数据元素。 (  对  )

    25．进行折半搜索的表必须是顺序存储的有序表。   (  对  )  

四、算法分析题(每小题10分，共30分)

26、在一棵空的二叉查找树中依次插入关键字序列为20、30、8、12、34、5、60、3、1，29，请画出所得到的二叉查找树。

27．  已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。并画出该二叉树。

    中序序列：e，b，d，c，a，g，i，h，j，f

    前序序列：a，b，e，d，c，f，g，h，i，j

后序序列： e，c ,d，b，i，j，h，f，a

28，假设用于通信的电文仅由A-H八个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这八个字母设计哈夫曼编码。

五、算法设计题(25分)

    29．已知二叉树中的结点类型用BinTreeNode表示，被定义为：

    struct BinTreeNode{char data BinTreeNode，*leftChild，*rightChild；}；其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数写出求一棵二叉树高度的算法，该高度由函数返回。假定根结点的层次为0，参数BT初始指向这棵二叉树的根结点。

int BTreeHeight(BinTreeNode*BT){

    if(BT＝＝NULL)return 一1；    //对于空树，返回一1并结束递归，1分

    else{

    int h１＝BTreeHeight(BT一＞leftChild)；//计算左子树的高度，2分

    int h2＝BTreeHeight(BT一＞rightChild)；//计算右子树的高度，2分

    if(hl＞h2)return h1+1；

    else return h2+1；    //返回树的高度，1分

    }

}