admin 管理员组文章数量: 1086019
2024年4月21日发(作者：enclose的中文是什么)
数据结构与算法考试参考题
专业：计算机科学与技术 13年
一、单选（ 30分 ）
1. 在数据结构中，数据的逻辑结构可分（ B.线性结构和非线性结构 ）
2. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ C.指向后继元素的指针表示 ）
3.设p指向单链表中的一个结点。S指向待插入的结点，则下述程序段的功能是（ D.在结点*p之前插入结点*s ）
s->next=p->next; p->next=s!
t=p->data; p->data=s->data; s->data=t;
B.在p所指结点的元素之前插入元素 D.在结点*p之前插入结点*s
4. 栈和队列都是（ C:链式存储的线性结构 ）
A:限制存取位置的线性结构 B:顺序存储的线性结构
C:链式存储的线性结构 D:限制存取位置的非线性结构
5. 下列关于线性表的基本操作中，属于加工型的操作是（ B初始化、插入、删除操作 ）
6. 根据定义，树的叶子结点其度数（ B.必等于0 ）
7. 多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（ A.数组的元素处在行和列两个关系中 ）
8. 从广义表LS=（ （ p,q ）,r,s ）中分解出原子q的运算是(B. head(tall(head (LS)))
9. 在具有n个叶子结点的满二叉树中，结点总数为（ C. 2n-1 ）
10. 若
11. 二叉树若采用二叉链表结构表示，则对于n个结点的二叉树一定有（ B. 2n个指针域其中n+1个指针为NULL ）
12. 在一个无向图中，所有顶点的度数之和等于边数的（ B. 2倍 ）
13. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度
为（ A.O(n) ）
14. 散列法存储中出现的碰撞（冲突）现象指的是（ B.不同关键码值对应到相同的存储地址 ）
15. 循环链表适合的查找方式是（ A. 顺序 ）
二、填空（ 20分 ）
1.若一棵完全二叉树中含有121个结点，则该树的深度为（ 7 ）
2.若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数之和即为顶点Vi的
。
3.二叉树的遍历主要有先序遍历、后序遍历和（ 中序遍历 ）三种。
4.深度为3的完全二叉树至少有（ 4 ）个结点。
5.若图的邻接矩阵是一个对称矩阵，则该图一定是一个（ 无向图 ）
6.若某无向图G的邻接表如下图所示，试给出以顶点V3为出发点，按广度优先搜索所产生的结点序列（ V3-2V1-V4-V5 ）
V
1
V
2
V
3
V
4
V
5
V
2
V
1
Λ
V
1
V
1
V
1
V
3
V
4
V
3
V
3
V
4
V
5
V
5
V
4
Λ
Λ
Λ
V
5
Λ
7.在无向图中，若从顶点a到顶点b存在（ 路径 ），则称a与b之间是连通的。
8.我们通常把队列中允许删除的一端称为（ 队头 ）
9.表头和表尾均为（ a,(b,c) ）的广义表L= （ ）
10.假定对有序表：（ 3.4.5.7.24.30.42.54.63.72.87.95 ）进行折半查找，若查找元素24（ 程序设定为向下取整 ），需依
次与（ 30.5.7.24 ）元素进行比较。
三、解答（ 50分 ）
1. 二维数组A[10.20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[1.1]的存储地址为300，则请算A[10,10]
的存储地址。
答： 300+（ 9*20+10 ）*
4=300+190*4=300
+760=1060
2. 已知树如右图所示：
（1）画出由该树转换得到的二叉树；
原图 答图：
A
A
B
E
J
F
K
G
C
H
D
I
E
F
J
K
B
C
D
G
H
I
（2）写出该二叉树的后序序列：
答： 后序序列为：E B K J I H G F D C A
3. 试给出如图所示的邻接矩阵和邻接表表示。
V
1
4
2
8
7
11
6
V
2
13
V
5
V
3
V
4
答： 邻接矩阵
邻接表
0
0
0
0
0
0246
0080
A
0000
07110
01300
1
2
3
4
5
V
1
V
2
V
3
Λ
V
4
V
5
22
38Λ
27
213Λ
3446Λ
311Λ
4. 已知某二叉排序树10个结点的值依次为1-10，其结构如图所示，试标出该二叉排序树各
结点所对应的具体值。
6
5
3
4
2
7
8
9
10
原图：答图：
1
5. 试构造下图的最小生成树，要求分步给出构造过程。
V
1
6
2
V
2
8
4
5
5
V
3
V
4
7
V
5
原图：
答图：
V
1
V
1
V
1
V
1
V
2
2
V
3
2
V
2
5
V
3
2
5
V
2
5
V
4
V
3
2
5
V
2
5
6
V
4
V
3
1. 2. 3.4.
6. 从一个空的二叉排序树开始，依次插入关键字25.13.15.14.7.20.37试画出插入关键字后的
二叉排序树，并计算查找成功时的平均查找长度。
average search length平均查找长度
答： ASL=(1*1+2*2+3*3+4*1)/7=18/7
V
4
V
5
V
4
V
5
V
5
V
5
25
13
7
15
20
34
37
主要思想是以第一个数为标准，将比此数小的放在左边，大的放在右边，再一一插入，通过比较，找到末端为止。
如13比25小，便在左边，后15小于25，又在25左端，但是比13大，故放在了13的右边，每个数都是这样找
到自己的位置的。
7. 为关键字（ 17.33.31.40.48 ）构造一个长度为7的散列表，设散列函数为h(key)=key%7,
用开放定址法解决冲突的探查序列是
Hi=(h(key)+(key%5+1))%7 0≤i≤6
(1)画出构造所得的散列表；
(2)求出在等概率情况下查找成功时的平均查找长度。
答：
ASL=(1+1+3+2+4)/5=11/5
H(17)=17%7=3
H(33)=33%7=5
H(31)=31%7=3 冲突 %=（ 3+1（ 31%5+1 ） ）%7
=5%7=5 冲突
Hi=(3+2(31%5+1))%7
=(3+4)%7=0
H(40)=40%7=5 冲突
Hi=(5+1(40%5+0))%7
=6%7=6
H(48)=48%7=6 冲突
Hi=(6+1(48%5+1))%7
=(6+4)%7=3 冲突
Hi=(6+2(48%5+1))%7
=(6+8)%7=0 冲突
Hi=(6+3(48%5+1))%7
=(6+12)%7
=18%7
=4
0
31
1 2 3 4 5 6
17 48 33 40
8.……顶点C出发进行深度优先遍历的序列。
原图：
邻接点
0
1
2
3
4
5
权值
207
011
308
120
514
109
链域
111Λ
509
007Λ
208Λ
115Λ
414Λ
A
B
C
D
E
F
415320Λ
答： CDABFE
A
11
B
15
20
E
14
9
F
8
7
C
D
完
1. 已知一棵树边的集合为{
（ 1 ）哪个是根结点？ （ 2 ）哪些是叶子结点？ （ 3 ）哪个是结点g的双亲？ （ 4 ）
哪些是结点g的祖先？ （ 5 ）哪些是结点g的孩子？ （ 6 ）哪些是结点e的孩子？
（ 7 ）哪些是结点e的兄弟？哪些是结点f的兄弟？ （ 8 ）结点b和n的层次号分别是
什么？ （ 9 ）树的深度是多少？
（ 10 ）以结点c为根的子树深度是多少？ 1. 解答：
根据给定的边确定的树如图5-15所示。 其中根结点为a； 叶子结点有：d、m、n、j、k、
f、l；
c是结点g的双亲；
a、c是结点g的祖先；
j、k是结点g的孩子； m、n是结点e的子孙； e是结点d的兄弟；
g、h是结点f的兄弟；
结点b和n的层次号分别是2和5； 树的深度为5。
4. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和
后序遍历序列。
4. 解答：
先序序列：ABDHIEJKCFLG 中序序列：HDIBJEKALFCG 后序序列：HIDJKEBLFGCA
数据结构：在一棵空的二叉查找树中依次插入关键字学列为54，18，66，87，36，12 请画
出所得到的二叉排序树
数据结构题：二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A
[0][0]的存储地址是200
则A[6][12]的地址是326。
还有这题：二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，
并且A[10][5]的存储地址是1000，则A[18][9]的地址是1208。
答案
第一题:列序存储,则A[6][12]的地址的A[0][0]的地址加上"12*10+6"=200+126=326 (行序是
6*20+12)
第二题:行序存储,A[18][9]=A[10][5]+(8*6+4)*4=1000+208=1208;
20][5...10]等同于A[11][6] 然后已知A[0][0]的地址为1000，求A[8][4]的地址，注意
每个元素占4个存储单元了 需要乘上4
版权声明：本文标题：数据结构与算法-考试范围题与答案like 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1713665618a646065.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论