2012 11级算法与数据结构 B卷

装订 线

2012—2013学年第一学期闽江学院考试试卷

5、队列又称为 ( )。

A. FIFO表 B. LIFO表 C. 散列表 D.哈希表 考试课程：数据结构与算法

6、若进栈序列为1、2、3、4，进栈过程允许出栈，则下列出栈序列中，（ ）是不可能的。 试卷类别：B卷 考试形式：闭卷 A. 1、3、4、2 B. 2、4、3、1 适用专业年级：11电子信息工程、11电子科学与技术 、11电子信息科学与技术 C. 3、4、2、1 D. 1、4、2、3 班级 姓名 学号

7、如下陈述中正确的是（ ）

A．串的长度必须大于零 B．串是一种特殊的线性表

题号 一 二 三 四 五 总分 C．空串就是空白串 D．串中元素只能是字母

得分 8、下面程序段的时间复杂度为（ ）。 i=-1；s=0； 一、选择题 （共15小题，每题2分） 30% 得分 while(s

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A.O(n) B.O(n^2) C.O(log2n) D.O(1)

9、深度为5的二叉树至多有（ ）个结点。

A. 30 B. 31 C. 32 D. 63

1、以下数据结构中，（ ）是线性结构。

A. 有向图 B. 栈 C. 二叉树 D. 森林 10、某二叉树如图所示，对该二叉树进行中序遍历的结点序列为（ ）。

A. 1, 2, 3, 4, 5, 6, 7 2、在长度为n的顺序表中，向第k个元素（1≤k≤n+1）之前插入一个新元素时，需向后B. 1, 2, 4, 6, 7, 3, 5 移动（ ）个元素。

C. 2, 6, 4, 7, 1, 5, 3 A. n-1 B. n-k-1 C. n-k+1 D. k D. 6, 7, 4, 2, 5, 3, 1

3、用链表表示线性表的优点是（ ）。

11、有n个顶点的无向完全图中，具有（ ）条边。

A. 便于随机存取 B. 存储的密度较高

A. n(n-1)/2 B. n(n-1) C. n(n+1)/2 D. n2 C. 便于元素的插入和删除操作 D. 元素的物理顺序与逻辑顺序一致

12、采用顺序检索的方法检索长度为n的顺序表，检索每个元素的平均比较次数（即平均4、设用一维数组S存储一个栈，令S[n-1]为栈底，变量top表示当前栈顶的位置（下标），检索长度）为（ ）。

即S[top]为栈顶元素。则，栈满的条件表达式应为（ ）。

A. n B. n/2 C. (n+1)/2 D. (n-1)/2 A. top==n B. top==n-1 C. top==0 D. top==-1

13、以下关键码序列中，（ ）不是一个堆。

2014年2月14日

共 6 页 第1页

共 6 页 第2页

A.（100，85，98，77，80，60，82，40，20，10，66） B. （100，98，85，82，80，77，66，60，40，20，10） C. （100，85，40，77，80，60，66，98，82，10，20） D. （10，20，40，60，66，77，80，82，85，98，100）

14、对一组字母序列（Q，D，F，X，A，P，N，B，Y，M，C，W）用归并排序方法进行一趟归并后的结果为（ ）。

A.（D，F，Q，X，A，B，N，P，C，M，W，Y） B.（D，F，Q，A，P，X，B，N，Y，C，M，W） C.（D，Q，F，X，A，P，N，B，Y，M，C，W） D.（D，Q，F，X，A，P，B，N，M，Y，C，W）

15、以下4种排序算法中，时间复杂度最小的是（ ）。

A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序

1、（ ）一个n维数组可以视为其数据元素是n-1维的线性表。 2、（ ）子串“BC”在主串“CBABCABCD”中的位置为3。 3、（ ）队列是顺序存储的线性结构。

4、（ ）顺序存储结构不仅能用于表示完全二叉树，也能表示一般的二叉树。

5、（ ）二叉树先序遍历序列的最后一个结点，必是其中序遍历序列中的最后一个结点。 6、（ ）n个带权叶子结点构成的哈夫曼树（最优二叉树）是唯一的。 7、（ ）邻接表只能用于有向图的存储。

8、（ ）运用折半检索时，检索表中的元素必须以关键字递增（由小到大）有序排列。 9、（ ）散列表中若不存在地址冲突或同义词，则其成功检索的平均检索长度等于1。 10、（ ）对n个元素的集合进行归并排序时，需要的辅助存储空间为O(log2n)。

二、填空题（共5小题，每空 2分） 14%

得分 四、应用题（共6小题） 36% 得分 1、已知一棵二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDAHGF，试画出该二叉树。(4分)

1、在一个单链表中，在指针p所指向的结点之后插入指针s所指向的结点时，应执行如下操作：s->next= ; p->next= ;

2、n个结点的二叉链表中，共有2n个指针，其中有 个指针用于指向左、右孩子，剩余的 个指针为空。

3、由3个结点可以构成 棵形态不同的二叉树。

4、已知Huffman树的总结点数为m，叶子数为n，则m=________ 。

5、对于一个具有n个顶点e条边的无向图，若采用邻接表表示，则它的邻接表需n个表头结点和_____________个表结点。

（1）画出插入完成后的二叉排序树。(5分)

（2）设各数据元素的查找概率相等，给出该二叉排序树的平均查找长度。（1分）

?03、无向图G的顶点依次为a、b、c、d和e，其邻接矩阵如下，要求： ?1?(1) 画出该图。（3分）

?1(2) 从顶点a出发进行深度优先搜索所得到的序列和深度优先生成??1树；（2分） ??01110?0101??1010??0101?1010??

2、已知顺序表中存储的序列{19, 14, 22, 1, 66, 21, 83, 27, 56, 13}，将元素按其在表中的次序依次插入到一棵初始为空的二叉排序树中，要求：

(3) 从顶点b出发进行广度优先搜索所得到的序列和广度优先生成树；（2分）

三、判断题（共10小题，每题1分） 10% 得分 4、对下列数据表，写出采用冒泡排序算法排序的每一趟的结果（由前往后开始比较，最后结果为升序），（27，10，21，37， 9，55，16，61，103，2）。（9分）

2014年2月14日 共 6 页 第3页 共 6 页 第4页

5、对下图所给的带权有向图执行dijkstra算法，求顶点v1到其余顶点的最短路径。（5分）

{ elemtype data;

struct node *next; } listnode, *linklist; 主函数如下：

#include main()

{ linklist L; int n；

L=createlist(); n=length(L);

printf(\

6、对于下图给出的无向图，给出用Prim算法求得最小生成树的过程。（5分）

2、二叉树用以下静态二叉链表作为存储结构

#define n0 100 //数组最大下标

typedef char datatype; struct node

{ datatype data;

int lch,rch; //lch指向左子树，rch指向右子树 } tree[n0+l];

int root; //根结点指针

下面是先序遍历二叉树的非递归算法。一维数组s作为栈，t为栈顶指针。 请在下划线处填空，使程序完整。（5分） void preorder（）

{ int s[n0+l],t= ; int p=root;

while(p || ) if( p )

{ printf(“%c”, ) s[++t]= tree[p].rch;

p= tree[p]. ; }

else p=s[ ]; }

2 V2 2 V1 3 V3 1 V4 5 V5 4 V7

6 3 1 4 V6 1 V8

五、编程题（共2小题，每题5分） 10 % 得分 1、有一个不带头结点的单链表，指向第一元素结点的指针为hp，试编写计算单链表长度（结点个数）的算法函数length。假设，已定义单链表的结点类型node，它含有存放元素的data域和指向后继结点的指针域next。（5分） 链表结点类型定义如下：

typedef int elemtype; typedef struct node

2014年2月14日

共 6 页 第5页

共 6 页 第6页