数据结构期末考试试题及答案

《数据结构期末考试试题及答案》由会员分享，可在线阅读，更多相关《数据结构期末考试试题及答案（7页珍藏版）》请在装配图网上搜索。

1、数据构造期末考试试题及答案(-第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-next; p-next= Q.

2、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）次序存储构造中，设每个单元长度为L，元素ai存储地址L

3、OC(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分)(1) 构造HASH表。(2) 分别求查找成功和不成功时平均查

4、找长度。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 已知一网络邻接矩阵如下，求从顶点A开始最小生成树

5、。(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、FHuffman编码。7 已知有如下有向网： 2 5 36 4 10 6 1 2 2 AEBDC求顶点A到其他各顶点最短途径（采用Dijkstra算法，要有过程）。（6分）三、 设计题（30分，每题10分,用C语

6、言写出算法，做在答题纸上）1 已知线性表（a1,a2,an）以次序存储构造为存储构造，其类型定义如下： #define LIST_INIT_SIZE 100 /次序表初始分派容量 typedef struct Elemtype *elem; /次序存储空间基址 int length; /目前长度（存储元素个数） SqList;设计一种算法，删除其元素值为x结点（假若x是唯一）。并求出其算法平均时间复杂度。其算法函数头部如下： Status ListDelete(Sqlist &L,Elemtype x) ana2a12设次序栈如左图所示。 其中结点定义如下： top typedef struc

7、t 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 &n) /n is the number of leaves 答案：选择题（每题1分）1、C 2、D 3、A

8、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分） （5*1+1*2+2*3+1*7）/9=20/9查找不成功平均查找长度：（1分） （2+1+9+8+7+6+

9、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）（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

10、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;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，则平均时间复杂度为：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);