数据结构复习要点_第1页
数据结构复习要点_第2页
数据结构复习要点_第3页
数据结构复习要点_第4页
数据结构复习要点_第5页
已阅读5页,还剩8页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第一 数据结构概(有时候)个元素(根)之外,其它每个数据元素都只有一个直接前驱,以及多个或零个直nO(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(n(1)512可预期的后果5、高效率(O(1O(n指数阶O(2^n)。通常认为,具有常数阶量级的算法是好算法,而具有指数阶量级的算法是第二 线性定义:线性表n个数据元素的有限序列。一个数据元素可由若干个数据项初始化:p=(structstudent*)malloc(sizeof(structstudent));插入:p->next=head- head- p->next=q->next for(p=head;p;p=p-2pqqP->next=q->next 3、在长度为NN/2个元素,删除一个元素平均需要移动(N-1)/2个元素。300(n个元素的地址即首地址+(n-1)*a[12](13typedefintdatatype; typedefstructnode{ datatypestructnode Lnode,*pointer结点类型,typedefpointer lklistinitlist()pointerhead=newnode;//C++//head=( C return}(Cintinsert(lklisthead,datatypex,inti){pointerq,s;q=get(head,i-1);//i-1 //i-1i<1i>n+1{cout<<”非法插入位置!\n”;//这是C++做法即C语言中的 return0;}s=newnode;//生成新结点 即C语言中的s=(pointer)malloc(sizeof(Lnode));s->next=q->next;//新点的后继是原第i个点 return1; }(Cintdelete(lklisthead,inti){pointerp,q; if(q==NULL||q->next==NULL) //即i<1或i>n时{cout<<”非法删除位置!\n”;return0;} delete //释放结 即C语言中的return head为空的判定条件是(A head- head为空的判定条件是(B head- pps所指结点,则执行(B p- p所指结点的后续结点,则执行(A 平均比较(B)个结点。A. B C.n- D.O(nn个元素的向量,建立一个有序单链表的时间复杂度 D.O(n在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(B) D.O(n㏒2n)qp->next=(p->next->nextpss->next=(p->next)对于一个具有n,在已知所指结点后插入一个新结点的时间复杂度是(O(n)第三 栈和队栈typedefstructintlistsize; structlist*head;//栈顶指针structlist*base;//栈底指针}P46-47) ABCDEA. B. C. 2TOP表示栈顶元素,那么栈空的条件是A. B. C. O(1)(N无关。断栈空、出栈、入栈用函数实现2)(D) B.删除操作比较容易 typedefstructintstructQNodetypedefstruct{QueuePtrQueuePtrLinkQueueInitQueue(LinkQueue{return}LinkQueueEnQueue(LinkQueueQ,int{QueuePtrp;

return}{intQueuePtrreturn}structlist{structlistp=(structlist*)malloc(LEN);}structlist*push(structlist*head,int{structlistp=(structlist*)malloc(LEN);}structlist*pop(structlist{structlist*p;}intlistempty(structlist{elsereturn}(不是重点内容串的赋值:x=’abc’;或x[(不是重点内容position明确按行存储和按列存储1中类将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括:对称矩阵,三角矩三元组十字链表typedefint int typedefstruct{intmu,nu,tu; Triple typedefstructint int structOLNode //}OLNode,*OLink;typedefstruct{intmu,nu,tu; CrossListCreat(CrossListM){intm,n,t;M.rhead=(OLink*)malloc((m+1)*sizeof(OLink));//开辟行表头指针组M.chead=(OLink*)malloc((n+1)*sizeof(OLink));//开辟行列头指针组 }树树:n(n≥0)n=0⑵当n>1时,除根结点之外的其余结点被分成m(m>0)个互不相交的有限集合T1,T2,…,Tm,其中每个集合又是一棵树,并称为这个根结点的子树。0的结点,也称为终端结点。0的结点,也称为非终端结点。兄弟 n1,n2,…,nknini+1(1<=i<kxyxy的祖先,yx的子孙。1k层,则其孩子k+1层。树的深度 层序编号:将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从(1)n(n≥0)个结点的有限集合,该集合或者为空集(称为空(02i的结点在二叉树中的位置完全相同。1kk-1(i≥12k2k-1k2k-1:性质4:具有n个结点的完全二叉树的深度为 +15n1开始按层序编号,则对于任意的序i(1≤i≤n)的结点(i,有:i>1,则结点i的双亲结点的序号为i/2i=1i是根结点,无双2i≤ni2i2i>ni二叉树的遍历(递归调用与访问的顺序不同而产生不同的遍历方法voidXianXu(BiTreeT){ }}0(叶子结点)2(分支结点)1的结点147个结点,则该二叉树有(C)A. B. C. n-1 n n-1所以,叶子结点数 计算第n层和第n-1层的总叶子结点(CCA F ↙E4、完全二叉树

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论