《数据结构》期末考试试题及答案.docx
数据结构期末考试试题及答案贵州大学理学院数学系信息与计算科学专业数据结构期末考试试题及答案(2021-2021学年第2学期)一、单项选择题1对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。(A)、正确性(B). 可行性(C). 健壮性(D). 输入性2设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。for(i=n-1；i>=0；i-)for(j=0；j(A)、n2(B). O(nlgn) (C). O(n) (D). O(n2)3折半查找法适用于（）。（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4顺序存储结构的优势是（）。（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5深度为k的完全二叉树，其叶子结点必在第（）层上。（A）、k-1 （B）、k （C）、k-1和k （D）、1至k6具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377图的Depth-First Search(DFS)遍历思想实际上是二叉树（）遍历方法的推广。（A）、先序（B）、中序（C）、后序（D）、层序8在下列链队列Q中，元素a出队的操作序列为（）（B）、p=Q.front->next; Q.front->next=p->next;（C）、p=Q.rear->next; p->next= Q.rear->next;（D）、p=Q->next; Q->next=p->next;9 Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10线索二叉链表是利用（）域存储后继结点的地址。（A）、lchild （B）、data （C）、rchild （D）、root二、填空题1逻辑结构决定了算法的，而存储结构决定了算法的。2栈和队列都是一种的线性表，栈的插入和删除只能在进行。3线性表（a1,a2,a n）的顺序存储结构中，设每个单元的长度为L，元素a i 的存储地址LOC(a i)为4已知一双向链表如下(指针域名为next和prior)：现将p所指的结点插入到x和y结点之间，其操作步骤为：；5n个结点无向完全图的的边数为，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 的压缩存储三元组表如下： 写出A-B 压缩存储的三元组表。（5分）4 已知一维数组中的数据为（18,12,25,53,18）, 试写出插入排序（升序）过程。并指出具有n 个元素的插入排序的时间复杂度是多少？(5分)5 已知一网络的邻接矩阵如下，求从顶点A 开始的最小生成树。(8分，要有过程)A B C D E F（1）求从顶点A 开始的最小生成树。（2）分别画出以A 为起点的DFS 生成树和BFS 生成树。6把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。（1） 画出对应的Huffman 树。 （2） 计算带权路径长度WPL 。（3） 求A 、B 、C 、D 、E 、F 的Huffman 编码。?64266346751275356156F E D C B A7 已知有如下的有向网： 求顶点A 到其它各顶点的最短路径（采用Dijkstra 算法，要有过程）。（6分） 三、 设计题（30分，每题10分,用C 语言写出算法，做在答题纸上）1 已知线性表（a 1,a 2,a n ）以顺序存储结构为存储结构，其类型定义如下： #define LIST_INIT_SIZE 100 /顺序表初始分配容量 typedef struct Elemtype *elem; /顺序存储空间基址int length; /当前长度（存储元素个数） SqList;设计一个算法，删除其元素值为x 的结点（假若x 是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下： S tatus ListDelete(Sqlist &L,Elemtype x) 2设顺序栈如左图所示。其中结点定义如下：typedef struct Elemtype *base; /栈底指针 Elemtype *top; /栈顶指针Stack;设计算法，将栈顶元素出栈并存入e 中 base3设二叉链树的类型定义如下： typedef int Elemtype; typedef struct node Elemtype data;struct node *lchild, *rchild; BinNode, *BinTree; 试写出求该二叉树叶子结点数的算法:S tatus CountLeaves(BinTree &root,int &n)/n is the number of leaves答案：选择题（每题1分）1、C2、D3、A4、D5、C6、D7、A8、B9、C 10、C一、填空题1设计、实现2特殊、栈顶3LOC（a1）+(i-1)*L4p->next=q->next;q->next->prior=p; q->next=p;p->prior=q; 5n(n-1)/2、n-16ADCBFEG、ABCDEFFG7ABC、ABC二、应用题（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分，每行4、 初始关键字： 18 12 25 53 18第 一 趟：12 18 25 53 18第 二 趟：12 18 25 53 18 第 三 趟：12 18 第 四 趟：12 18 18 （4分）O （n 2）（1分）。 5、7分 （1）4分 （2）4分6、(1) 3分 A B 1 C3 25 D 4E F （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;iif(L->elemi=x) break; if(i=L->length) return ERROR; for(j=i;j设元素个数记为n ，则平均时间复杂度为：=-=-=n i n i n n E 121)(1 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);
