《数据结构期末考试试题及复习资料.docx》由会员分享，可在线阅读，更多相关《数据结构期末考试试题及复习资料.docx（8页珍藏版）》请在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= Q.front-next; （B）、p=Q.front-next; Q.front-next=p-next; （C）、p=Q.rear-ne
2、xt; 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 线性表（a1,a2,an）的顺序存
3、储结构中，设每个单元的长度为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,要求用线性探测法处理冲突。(6
4、分)(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）, 试写出插入排序（升序）过程。并指出具有n个元素的插
5、入排序的时间复杂度是多少？(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 AEBDC求顶点A到其它各
6、顶点的最短路径（采用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(Sqlist &L,Ele
7、mtype 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(BinTree &root,int
8、 &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）查找成功的平均查找长度：（1
9、分） （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 53 （4分） O（n2
10、）（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*25*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;ilength;i+)if(L-elem
11、i=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-rchild) n+; CountLeaves (T-lchild,n); CountLeaves (T-rchild,n);