学院领导
审批并签名
A  B卷
广州大学        学年第      学期考试卷
课程  数据结构与算法 考试形式（闭卷，考试）
信息学院      系        专业    级    班 学号：    姓名：           
题次
一
二
三
四
五
六
总分
评卷人
分数
20
10
先序中序后序遍历二叉树10
30
20
10
100
评分
一、填空题：（每格2分，共20分）
1．以{5，6，8，10，15}作为叶子结点的权值所构造的哈夫曼树的带权路径长度是                                        。
2．判断一个无向图是一棵树的条件是                              。
3．设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有          个结点。
4．一个无序序列可以通过构造一棵              树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
5．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是            。
6．设有向图有n个顶点和e条边，进行拓扑排序时，总的时间复杂度为   
7．在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的恰当位置，该排序方法叫                  。
8．用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。后序遍历该二叉树的访问结点序列是                              。
9．设散列函数H(k)=K mod 7,散列表的地址空间为0—6，则关键字为32的元素在哈希表中的下标为              。
10．一棵非空二叉树的先序序列和后序序列正好相反，则树的形状是
                              。
二、单项选择题（每题1分，共10分）
1．（      ）设一个栈的输入序列是 1，2，3，4，5 则下列序列中，是栈的合法输出序列的是：
A. 5 1 2 3 4      B. 4 5 1 3 2    C. 4 3 1 2 5    D. 3 2 1 5 4
2．（      ）在图采用邻接表存储时，求最小生成树的 prim 算法的时间复杂度为
A. O(n)            B. O(n+e)      C. O(n2)      D. O(n3)
3．（      ）下列排序算法中，哪种算法不能保证每趟排序至少能将一个元素放到其最终的位置上？
      A.快速排序    B. shell排序  C. 堆排序    D. 冒泡排序
4.（      ）一棵非空的二叉排序树在先序线索化后，其中值为空的链域的个数是：
        A.不确定        B. 0          C. 1            D.  2
5（      ）对于线性表最常用的操作是查指定序号的元素和在末尾插入元素，则选择哪种最节省时间？
    A．顺序表                      B. 单链表 
    C带头接点的双循环链表          D带尾接点的单循环链表
6（      ）求解最短路径的Floyd算发的时间复杂度为：
    A． O(n)    B. O(n+c)  C.  O(n2)   D. O(n3)
7（      ）数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算发中哪种算法的两趟排序后的结果？
    A．选择排序  B 冒泡排序  C 插入排序  D 堆排序
8（      ）下列序列中，哪个是堆？
        A．（100，80，55，60，50，40，58，35，20） 
    B．（100，80，55，60，50，40，35，58，20）
    C．（100，80，55，58，50，40，60，35，20） 
    D．（100，70，55，60，50，40，58，35，20） 
9（      ）一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：
    A．不确定    B 0    C 1      D 2
10（      ）算术表达式A+B*（C+D/E）转为后缀表达式后为：
A：AB+CDE/*
B：ABCDE/+*+
C：ABCDE/*++
D：ABCDE*/++
三、判断题（在括号内填上“√”或“╳”，每题1分，共10分，做错不倒扣）
1.（    ）线性表的特点是每个元素都有一个前驱和一个后继。
2.（    ）链队列执行出队操作不会改变头指针的值，但可能会改变尾指针的值。
3.（    ）所谓取广义表的表尾就是返回广义表中的最后一个元素。   
4.（    ）在后序线索二叉树中，仅借助于线索来求解任意结点的后继是不行的   
5.（    ）非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子
6.（    ）即使有向无环图的拓扑序列唯一，也不能唯一确定该图。
7.（    ）有向图中顶点V的入度等于其邻接矩阵中第V行中的1的个数。
8.（    ）广度遍历生成树描述了从起点到各顶点的最短路径。
9.（    ）冒泡排序算法在最好情况下的时间复杂度为O（n）。
10.（    ）凡是用数组存储的线性表一定是顺序表。
四、（1）（8分）给出如下关键字序列321，1576，57，46，28，7，331，33，34，63试按链基数排序方法，列出每一趟分配和收集的过程。
（2）（6分）可以生成如下的二叉排序树的关键字初始排列有几种？请写出其中任意的3个。
   
（3）已知一棵二叉树的先序 中序和后序序列如下，其中空缺了部分（空格代表一个字母），请画出该二叉数。(8分)
先序：—BC—EFG—IJK—
中序：CBED—GAJ—H—L
        后序：—E—FD—J—L—HA
（4）（8分）请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x)：元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x； sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enquence(Q,x)：插入一个元素x入队列Q；dequence(Q,x):删除队列的首元素，赋值给x；quence_empty(Q)：判断队列Q是否为空。

五、程序填空：  每格2分
（1）二叉查树的非递归算法：
在root指向的树中查元素item，若到返回item的结点指针，否则返回空。
template<class T>
BTNode<T> *&BiSearchTree<T>::Find(const T &item)
{    if(root!=NULL)
    {    BTNode<T> *temp=root;
        while(                         )
        {    if(temp->element==item) return temp;
            if(temp->element<item)                                    ;
            else temp=temp->Left();
        }
    }
                                    ;
}
（2）字符串匹配：判断字串t是否在字串st的start位置后面出现，若是，则返回首次出现的位置，否则返回-1
int mymatching(char *str,char *t,int start)
{    int i=start,j=0,v;
    while (i<strlen(str)&&                          )
    {    if (str[i]==t[j])
        {    i++;                             ;        }
        else
        {    i=++start;
                                    ;
        }
    }
    if (j>=strlen(t)) v=i-strlen(t);
    else                         ;
    return v;
}
（3）有向图的拓扑排序：
struct node { int vex; struct node *next;} g[nv+1];
// 图用邻接链表g表示，g[i].vex表示第i个结点的入度
void toporder()

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。