姓名。班级学号。系部名称。
专业名称。数据结构》试题（卷二）
适用班级）
2012/2013学年第二学期期末试题。
一、 单项选择题 (每小题1分，共15分)
1. 下面程序段的时间复杂度是（ a ）。
s=0;for( i =0; is+=a[i];
a）o(nb）o(1c）o(0) d）o(n2)
2. 在以下的叙述中，正确的是（ c ）。
a）线性表的顺序存储结构优于链表存储结构 b）栈的操作方式是先进先出。
c）二维数组是其数据元素为线性表的线性表 d）队列的操作方式是先进后出。
3. 不带头结点的单链表head为空的判定条件是（ d ）。
a）head! =nullb） head->next ==null
c）head->next ==headd） head==null
4. 如果最常用的操作是取第i个结点及其前驱，则采用（ d ）存储方式最节省时间。
a）单链表 b）双链表 c）单循环链表 d） 顺序表。
5. 在n个结点的线性表的数组实现中，算法的时间复杂度是o（1）的操作是（ a ）。
a）访问第i（1<=i<=n）个结点和求第i个结点的直接前驱（1b）在第i（1<=i<=n）个结点后插入一个新结点。
c）删除第i（1<=i<=n）个结点。
d）以上都不对
6. 栈和队列的共同点是（c ）。
a） 都是先进先出b） 都是先进后出
c） 只允许在端点处插入和删除元素 d） 没有共同点。
7. 稀疏矩阵一般的压缩存储方式有两种，即（b ）。
a）二维数组和三维数组b） 三元组和十字链表。
c）三元组和散列d） 散列和十字链表。
8. 深度为4的二叉树至多有（ a ）个结点。
a）15b） 16c） 8d）10
9. 设栈s和队列q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈s，一个元素出栈后即进队列q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈s的容量至少应该是（ 3 ）。
a） 2 b） 3 c） 4d） 6
10. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ b ）。
a）9 b）11 c）15 d）不确定。
11. 具有6个度为2结点的二叉树中有（ b ）个叶子结点。
a）6b）7c）8d）9
12. 在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ a ）。
a）完全相同b）都不相同
c）先序和中序相同，而与后序不同 d）中序和后序相同，而与先序不同。
13. 对线性表进行折半查找时，要求线性表必须（ d ）。
a） 以顺序方式存储 b）以链式方式存储，且结点按关键字有序排列。
c） 以链式方式存储 d）以顺序方式存储，且结点按关键字有序排列。
14. 堆排序是一种（ b ）排序。
a）插入b）选择c）交换d）归并。
15. 快速排序在最坏情况下的时间复杂性为(d )。
a）o(nlog2n) b）o(nlogn) c）o(nd）o(n2)
二、 填空题 (每空1分，共15分)
1. 数据逻辑结构包括线性结构、树形结构和图结构三种类型。
2. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后继结点，其余每个结点的后续结点可以任意多个。
3. 一棵有6个叶子结点的哈夫曼树共有 11 个结点。
4. 具有8个叶子结点的二叉树中有 7 个度为2的结点。
5. 线索二叉树的左线索指向其遍历序列中的前驱 ，右线索指向其遍历序列中的后继 。
6. 若用n表示图中顶点数目，则有 n*(n-1)/2 条边的无向图成为完全图。
7. 在图g的邻接表表示中，每个顶点邻接表中所含的结点数，对于有向图来说等于该顶点的出度 。
8. 在分块索引查找方法中，首先查找索引表，然后查找相应的块表 。
9. 顺序查找30个元素的顺序表，若查找成功，则比较关键字的次数最多为 30 次；当使用监视哨时，若查找失败，则比较关键字的次数为 31 。
10. 对于长度为169的表，采用分块查找，每块的最佳长度为 13 。
11. 属于不稳定排序的有希尔排序、快速排序、选择排序和堆排序 。
三、 简答题(每小题5分，共10分)
1. 由3 个结点可以构造出多少种不同的二叉树？画出它们分别对应的逻辑图形表示。
答：5种。（答对一种给1分）
2. 对于一个栈，如果输入项序列由a，b，c组成，试给出全部可能的输出序列。
答：abc acb bac bca cab cba
说明：答对一个给1分。
四、 计算题（每小题8分，共16分）
1. 已知如图所示的有向图：
1）计算每个顶点的入度和出度；（4分）
2）画出该图的邻接矩阵。（4分）
2. 有一组数据：8，15，38，57，68，88，98，108，129，234，256。 请画出采用折半查找法对应的判断树，并计算平均查找长度。
答：asl=(1+2*2+3*4+4*4)/11=33/11=3（2分）
折半查找法对应的判断树6分。
五、 应用题（每小题8分，共32分）
1. 已知一棵树边的集合为；
1）画出这棵树；（4分）
2）将这棵树转换成对应的二叉树。（4分）
2. 已知下图所示二叉树，解答下列问题：
1）写出二叉树先序遍历结果；（4分）
答：a b d e c f g
2）将二叉树转换成为森林。（4分）
3. 使用普里姆算法构造出如图所示图g的一棵最小生成树，并计算其代价。
答：最小生成树6分。
代价=2+4+5+6+8+9=34 （2分）
4. 对有五个顶点的图的邻接矩阵如图所示，解答下列问题：
1）画出该有向图；（4分）
2）写出从v1顶点出发的深度优先遍历和广度优先遍历序列。
深度优先遍历：v1 v3 v4 v2 v5 （2分，答案不唯一）
广度优先遍历：v1 v2 v3 v5 v4 （2分，答案不唯一）
六、 算法设计题（每小题6分，共12分）
1. 设计一个算法，在带头结点的单链表中删除一个最小值结点的算法。（6分）
int deletemin(linklist la)
minpre->next=minp->next;
delete minp;}
2. 假设二叉树采用链式存储方式存储，编写一个二叉树前序遍历的算法。（6分）
答：采用递归或非递归均可。
void preorder (bitree t)
void preorder_f( bitree t )
else//whike
// preorder_f
2019数据结构A卷
数据结构 试卷a 1.算法的时间复杂度取决于 问题的规模 待处理数据的初态和 的长短。2 从逻辑上可以把数据结构分为 两大类。动态结构 静态结构 顺序结构 链式结构 线性结构 非线性结构 初等结构 构造型结构。3.对于栈操作数据的原则是。先进先出 后进先出后进后出不分顺序。4.一个栈的输入序列为12...
《算法与数据结构》A卷
2011 2012学年第一学期期末考试试题 a 卷。课程名称 算法与数据结构 任课教师签名 出题教师签名 2011计算机合作联盟命题组审题教师签名 考试方式 闭 卷适用专业 10计科1 2 考试时间 110 分钟。注 判断题和选择题的答案写在答题纸上 1.与数据元素本身的形式 内容 相对位置 个数无...
数据结构 数据结构与算法大作业二
电子工程系无23班邓创 021372 算法分析。首先把本问题抽象为一个带权图的问题。如图，由6个地点组成的销售网络。其中的路径上的权值已标注。题目要求在每一个点设置一种主销产品，两种辅销产品。对下图来说，不妨设节点n主销第n种产品。这样确定主销产品后，对辅销产品的确定也很方便。即对节点n 1 n 6...