09春《数据结构与算法分析》试卷B1

西北农林科技大学本科课程考试试题（卷）

2008—2009学年第2学期《数据结构与算法分析》课程B 卷

专业班级： 命题教师： 审题教师：

学生姓名： 学号： 考试成绩：

一、选择题（每小题2分，共20分） 得分： 分

1．冒泡排序算法的时间复杂度为（ ）

A.O(2n) B.O(n) C.O(n2) D.O(log2n)

2．主关键字能唯一标识（ ）

A．一个记录 B．一组记录 C．一个类型 D．一个文件

3．已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( )

A.a c e f b d

B.a c b d f e

C.a c b d e f

D.a c d b f e

4．一棵有16结点的完全二叉树，

对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（ ）

A．2，14 B．2，15 C．3，14 D．3，15

5．串的长度是指（ ）

A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数

6．对顺序表进行二分法查找时，要求顺序表必须（ ）

A．以顺序方式存储

C．以链接方式存储 B．以顺序方式存储，且数据元素有序 D．以链接方式存储，且数据元素有序

7．一组记录的键值为（46，79，56，38，40，84），利用堆排序的方法建立的初始堆为（ ）

A．（79，46，56，38，40，84） B．（84，79，56，38，40，46）

C．（84，79，56，46，40，38） D．（84，56，79，40，46，38）

8.在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是

( )

第 1 页 共 5 页

A.0 B.2 C.3 D.5

9.已知广义表的表头为a，表尾为(b,c)，则此广义表为( )

A.(a,(b,c)) B.(a,b,c) C.((a),b,c) D.((a,b,c))

10.二叉树中第5层上的结点个数最多为( )

A.8 B.15 C.16 D.32

二、填空题（每空2分，共30分） 得分： 分

1．数据的逻辑结构通常包括集合、线性结构、 和图状结构。

2．队列可以看成是一种运算受限制的线性表，也称为_ 线性表。

3．已知一棵哈夫曼树含有60个叶子结点，则该树中共有_______个非叶子结点。

4．在具有n （n>1）个结点的树中，深度最大的那棵树深度是 。

5．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为_____ 。

6．设某非空双链表，其结点形式为 若

点，则需执行下述语句段：q->prior->next＝q->next; ;free(q)。

7．栈中允许进行插入或删除的一端是 。

8．如图所示的二叉树，若按后根遍历，则其输出序列为________________。

要删除指针q所指向的结，

9．一个具有n个顶点的有向完全图的弧数为________________。

10．对稀疏矩阵进行压缩存储的目的是节省 。

11．如果希望循环队列中的向量单元都能得到利用，则可设置一个标志域tag,每当尾指针和头指针值相同时，以tag的值为0或1来区分队列状态是“空”还是“满”。请对下列函数填空，使其分别实现与此结构相应的入队列和出队列的算法。

int EnQueue(CirQueue *Q,DataType x){ if( ) return 0;

Q->rear=(Q->rear+1)% MAXQSIZE

Q->data[Q->rear]=x;

第 2 页 共 5 页

;

return 1;

}

int DeQueue(CirQueue *Q,DataType *x) {if( ) return 0;

*x=Q->data[Q->front]; Q->front= ; ;

return 1;

}

三、解答题（每小题6分，共30分） 得分：

1．画出下列二叉树的二叉链表表示图。

2. 画出与如图所示森林对应的二叉树。

第 3 页 共 5 页 分

112610 1 89 3．已知连通网的邻接矩阵A= 128 2 ， 试画出它所表示的连通网并画出该连通网的最小 69 4 10 24

生成树。

4. 假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符。

5. 已知无向图G的邻接表如图所示，请画出该无向图，并写出其按深度优先搜索时的访问序列。其中nil表示空。

1

2

3

4

第 4 页 共 5 页

四、程序设计题（每小题10分，共20分） 得分： 分

1.已知单链表A，表的结点结构如下：

struct node{datatype data;

struct node *next;};

试编写一个函数void copy(struct node *A, struct node *B)复制不带头结点的单链表A到B。

2.以二叉链表为存储结构，写出求二叉树叶子结点个数的算法int Countleaf（Bitree *t

第 5 页 共 5 页 ）。