没有合适的资源?快使用搜索试试~ 我知道了~
2020-2021学年《数据结构》期末考试试题及答案.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
5星 · 超过95%的资源 1 下载量 154 浏览量
2022-10-29
22:46:21
上传
评论
收藏 888KB DOCX 举报
温馨提示
试读
126页
2020-2021学年《数据结构》期末考试试题及答案.docx2020-2021学年《数据结构》期末考试试题及答案.docx
资源推荐
资源详情
资源评论
2020-2021 学年《数据结构》期末考试复习试题
一、 单项选择题
1.对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为
(
)。
(A)、正确性
(B). 可行性
(C). 健壮性
(D). 输入性
2.设 S 为 C 语言的语句,计算机执行下面算法时,算法的时间复杂度为(
for(i=n-1;i>=0;i--)
)。
for(j=0;j<i;j++) S;
(A)、n
2
(B). O(nlgn) (C). O(n) (D). O(n )
2
3.折半查找法适用于(
)。
(A)、有序顺序表 (B)、有序单链表
(C)、有序顺序表和有序单链表都可以 (D)、无限制
4.顺序存储结构的优势是(
)。
(A)、利于插入操作 (B)、利于删除操作
(C)、利于顺序访问 (D)、利于随机访问
5.深度为 k 的完全二叉树,其叶子结点必在第(
(A)、k-1 (B)、k (C)、k-1 和 k
)层上。
(D)、1 至k
6.具有60 个结点的二叉树,其叶子结点有12 个,则度过1 的结点数为(
)
)遍历方法
(A)、11 (B)、13 (C)、48 (D)、37
7.图的 Depth-First Search(DFS)遍历思想实际上是二叉树(
的推广。
(A)、先序 (B)、中序 (C)、后序 (D)、层序
8.在下列链队列 Q 中,元素 a 出队的操作序列为(
)
a
front
b
c
d
∧
Q
(A)、p=Q.front->next; p->next= Q.front->next;
(B)、p=Q.front->next; Q.front->next=p->next;
(C)、p=Q.rear->next; p->next= Q.rear->next;
(D)、p=Q->next; Q->next=p->next;
9. Huffman 树的带权路径长度 WPL 等于(
(A)、除根结点之外的所有结点权值之和
(C)、各叶子结点的带权路径长度之和
)
(B)、所有结点权值之和
(D)、根结点的值
)域存储后继结点的地址。
10.线索二叉链表是利用(
(A)、lchild
二、填空题
(B)、data (C)、rchild (D)、root
第 1 页 共 126 页
1. 逻 辑 结 构 决 定 了 算 法 的
, 而 存 储 结 构 决 定 了 算 法
的
。
2. 栈和队列都是一种
的线性表,栈的插入和删除只能在
进行。
3. 线性表(a ,a ,…,a )的顺序存储结构中,设每个单元的长度为 L,元素 a
1
2
n
的存储地址 LOC(a )为
i
i
4. 已知一双向链表如下(指针域名为 next 和 prior):
x
y
q
e
p
现 将 p 所 指 的 结 点 插 入 到 x 和 y 结 点 之 间 , 其 操 作 步 骤
为: ;
;
;
;
5.n 个结点无向完全图的的边数为
n 个结点的生成树的边数为
,
。
6.已知一有向无环图如下:
B
F
D
A
G
C
E
任意写出二种拓扑排序序列:
、
。
7.已知二叉树的中序遍历序列为 BCA,后序遍历序列为 CBA,则该二叉树的先序
遍历序列为
,层序遍历序列为
。
三、应用题
1. 设散列函数 H(k)=k % 13,设关键字系列为{22,12,24,6,45,7,8,13,21},要
求用线性探测法处理冲突。(6 分)
(1) 构造 HASH 表。
(2) 分别求查找成功和不成功时的平均查找长度。
2. 给定表(19,14,22,15,20,21,56,10).(8 分)
(1) 按元素在表中的次序,建立一棵二叉排序树
(2) 对(1)中所建立的二叉排序树进行中序遍历,写出遍历序列。
(3) 画出对(2)中的遍历序列进行折半查找过程的判定树。
第 2 页 共 126 页
3. 已知二个稀疏矩阵 A 和 B 的压缩存储三元组表如下:
A
B
i
1
2
2
4
5
j
3
4
5
2
2
V
-5
6
i
2
3
4
5
5
j
5
3
1
2
5
V
2
7
2
3
-1
9
-9
8
写出 A-B 压缩存储的三元组表。(5 分)
4. 已知一维数组中的数据为(18,12,25,53,18), 试写出插入排序(升序)过
程。并指出具有 n 个元素的插入排序的时间复杂度是多少?(5 分)
5. 已知一网络的邻接矩阵如下,求从顶点 A 开始的最小生成树。(8 分,要有
过程)
A
B C
D
E F
6 5 1
A
B 6 5 3
5 7 2
C
D 1 5 7 6 4
E 3 6 6
2 4 6
F
(1)求从顶点 A 开始的最小生成树。
(2)分别画出以 A 为起点的 DFS 生成树和 BFS 生成树。
6.已知数据六个字母及在通信中出现频率如下表:
A
B
C
D
E
F
0.15
0.15
0.1
0.1
0.2
0.3
把这些字母和频率作为叶子结点及权值,完成如下工作(7 分,要有过程)。
(1) 画出对应的 Huffman 树。
(2) 计算带权路径长度 WPL。
(3) 求 A、B、C、D、E、F 的 Huffman 编码。
7. 已知有如下的有向网:
A
第 3 页 共 126 页
2
5
3
6
B
E
C
D
求顶点 A 到其它各顶点的最短路径(采用 Dijkstra 算法,要有过程)。(6 分)
三、 设计题 (30 分,每题 10 分,用 C 语言写出算法,做在答题纸
上)
1. 已知线性表(a ,a ,…,a )以顺序存储结构为存储结构,其类型定义如下:
1
2
n
#define LIST_INIT_SIZE 100 //顺序表初始分配容量
typedef struct {
Elemtype *elem;
int length;
//顺序存储空间基址
//当前长度(存储元素个数)
}SqList;
设计一个算法,删除其元素值为x 的结点(假若x 是唯一的)。并求出其算法的
平均时间复杂度。其算法函数头部如下:
Status ListDelete(Sqlist &L,Elemtype x)
{
……
}
2.设顺序栈如左图所示。
其中结点定义如下:
typedef struct {
top
a
n
…
Elemtype *base; //栈底指针
Elemtype *top; //栈顶指针
}Stack;
a
2
a
1
设计算法,将栈顶元素出栈并存入e 中.
base
3.设二叉链树的类型定义如下:
typedef int Elemtype;
typedef struct node{
Elemtype data;
struct node *lchild, *rchild;
}BinNode, *BinTree;
试写出求该二叉树叶子结点数的算法:
Status CountLeaves(BinTree &root,int &n)
{//n is the number of leaves
第 4 页 共 126 页
……
}
答案:
选择题(每题1 分)
1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C
一、填空题
1.设计、实现
2.特殊、栈顶
3.LOC(a1)+(i-1)*L
4.p->next=q->next;q->next->prior=p; q->next=p;p->prior=q;
5.n(n-1)/2、n-1
6.ADCBFEG、ABCDEFFG
7.ABC、ABC
二、应用题
1 (1)Hash 表(4 分)
0
1
2
3
4
5
6
6
1
7
45
2
8
7
3
9
22
1
10 11 12
地址
13 21
1
8
3
24 12
关键安
7
1
1
探测次数
(2)查找成功的平均查找长度:(1 分)
(5*1+1*2+2*3+1*7)/9=20/9
查找不成功的平均查找长度:(1 分)
(2+1+9+8+7+6+5+4+3+2+1)/13=
2(1)、构造(3 分)
19
14
22
10
15 20
56
21
(2)、10 14 15 19 20 21 22 56(2 分)
(3)、(3 分)
第 5 页 共 126 页
剩余125页未读,继续阅读
资源评论
- qq_417887212022-11-27资源内容详细全面,与描述一致,对我很有用,有一定的使用价值。
G11176593
- 粉丝: 6687
- 资源: 3万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功