数据结构2021试题(A)-答案.pdf

该【数据结构2021试题(A)-答案 】是由【小屁孩】上传分享，beplayapp体育下载一共【4】页，该beplayapp体育下载可以免费在线阅读，需要了解更多关于【数据结构2021试题(A)-答案 】的内容，可以使用beplayapp体育下载的站内搜索功能，选择自己适合的beplayapp体育下载，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此beplayapp体育下载到您的设备，方便您编辑和打印。:..数据结构2021试题(A)-(A)-,p2,p3,…,pn,其输出序列是1,2,3,…,武汉大学计算机学院n,若p3=3,则p1的值。2021年-2021学年第二学期“数据结构”考试试题(A)(序号)_班号要求:所有的题目的解答均写在答题纸上(每张答题纸上要写清楚姓名、),需写清楚题目的序号。每张答题纸都要写上姓名和序号。,最适合用作链队的链表是。一、单项选择题(每小题2分,共20分),通常不仅要存储各数据元素的值,而且还要存储。(长度为n,每个结点存储一个字符),查找元素值为ch的算法的时间复杂度为。(1)。(n)=nlog2n+(n)(n2)[6][10],每个数组元素占用4个存储单元,(n)=n2-8000n放的数组元素a[3][5]的存储地址为1000,则a[0][0]的存储地址是。(n)=nlogn-(n)=1000nlog2n+。(1≤i≤n):..。~,其中叶结点的个数是多少?(需写出推1025导过程,8分),采用邻接矩阵和邻接表表示时,~1024一个顶点的度是多少?(8分)数据结构2021试题(A)-{4,5,7,2,1,3,6}中的数依次插入到一棵空的平衡二叉树中,,中序遍历序列为DEBAC,则先序遍历相应的平衡二叉树。(要求画出每个元素插入过程,若需调整,还需给出调整后序列为。的结果,并指出是什么类型的调整,12分),假设R[0..i-1]为有序区,R[i..n-1]为无序区,现要将R[i]插入到有序区中,可以用二分查找来确定R[i]在有序区中的可能插入位置,,从顶点1开始进行深这样做能否改善直接插入排序算法的时间复杂度?为什么?(8分)度优先遍历;。。(4分)图1一个无向图四、算法设计题(共30分)二、填空题(每题2分,共10分)。。,设计一个算法,,每个顶点的度最大可达。另一棵二叉树t。(15分)[1..18]进行二分查找,则查找R[3]的比较序列的下数据结构2021试题(A)-答案标为。,所需进行的关键字之间的一、单项选择题(每小题2分,共20分)比较次数为。{2,7,4,3,1,9,10,5,6,8},,构造的初始堆(大根堆)是。(不用画出堆,只需写出初始堆的序列)、问答题(共40分):..,时间的复杂度仍为O(n)。二、填空题(每题2分,共10分)评分标准:答对“不能”占3分,说明理由占5分。。(n-1)。、4、2、(n-1)/2。:生成初始归并段(或顺串),采用多路平衡归并方法进行归并。,8,9,6,7,2,4,5,3,1。(序列不全对不给分)2三、问答题(共40分)四、算法设计题(共30分):二叉树中度为1的结点个数只能是1或0。设n1=1,。n=n0+n1+n2=n0+n2+1=1001,由性质1可知n0=n2+1,由两式可求n0=,不解:用p从头至尾扫描单链表,pre指向*p结点的前驱,用minp保存值最小成立;设n1=0,n=n0+n1+n2=n0+n2=1001,由性质1可知n0=n2+1,由两式可求的结点指针,minpre指向*minp结点的前驱。一面扫描,一面比较,将最小值的n0=501。本题答案为:501。结点放到*minp中。算法如下:评分标准:只给出结果给3分,推导过程占5分。voiddelminnode(LinkList*L){:对于邻接矩阵表示的无向图,顶点i的度等于第i行中元素等于1的个;LinkList*pre=L,*p=pre-next,*minp=p,*minpre=pre;while(p!=NULL){对于邻接矩阵表示的有向图,顶点i的出度等于第i行中元素等于1的个数;入度等于第i列中元素等于1的个数;度数等于它们之和。if(p-dataminp-data){minp=p;对于邻接矩阵表示的无向图,顶点i的出度等于g-adjlist[i]为头结点的单链表中//查找最小值结点*minp及其前驱结点*minpre结点的个数;入度需要遍历各顶点的边表,若g-adjlist[k]为头结点的单链表中存数据结构2021试题(A)-答案在顶点编号为i的结点,则顶点i的入度增1;度数等于它们之和。}评分标准:有向图、无向图两种存储方式各占4分。}(图中加阴影的结点表示要调整的结点)。}pre=p;p=p-next;数据结构2021试题(A)-答案minpre=pre;图2构造平衡二叉树过程minpre-next=minp-next;//删除*minp结点free(minp);评分标准:除第一步外,每插入一个元素占1分,每次调整占2分。评分标准:根据算法的正确性评分,不考虑算法的时间复杂度。:不能。因为在这里,二分查找只减少了关键字间的比较次数,,设计一个算法,由二叉树b复制成3:..另一棵二叉树t。(15分)解:递归算法如下:voidcopy(BTNode*b,BTNode*t){}BTNode*l,*r;if(b==NULL)t=NULL;else{}t=(BTNode*)malloc(sizeof(BTNode));copy(b-lchild,l);copy(b-rchild,r);t-lchild=l;t-rchild=r;评分标准:根据算法的正确性评分,不考虑算法的时间复杂度。4