数据结构复习要点

第一 数据结构概（有时候）个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直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、完全二叉树