2006 - 2007学年第一学期末考试卷B

浙江林学院 2006---2007学年第一学期末考试卷（B）

课程名称：数据结构 课程类别：必修 考试形式：闭卷 注意：本试卷一共五大题, 都为必做题目,请认真读题，给出答案。

一 二 三 四

一、填空题(10×2 = 20 分，每题2分)

1 、______________指算法执行过程中所需要的最大存储空间。

2 、对于频繁进行插入和删除的线性表，宜采用______________做存储结构。 3 、已知顺序表中一个元素的存储位置是 x，每个元素占 c个字节，求其后续元素的存储位置计算公式为 ____________ 4 、栈是一种具有__________特性的线性表。

5 、在循环单链表中，最后一个结点的指针指向_________结点。 6 、8层完全二叉树至少有______个结点。

7 、栈和队列的区别仅在于__________操作定义不相同。

8 、有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的带权路径长度WPL为______。

9 、已知一个连通图的边集为{(1,2)3, (1,3)6, (1,4)8, (2,3)4, (2,5)10, (3,5)12, (4,5)2}，则度为3的顶点个数有________个

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

二、判断(对的打∨,错误打×, 10×1 = 10 分)

1、 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法

的期望运行时间。( )

2、 线性表的特点是每个元素都有一个前驱和一个后继。( )

3、 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 4、 n个元素进队列的顺序和出队列的顺序总是一致的。( ) 5、 空串是指仅由一个或多个空格组成的串。( ) 6、 将一棵树转成二叉树，根结点没有左子树。( )

7、 当树中结点数多于 1个时，不可能根据结点的前序序列和后序序列唯一地

第 1 页 共 5 页

五 得分 确定该树的逻辑结构。 ( )

8、 用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关( ) 9、 不同的求最小生成树的方法最后得到的生成树是相同的.。( ) 10、含有n个结点的二叉排序的平均查找长度和树的形态有关( )

三、选择题（20×2=40分）

1、 算法分析的主要任务是分析 ( )

A. 算法是否具有较好的可读性 B. 算法中是否存在语法错误

C. 算法是否健壮 D. 算法的执行时间和问题规模之间的关系 2、 下面程序的时间复杂度为( )

i=1;k=0;n=100; do { k=k+10*i; i=i++;

} while(i!=n);

A. O(n) B. O(n*n) C. O(nlogn) D. O(n*n+2n)

3、 在一个单链表中，已知 q 指向 p 所指向结点的前驱结点，若在 q，p 所

指结点之间插入一个 s所指向的新结点，则执行的操作是( ) A. q - >next=s；s- >next=p； B. q - >next=s- >next ；s- >next=p； C. p - >next=s；s- >next=q； D. s- >next=p - >next；p - >next=s；

4、 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈

序列？( )

A. 2 3 4 1 5 6 B. 1 2 4 5 3 6

C. 6 4 5 1 2 3 D. 4 5 3 1 2 6

5、 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i

（1<=i<=n）个元素是( )。

A. n-i+1 B. n+1 C. 不确定 D. i+1

6、 输入序列为ABC，可以变为CBA时，经过的栈操作为( ) A. push,pop,push,pop,push,pop

B. push,push,push,pop,pop,pop C. push,pop,push,push,pop,pop D. push,push,pop,pop,push,pop

第 2 页 共 5 页

7、 假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件

是( ) 。

A. f = = r C. f = = 0

A.12 C.14

B. r+1 = = f D. f = = 0 B.13 D.15

8、设s1=\则strlen(strcat(s1,s2))的值为（ ）

9、对于一棵具有n个结点、度为4的树来说 A. 树的高度至多是 n-3 B. 树的高度至多是 n-4 C. 树的高度至多是 n-5 D. 第i层上至少有4个结点

10、根据使用频率为五个字符设计的哈夫曼编码不可能是 A. 111，110，l0，01，00 B. 100，11，10，1，0 C. 000，001，010，0ll ,1 D.001，000，01，11， 10 11、线性链表具有的特点( ).

A.随机访问 B.需要事先估计所需存储空间大小 C.插入与删除时不必移动元素 D.所需空间与线性表长度成反比 12、向顺序栈中压入新元素时,应当( ).

A.先移动栈顶指针,再存入元素 B.先存入元素,再移动栈顶指针 C.先后次序无关紧要 D.同时进行

13、具有129个结点的完全二叉树的高度为( ). (根的层次号为1)

A.8 B.7 C.6 D.5

14、由权值分别为13，28，10，42，86的叶子结点生成一棵哈夫曼树，则其

中非终端结点数为( )。

A. 2 B. 3

C. 4 D. 5

15、n个顶点的无向图中含有向边的数目最多为( )

A.n-1 B.n C.n(n-1)/2 D.n(n-1)

16、对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键字等于给定值，此时元素比较顺序依次为（ ）。

A．R[0]，R[1]，R[2]，R[3] B．R[0]，R[13]，R[2]，R[3] C．R[6]，R[2]，R[4]，R[3] D．R[6]，R[4]，R[2]，R[3]

17、一个对象序列的排序码为{46,79,56,38,40,84},采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为( ).

第 3 页 共 5 页

A.{38,46,79,56,40,84} B.{38,79,56,46,40,84} C.{40,38,46,56,79,84} D.{38,46,56,79,40,84} 18、关键路径是指AOE-网中

A. 从开始结点到完成结点的最短的路径 B. 最长的回路 C. 从开始结点到完成结点的最长的路径 D. 最短的回路

19、长度为17的哈希表中已经填有关键字37，60，29的记录，采用二次探测再散列方法解决冲突，则填入关键字38其地址应该为( )（哈希函数为h(key)=key mod 11）

A.4 B.5

C.3 D.6

20、在一个有向图中,所有顶点的度数之和等于所有边数的( )倍. A.3 B.2 C.1 D.1/2

四、程序分析设计题(共30分,其中1-4为必做题，信息工程学院学生5，6选一，其他学院学生5，6，7，8任意选一) 1、用栈对算术表达式求值：3*（7-2），写出堆栈的操作顺序和过程（本题5分)

2、对于给定的一组权值W={7，2，8，4，16，3，9}，请构造出哈夫曼树（最优二叉树），并计算出其带权路径长度。（构造出二叉树3分，计算带权路径长度2分，共5分）

3、请简述折半查找的查找过程，编写一个在有序表中折半查找给定关键字记录的算法（5分）

4、请根据给出的网络（带有权值的无向图），回答下列问题：（5分） 18 1 1． 该图的邻接矩阵； 62312 2． 该图的邻接表形式；（和邻接矩阵必须对应）

47 5 3． 该图从顶点1出发的深度优先搜索序列； 15 4． 该图从顶点1 出发的广度优先搜索序列； 7 6 5． 该图的一棵最小代价生成树。 20

5、试设计一个非递归求算二叉树T中叶子节点个数的算法。（10分） 要求：先描述算法思想，再写出完整的C语言程序。 6、描述希尔排序的算法并写出C语言程序。（10分）

2 58 3 104 第 4 页 共 5 页

要求：先描述算法思想，再写出完整的C语言程序。

7、试设计一个计算二叉树T非叶子个数的算法。（提示可用递归方法）（10分） 要求：先描述算法思想，再写出完整的C语言程序。 8、描述直接插入排序的算法并写出C语言程序。（10分） 要求：先描述算法思想，再写出完整的C语言程序。

第 5 页 共 5 页

本文来源：https://www.bwwdw.com/article/b19o.html