《《数据结构》期末考试试题及答案.pdf》由会员分享，可在线阅读，更多相关《《数据结构》期末考试试题及答案.pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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=next;（B）、p=next;next=
2、p-next;（C）、p=next;p-next=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 线性表（a1,a2,
3、an）的顺序存储结构中，设每个单元的长度为 L，元素 ai的存储地址 LOC(ai)为 4 已知一双向链表如下(指针域名为 next 和 prior)：q p 现 将p所 指 的 结 点 插 入 到x和y结 点 之 间，其 操 作 步 骤为：；5n 个结点无向完全图的的边数为 ，n 个结点的生成树的边数为 。x y e 古之立大事者，不惟有超世之才，亦必有坚忍不拔之志。苏轼古之立大事者，不惟有超世之才，亦必有坚忍不拔之志。苏轼6已知一有向无环图如下：任意写出二种拓扑排序序列：、。7已知二叉树的中序遍历序列为 BCA，后序遍历序列为 CBA，则该二叉树的先序遍历序列为 ，层序遍历序列为 。三、应
4、用题 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 的压缩存储三元组表如下：A B i j V i j V 1 3-5 2 5 2 2 4 6 3 3 7 2 5 2 4
5、1 3 4 2-1 5 2-9 5 2 9 5 5 8 写出 A-B 压缩存储的三元组表。（5 分）4 已知一维数组中的数据为（18,12,25,53,18）,试写出插入排序（升序）过程。B A C D F E G 其身正，不令而行；其身不正，虽令不从。论语谋事在人，成事在天！增广贤文并指出具有 n 个元素的插入排序的时间复杂度是多少(5 分)5 已知一网络的邻接矩阵如下，求从顶点 A 开始的最小生成树。(8 分，要有过程)A B C D E F（1）求从顶点 A 开始的最小生成树。（2）分别画出以 A 为起点的 DFS 生成树和 BFS 生成树。6已知数据六个字母及在通信中出现频率如下表：A
6、 B C D E F 把这些字母和频率作为叶子结点及权值，完成如下工作(7 分，要有过程)。（1）画出对应的 Huffman 树。（2）计算带权路径长度 WPL。（3）求 A、B、C、D、E、F 的 Huffman 编码。7 已知有如下的有向网：求顶点 A 到其它各顶点的最短路径（采用 Dijkstra 算法，要有过程）。（6 分）2 5 3 6 A B C D E 64266346751275356156FEDCBA丈夫志四方，有事先悬弧，焉能钧三江，终年守菰蒲。顾炎武宠辱不惊，看庭前花开花落；去留无意，望天上云卷云舒。洪应明三、设计题（30 分，每题 10 分,用 C 语言写出算法，做在答
7、题纸上）1 已知线性表（a1,a2,an）以顺序存储结构为存储结构，其类型定义如下：#define LIST_INIT_SIZE 100 /顺序表初始分配容量 typedef struct Elemtype *elem;/顺序存储空间基址 int length;/当前长度（存储元素个数）SqList;设计一个算法，删除其元素值为 x 的结点（假若 x 是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下：Status ListDelete(Sqlist&L,Elemtype x)2设顺序栈如左图所示。其中结点定义如下：top typedef struct Elemtype *base;
8、/栈底指针 Elemtype *top;/栈顶指针 Stack;设计算法，将栈顶元素出栈并存入 e 中 base 3设二叉链树的类型定义如下：typedef int Elemtype;typedef struct node Elemtype data;struct node *lchild,*rchild;BinNode,*BinTree;an a 良辰美景奈何天，便赏心乐事谁家院。则为你如花美眷，似水流年。汤显祖穷则独善其身，达则兼善天下。孟子试写出求该二叉树叶子结点数的算法:Status CountLeaves(BinTree&root,int&n)/n is the number of
9、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)*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（
10、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 分）(2)、10 14 15 19 20 21 22 56（2 分）（3）、（3 分）3、(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 18 25 53 18 第 二 趟：12 18 25 53
11、18 19 14 22 10 15 20 56 宠辱不惊，看庭前花开花落；去留无意，望天上云卷云舒。洪应明万两黄金容易得，知心一个也难求。曹雪芹第 三 趟：12 18 25 53 18 第 四 趟：12 18 18 25 53 （4 分）O（n2）（1 分）。5、7 分（1）4 分 （2）4 分 6、(1)3 分 （2）WPL=*3+*3+*2+*3+*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 B 1 C 3 2 5 D 4 E F E F A B C D 丈夫志四方，有事先悬弧，焉能钧三江，
12、终年守菰蒲。顾炎武古之立大事者，不惟有超世之才，亦必有坚忍不拔之志。苏轼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;ilength;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，则平均时间复杂度为：nin
13、innE121)(1 2（10 分）void pop(Stack&S,Elemtype&e)if=return ERROR;e=*;2、（10 分）我尽一杯，与君发三愿：一愿世清平，二愿身强健，三愿临老头，数与君相见。白居易非淡泊无以明志，非宁静无以致远。诸葛亮voidCountLeaves(BinTree T,int&n)if(T)if(!(T-lchild)&!(T-rchild)n+;CountLeaves(T-lchild,n);CountLeaves(T-rchild,n);云路鹏程九万里，雪窗萤火二十年。王实甫百学须先立志。朱熹 志不强者智不达，言不信者行不果。墨翟海纳百川，有容乃大；壁立千仞，无欲则刚。林则徐 其身正，不令而行；其身不正，虽令不从。论语宠辱不惊，看庭前花开花落；去留无意，望天上云卷云舒。洪应明 先天下之忧而忧，后天下之乐而乐。范仲淹以铜为镜，可以正衣冠；以古为镜，可以知兴替；以人为镜，可以明得失。旧唐书魏征列传 宠辱不惊，看庭前花开花落；去留无意，望天上云卷云舒。洪应明人不知而不愠，不亦君子乎？论语