上海大学数据结构试卷及答案
很好的考试复习资料,内容很多,讲解很细致,而且涉及的也是重点数据结构试卷(一)参考答案选择题2.C3.DC 5. A6,C7.C8,B9.810.B填空题1.(F+!2.0(n),0(n1,4. s->rext=p-7nexl: y>neext=sn, 2e6.m=2了,CBA8.4,1610.n-1、应用题1.链式存储结构略,前序 ABDEL,中序 DBEAC,后序 DEBCA,2.哈夫曼树略,WPL=783.(i8,5,16,19,21,23),(5,16,21,19,18,23)h1012345674.线性探测:链地址法:h2->1人8∧1025322768h4->25->326865.深度:125364,广度:123456,最小生成树T的边集为E={(1,4),(1,3)(3,5,(,如,(.6)}四、算法设计题1.设计判断单链表中结点是否关于中心对称算法typedef struct (int s[100]; int top, y sqstack;int lklistsymmetry(iklist *head)sqstack stack; stack top=-1; Iklist"p;forip=head;pl=O; p=p->next)(stack. op++;stack s[stack top=p->data; 3for(p=head;pl=0;p=p->next)iE (p->data==stack s(stackLop!)stack top=stack top- 1; else return(0);return(1);2.没计链式存储结构上建立一楳二又树的算法。typedef char datatype,typedef struct node (datatype data; struct node *lchild, *rchild; bitreevoid createbitree( bilree*&bt)char ch; scanf("%c, &eif(ch==")(bt=0; return; Jbt=(bitree*)malloc(sizeof(bitree)); bt->data=chreatebitree(bt->lchild); createbitree(bt->rchild);3.设计判断一棵二叉树是否是二义排序树的算法。int minnum=-32768, flag=1typedef struct nodefint key; struct node"Child, *rchild; bitree;yoid inorder ( bitree *bt)if (bt =0)[inorder(bt->child ); if(minnum>bt->key)flag=0; minnum=bt->key, inorder (bt->rchild); h数据结构试卷(二选择题(24分)1.卜面关于线性表的叙述错误的是(D)(A)线性表采用顺序存储必须:用一片连续的存储空间(B)线性表采用链式存儐不必山用一片迕续的存储空闫(C)线性表用链式存便丁插入和删除操作的实现D)线性表釆用顺序存储便亍插入和删除操作的实现设哈大曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有(A界个空指针域,9有叶万为的纸且2(A)2m-1(B)2mC)2m+1妤没顺序循环队列Q0:M1]的头指针和尾指针分别为P和R,头指针F总是指向队头元素的前一位置尾指针R总是指向队尾元的当前位置,则该循环队列中的元素个数为()(A)R-T(B)F-R(C)(R-F+M)%M()(F-R+M)%M√4!设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为A(A)BADC(B)BCDA(C CDAB(D) CBDA5.设某完全无向图有n个顶点,则该完全无向图中有(A条边(A)n(n-1)/2(B)n(n-1)(C)n26.设某棵二叉树中有2000个结点,则该二叉树的最小高度为(O)。(C)11D)12设采图中有m个顶点,则该有向图对应的剑趣中有()个表头结点(B)n(D)2n-18.设一组初始记录关键字序列(5,2,6,3,8),以笫一个记录关键字5为基准进行一趟快速排序的结果为(C)。(A)2,3,5;8,6(B)3,2,5,8,6(C)3,2,5:6,8①D)2,3,6,5,8、填空题(24分)1.为了能有效地应用HASH查找技术,必须解决的两个问题是和下面程序段的功能实现数据x进栈,要求在下划线处填上正确的语句typedef struct (int s[ 100]; int top: f sqsiack;void push (sqstack &stack, int x)if( stackop==m-1) printf(“ overflow”)lies9tk二x;“a少+:3.中序遍历二叉排序树所得到的序列是有度序列(填有序或无序铁邀神厅的最间复弟度为1),平均时间复杀度为地D(3设某倮二叉树中度数为0的结点数为N,度数为1的结点数为N,则该二叉树中度数为2的结点数若采用二叉链表作为该二叉树的存储结构,则该二叉树中共有山+41个空指针域6.设某无向各中顶点数和边数分别为n和e,所有顶点的度数之和为d,则e=7.设一缃初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为8.改某无向图G的邻接表为2->1>3又v--1->4->2·从点W开始的深度优先遍历序圳为1,24:切度优先遍历序列为省三、应用题(36分)].设一组初始记录关键字序为(45,80,48,40,22,78),则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果2.设指针变p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结京的两个指针域分别为11ink和 rlink)a设一组有序的记录关键字序圳为(13,18,24,35,47,50,62,83,90),查找方法用二分查找要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度4设一棵树T中边的集合为联A,B),(A,C,(A,D),(B,E),(C,F,(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树5.设有无向图G(如右图所示),要求给出用普里姆算法构造最小生成树所走6过的边的集合。6.设有—组初始记录关键字为(45,80,48,4,2,178,要求构造一楔二(56叉排序树并给出构造过程。四、算法设计题(16分)1.设有一组初始记录关键字序列(K,K2,…,K),要求设计一个算法能够在0(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于K,右半部分的每个关键字均大于等于K2.设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C用链式存储结构表示数据结构试卷(二)参考答案选择题ltd 2. B5,A7,B8.C二、填空题构造一个好的HASH凼数,确定解决冲突的方法2. stack top+t, stack s[stack top ]=3.有序4.0(n2),0( logan)5.N-1,2N+N6.d/27.(31,38,54,56,75,80,55,638.(1,3,4,2),(14)应用题1.(22,40,45,48,80,78),(40,45,48,80,22,78)2. q>llink=p: g->rlink=p->rlink; p->rlink->link=q; p->rlink=q·3.2,ASL=91*1+2*2+3*4+4*2)=25/94.树的链式存储绪构略,二叉树略E={(1,3),(1,2),(3,5),(5,6),(6,4)}6.略四、算法设计题1.设有组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在0(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于K1,右半部分的每个关键字均大于等于KYoid quickpass(int r[, int s, int t)int i=s,j=t, x=r[s]While(inext: p->data=g->data: p->next=g->next: free(q)B)gp->next: g->data=p->data: p->next=g >next free(g):(C)q=p->next: p->next=q->next: free(q)(D)q=p->next: p->data=q->data: free q)4.设有n个待排序的记录关键字,则在堆排序中需要(小个辅助记录单元(A)1(B)n(c)nlogen5.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录的一趟快速排序结束后的结果为(A)10,15,14,18,20,36,40,21(B)10,15,14,18,20,40,36,2I(C)10,15,14,20,18,40,36,21(D)15,10,14,18,20,36,40,21y/设二叉排序树中有n个结点,则在二叉排序树的平均平均查找长度为)(A)0(1)(B)0(10g2n)((D)O(n2)7.设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点的个数分别为(D(B)e,nC)2D)n,28.设某强连通图中有n个顶点,则该强连通图中至少有(C)条边(A)n(n-1)(B)n+1D)n(+19.设有5000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字,则用下列)方法可以达到此目的(A)快速排序(B)堆排序(C)归并排序D)插入排序0下列四种排序中()的空间复杂度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序二、填空殖(48分,其中最后两小题各6分)数据的物理结构主要包括座不构利和环结堆两种情况设一棵完全:叉树中有500个结点,则该二叉树的深度为4:若用二叉链表作为该完全二叉树的存情结构,则共有55个空指针域3.设输入序列为1、2、3,则经过栈的作用后可以得到种不同的输出序列。4.设有向图G用邻接矩阵An]「m作为存储结构,则该邻接矩阵中第i行上所有元素之和等于顶点i的友,第1列上所有元素之和等于顶点i的入区毕设哈夫曼树中共有n小结点,则该哈夫曼树中有日个度数为1的结点6.没有向图G中有n个顶点e条有向边,所有的顶人度散之和为d则形和d的关系为=e遍历二义排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)8.改奁找表中有100个元素,如果川二分法查找方法查找数据元素X,则最多需要比较次就可以断定数据元素K是否在查找表中9.·不论是顺序存储结构的栈还烂链式存储结构的栈:其入饯和出栈榤作的间复柒度均为的10.设有a个结点的完全一义树,如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的义结点编号为“,右孩子结点的编号为2计11.设一组初始记录关键字为(72,73,71,23,94,16,5),则以记录关键字72为基准的·趟快速排序结果为!2.设有向图G中有向边的集合F=(,,,,key==k)Y七; else if(t->key>k)tt>lchd;lse七飞→YC三、算法设计题(22分设计在单链表中删除值相同的多余结点的算法2.设计-个求结点x在二叉树中的双亲结点算法。数据结构试卷(三)参考答案、选择题B4.A5.A6.B7.D8.C9.B10. D第3小题分析:首先用指针变量q指向结点A的后继结点B,然后将结点B的值复制到结点A中,最后删除结点B第9小题分析;9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数,而堆排序只需要在初始堆的基础上再进行10次筛选即可,每次筛选的时间复杂度为0(1ogn)。土、填空题1.顺序存储结构、链式存储结构2.9,5013.54.出度,入度6.7.中序8.79.0(1)10.豆/2,2i+111.(5,16,71,23,72,94,73)12.(1,4,3,2)13. j+l, hashtable[i]. key==k14. return(t),t=t-rchild第8小題分析:二分査找的过程可以用一棵二叉树来描述,该二叉树称为二叉判定树。在有序表上进行分查找时的查找长度不超过二叉判定树的高度1+log2n三、算法设计题设计在单链表中删除值相同的多余结点的算法。typedef int datatype;typedef struct node datatype data; struct node *next; lklistvoid delredundant (lklist *&head)Iklist *p,响q,*s;for(p=head; pl=0; p=p->next)tor(q=p>nex s=4;q!=0;if (q->data==p->data)[s->next=q->next; free(q); q=s->next; 1else (s=q, q=q->next; y。2.设计个求结点x在二义树中的双亲结点算法。typedef struct node (datatype data; struct node *Child, *rchild; bitree;bitree*q[20]; int r=0, f=0, flag=0void preorder (bitree * bt, char x)
- 2021-05-07下载
- 积分:1
鲁棒控制——LMI处理方法
俞立老师的经典书籍——《鲁棒控制——基于线性矩阵不等式的处理方法》振动论坛鲁棒控制—线性矩阵不等式处理方法俞著清华大学出版社振动论坛(京)新登字158号内容简介木书结合作者的研究工作,详细介绍了基于线性矩阵不等式的不确定系统食棒控制的概念、理论及设计方法。主要为謇括日前应用广泛的线性矩阵不等式的概念、理论、算法及相关软件:基于线性矩阵不等式处理方法的线性时不变系统性能分析和缤合方法:重点介绍了不确定系统的模型、曹棒性能分妡、鲁棒砂以H控制、LM区域及相应的区域极点配置方法,绪合二次型性能指标的保性能控制、鲁榨方差控制对将系统的分析与鲁棒控制器设计、不确定系统的鲁滤波问题及鲁棒滤波器设计本书反映了近年来鲁棒控制领域中的最新研究成果,系统介纲了线性矩阵不等式这一有效工具,它在应用中的典型处理方法及 MATLAB软件中的LMI具箱,本书可作为从事自动控制工作的科研员、工技术人员以及高等院校自动化及其他相关专业教师高年级学生和研究生的参老用书版权所有,翻印必究本书封面貼有清华大学出版杜激光防伪标签,无标签者不得销售。书名:鲁棒控制—线性矩阵不等式处理方法作者:俞立著出版者:清华大学出版社(北京清华大学学研大厦,的编100084)http://www.lup,lsingt:ua.educn费任编辑:朱英彪印刷者:北京通州区大中印刷发行者:新华书店总店北京发行所开本;787×10921:16即张;17.75字数:403千字版次:202年12月第1版20年12月第1次印刷书号:ISEN730245854-7/O·269印数:0001~400定价:26.00元振动论坛前言在实际工业控制牛,各种工业牛产过程、生产设备以及其他众多的被控对象,其动态牿性一般鄱难以用精确的数学模型来描述。有时即使能获得被控对象的精确数学模型,但白于过于短杂,使得难以对其进行有效的掉制性能分析和综合,因此必须进行适当的简化。另一方面,难着生产过程中主作条件和环境的变化,控制系统中元器件的老化或损坏,被控对象本身的特性也会随之发生变化。所有这些因素使得描述被控对象的数学模型和实际对象之间不可避免地具有误差。因此,在工程实践中,釆用基于精确数学模型的现代控制理论方法所设计的控制系统往往难以具有所期望的性能,甚至连系统的稳定性都难以得到保证。鲁棒控制理论结合系统模型参数不确定性和外部找动不确定性的考虑,研究系统的鲁棒性能分析和综合问题,弥衤了现代控制理论需要对象精确数学模型的缺陷,使得系统的分析和综合方法加有效、实用棒挖制自提出以来,很快受到了人们的广泛重视和研究,取得了一系列的研究结果和方法,并在一些工程领域中获得了成功的应用。特别地,随着线性短阵不等式及求解凸优化问题的内点法的提出,为许多控制问题的分析和求解提供了有效工具。 MATLAB软件中线性矩阵不等式工具箱的推出使得各种线性矩阵不等式问题的求解旻加方便、直接从而,进一步推动了线性矩阵不等式处理方法在系统和控制领域中的应用。本书系统介绍了线性矩阵不等式的概念、性质、求解线性矩阵不等式相关问题的算法以及 MATLAB软件中的线性矩阵不等式工具箱。结合作者的研究工作,介绍了基丁线性矩阵不等式的鲁棒控制性能分析和综合方法,并指出了一些在系统和控制中有广泛应用价值的线性矩阵不等式典型处理方法。作者努力将售棒控制的最新研究成果和方法反映存本书中,但限于篇幅,书中所包含的内容仅仅是鲁棒控制研究成果的很少-部分。振于作者的水平,书中不妥和错误之处在所难免,恳请广大读者批评指正本书中介绍的作者研究工作及本书的撰写得到了国家然科学基金和教育部高校优秀青年教帅教学科研奖励计划的资助,在此表示衷心的感谢。作者02年5月杭州振动论坛目录第1章引言…第2章线性矩阵不等式……621线性矩阵不等式的表示式口·■■■甲↓郾■■.■看■■bL■2Ll1线性矩阵不等式的般表示2l2可转化成线性矩阵不等式表小的问题213复线性矩阵不等式的处理…10214非严格线性矩阵不等式22一堂标准的线性矩阵不等式间题23求解线性矩阵不等式问题的算法23.1椭球法…Isn15232内点法↓乐24关于矩阵不等式的一些结论1824.1矩阵变量的消去法1T·平P1t幽山I82.4.2 S-procedureP甲■20第3章系统性能分析.连续时间系纷…2331.1系统增益指标∴233,12H性能甲日唱·■唱日4自·日血即141■4b1293.13H性能3132离散时间系统1鲁日日司即■命b命即■■■■■着■■■着L=,341第4章控制系统综合.4.1F控制4.l.1状态反馈H控制…d?■■424.],2输出反馈Hx控制■p即42H2控制43H2H控制平1■十■昏■b■m■■■4■qp6144设计示例64第5章不确定系统的分析与综合685]不确定模型68振动论坛會棒控制——一线性矩阵不等式处理方法511不确定状态空闻模型68512不确定线性分式模型■p■b血d卩■b■52鲁棒稳定性分忻P‘■■日音牛114a日4521二次稳定性522仿射二次稳定性I"P}4Pbb4b4}·53鲁棒性能分析.…■■昏■昏1山■d■晶t■■p聊8354鲁棒F2H控制■■■山昏晉昏晋■+口■口■口6541问题的描述和准备…86542H2H整制器设计91第6章区域极点配置1亠山品品61LMI区域9761.】LM区域的描述…,-11111976,2D-稳定性分析…〓P■■■■■■■■■■10062具有闭坏k域极点约束状态反馈控制器设计0463鲁棒D-稳定性分析日日日语■山■,1763无结构不确定性1963.2结构不确定性111464输出反馈控制器设计,第7章保性能控制1227】连续系统的保性能控制…··■■晶■上h香≠p甲日目甲日唱黑L聊■12272离散系统的保性能掉制.12了73其有闭环极点约束的保性能挡制131731鲁棒性能分析…132732二次D保性能控制器设计看自;血自自血即血日昏■是■如4135第B章鲁棒方差控制1418I连续系统的鲁棒方差控制.■d昏【山■血晶b14181.Ⅰ系统性能分析1418L.2状态反馈控制器设计14813输出反愤控制器设计14682离散系统的鲁棒方差控制152第9章时滞系统的分析和综合15891时滞系统的稳定性…15891.1时滞独立的稳定性条件……,1599.1.2时滞依赖的稳定性条件,+--114141609.1.3 Lurie时滞系统的稳定性分析T宁宁·自血日甲自自要振动论坛自录92时滞系统的鲁棒稳定性分析16992.!时滞独立的鲁棒稳定性条件P·q甲,甲■15992.2时滞依赖的鲁棒稳定性条件17493不确定滞系统的保性能控制.■■■■793.1鲁棒性能分析I789.32状态反馈俣性能控制器设计,4.4.418393.3输出反馈俣性能控制器设计1869.34不确定离散时滞系统的保性能控制I9394时滞系统的玨控制941时滞系统的性能分析,…199942H控制器设计943不确定离散时滞系统的鲁棒H控制207第10章寯波器设计213101B滤波器设计2I310.2FH滤波器设计2l9第11章大系统射分散控制22311时滞系统的分散稳定化控制22311,2离散关联系统的分散保性能控制229l1,21保性能分析■■■山■↓山 -r.E= PPE+■▲画2291121分散保性能控制器设计234附录ALM工具箱介绍■L■■■an·■■甲口■看■■口■山241A.F线性矩阵不等式及相关术语……24LA.2线性矩阵不等式的确定■■■■昏昏斷■+d山夏旷aaa■_画d■242A.3信息提取2499A4绒性矩阵不等式求解器■■■■■■日■司罾■严早■■■吾-■山■山m矿画maaa250A.5结果验证…258A6修改一个线性矩阵不等式系统A.7一些进一步的功能261A.8系统棋型描述…,267参考文献270振动论坛第1章引言自20世纪5年代末现代控制理论誕生以米,控制理论得到了飞速的发展,并在20世纪60年代然航天领域中得到成功的应用。但是,现代控制理论在随后的工业应用中却遇到了很大的困难。我们知道,现代控制理论的许多结果都是基于对象的一个数学模型,根据系统的性能要求,通过刈被控对象的数学模型进行分析来设计系统的控制律,进而将所得到的控制律应用于被控对象来保证闭环系统貝有所期望的性能。显然,当对象模型不能精地描述被控对象或在系统运行过程中模型和实际对象产生侃离时,基于这栟的模型设计的控制系统很难保证具有所期望的性能要求实际上,对于复杂物理系统的模型,存在以下两个问题描述物理系统的解析模型很难,甚至不可能精确地刻画,因此为了便于处理,不得不筒化模刑:2.一个模型,无论多么详细,都不可能是物理系统的一个濤确表示。因此,模型存在本质的不精确性。建模中的以上两个方面称为模型的不确定性。对于一个复杂系统,为了得到一个较为简单的模型,一种处珄方法是将其分解线性部分和非线性部分的组合,进而用一个更空易处理和分析的对象来替代这个非线性邺分,达到简化原文复杂系统棋型的目的考虑由以下非线性微分方程描述的复杂动态系统x=f(x, m)H(x, u)初始条件是x(0),x()、y()和()是向量值函数,∫和h是光滑的向量值函数。在特殊的运行点附近,可以将系统(1.)分解成一个线性部分和一个线性部分的组合特别地,可以在原点x,)=(0,0处进行这样的分解。定义系统Ax t Bu+gtr, Wv=Cx+IH+rx, uj其中:A、B、C和D是系统(11)的一个线性化近似g(x,叫)=f(x,)-Ax-Br(, u)-hr, u)-Cx-Du显然,这样定义的系统(1.2)和系统(1:)是等价的。因此,它们之间存在-—对应的关系。得到这样的等价系统的一种方式是将函数∫和h在原点处线性化,可得Cl(x.)=(0.0)x,)=(0,Q)0.0Ca(x,)=()振动论坛鲁棒控制——线性矩阵不等式处理方浊进一步可以将方程(12)受成以下等价的形式:x= Ar I Bu I wL1.3y=cx+Da+脚2(14)(w1,w2}=(g(x,L),r(x,)(1.5设G是宙(1.3)~(1.4)式确定的映射;对给定的初始条作x(0),門2,)以(x环,y)。Ω是由(1.5)式确定的映射:(x,n)卜(1,2)。因此,〈1.3(1〕式描述的系统可以用图11来表示图11系统分解容易看到,G是系统的线性部分,Q是静杰的非线性映射。这样就将系统的非线性部分分离出来,归入到映射g中,非线性部分和线性部分通过反馈关联联系起来更一般地,我们用这样的方法不仅可以处理系统的非线性特性,而且也可以处理系统的某些动态特性。考虑由以下方程组描述的系练f2(x1,x2(1y=H(x1,x2,采用前面系统分解思想,对系统(16)中的方程x=f(x1,x2,4)卩=(x,x2进行分解,并得到:=团x+B+8(x2f2(x1,x2,a)(1.)卩=C1x+D4+r(x,x2,a)进步,系统(17)中的方程等价于以下的线性方程:x=A1x1+BM+即8y=C,+Du+M其中,w2}=(g1(x,x2,),P(x,x2,Bm)x2=f1(x,x2,x)(1,9)设G是由方程(18)描述的线性系统;(w3,2,(x,,y),是由(9)式描述的系统:(x1,4)"(m,m2)。对这样定义的G和Q,图1也同样描述了系统(1.6)。
- 2020-12-06下载
- 积分:1