数据结构2013试题B卷.docx
版权申诉
178 浏览量
2021-11-23
07:52:01
上传
评论
收藏 124KB DOCX 举报
考试类别[学生填写]（□正考 □补考 □重修 □补修 □缓考 □其它）
8、高度为 h 的完全二叉树最少有（
A）2
h
B）2 +1
9、假设一个有 n 个顶点和 e 条边的有向图用邻接表表示，则删除与某个顶点 v 相关的
）个结点。
C）2
h-1
D）2 -1
h
h
题号
得分
一
二
三
四
总分
i
所有边的时间复杂度为（
A）O(n) B）O(e)
）
C）O(n+e)
D）O(ne)
评阅人
10、无向图 G=(V, E)，其中 V={a，b，c，d，e，f}，E={（a，b），（a，e），（a，c），
（b，e），（c，f），（f，d），（e，d）}，对该图进行深度优先遍历，得到的顶点序列正
卷
B
2
30
一、选择题（每题 分，共 分，请将答案写到下面的表格内）
确的是（
）
卷
试
1
2
3
4
5
6
7
8
9
10
11 12 13 14 15
A）a，b，e，c，d，f
C）a，e，b，c，f，d
B）a，c，f，e，b，d
D）a，e，d，f，c，b
线
订
装
构
11、对于顺序存储的有序表（5, 12, 20, 26, 37, 42, 46, 50, 64），若采用折半查找，则查找
元素 26 的查找长度为（
A）2 B）3
12、采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是（
结 号
据 学
数
1、以下属于逻辑结构的是（
A）顺序表 B）散列表
）
）
C）有序表
D）单链表
C）4
D）5
2、以下算法的时间复杂度为（
）
）
void fun(int n){
int i=1;
while(i<=n)
i=i*2;
A）数据元素过多
B）装载因子过大
期
学
C）散列函数选择不当
D）解决冲突的方法选择不当
13、若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（
）
1 名
第 姓
A）直接插入排序
C）基数排序
B）选择排序
D）快速排序
}
A）O(n)
3、若线性表最常用的操作是存取第 i 个元素及其前驱和后继元素的值，为了提高效率，
应采用（ ）的存储方式。
A）单链表 B）双向链表
B）O(n )
C）O(nlog n)
D）O(log n)
14、对以下数据序列利用快速排序进行排序，速度最快的是（
）
2
年
学
4
1
0
2
2
2
A）{21，25，5，17，9，23，30}
C）{21，9，17，30，25，23，5}
B）{25，23，30，17，21，5，9}
D）{5，9，17，21，23，25，30}
C）单循环链表
D）顺序表
15、堆是一种有用的数据结构，下列排序码中序列中，（
A）100，85，98，77，80，60，82，40，20，10，66
B）100，98，85，82，80，77，66，60，40，20，10
C）10，20，40，60，66，77，80，82，85，98，100
D）100，85，40，77，80，60，66，98，82，10，20
）不是一个堆。
4、设线性表中有 2n 个元素，（
更高。
）算法，在单链表上实现要比在顺序表上实现效率
—
3
1
0
2
A）删除所有值为 x 的元素
B）在最后一个元素的后面插入一个新元素
C）顺序输出前 k 个元素
二、填空题（每空 2 分，共 10 分）
院 级
学 班
业 及
工 级
轻 年
州 业
郑 专
D
）交换第 个元素和第 2n – i – 1 个元素的值（ ，…， ）
i
i=0
n-1
下面是折半插入排序算法的实现，请补充完整代码。
5、栈和队列的主要区别在于（
A）它们的逻辑结构不一样
C）所包含的元素不一样
）
void InsertSort(ElemType A[], int len)
B）它们的存储结构不一样
{
D）插入、删除操作的限定不一样
int i, j, low, high, mid;
6、设有一个10阶的对称矩阵 A[10][10], 采用压缩存储方式按行优先将矩阵中下三角
for(i=2; i<=len; i++)
部分的元素存入一维数组 B 中，A[0][0]存入 B[0]中 ，则 A[8][5]在 B 中的位置是(
)
{
A）32
B）33
C）41
D）65
A[0]=A[i];
7、树最适合用来表示（
A）有序
）的数据。
low=1; high=__________;
B）无序
while(__________________)
{
C）任意元素之间具有多种联系
D）元素之间具有分支层次关系
第 1 页/共 4 页
节 约 用 纸 两 面 书 写
资源评论
