《数据结构》期末考试试题及答案(共13页).doc

《《数据结构》期末考试试题及答案(共13页).doc》由会员分享，可在线阅读，更多相关《《数据结构》期末考试试题及答案(共13页).doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构期末考试试题及答案(2003-2004学年第2学期)单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、1对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。 (A)、正确性 (B). 可行性 (C). 健壮性 (D). 输入性2设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（ d ）。for(i=n-1；i=0；i-) for(j=0；jnext; p-next= Q.front-next; （B）、p=Q.front-next; Q.front-next=p-next; （C

2、）、p=Q.rear-next; p-next= Q.rear-next; （D）、p=Q-next; Q-next=p-next;9 Huffman树的带权路径长度WPL等于（ c ）（A）、除根结点之外的所有结点权值之和 （B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和 （D）、根结点的值10线索二叉链表是利用（ c ）域存储后继结点的地址。 （A）、lchild （B）、data （C）、rchild （D）、root二、填空题1 逻辑结构决定了算法的 设计 ，而存储结构决定了算法的 实现 。2 栈和队列都是一种 特殊 的线性表，栈的插入和删除只能在 栈顶 进行。3 线性表（

3、a1,a2,an）的顺序存储结构中，设每个单元的长度为L，元素ai的存储地址LOC(ai)为 4 已知一双向链表如下(指针域名为next和prior)： y x e q p现将p所指的结点插入到x和y结点之间，其操作步骤为： ； ； ； ；5n个结点无向完全图的的边数为 ， n个结点的生成树的边数为 。6已知一有向无环图如下： BACDFEG 任意写出二种拓扑排序序列： 、 。7已知二叉树的中序遍历序列为BCA，后序遍历序列为CBA，则该二叉树的先序遍历序列为 ，层序遍历序列为 。三、应用题1 设散列函数H(k)=k % 13,设关键字系列为22,12,24,6,45,7,8,13,21,要求

4、用线性探测法处理冲突。(6分)(1) 构造HASH表。(2) 分别求查找成功和不成功时的平均查找长度。2 给定表（19,14,22,15,20,21,56,10）.（8分）（1） 按元素在表中的次序，建立一棵二叉排序树（2） 对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。（3） 画出对(2)中的遍历序列进行折半查找过程的判定树。3 已知二个稀疏矩阵A和B的压缩存储三元组表如下： A BijVijV13-525224633725241342-152-9529558写出A-B压缩存储的三元组表。（5分）4 已知一维数组中的数据为（18,12,25,53,18）, 试写出插入排序（升序）过

5、程。并指出具有n个元素的插入排序的时间复杂度是多少？(5分)5 已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。(8分，要有过程) A B C D E F（1）求从顶点A开始的最小生成树。（2）分别画出以A为起点的DFS生成树和BFS生成树。6已知数据六个字母及在通信中出现频率如下表：ABCDEF0.150.150.10.10.20.3把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。（1） 画出对应的Huffman树。（2） 计算带权路径长度WPL。（3） 求A、B、C、D、E、F的Huffman编码。7 已知有如下的有向网： 2 5 36 4 10 6 1 2 2

6、AEBDC求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6分）三、 设计题（30分，每题10分,用C语言写出算法，做在答题纸上）1 已知线性表（a1,a2,an）以顺序存储结构为存储结构，其类型定义如下： #define LIST_INIT_SIZE 100 /顺序表初始分配容量 typedef struct Elemtype *elem; /顺序存储空间基址 int length; /当前长度（存储元素个数） SqList;设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下： Status ListDelete(

7、Sqlist &L,Elemtype x) ana2a12设顺序栈如左图所示。 其中结点定义如下： top typedef struct Elemtype *base; /栈底指针Elemtype *top; /栈顶指针 Stack;设计算法，将栈顶元素出栈并存入e中 base3设二叉链树的类型定义如下： typedef int Elemtype; typedef struct node Elemtype data; struct node *lchild, *rchild; BinNode, *BinTree;试写出求该二叉树叶子结点数的算法: Status CountLeaves(BinT

8、ree &root,int &n) /n is the number of leaves 答案：选择题（每题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)*L4 p-next=q-next;q-next-prior=p; q-next=p;p-prior=q;5 n(n-1)/2、n-16 ADCBFEG、ABCDEFFG7 ABC、ABC二、 应用题1 （1）Hash表（4分）地址0123456789101112关键安132164572282412探测次数171231311（2）查

9、找成功的平均查找长度：（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分）3、(5分，每行0.5)ijv13-524633741342-152185584、 初始关键字： 18 12 25 53 18 第 一 趟：12 18 25 53 18第 二 趟：12 18 25 53 18第 三 趟：12 18 25 53 18第 四 趟：12 18 18 25

10、 53 （4分） O（n2）（1分）。5、7分（1）4分A B 1 C 3 2 5 D 4 E F（2）4分6、(1) 3分 E F A B C D （2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= (1分)（3）A：010 B：011 C：110 D：111 E：00 F；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分 三，设计题（20分）1、(10分)Status ListDelete(Sqlist &L,ElemType x) int i,j; for(i=0;ile

11、ngth;i+)if(L-elemi=x) break; if(i=L-length) return ERROR; for(j=i;jlengthi-1;j+) L-elemj=L-elemj+1; L-length-; （8分）平均时间复杂度：（2分）设元素个数记为n，则平均时间复杂度为：2（10分）void pop(Stack &S,Elemtype &e) if(S.top=S.base) return ERROR; S.top-; e=*s.top;2、（10分）voidCountLeaves(BinTree T,int &n)if(T)if(!(T-lchild)&!( T-rchi

12、ld) n+; CountLeaves (T-lchild,n); CountLeaves (T-rchild,n);人生中每一次对自己心灵的释惑，都是一种修行，都是一种成长。相信生命中的每一次磨砺，都会让自己的人生折射出异常的光芒，都会让自己的身心焕发出不一样的香味。我们常常用人生中的一些痛，换得人生的一份成熟与成长，用一些不可避免的遗憾，换取生命的一份美丽。在大风大雨，大风大浪，大悲大喜之后，沉淀出一份人生的淡然与淡泊，静好与安宁，深邃与宽厚，慈悲与欣然生活里的每个人，都是我们的一面镜子，你给别人什么，别人就会回待你什么。当你为一件事情不悦的时候，应该想想你给过人家怎样负面的情绪。世界上的

13、幸福，没有一处不是来自用心经营和珍惜。当你一味的去挑剔指责别人的时候，有没有反思过自己是否做得尽善尽美呢？假如你的心太过自我，不懂得经营和善待，不懂得尊重他人的感受，那么你永远也不会获得真正的爱和幸福人生就像一场旅行，我们所行走的每一步都是在丰富生命的意义。我们一边穿越在陌生的吸引里，一边咀嚼回味着一抹远走光阴的旧味，一切都是不可预料，一切又似在预料之中。人生看的多了，走的多了，经历的多了，也就懂得多了。每一份深刻的感悟大多来自一个人深刻的经历。人生总有那么一两件重大的事情让你成熟和改变。这份错失，会让你反思自己，检讨自己，叩问自己，也让你意识到了自己真正的缺失，这或许就是一份痛苦的领悟吧！人

14、生可以平平淡淡，亦可以异彩纷呈。相信只要自己的德馨足够善美，上天就会把最好的一切赐予你。予人快乐，收获快乐；予人幸福，收获幸福；予人真情，收获厚意。人生的一切往来皆有因果，生活只善待有心人假如你有一颗计较的心，你就会很难获得一份幸福。当一个人放下了自己内心的那份累心的奢求，你的心空就会变得更加蔚蓝干净。宽容，不仅是一种豁达的态度，更是一种心灵的品德，是一种处事的修行，宽容别人不是低矮了自己，而是释放了自己，升华了自己。你把世界宽待在心中，世界也同样装饰了你的一份美丽。当你简约、释然了自己的时候，你会发现另一份生命中的快乐。那快乐是发自一颗简单的心，那快乐是从心灵的草地里欢快的迸发出来，通过你温

15、柔的眼眸和开心的笑声来传递。所以，心宽便心悦，你人生的天空是什么颜色，往往取决于你对人生的态度和对于自己情绪的驾驭世界上美好的东西那么多，有缘来到你的身旁，被你握到掌心的却又那么少。所以一切在的时候请学会珍惜，因为大多美丽的东西只会为你来过一次。你一不小心就会失落，无处找寻，增加了你人生的又一次遗憾过往，终是回不去的曾经。人总是在失去的时候才懂得珍惜，人总是在回味的时候才知道甜美。往事已矣，该放下的终归要放下，该忘记的一定要学会忘记。其实这个世界上什么都不是我们的，在人间，我们只是一场心灵的路过而已或许唯一属于过我们的，只是生命刹那的快乐与悲伤，以及自己一颗思索的灵魂站在时光的路口回望曾经，盘点每一份经历过的心情，人生有太多得不到的美好，有太多想不到的结局。终有一天，我们热望过的，贪念过的，彷徨过的，握紧过的，放手过的，都将化作尘埃随风飞去人生渺如尘埃，小如露珠，寻常如泥土，从不可知处而来，到不可知处而去。我们用灵魂结伴身体，走过这短暂的一朝一夕的寒暖，踏过流年的坎坷与花香，便是在世间真正的来过了。专心-专注-专业