2013级软件工程(云计算方向)专业《数据结构与算法》期末考试(A卷)

福建师范大学 软 件 学院 2014 — 2015 学年第 1 学期考试 A 卷

专 业：软件工程(云计算方向) 年 级： 2013级 课程名称: 数据结构与算法 任课教师： 试卷类别：开卷（ ）闭卷（√） 考试用时： 120 分钟 考试时间: 年 月 日 午 点 分 题号 一 二 三 四 五 总得分 评卷人 得分 题号 六 七 八 九 十 得分 Score Marker Checker 一、 单择题（每题2分，共60分） （请将答案填写到下面表格中， 否则不给分） 题号 1 2 3 4 5 6 7 8 9 10 答案 题号 11 12 13 14 15 16 17 18 19 20 答案 题号 21 22 23 24 25 26 27 28 29 30 答案 1、算法分析的两个主要方面是（ ）。 A．空间复杂度和时间复杂度 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性

福建师范大学试卷纸 第 1 页 共 8 页

2、设语句x++的时间是单位时间，则以下语句的时间复杂度为（ ）。 for(i=1; i<=n; i++) for(j=1; j<=n; j++) x++;

A．O(1) B．O (n2) C．O(n) D．O (n3) 3、以下哪种逻辑结构关系最紧密（ ） A．集合 B．线性 C．树 D．图

4、以下哪种线性表的存储地址一定是连续的（ ）

A．有序表 B．顺序表 C．单链表 D．双链表 5、带尾指针的循环链表在表头插入，时间复杂性 ( ) A．O(1) B．O(n） C．O (n2) D．O (n3)

6、设结点结构为(data, next)，L是带头结点和尾指针的单循环链表，L->last是表尾结点指针。若想删除链表的首元结点，则应执行下列（ ）操作？ A．s = L->last; L->last= L->last->next; free(s); B．L->last= L->last->next; free(L->last);

C．L->last= L->last->next->next; free(L->last);

D．s = L->last->next->next; L->last->next->next = s->next; free(s); 7、不带头结点的单链表L为空的判定条件是（ ） A．L->next == NULL; B．L!= NULL; C．L->next== L; D．L== NULL;

8、设结点结构为(prior,data,next)，L是不带头结点循环双链表，L是表头结点指针。若想删除循环双链表中p结点的后继结点(假设存在)，则应执行下列（ ）操作？ A．p->next = p->next->next;

B．p->next = p->next->next; p->next->prior = p;

C．p->next = p->next->next; p->next->next->prior = p;

D．p->next->prior = p; p->next = p->next->next; 9、若在线性表中经常涉及按元素序号查找元素，则采用以下哪种表进行元素存储比较好（ ）？ A．有序表 B．顺序表 C．单链表 D．双链表

10、在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时，需向前移动（ ）个元素。

A．n-i B．n-i+1 C．n-i-1 D．i

11、假定对元素序列（7, 3, 5, 9, 1, 12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（ ）。

A．1, 3, 5, 7, 9, 12 B．1, 3, 5, 9, 7, 12 C．1, 5, 3, 7, 9, 12 D．1, 5, 3, 9, 12, 7

12、假定一个初始堆为(1, 5, 3, 9, 12, 7, 15, 10)，则进行第一趟堆排序后得到的结果为（ ）。

A．3, 5, 7, 9, 12, 10, 15, 1 B. 3, 5, 9, 7, 12, 10, 15, 1 C. 3, 7, 5, 9, 12, 10, 15, 1 D. 3, 5, 7, 12, 9, 10, 15, 1 13、在平均情况下速度最快的排序方法为（ ）

A．直接选择排序 B．归并排序 C．基数排序 D．快速排序

福建师范大学试卷纸 第 2 页 共 8 页

14、若一个元素序列基本有序，则选用（ ）方法较快。 A．直接插入排序 B．简单选择排序 C．归并排序 D．快速排序 15、以下（ ）算法是稳定的算法。 A．直接选择排序 B．堆排序

C．归并排序 D．快速排序

16、设元素的进栈次序为A, B, C，那么有____种出栈的元素序列。 A．1 B．5 C．6 D．8

17、栈的插入和删除操作在（ ）进行。

A．栈顶 B．栈底 C．中间 D．任意位置 18、栈中元素的进出原则为（ ）。

A．先进先出 B．后进先出 C．大数先出 D．小数先出 19、任何二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ ）。

A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对

20、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。

A. 24 B. 48 C. 72 D. 53

21、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。

A. 4 B. 5 C. 6 D. 7 22、在一棵二叉树上第4层的结点数最多为（ ）。

A. 2 B. 4 C. 6 D. 8 23、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（ ）。

A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1]

24、已知图中某条路径路径长度为k，则该路径上有（ ）个顶点。

A．k-1 B．k C．k+1 D．2k

25、以下( )算法用于在有向网中求单源最短路径。 A．普里姆算法 B．克鲁斯卡尔算法 C．迪杰斯特拉算法 D．弗洛伊德算法

26、在一张有向图中，若一个顶点的入度为k1，出度为k2，则对应邻接表中该标点单链表中的结点数为( )。

A．k1 B．k2 C．k1+k2 D．2(k1+k2)

27、设有8个结点的无向图，该图至少应用( )条边能确保是一个连通图。 A．5 B．6 C．7 D．8

28、10个顶点组成的有向完全图中，有( )条弧。 A．45 B．90 C．100 D．200

29、对于顺序存储的有序表(5,12,20,26,37,42,46,50,)，若采用折半查找，则查找元素26的比较次数为( )。

福建师范大学试卷纸 第 3 页 共 8 页

A. 2 B. 3 C. 4 D. 5 30、假定对线性表(38,25,74,52,48)进行哈希存储，采用H(k)=k%6作为哈希函数，采用开放定址法处理冲突，则在建立哈希表的过程中，将会碰到( )次存储冲突。 A. 0 B. 1 C. 2 D. 3 二、填空题（每空2~4分，共30分） Score Marker Checker 1、已知记录 (46,74,53,14,26,38,86,65,27,34)，请给出快速排序的第一趟排序结果(以第一个元素作为基准)：______ (2分) 2、从一棵二叉排序树中查找一个元素时，若元素的值小于根结点的值，则继续向____查找。(2分) 3、将n阶对称矩阵只存储下三角部分，共需_ 个存储空间。(2分) 4、下图所示的有向无环图，写出所有的拓扑序列：______ (2分) 5、假定一组数据对象为 ( 40, 28, 16, 56, 50, 32, 30, 63 )，按次序插入每个对象生成一棵AVL树（高度平衡的二叉搜索树），请回答以下问题: (1) 在插入16时需要进行______________操作, 使树保持平衡. (2分) (2) 在插入50时需要进行______________操作, 使树保持平衡. (2分) (3) 在插入32时需要进行______________操作, 使树保持平衡. (2分) 6、假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树______(4分)，并写出该二叉树的后序遍历序列______________________________。(2分) 福建师范大学试卷纸 第 4 页 共 8 页

7、已知图的邻接矩阵定义如下： public class AdjMatrixGraph extends AbstractGraph { private static final int MAX_VERTEX_NUM=20; protected char vexs[MAX_VERTEX_NUM]; //顶点数组 protected int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 protected int vexnum, arcnum; //顶点数与边(弧)数 } 注：邻接矩阵arcs中，1表示有边，0表示无边。 下列程序段为图的深度优先搜索算法，请将算法中缺失的语句补充完整： //从编号为v的顶点出发进行深度优先搜索遍历 public void DFS (AdjMatrixGraph G, int v) { //假设所有变量、函数皆已定义 boolean[] visited=new boolean[vexnum] //访问标志数组，true表示访问过，false表示未被访问过 System.out.print (vexs[v]); //在控制台输出v标点 for( j=0; ______________(2分);______________ (2分)) { if(______________(2分)&&______________ (2分)) { ______________; (2分) } } } 三、分析题（每题10分，共10分） 1、已知下图，请根据Dijkstra算法，分析最短路径，初始点为{ 1 }。 Score Marker Checker 10 1 30 100 2 50 3 5 10 20 4 60 福建师范大学试卷纸 第 5 页 共 8 页

＿＿＿＿＿号学 ＿＿ 栏＿＿ ＿ ＿ 名 姓 息 级 年线 ＿ ＿ ＿ 信 ＿ ＿ ＿ 业 专订 ＿ 生 ＿ ＿ ＿ ＿ ＿ 系 考＿装＿＿＿＿＿院学＿＿＿＿＿＿

福建师范大学试卷纸 第 6 页 共 8 页

福建师范大学试卷纸 第 7 页 共 8 页

福建师范大学试卷纸 第 8 页 共 8 页