2014考研计算机数据结构冲刺课程讲义

[[题1]以下算法的时间复杂度是（）voidfn){inti,j,fori=1i<nfor(intj=n;j>=i+1;j--)x++；} B. C.O(nlog2n)D.分析：基本运算是语句x++，设其执行时间为Tn解答：D==n(n-1)/2=[[题 以下算法的时间复杂度是 ）voidfn){inti=0;}A. B. C.O(nlog2n)D.)分析：基本运算是语句i++，设其执行时间为则有T(n)×T(n)×T(n)即解答：D=)[[题3]以下算法的时间复杂度是（）voidf(intwhile(d>0){if(d%2==1) =*f=f*f;d=d/2;}} B. C. D.则有d=n/2T(n)>0≥1，2T(n)≤n12、线性表有顺序和链式两 结构 操作平均移动n/2个结点，删除操作平均移动 网络课堂系列 #defineLISTSIZEtypedef ElemType//当前#defineLIST_INIT_SIZE#defineLISTINCREMENTtypedefstruct{ElemType*elem;//初始分配//分配}（（2）间的逻辑关系，必须附加指针来表示，这也导致线性表的空间利用率降低。但在链表中或删除操作始，只需修改相关结点的指针域即可，不typedefstruct data;//数据域structLNode*next;//指针域} [[题1]设线性表有n个元素，以下操作中，（）在顺序表上D．输出与给定值x相等的元 性表中的序[[题2]采用顺结构的线性表算法中，当n个空已满时，可申请再增加分配m个空间。若申请失败，则明系统没有（）可分配的 A．m个B．m个连续的 表的顺 顺序存放线性表的各元素解答移动上，在第i个位置上xai到an2、顺序表的删除运算与运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素ai+1～an都要向上移动一个位置，共移动了n-i个元素。时间复杂度为Ｏ(n)。 [ ]网络课堂系 计算 根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出；分析：此题主要考查线性表的顺序结构（这里为数组）的应用。算法的基。这样，可使算法的时间复杂度为O(n){inti=1,j=n,temp;while(A[i]%2!=0)i++;∥A[i]为奇数时，i增1while(A[j]%2==0)j++;∥A[j]为偶数时，j减1if(i<j){temp=A[i];A[i]=A[j];A[j]=temp;}}}1、建立单链表（1）头插法2、链表中查找第i法3、链表 运5法 voidCrea n){LNode*s;inti; s->next=L- }}voidCrea istR(LinkList&L,ElemTypea[],intn){LNode*s，*r;inti;r=L；∥rfor(i=0;i<n;i++)r-r=s;;}[[题1]采用法对单链表中的元素进行排序，其中L链表的头结点指针，链表元素的数据类型为整型int分析：此题主要考查线性表的链式结构的应用，此题空链表，然后将待排序链表的结点依次这个空链表，所有结点 完毕后，这个新生成的链表就是所的有序链voidvoidInsertsort（LinkList{LNode// r=L;q=L-while(q!=NULL&&q->data<=p-} }s->next=① t=p-p->data=② s->data= 分析：采用的方法是在p所指结点之一个s所指结点时一个s所指结点，然将p所指结点和s所指结点的数据域进行交换解答：①p->next②s voidvoidIntersection(LinkListha,LinkListhb,LinkList∥将ha和 同的元素到单链表hcLNodeInsertsort(ha);∥参考题1将ha指向的单链表由小到大排序Insertsort(hb);∥参考题1将hb指向的单链表由小到大排序 ∥申请头hc-whliewhlie(pa&&if(pa->data<pb- pb=pb->nxtelse{∥pa和pbpc=(LNode*)malloc(sizeof(LNode));∥pb=pb-∥}}结点*q的操作是（）q- p- 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-顺序不能完成在*p结点之后结点*q的操作。1、栈是运算受限（限制在表的一端）的线性表，允许、删除的这一端称为栈顶，—可以使数据通过栈后仍然保持次，对于顺序结构的栈还需注意（1）进[[题1]设n个元素进栈序列是p1，p2，p3，…，pn，其输值是。A.n- B.n- D.有多种可，p2，p3，…，pn进栈，然后依次出栈，即pn- 解答：C1、队列是运算受限（在表的一端进行，而删除在表的另一端进行）的线性表，允许的一端称为队尾，把允许删除的一端称使队列的向量空间得到充分的利用。判断循环队列的“空”和 加入两个元素后，rear和front的值分别为（）。A．1和 B.2和 C.4和 D.5和解答：BLOC(aij)=LOC(a00)+(i×n+j)×d ，每个数组元素占据d个地址单元,LOC(aij)=LOC(a00)+(j×n+i22、特殊矩阵的压（假设以行序为主序（1）对称矩阵：将对称矩阵A压 到SA[n(n+1)/2]（上）三角中的元后，接着对角线上（下）方的到SA[n(n+1)/2+1]中，aij的下标i、j与在SA[k]将对角矩阵A与在SA[k]中的对应元素的下标k的关到一维数组SA[0..u-1]中，aij的下标i、当0≤i，j≤n-1时例如：将三对角矩阵A与在SA[k]中的对应元素的下标k的关系为：当0≤i，j≤n-0≤k＜3n-2时，k=2i+j到SA[3n-2]中，aij的下标i、[[题 设矩阵A[1..n][1..n]是一个对称矩阵，为了节省空间，下三角部分按行序存放在一维数组B[1..n(n-1)/2]下三角部分中任一元素置k的值为 ）—BA.i(i-1)/2+j- B.i(i- C.i(i+1)/2+j- D.分析：对称矩阵A的下标从1开始，对于任一元素aij（由于共有i(i-1)/2+j-1个元素，k=i(i-1)/2+j-1+1=i(i-1)/2+j。解答：B[[题2]设二维数组A[6][10]，每个数组元素占用4若按行优先顺序存放的数组元素a[3][5] 地址为，则a00 地址是（） LOC(aij)=LOC(a00)+(i×n+j)×d可知，解答：B九、树、九、树、二叉树结 从左到右的顺序进行，如果为i（1≤i≤n）的结点与满二叉树中为i的33、二叉树 结（1）顺 结完全二叉树和满二叉树采用顺比较合适，树中结 灵活、操作方便，对于一般情况的二叉树，甚至比顺序结构还节省空间。因此，二叉链表是最常用的二叉树方式。typedef emTypestructBiTNode*lchild;*rchild;//BiTree [[题2]设二叉树只有度为0和2的结点，其结点个数为15二叉树的最大深度为 ）。由于结点个数为15，因此二叉树的深度h为8解答：C性质性质4：具有n个结点的完全二叉树的深度k。的顺序对二叉树中的所有结点从1开始顺序，则对于任意的序号二二叉树性质的度为1的结点，N2个度为2的结点，，Nm个度为m的结①有n>0个叶结点的完全二叉树的高度(结点层次数)当n≠2k,即n不是2的方幂或者n=2k但是一棵满二叉树，其 当n=2k但是非满二叉树，其高度 ②有n个结点的完全k叉树的高度 ①，为p=1的结点无父结点，否为p结点的父 ②为p的结点的第k-1个孩子为p×k，所以，如号为p结点有孩子，其第i个孩子为p×k+(i 为p的结点有右兄弟的条件是(p-1)%k0时，其右兄弟 性质1：树中的结点数等于所有结点的度数+1性质2：度为m树中第i层上至多有mi-1个结点（i≥1）性质3：高度为h的度为m树至多有(mh-1)/(m-1)个结点。性质4：具有n个结点的度为m树的最小高度为logm(n(m-。[[题1]若一棵二叉树有126个结点，在第7层（根结点在第1层）至多有 D.不存在第7。[[题2]若一棵度为7的树有8个度为1的结点，有7个度为2的结共有（）个叶结点。 分析：由二叉树性质3的推广，度为7的树应该有解答：D十十一、二叉树的遍历及应先序遍历：递归算法、非递归层次遍 [[题1]任何一棵非空二叉树中的叶子结点在先序遍历、中序遍历与后序遍历中的相对位置（）。A．都会发生改 B．不会发生改C．有可能会发生改 D．部分会发生改或是后序遍历（LRD），对于叶子结点而言，被的解答：B[[题2]对于二叉树的两个结点X和Y，应该选择（）两个序A．先序和后 B．先序和中C．中序和后 D．A、B、C都解答：D反例（给出任何一个正确的反例即可 结voidvoidlink(BiTreebt,BiTNode*head,BiTNodeif(bt!=NULL){if(bt->lchild==NULL&&bt->rchild==NULL)//叶子结点if(head==NULL){ if(bt->lchild!=NULL)link(bt->lchild,head,tail);if(bt->rchild!=NULL)link(bt->rchild,head,tail);}} f(b,path,pathlen)：将b->data放入path，pathlen++；//其他情况f(b-inti；ifif(b->lchild==NULL&&b-printf(%c到根结点路径：%c,b>data);for(i=pathlen-1;i>=0;i--) (“%c”,path[i]);printf(“\n”);} Allpath(b->lchild,path,pathlen);//递归扫描左子树Allpath(b->rchild,path,pathlen);//递归扫描右子树 }}}十二、十二、这样 ，也不使用栈（其中后序线索二叉树中查找后继仍需要栈）索二叉树中，下面说法不正确的是（） A．不确 解答：D 1,T2,…,Tn) 其中，T1=(root，t11,t12,…,t1m)；二叉树B=(LBT,Node(root),RBT)；若F=Φ，则B=Φ；由(t11t12t1mLBT(T2T3TnRBT若B=Φ,则F=Φ；否则，由Node(root)ROOTT1 33、森林的遍①森林中第一棵树的根结②森林中第一棵树的子树③森林中其他树构成的森森林的遍历可有2条搜索路①先序②中序孩子，则只要先找到*p的第1个孩子，然后（）。解答：D 解答：D十十四、二叉排序树与平衡二ASLn个关键字，构造所得的不同形。33、（1） 注意：在二叉排序树 的结点均作为叶子结点①被删除的结点*p，且左子树和右子树高度之差的绝对值不超过1LL型平衡旋转，A；RR型平衡旋转；A； A．充分不必 B．必要不充C．充分必 D．既不充分也不必值30时发生不平衡，则应进行的平衡旋转是 ） D.[[题 在含有n个结点的二叉排序树中查找一个关键字，进关键字比较次数最大值是 B.） 解答：D十十五、哈夫曼树和哈夫曼编33、对哈夫曼树的55、对哈夫曼树编深度为h的哈夫曼树，其叶子结点的最大编码长度为h-。 解答：C十十六、图的基本概1、2、无向3、有向4、无向完全图：在一个含有n个顶点的无向完，有n(n-1)/2条边5、有向完全图：在一个含有n个顶点的有向完，有n(n-1)条边1111、子图：对于图G=（V，E），G’=（V’，E’），若存在是V的子集，E’是E的子集，则称图G’是G的一个子图12、连通图、连13、强连通图、强连通14、生成15[[题1]以下关于图的叙述中，正确的是（） [[题2]一个有28条边的非连通无向图至少有）个顶 解答：C结之间的邻接关系（邻接矩阵的形式描述）角矩阵的元素即可，又由于主对角线为0，则至少需要n(n-1)/2空间。行（或第列）非零元素（或非元素）的个数正好是第i个顶点的度TD(i。行（或第列）非零元素（或非元素）的个数正好是第i个顶点的出度(i（或入度(i)）。用邻接矩阵方法图，很容易确定图中任意两个顶点之间是否有边相测，所花费的时间代价很大。这是用邻接矩阵图的局限性。稠密图适合用邻接矩阵的22、邻接表是图的一方法，类似n个顶点、条边，则它的邻接表需个头结点和2个表结点。稀疏图用邻接表表示比邻接矩阵节省多时更是如此。（i和j）i个或第j例a例abcd111^ ^344 4 4 ^13c链34^^例例abcde441a121^4^2b3c32344d5e52^3^5^[[题 n个顶点的无向图的邻接表中边表结点总数最多有 ） D.n(n-解答：D1、图的遍历通常有深度优先搜索和广度优先搜索两种（1）①递归算法②非 先搜索遍历图的时间复杂度为O(n+e)。深度优先搜索遍点的顺序不同。 解答：B[[题2]假设图G，设计一个算法，输出图G。由于在搜索过程中，每个顶点只voidvoidPathAll(ALGraph*G,intu,intv,intk,intpath[],intintm,i; ode*p; 路径长度加 if(u==v&&d==k)for(i=0;i<=d;i++)printf(path[i]);//输出一条路径 arc;//p指向顶点u的第一条弧的弧头结点while if(visited[m]==0) p->nextarc;}} 3、克鲁 （Kruskal）算法的基本思 A.G是G的连通分 B.G是G的无环子C.G’是G的子 G’是G的极小连通子图且解答：A1、拓扑有序序列是AOV网G中的顶点所构成的有序序列1,…,i,…,n），33、对AOV网进行拓扑排序的方法。 A．深度优先遍 B．广度优先遍C．求最短路 D．求关键路理由是：设整个图G的度之和为N，则N≥2n，又因为图中边数，因此图G至少有n条边因为多于n-1条边的图中必然存在回路，所以图G解答：A[[题2]已知带权图G＝（V，E），其中 ＝{<v1，v2>，<v1，v4>，<v2，v6>，<v3，v1>，<，<v5，v2>，<v5，v6>},G的拓扑序列是（）。 二二十一、求AOV网中所有事件的最早发生时间求AOV网中所有事件的最迟发生时间求AOV网中所有活动的最早发生时间求AOV网中所有活动的最迟发生时间（5）求AOV网中所有活动的事件余量 ；- （6）找出所有 )为0的活动构成的关键路径,ve(源点ve(k)=Max{ve(j)+dut(<j,vl(汇点)=ve(汇点vl(j)=Min{vl(k)–dut(<j,e[i]=l[i]的活动就是关键活动，关键活动所在的路径就是关[[题1]下面关于关键路径的问题中说法正确的是（）A．仅Ⅰ和IIB．仅Ⅰ和IIIC．仅ⅠD．仅III解答：D二十二、二十二、法的时间复杂度也是O(n3)[[题1]下列说法不正确的是（）I求从指定源点到其余各顶点的Dijkstra最短路径算法中弧上权值可以为负值 IV求单源路径的Dijkstra算法不适合用于有回路的A.I、II、III、 B.I、 C.I、III、 D.II、分析：每次以一个顶点为源点，重复利用Dijkstr算法n次求得每一对不同顶点n3)，因此I正确；而最短路径算法要求弧、III错误；Dijkstr算法可用于有回路的有向网，例如知识点聚焦22的例题1中就是有回路的有向网解答：C二十三、二十三、顺序查找算法的时间复杂度为O(n)。它的缺点是当n，平均查找长度较大，效率低；优点是表的结构是顺。 44、分块查找分块查找法要求将列表组织成以下索引顺序块的长度均匀，最后一块可以不满。每块中元素任意排例如例如顺序 索索引顺序214078定表中每个元素的查找概率相等，则每个索引项的查找概率为1/b，块将将typedefstructnode{intA[m]；structnode*next;//指向下一结点的指针typedefstruct{intj; LNode*s;

n){rcd*R;while&&!found){forifp->A[j]=nfound=1;//p=p-if(p==NULL)returnNULL;else{ R.j=i;return}}[[题2]顺的某线性表共有123个元素，按分块查找等分为3块。若对索引表采用顺序查找方法来确定子块在确定的子块中也采用顺序查找方，分块查找成功的平均查概率况B.C.D.解答二十四、二十四、B‐树与B+1、一棵m阶的B-树，或者为空树，或为满足下列特性的m⑴树中每个结点至多有m⑶除根结点之外的所有非终端结点至少有m/2Kii=12…n)，An所指子树中所有结点的关键码均大于Kn，m/222、B-树的基本（1）查点的路径上涉及的结点数不超过B-关键字而得。但由于B-结点中的关键字个数必须大于等于m/21一个关键字不是在树中添加一个叶子结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m1（3）在B-完成，否则要产生结点的”33、一棵m阶的B+树和m阶的B-树的差有n棵子树的结点中含有n个关键 [[题1]下面关于m阶B-树说法正确的是（） IV 一个数据引起B-树结A．I、II、 B．II、C．II、III、 [[题2]下面关于B-树和B+树的叙述中，不正确的是（）B．B树和B+树都可用于文件的索引结构到大地顺序，所以支持从根结点的随机检索和直接从叶子结点二十五、二十五、 ”现象，即：key1，而f(key1f(key2)H(key)=keyMOD Hi=H +diMOD1≤i<m其中：di1，2，……，m-1，且di=i ②二次探测法 Hi=(H(key)±di)MOD其中：di为增量序列12，-12，22，-22，……，q2，-q2且q≤m/2。 种方法中，散列表每个单元存放的不再是记录本身，而是相应同义44，但找到位置的平均探查次数，它是表中所有可能散列到的位置上要新元素时为找到空位置的探查次数的平均[[题1]下列有关散列查找的叙述正确的是（） D.若散列表的装填因子α<<1，则可避 的产 ，所以选项A正确；散列是指多个不同关键字对应相，选项B错误；用线性探测法解决的散列表中，散列函数值相同的关键字不一定总是存放在一片连续的单元中，选项C错误；装填因子α越小，发生的概率越小，但仍有可能发生。解答：A[[题2]散列表的平均查找长度） 解答：A[[题3]采用散列函数H(k)=3×kMOD13并用线性探测开放地 构造散列表（画示意图装填因等概率情况下查找失败的平均查找长度[[题 已知一组关键字为列函数的形式为Hke =keyMODp，回答下列问题：分析：本题是对散列表的一种常见考查方式。采用链地址，查找成功表示找到了关键字集合中的某记录的比较次数，查找不成功表示在散列表中未找到指定关键字的记录的比较次数。首首先，回忆一下串匹配(查找)的定义INDEX(S,T,初始条件：ST存在，T1≤pos≤StrLength(S)操作结果：若主串S中存在和串T值相同的Spos个字符之后第一次出现的位置;否则函数值为0。intintIndex(StringS,StringT,intpos)回第一个这样的子串在S中的位置，否则返回0if(pos>0)n=StrLength(S);m=StrLength(T);i=while(i<=n-m+1)SubString(sub,S,i,if pare(sub,T)!=0)++ielse}//}//return }//J.H.Morris)算法intintIndex(SStringS,SStringT,intpos)//其中，T非空，1≤pos≤StrLenthSi=pos;j=while(i<=S[0]&&j<=T[0])if(S[i]T[j])++i;++j}elseii-j+2;j1}if(j>T[0])returni-elsereturn}//二、二、首尾匹配算n-1intintIndex_FL(SStringS,SStringT,intpos)sLength=S[0];tLength=T[0];i=pos;patStartChar=T[1];patEndChar=while(i<=sLength–tLength+1)if(S[i]patStartChar++i;//elseif(S[i+tLength-1]!=patEndChar)else}return}三三、KMP(D.E.KnuthV.R.Pratt,J.H.MorrisKMP算法的时间复杂度可以达到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-定义：定义：模式串的next[[题1]串‘ababaaababaa’的next数组为 intintIndex_KMP(SStringS,SStringT,intpos)//1≤pos≤StrLength(S)i=pos;j=1;while(i<=S[0]&&j<=T[0])if(j=0||S[i]==T[j]){++i;++j;elsej if(jT[0])returni- elsereturn}/