莆田学院期末考试试卷 （a）卷。
2007 ——2008 学年第一学期。
课程名称： 数据结构适用年级/专业： 06/计应、计教
试卷类别开卷（ ）闭卷（√）学历层次本科考试用时 120分钟
考生注意：答案要全部抄到答题纸上，做在试卷上不给分》
一、单项选择（每小题2分，共20分）
）1．算法的计算量的大小称为计算的（ ）
a．可读性b. 复杂性 c. 现实性d. 难度。
）2．链接存储的存储结构所占存储空间：
a．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。
b．只有一部分，存放结点值。
c．只有一部分，存储表示结点间关系的指针。
d．分两部分，一部分存放结点值，另一部分存放结点所占单元数。
）3．对于顺序存储的线性表，访问结点和删除结点的时间复杂度为（ ）
a．o(n) o(n) b. o(n) o(1) c. o(1) o(n) d. o(1) o(1)
）4．设有4个数据元素a1、a2、a3和a4，对他们进行队操作，在进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设队的初始状态是空，进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是（ ）
a．a1b. a2 c. a3d. a4
）5．有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）
a.10b. 66c. 18000d. 33
）6．串的长度是指（ ）
a．串中所含不同字母的个数 b．串中所含字符的个数。
c．串中所含不同字符的个数 d．串中所含非空格字符的个数。
）7．设森林f中有三棵树，第一，第二，第三棵树的结点个数分别为m1，m2和m3。与森林f对应的二叉树根结点的右子树上的结点个数是（ ）
a．m1b．m1+m2 c．m3d．m2+m3
）8．用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。
a．栈b. 队列c. 树d. 图。
）9．在表长为ｎ的链表中进行线性查找，它的平均查找长度为。abcd
）10．下列关键字序列中， （是堆。
a. 16, 72, 31, 23, 94, 53 b. 94, 23, 31, 72, 16, 53
c. 16, 53, 23, 94，31, 72 d. 16, 23, 53, 31, 94, 72
二、填空题（每空2分，共30分）
1．数据结构被形式地定义为（d, r），其中d是的有限集合，r是d上的关系有限集合。
2．在带有头结点的单向循环链表(头结点为*head)中，至少有一个结点的条件是。
3．在一个长度为n的顺序表中，如果要删除第i个元素（0<=i<=n-1），需向前移动。
① 个元素。
4．循环队列的引入，目的是为了克服。
5．广义表(((a),b),c)深度为。
6．由3个结点所构成的二叉树有种形态。
7．无向图g=(v,e),其中：v=,e=，对该图进行深度优先遍历，得到的顶点正确的。
8．在aoe网中，某些关键活动提前完成，那么整个工程会提前完成。
9．散列法存储的基本思想是由决定数据的存储地址。
10. 对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为。
三、应用题（每小题10分，共50分）
1．给定二叉树的两种遍历序列，分别是：前序遍历序列：d，a，c，e，b，h，f，g，i； 中序遍历序列：
d，c，b，e，h，a，g，i，f，（1）画出二叉树；（2）给出二叉树中序遍历序列；(3)至少还需几个结点可以构成一个完成二叉树？
2．给定集合。
1)用□表示外部结点，用○表示内部结点，构造相应的huffman树：
2)计算它的带权路径长度：
3)写出它的huffman编码：
4) 写出外部结点n外和内部结点n内的关系。
3．请对下图的无向带权图：
1)写出它的邻接矩阵。
2)按普里姆算法求其最小生成树；
4．假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
(1)画出描述折半查找过程的判定树；
(2)若查找元素54，需依次与哪些元素比较？
(3)若查找元素90，需依次与哪些元素比较？
(4)假定每个元素的查找概率相等，求查找成功时的平均查找长度。
5．给定一个关键字序列，请写出快速排序第一趟的结果；归并排序的全过程。然后回答上述二种排序方法中那一种方法使用的辅助空间较少？
四、算法设计题（10分）
编写一个算法，将十进制数据转换为八进制数据。
要求：利用顺序栈求解，堆栈的基本操作(创建空栈：createemptystack；入栈：
push_seq；出栈：pop_seq；取栈顶元素：top_seq；判断空栈：
isemptystack)可直接引用，必须先给出顺序栈的说明。
数据结构A期末试卷 A卷
试卷编号拟题教研室 或教师 签名乐晓波教研室主任签名。长沙理工大学考试试卷 a卷 课程名称 含档次 数据结构a 课程代号 0812002615 课程编号 002131 专业计算机相关专业层次 本 专 本科考试方式 开 闭卷 闭卷 一 应用题 2小题，共8分 设有一个栈，元素进栈的次序为 a，b，c，...
2019《数据结构》期末试卷A卷
一 本题10分 1 线性表和广义表的主要区别是什么？2 已知广义表 c a,b,a,b a,b a,b 则tail head tail c 二 本题10分 简述二叉树的两种存储结构 顺序存储和链式存储 的数据结构及主要优缺点。在哈夫曼树中，使用哪种存储结构，并说明理由。三 本题10分 一棵二叉树的先...
2019《数据结构》期末试卷B卷
一 本题10分 1 线性表和广义表的主要区别点是什么？已知广义表 c a,b,a,b a,b a,b 则tail head tail c 2 满足什么条件可以实施二分查找？二分查找的时间复杂度是多少？二 本题10分 证明 一棵二叉树的先序序列和中序序列可惟一确定这棵二叉树。三 本题15分 某带权有向...