数据结构期末考试试题及答案.docx
《数据结构期末考试试题及答案.docx》由会员分享，可在线阅读，更多相关《数据结构期末考试试题及答案.docx（13页珍藏版）》请在冰点文库上搜索。
数据结构期末考试试题及答案
《数据结构》期末考试试题及答案
（2003-2004学年第2学期）
单项选择题1、C2、D3、A4、D5、C6、D7、A8、B9、C10、C
、
1.对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为
（c）。
10.线索二叉链表是利用（c）域存储后继结点的地址。
（A）、Ichild（B）、data（C）、rchild（D）、root
二、填空题
1.逻辑结构决定了算法的设计，而存储结构决定了算法的实
现。
2.栈和队列都是一种特殊的线性表，栈的插入和删除只能在栈顶
进行。
3.线性表（ai,a2,…,an）的顺序存储结构中，设每个单元的长度为L,元素a
的存储地址LOC（a）为
4.已知一双向链表如下（指针域名为next和prior）:
现将p所指的结点插入到x和y结点之间，其操作步骤
?
?
?
5.n个结点无向完全图的的边数为,
n个结点的生成树的边数为。
6.已知一有向无环图如下：
任意写出二种拓扑排序序列：
、。
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）中的遍历序列进行折半查找过程的判定树。
3.
已知二个稀疏矩阵A和B的压缩存储三元组表如下：
4.已知一维数组中的数据为（
18,12,25,53,18_）,试写出插入排序（升序）过
程。
并指出具有n个元素的插入排序的时间复杂度是多少？
（5分）
（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）求AB、C、DE、F的Huffman编码。
7.已知有如下的有向网:
100〃顺序表初始分配容量
〃顺序存储空间基址
〃当前长度（存储元素个数）
求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。
（6分）
三、设计题（30分，每题10分,用C语言写出算法，做在答题纸上）
1.已知线性表（a1,a2,…,an）以顺序存储结构为存储结构，其类型定义如下：
#defineLIST_INIT_SIZEtypedefstruct{Elemtype*elem;intlength;
}SqList;
设计一个算法，删除其元素值为x的结点
平均时间复杂度。
其算法函数头部如下：
StatusListDelete（Sqlist&L,Elemtypex）{
}
2•设顺序栈如左图所示。
其中结点定义如下：
typedefstruct{
Elemtype*base;〃栈底指针Elemtype*top;〃栈顶指针}Stack;
设计算法，将栈顶元素出栈并存入e中.
3.设二叉链树的类型定义如下：
typedefintElemtype;
typedefstructnode{Elemtypedata;
structnode*lchild,*rchild;}BinNode,*BinTree;
试写出求该二叉树叶子结点数的算法：
StatusCountLeaves（BinTree&root,int&n）
{〃nisthenumberofleaves
}
答案：
选择题（每题1分）
1、C2、D3、A4、D5、C6、D7、A8、B9、C10、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
7
8
9
10
11
12
关键安
13
21
6
45
7
22
8
24
12
探测次数「
1
7
1
2
3
1
3
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分）
⑵、1014151920212256（2分）
（3）、（3分）
3、（5分，每行0.5）
i
j
v
1
3
-5
2
4
6
3:
3
7
4
1
3
4
2
-1
5
2
18
5
5
8
4、初始关键字：
[18]
12
25
53
18
第一趟:
[12亠
「8]
25
53
18
第二趟：
[12
18
25]
53
18
第三趟:
[12
18
25
53]
18
第四趟：
[12
18
18-25'53]
O（n2）（1分）。
5、7分
（1）4分
（4分）
（2）4分
6、
（1）3分
F
（2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*2仁（1分）
（3）
A:
010B:
011
C:
110D:
111E:
00F
10（3分）
12、
A-B:
（A、B）
1分
A-C:
（A、D、
C）
2分
A-D:
（A、D）
1分
A-E:
（A、D、
E）
2分
—k?
设计题（20分
卜）
1、（10分）
StatusListDelete（Sqlist&L,ElemTypex）
{
inti,j;
for（i=0;ilength;i++）if（L->elem[i]==x）break;
if（i=L->length）returnERROR;
for（j=i;jlengthi_1;j++）L->elem[j]=L->elem[j+1];
L->length--;
}（8分）
平均时间复杂度：
（2分）
设元素个数记为n,则平均时间复杂度为:
1n
E（n-i）二
ni#
2（10分）
voidpop（Stack&S,Elemtype&e）{
if（S.top==S.base）returnERROR;
S.top--;
e=*s.top;
}
2、（10分）
voidCountLeaves（BinTreeT,int&n）{
if（T）
{
if（（!
（T->lchild）&&!
（T->rchild））n++;
CountLeaves（T->lchild,n）;
CountLeaves（T->rchild,n）;
人生中每一次对自己心灵的释惑，都是一种修行，都是一种成长。
相信生命中的每一次磨砺，都会让自己的人生折射出异常的光芒，都会让自己的身心焕发出不一样的香味。
我们常常用人生中的一些痛，换得人生的一份成熟与成长，用一些不可避免的遗憾，换取生命的一份美丽。
在大风大雨，大风大浪，大悲大喜之后，沉淀出一份人生的淡然与淡泊，静好与安宁，深邃与宽厚，慈悲与欣然……
生活里的每个人，都是我们的一面镜子，你给别人什么，别人就会回待你什么。
当你为一件事情不悦的时候，应该想想你给过人家怎样负面的情绪。
世界上的幸福，没有一处不是来自用心经营和珍惜。
当你一味的去挑剔指责别人的时候，有没有反思过自己是否做得尽善尽美呢？
假如你的心太过自我，不懂得经营和善待，不懂得尊重他人的感受，那么你永远也不会获得真正的爱和幸福……
人生就像一场旅行，我们所行走的每一步都是在丰富生命的意义。
我们一边穿越在陌生的吸引里，一边咀嚼回味着一抹远走光阴的旧味，一切都是不可预料，一切
人生看的多了，走的多了，经历的多了，也就懂得多了。
每一份深刻的感悟大多来自一个人深刻的经历。
人生总有那么一两件重大的事情让你成熟和改变。
这份错失，会让你反思自己，检讨自己，叩问自己，也让你意识到了自己真正的缺失，这或许就是一份痛苦的领
悟吧！
人生可以平平淡淡，亦可以异彩纷呈。
相信只要自己的德馨足够善美，上天就会把最好的一切赐予你。
予人快乐，收获快乐；予人幸福，收获幸福；予人真情，收
获厚意。
人生的一切往来皆有因果，生活只善待有心人……
假如你有一颗计较的心，你就会很难获得一份幸福。
当一个人放下了自己内心的那份累心的奢求，你的心空就会变得更加蔚蓝干净。
宽容，不仅是一种豁达的态度，更是一种心灵的品德，是一种处事的修行，宽容别人不是低矮了自己，而是释放了自己，升华了自己。
你把世界宽待在心中，世界
也同样装饰了你的一份美丽。
当你简约、释然了自己的时候，你会发现另一份生命中的快乐。
那快乐是发自一颗简单的心，那快乐是从心灵的草地里欢快的迸发出来，通过你温柔的眼眸和开心
的笑声来传递。
所以，心宽便心悦，你人生的天空是什么颜色，往往取决于你对人生的态度和对于自己情绪的驾驭……
世界上美好的东西那么多，有缘来到你的身旁，被你握到掌心的却又那么少。
所以一切在的时候请学会珍惜，因为大多美丽的东西只会为你来过一次。
你一不小心
就会失落，无处找寻，增加了你人生的又一次遗憾……
过往，终是回不去的曾经。
人总是在失去的时候才懂得珍惜，人总是在回味的时候才知道甜美。
往事已矣，该放下的终归要放下，该忘记的一定要学会忘记。
其实这个世界上什么都不是我们的，在人间，我们只是一场心灵的路过而已……或许唯一属于过我们的，只是生命刹那的快乐与悲伤，以及自己一颗思索的灵魂
站在时光的路口回望曾经，盘点每一份经历过的心情，人生有太多得不到的美好，有太多想不到的结局。
终有一天，我们热望过的，贪念过的，彷徨过的，握紧过
的，放手过的，都将化作尘埃随风飞去……
人生渺如尘埃，小如露珠，寻常如泥土，从不可知处而来，到不可知处而去。
我们用灵魂结伴身体，走过这短暂的一朝一夕的寒暖，踏过流年的坎坷与花香，便是
升级会员 