东北大学数据结构II试卷及答案.docxVIP

东北大学数据结构II试卷及答案

考试时间：______分钟总分：______分姓名：______

一、选择题（每题2分，共20分）

1.下列数据结构中，适合用来表示稀疏矩阵的是（）。

A.链表

B.线性表

C.矩阵

D.稀疏矩阵

2.在树形结构中，一个节点可以有多个父节点，这种结构称为（）。

A.树

B.二叉树

C.多路树

D.图

3.下列排序算法中，不稳定排序算法是（）。

A.冒泡排序

B.插入排序

C.快速排序

D.归并排序

4.在有向图中，如果从一个顶点出发，沿着有向边可以到达图中所有其他顶点，则称该顶点为（）。

A.入度

B.出度

C.路径

D.生成点

5.下列数据结构中，适合用来实现深度优先有哪些信誉好的足球投注网站的是（）。

A.线性表

B.栈

C.队列

D.链表

6.哈希表解决冲突的链地址法是指（）。

A.将所有冲突的元素存储在同一个链表中

B.将所有冲突的元素存储在不同的链表中

C.将所有冲突的元素存储在哈希表中

D.将所有冲突的元素丢弃

7.下列数据结构中，适合用来实现广度优先有哪些信誉好的足球投注网站的是（）。

A.栈

B.队列

C.链表

D.线性表

8.在树形结构中，每个节点只有一个父节点，这种结构称为（）。

A.树

B.二叉树

C.多路树

D.图

9.下列数据结构中，允许元素插入和删除的是（）。

A.数组

B.队列

C.栈

D.链表

10.哈希表的装填因子是指（）。

A.哈希表中元素个数与哈希表长度的比值

B.哈希表中元素个数与哈希表长度的差值

C.哈希表中空链表个数

D.哈希表中冲突次数

二、填空题（每题2分，共20分）

1.在树形结构中，根节点的度数为______。

2.快速排序算法的平均时间复杂度为______。

3.在图G中，如果G是连通的，且去掉任何一条边后都不再连通，则称G为______。

4.哈希表的地址计算函数通常称为______。

5.队列是______结构。

6.二叉树的深度是指从根节点到最远叶子节点的最长路径上的节点数，其计算公式为______。

7.基于查找表实现的查找算法通常称为______。

8.在有向图中，从一个顶点出发，沿着有向边可以到达的所有顶点组成的集合称为______。

9.线性表的顺序存储结构通常使用______来实现。

10.哈希冲突的两种主要解决方法为______和______。

三、简答题（每题5分，共30分）

1.简述线性表和链表的区别。

2.简述二分查找算法的适用条件。

3.简述图的两种存储结构：邻接矩阵和邻接表。

4.简述哈希表的基本原理。

5.简述栈的基本操作及其应用场景。

6.简述树形结构的定义及其特点。

四、编程题（每题15分，共30分）

1.编写一个函数，实现单链表的逆序。

2.编写一个函数，实现二分查找算法。

---

试卷答案

一、选择题

1.D

2.C

3.C

4.D

5.B

6.A

7.B

8.A

9.D

10.A

二、填空题

1.0

2.O(nlogn)

3.极小连通子图

4.哈希函数

5.先进先出

6.depth(root)=max{depth(root-left),depth(root-right)}+1

7.查找算法

8.强连通分量

9.数组

10.开放定址法；链地址法

三、简答题

1.线性表和链表的区别

-线性表：数据元素在存储空间上可以连续也可以不连续，通过逻辑上的邻接关系来维护元素之间的联系，需要通过指针或索引来访问非首尾元素。

-链表：数据元素在存储空间上不要求连续，通过指针明确地表示元素之间的逻辑关系，插入和删除操作方便，但访问速度较慢。

2.二分查找算法的适用条件

-所要查找的序列必须是有序的（通常是升序或降序）。

-所要查找的序列必须能够随机访问，即支持通过索引快速访问任意元素（如数组）。

3.图的两种存储结构：邻接矩阵和邻接表

-邻接矩阵：使用二维数组表示图，矩阵中的元素表示顶点之间是否存在边。优点是表示简单，缺点是空间复杂度较高，特别是对于稀疏图。

-邻接表：使用链表数组表示图，每个链表表示一个顶点的所有邻接顶点。优点是空间利用率高，特别是对于稀疏图，缺点是表示较复杂