数据结构2016冲刺讲义

Ο(1)＜Ο(logn)＜Ο(n)＜Ο(nlogn)＜Ο(n2)＜Ο(n3)＜Ο(2nO(nO(nn [题1]以下算法的时间复杂度是 voidf(intinti,j,for(i=1;i<n;for(intj=n;j>=i+1;j--)} B.O(n C. D.O(n ==n(n-1)/2=[题2]以下算法的时间复杂度是 voidf(intint}A. ) B. C. D.O(即T(n)≤=O()。[题3]以下算法的时间复杂度是 voidf(intwhile(d>0){if(d%2==1)p=p*f; d=d/2;}} B. C. D.基本运算是语句d=d/2（或f=f*f），设其执行时间为T(n)，则有d=n/2T(n) 即T(n)≤logn=O(log 线性表的静态分配顺序结构：#defineLISTSIZE typedefElemType #defineLIST_INIT_SIZE100 #defineLISTINCREMENT10 typedefstruct{ElemType //空间基 }系，必须附加指针来表示，这也导致线性表的空间利用率降低。typedefstructstruct*next;//指针域}下，最好采用链表作为结构。 [题2]采用顺序结构的线性表的插入算法中，当n个空间已满时，可申请再增加分配m个 ）可分配的空间。A.m C.n+m 连续的一块空间顺序存放线性表的各元素。1、顺序表上的插入运算，时间主要消耗在了数据的移动上，在第ixann－i＋1个元素。时间复杂度为Ｏ(nai+1～ann-i个元素。时间分析：此题主要考查线性表的顺序结构（这里为数组）的应用。算法的基本设计思想是voidAdjust（int{inti=1,j=n,temp;while(A[i]%2!=0)iA[i]为奇数时，i增1while(A[j]%2==0)j++;∥A[j]为偶数时，j减1if(i<j){temp=A[i];A[i]=A[j];A[j]=temp;}}}表结点，因此这类算法中建立链表的算法是。void istF(LinkList&L,ElemTypea[],intLNode*s;inti;for(i=0;i<n;i++) }}voidCrea istR(LinkList&L,ElemTypea[],intn){LNode*s，*r;inti;L=(LinkList)malloc(sizeof(LNode for(i=0;i<n;i++) r=s;r->next=NULL;∥终端结点next域置为}分析：此题主要考查线性表的链式结构的应用，此题目具有一定的难度。算法的基本设voidInsertsort（LinkList{LNode*p,*q,*r,*u; while(q!=NULL&&q->data<=p-}u=p->next;p->next=r->next;r-}}①；②；s-③；解答：①p->nexts->data分析：假设ha和hb是两个结点的单链表，分别表示两个集合A和B，求C=A∩B,这里用单链voidIntersection(LinkListha,LinkListhb,LinkList∥将ha和hb中共同的元素到单链表hcLNodepa=ha->next;pb=hb->next;hc=(LinkList)malloc(sizeof(LNode));∥申请头结点whlie(pa&&if(pa->data<pb->data)pa=pa->next;else{pa和pb两个结点的数据域值相等 }}q- p->next->prior=q;q->next=p-q->next=p->next;p->next->prior=q;p->next=q;q-p->next=q;q->prior=p;q->next=p->next;p->next-p->next->prior=q;q->next=p->next;q->prior=p;p-] （1≤i≤n-1）的值是（） [题1]若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。 B.2和 C.4和 D.5和LOC(aij)=LOC(a00)+(i×n+jLOC(aij)=LOC(a00)+(j×n+i三角矩阵：与对称矩阵类似，不同之处在于存完下（上）三角中的元后，接着[题1]设矩阵A[1..n][1..n]是一个对称矩阵，为了节省空间，其下三角部分按行序存放在一标位置k的值为（）。A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.个元素，k=i(i-1)/2+j-1+1=i(i-1)/2+j。 地址是（ 分析：由二维数组按行优先寻址计算LOC(aij)=LOC(a00)+(i×n+j)×d可知， 完全二叉树和满二叉树采用顺序比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省空间，又可以利用数组元素的下对于一般情况的二叉树，甚至比顺序结构还节省空间。因此，二叉链表是最常用的二叉树方式。typedefstructBiTNode{emTypestructBiTNode*lchild;*rchild;BiTree ） 1点，……，Nm个度为m的结点，则有：N0=1+N2+2N3+……+(m-1)Nm。n2kn不是2n2k。当n=2k但是非满二叉树，其高度为②有n个结点的完全k。①编号为②编号为p的结点有右兄弟的条件是(p-1)%k≠0时，其右兄弟的编号为p+1 和左、右子树之间的交换，其思想是选择合适的遍历方式进行操作，大部分操作 ） voidlink(BiTreebt,BiTNode*head,BiTNodeif(bt!=NULL){if(bt->lchild==NULL&&bt->rchild==NULL)//叶子结点if(head==NULL){//第一个叶子结点else{tail->rchild=bt;tail=bt;if(bt->lchild!=NULL)link(bt->lchild,head,tail);if(bt->rchild!=NULL)link(bt-}} voidAllpath(BiTreeb,ElemTypepath[],intpathlen)inti；ifif(b->lchild==NULL&&b-for(i=pathlen-1;i>=0;i--) printf(“\n”); else{path[pathlen]=b->data;//将当前结点放入路径中 }[题1]索二叉树中，下面说法不正确的是（）[题2]一棵左子树为空的二叉树在先序线索化后，其中空链域的个数是 设森林FT1T2Tn)；其中，T1root，t11t12t1m)；二叉树B=(LBT,Node(root),RBT)；若F=Φ，则B=Φ；ROOT(T1t11t12t1mLBT(T2T3TnRBT若B=Φ,则F=Φ；Node(root)ROOT(T1由LBTt11t12t1m)；由RBT(T2T3Tn①子，然后（）。 值相同的n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚3 ） B. C. ） [题1]以下关于图的叙述中，正确的是（）。A.B. 对角线为0，则至少需要n(n-1)/2空间。用邻接矩阵方法图，很容易确定图中任意两个顶点之间是否有边相连；但是，要点（vi和vj）之间是否有边或弧相连，则需搜索第i个或第j个链表，因此，这种方法不及邻[题1]n个顶点的无向图的邻接表中边表结点总数最多有（） 图的结构用邻接矩阵表示时，深度优先搜索遍历图的时间复杂度为O(n2)。当以邻接表作结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。深度优先搜索遍历图的空间同之处仅仅在于对顶点的顺序不同。（） C.有回路D.一棵分析：对于无向图来说，若无向图是连通图，则一次遍历能够到图中的所有顶点，但若无向图是非连通图，则只能到初始点所在连通分量中的所有顶点，其他连通分量[题2]假设图G采用邻接表，设计一个算法，输出图G中从顶点u到v的长度为k的所有简单开始，进行深度优先搜索。由于在搜索过程中，每个顶点只一次且不重复，voidPathAll(ALGraph*G,intu,intv,intk,intpath[],intintif(u==v&&d==k)for(i=0;i<=d;i++)printf(path[i]);//输出一条路径 while if(visited[m]==0)p->nextarc;} }[题1]设有无向图G=（V，E）和G’=（V’，E’），如果G’是G的生成树，则下面不正确的说法是（）。A.G’是G的连通分量BG’是GC.G’是GD.G’是G的极小连通子图且（）A．深度优先遍历B．广度优先遍历C．求最短路径D．求关键路径>，< 的最早发生时间ve( 的最迟发生时间vl(求AOV网中所有活动的最早发生时间e求AOV网中所有活动的最迟发生时间l求AOV网中所有活动的余量d()=l()-e(,ve(ve(k)=Max{ve(j)+dut(<j,vl(ve(vl(j)=Min{vl(k)–dut(<j,IA．仅Ⅰ和IIB．仅Ⅰ和III C．仅ⅠD．仅III[题2]下面关于工程计划的AOE网的叙述中，不正确的是（）)； ） B.I、 C.I、III、 D.II、 有序表，且限于顺序结构（对线性链表无法有效地进行折半查找）。因此，折半查找不适4块内进行顺序查找的平均查找长度为LW。ASLbs=LB+LWtypedefstructnode{intA[m]；structnode*next;typedefstruct{intj; LNode*s; rcd*Lsearch(LinkListhead,intn){rcd*R;while&&!found){forif(p->A[j]==n)if(p==NULL)returnNULL;else{ returnR;}}A．21B.23C.41D.⑶除根结点之外的所有非终端结点至少有m/2针Ai-1所指子树中所有结点的关键码均小于Ki(i=1,2,…,n)，An所指子树中所有结点的关键码均大于Kn，m/21≤n≤m1，n为关键码的个数。不超过:m/21，因此，每次插入一个关键字不是在树中添加一个叶子结点，而是[题1]下面关于m阶B-树说法正确的是 A．I、II、 B．II、 C．II、III、 1个关键字，每个结点含有的关键字数目比指向孩子结点的指针数目少1，所以说法II起B-树结点后，只要从根结点到该元素插入位置的路径上至少有1个结点未满，B-[题2]下面关于B-树和B+树的叙述中，不正确的是（）在一般情况下，很容易产生“”现象，即：key1key2，而f(key1)=f(key2)。H(key)=keyMOD Hi=(H(key)+di)MOD (1≤i<m其中：di1，2，……，m-1，且di=i Hi=(H(key)±di)MODid12，-12，22，-22，……，q2，-q2且q≤m/2。i[题1]下列有关散列查找的叙述正确的是 分析：在散列表中，每个元素的位置通过散列函数和解决的方法得到，散列法多个不同关键字对应相同的散列地址，选项B错误；用线性探测法解决的散列表装填因子α越小，发生的概率越小，但仍有可能发生。[题2]散列表的平均查找长度（） [题3]采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理，在散列地址空[题4]已知一组关键字为（26，36，41，38，44，15，68，12，6，51，25），用链地址法解决。假设装填因子α=0.75，散列函数的形式为H(key)=keyMODp，回答下列问分析：本题是对散列表的一种常见考查方式。采用链地址法处理，查找成功表示找到了三、J.H.Morris)KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)S[iT[j]S[i-j+1..i-1]==T[1..j- T[1..k-1]==T[j-k+1..j- S[i-k+1..i-1]==T[1..k-[题1]‘ababaaababaanext 第一趟：第二趟：第三趟： voidQuickSort(El