数据结构复习神卷学习教案.pptx

《数据结构复习神卷学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构复习神卷学习教案.pptx（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构(sh j ji u)复习神卷复习神卷第一页，共51页。n n若采用邻接矩阵来存储简单(jindn)有向图，则其某一个顶点i的入度等于该矩阵_。n nA.第i行中值为1的元素个数n nB.所有值为1的元素个数n nC.第i行及第i列中值为1的总个数n nD.第i列中值为1的元素个数由由邻接矩接矩阵的定的定义可知，可知，对于于(duy)无向无向图，其，其邻接接矩矩阵第第i行元素的和即行元素的和即为顶点点i的度，的度，对于于(duy)有向有向图，其，其邻接矩接矩阵的第的第i行元素之和行元素之和为顶点点i的出度，而的出度，而邻接矩接矩阵的第的第i列元素之和列元素之和为顶点点i

2、的入度的入度第1页/共51页第二页，共51页。n n设一个包含N个顶点、E条边的简单(jindn)有向图采用邻接矩阵存储结构（矩阵元素Aij等于1/0分别表示顶点i与顶点j之间有/无弧），则该矩阵的元素数目为_,其中非零元素数目为_。n nA.E2 B.N2 C.N2-E2 D.N2+E2 n nA.N B.N+E C.E D.NE第2页/共51页第三页，共51页。n n采用(ciyng)邻接表表示一有向图，若图中某顶点的入度和出度分别为d1和d2，则该顶点对应的单链表的结点数为（）n nA.d1 B.d2 n nC.d1-d2 D.d1+d2第3页/共51页第四页，共51页。n n求单源点最

3、短路径的迪杰斯特拉(Dijkstra)算法是按_的顺序(shnx)求源点到各顶点的最短路径的n nA.路径长度递减n nB.路径长度递增n nC.顶点编号递减n nD.顶点编号递增第4页/共51页第五页，共51页。n nkruskal算法的时间复杂度为（），它对（）图较为适合(shh)。n nPrim算法的时间复杂度为（），它对（）图较为适合(shh)。n nO(eloge)(n是顶点数、e是边数)n n边稀疏n nO(n*n)n n边稠密第5页/共51页第六页，共51页。n n 求解每对结点之间的最短路径问题时，设有向求解每对结点之间的最短路径问题时，设有向图图G=G=共有共有n n个结点，

4、结点编号个结点，结点编号1 1n n，设，设C C是是GG的成本的成本(chngbn)(chngbn)邻接矩阵，用邻接矩阵，用Dk(i,j)Dk(i,j)即为即为图图G G 中结点中结点i i到到j j并且不经过编号比并且不经过编号比k k还大的结点还大的结点的最短路径的长度（的最短路径的长度（Dn(i,j)Dn(i,j)即为图即为图GG中结点中结点i i到到j j的最短路径长度），则求解该问题的递推关系的最短路径长度），则求解该问题的递推关系式为式为_n nA ADk(i,j)=Dk-1(i,j)+C(i,j)Dk(i,j)=Dk-1(i,j)+C(i,j)n nB BDk(i,j)=min

5、Dk-1(i,j),Dk-1(i,j)+C(i,j)Dk(i,j)=minDk-1(i,j),Dk-1(i,j)+C(i,j)n nC CDk(i,j)=Dk-1(i,k)+Dk-1(k,j)Dk(i,j)=Dk-1(i,k)+Dk-1(k,j)n nDDDk(i,j)=minDk-1(i,j),Dk-1(i,k)+Dk-1(k,j)Dk(i,j)=minDk-1(i,j),Dk-1(i,k)+Dk-1(k,j)第6页/共51页第七页，共51页。n n有向图G=(V,A)，其中V=a,b,c,d,e，A=,，对该图进行(jnxng)拓扑排序，下面序列中哪一个不是拓扑序列n nA.a,d,c,b

6、,e B.d,a,b,c,e n nC.a,b,d,c,e D.a,b,c,e,dn n试述一种判定有向图G中是否有圈（回路）的方法n n拓扑序列算法第7页/共51页第八页，共51页。对于一个具有n个顶点和e条边的无向图，若采用邻接(ln ji)表表示，则表头向量的大小为_。A、n B、n+1 C、n-1 D、n+e第8页/共51页第九页，共51页。n n拓扑排序是指有向图中的所有顶点(dngdin)排成一个线性序列的过程，若在有向图中从顶点(dngdin)vi到vj有一条路径，则在该线性序列中，顶点(dngdin)vi必然在顶点(dngdin)vj之前。因此，若不能得到全部顶点(dngdin

7、)的拓扑排序序列，则说明该有向图一定_。n nA.包含回路 n nB.是强连通图 n nC.是完全图 n nD.是有向树第9页/共51页第十页，共51页。n n判断题n n不是所有的AOV网都有一个拓扑序列n n正确 n n每个加权连通无向图的最小生成树都是惟一(wiy)的n n错误第10页/共51页第十一页，共51页。n n拓扑序列是无环有向图中所有顶点(dngdin)的一个线性序列，图中任意路径中的各个顶点(dngdin)在该图的拓扑序列中保持先后关系，_为图中所示有向图的一个拓扑序列。n nA.1 2 3 4 5 6 7 B.1 5 2 6 3 7 4 n nC.5 1 2 6 3 4

8、7 D.5 1 2 3 7 6 41234567第11页/共51页第十二页，共51页。n n一个加权连通无向图的最小生成树可以使用（）生成；一项过程(guchng)完工所需的最少时间等于某个（）n nA.Hash算法 B.Dijkstra算法 n nC.Prim算法 D.Huffman算法n nA.AOE网中源点到汇点事件最多的路径的长度n nB.AOE网中源点到汇点的最长路径的长度n nC.AOE网中源点到汇点的最短路径的长度n nD.AOE网中源点到汇点活动最多的路径的长度第12页/共51页第十三页，共51页。n n n n在活动图中，结点表示项目中各个工作阶段在活动图中，结点表示项目中各

9、个工作阶段(jidun)(jidun)的里程碑，连接各个结点的边表示活动，边上的数字的里程碑，连接各个结点的边表示活动，边上的数字表示活动持续的时间。在下面的活动图中，从表示活动持续的时间。在下面的活动图中，从 A A 到到 J J 的关键路径是的关键路径是 _(16)_ _(16)_，关键路径长度是，关键路径长度是 _(17)_ _(17)_，从，从 E E 开始的活动启动的最早时间是开始的活动启动的最早时间是 _(18)_ _(18)_。(16)A.ABEGJB.ADFHJC.ACFGJD.ADFIJ(17)A.22B.49C.19D.35(18)A.10B.12C.13D.15第13页/

10、共51页第十四页，共51页。n n n n某工程计划图如下图所示，弧上的标记为作业编码及其需要的完成(wn chng)时间（天），作业E最迟应在第_天开始。n n A.7 B.9 n nC.12 D.13第14页/共51页第十五页，共51页。n n n n某工程某工程(gngchng)(gngchng)计划如下图所示，各个作业所需的计划如下图所示，各个作业所需的天数如下表所示，设该工程天数如下表所示，设该工程(gngchng)(gngchng)从第从第 0 0 天工，天工，则该工程则该工程(gngchng)(gngchng)的最短工期是的最短工期是 （）天，作业（）天，作业 J J 最最迟应在

11、第迟应在第 （）（）天开工天开工n nA.17A.17B.18B.18C.19 C.19 D.20D.20n nA.11A.11B.13B.13C.14 C.14 D.16D.16第15页/共51页第十六页，共51页。n n n n在11个元素的有序表A1.11中进行折半(zhbn)查找(low+high)/2)，查找元素A11时，被比较的元素的下标依次是_。n nA.6，8，10，11 B.6，9，10，11n nC.6，7，9，11 D.6，8，9，11第16页/共51页第十七页，共51页。n n n n结点数目为n 的二叉查找树（二叉排序(pi x)树）的最小高度为_、最大高度为_。n

12、nA.n B.n/2 C.log2n D.log2(n+1)n nA.n B.n/2 C.log2n D.log2(n+1)第17页/共51页第十八页，共51页。n n n n构造一棵二叉排序树，对其进行前序遍历可得到(d do)如下元素下列：n n50,45,35,15,40,46,65,75,70第18页/共51页第十九页，共51页。n n n n在平衡二叉树中，。n nA.任意结点(ji din)的左、右子树结点(ji din)数目相同n nB.任意结点(ji din)的左、右子树高度相同n nC.任意结点(ji din)的左右子树高度之差的绝对值不大于1n nD.不存在度为1的结点(j

13、i din)第19页/共51页第二十页，共51页。n n n n由元素序列（27,16,75,38,51）构造平衡二叉树，则首次出现(chxin)的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为 2 的结点）为 _。n nA.27 B.38 n nC.51 D.75第20页/共51页第二十一页，共51页。n n n n下图所示平衡二叉树（树中任一结点下图所示平衡二叉树（树中任一结点(ji di(ji di n)n)的左右子树高度的左右子树高度之差不超过之差不超过 1 1）中，结点）中，结点(ji di(ji di n)An)A的右子树的右子树 AR AR 高度为高度为 h h，结点结

14、点(ji di(ji di n)B n)B 的左子树的左子树 BL BL 高度为高度为 h h，结点，结点(ji di(ji di n)C n)C 的左的左子树子树 CL CL、右子树、右子树 CR CR高度都为高度都为 h-1 h-1。若在。若在 CR CR 中插入一个结点中插入一个结点(ji di(ji di n)n)并使得并使得 CR CR 的高度增加的高度增加 1 1，则该二叉树，则该二叉树 _ _ n nA.A.以以 B B 为根的子二叉树变为不平衡为根的子二叉树变为不平衡n nB.B.以以 C C 为根的子二叉树变为不平衡为根的子二叉树变为不平衡n nC.C.以以 A A 为根的子

15、二叉树变为不平衡为根的子二叉树变为不平衡n nD.D.仍然是平衡二叉树仍然是平衡二叉树第21页/共51页第二十二页，共51页。n n n n在 存储结构中，数据结构中元素的存储地址(dzh)与其关键字之间存在某种映射关系。n nA.顺序（Sequence）n nB.链表（Link）n nC.索引（Index）n nD.散列（Hash）第22页/共51页第二十三页，共51页。n n已知一个线性表（已知一个线性表（16,25,35,43,51,62,87,9316,25,35,43,51,62,87,93），采用散列函数），采用散列函数H(Key)=Key mod 7H(Key)=Key mod

16、7将元素散列到表长为将元素散列到表长为9 9的散列表中。若采用的散列表中。若采用线性探测的开放定址法解决冲突（顺序地探查可用存储单元）线性探测的开放定址法解决冲突（顺序地探查可用存储单元），则构造的哈希表为，则构造的哈希表为_，在该散列表上进行等概率，在该散列表上进行等概率成功成功(chnggng)(chnggng)查找的平均查找长度为查找的平均查找长度为_（为确定（为确定记录在查找表中的位置，需和给定关键字值进行比较的次数记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值为查找算法在查找成功的期望值为查找算法在查找成功(chnggng)(chnggng)时的平均查找长时的平均查找长

17、度）。度）。A.(5*1+2+3+6)/8B.(5*1+2+3+6)/9C.(8*1)/8D.(8*1)/9第23页/共51页第二十四页，共51页。n n n n设设H(x)H(x)是一哈希函数，有是一哈希函数，有K K个不同的关键字个不同的关键字（x1,x2,x3,xkx1,x2,x3,xk）满足）满足H(x1)=H(x2)=H(xk)H(x1)=H(x2)=H(xk)，若，若用线性探测法将这用线性探测法将这K K个关键字存入哈希表中，至少个关键字存入哈希表中，至少要探测（要探测（）次）次n nA.K-1 B.K C.K+1 D.K(k-1)/2A.K-1 B.K C.K+1 D.K(k-1

18、)/2n nx1x1计算计算hashhash值，找到自己的位置值，找到自己的位置n nx2x2计算计算hashhash值，与值，与x1x1冲突冲突(chngt)(chngt)，向后再探测，向后再探测1 1次，次，共共1 1次次n nx3x3计算计算hashhash值，与值，与x2x2冲突冲突(chngt)(chngt)，向后再探测，向后再探测1 1次，次，向后与向后与x1x1冲突冲突(chngt)(chngt)，再探测，再探测1 1次，共次，共2 2次次n n。n nxkxk计算计算hashhash值，与值，与xk-1xk-1冲突冲突(chngt)(chngt)，向后再探测，向后再探测1 1次

19、。向后与次。向后与x1x1冲突冲突(chngt)(chngt)，再探测，再探测1 1次，共次，共k-k-1 1次次n n一共一共1+.+k-1=(1+k-1)*(k-1)/2=(k-1)k/21+.+k-1=(1+k-1)*(k-1)/2=(k-1)k/2第24页/共51页第二十五页，共51页。n n有关键字集合有关键字集合K=15,22,50,13,20,36,28,48,35,31,41,18K=15,22,50,13,20,36,28,48,35,31,41,18采采用散列存取，哈希表为用散列存取，哈希表为HT0.14HT0.14。设哈希函数。设哈希函数H(K)=K MOD 13H(K)

20、=K MOD 13，解决冲突采用开发定址法中的二，解决冲突采用开发定址法中的二次探测再散列的方法。试将次探测再散列的方法。试将K K值填入值填入HTHT表中，并把查表中，并把查找找(ch zh(ch zh o)o)每个关键字所需比较次数每个关键字所需比较次数mm填入下表，填入下表，并请计算出查找并请计算出查找(ch zh(ch zh o)o)成功时的平均查找成功时的平均查找(ch(ch zhzh o)o)长度。长度。第25页/共51页第二十六页，共51页。n n已知一个线性表（38，25，74，63，52，48），假定采用散列函数h(key)=key%7计算散列地址，并散列存储在散列表A0.6

21、中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找(ch zho)的平均查找(ch zho)长度为_n nA.1.5B.1.7n nC.2.0D.2.3 第26页/共51页第二十七页，共51页。n n从未排序的序列(xli)中依次取出一个元素与已排序序列(xli)中的元素进行比较，然后将其放在已排序序列(xli)的合适位置上，该排序方法称为（）n nA.插入排序 n nB.选择排序 n nC.希尔排序 n nD.归并排序第27页/共51页第二十八页，共51页。n n在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终的排序算法(sun f)是（）n nA.冒泡排序 n nB

22、.基数排序 n nC.快速排序 n nD.归并排序第28页/共51页第二十九页，共51页。n n请指出三个稳定和三个不稳定的内部(nib)排序方法n n基数排序、简单选择排序、插入排序、归并排序、冒泡排序n n快速排序、堆排序、希尔（Shell）排序 第29页/共51页第三十页，共51页。n n快速排序的速度在所有排序方法中为最快，而且所需附加(fji)空间也最少n n错误 所需额外栈空间比堆排序所需空间要大n n若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）n nA.快速排序 B.堆排序 n nC.归并排序 D.直接插入排序第30页/共51页第

23、三十一页，共51页。n n如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快n nA.起泡(q po)排序 n nB.快速排序 n nC.Shell排序 n nD.堆排序 n nE.简单选择排序第31页/共51页第三十二页，共51页。n n设有设有10001000个无序的元素，希望用最快的速度挑选个无序的元素，希望用最快的速度挑选出其中前出其中前1010个最大的元素，在以下的排序方法中个最大的元素，在以下的排序方法中采用哪一种最好？为什么？采用哪一种最好？为什么？n nA.A.快速排序快速排序 B.B.归并排序归并排序 C.C.堆排序堆排序 D.D.基数排

24、序基数排序 E.ShellE.Shell排序排序n nA An n可以每次对第一个子序列进行分割，直至子序可以每次对第一个子序列进行分割，直至子序列长度小于或等于列长度小于或等于1010，若长度不足，若长度不足(bz)10(bz)10，则，则对每两个子序列分割出相应长度的子序列即可。对每两个子序列分割出相应长度的子序列即可。第32页/共51页第三十三页，共51页。n n以关键字比较为基础的排序算法在最坏情况下的计算(j sun)时间下界为O(nlogn)。下列的排序算法中，最坏情况下计算(j sun)时间可以达到O(nlogn)的是（）n nA.归并排序 n nB.插入排序 n nC.选择排序

25、 n nD.冒泡排序 第33页/共51页第三十四页，共51页。n n用冒泡排序的方法对用冒泡排序的方法对n n个记录进行排序，第一趟个记录进行排序，第一趟共要比较共要比较(b(b jio)jio)（）对元素。对）对元素。对n n个数据进行个数据进行排序，不稳定排序是（排序，不稳定排序是（），快速排序是一种），快速排序是一种（），关键字序列（），关键字序列（）是一个堆）是一个堆n nA.n-1 A.n-1 B.n/2 B.n/2 C.n+1 C.n+1 D.nD.nn nA.A.直接插入排序直接插入排序 B.B.冒泡排序冒泡排序 n nC.ShellC.Shell排序排序 D.D.归并排序归并排

26、序n nA.A.插入排序插入排序 B.B.交换排序交换排序 n nC.C.枚举排序枚举排序 D.D.选择排序选择排序n nA.20,76,35,23,80,54 A.20,76,35,23,80,54 B.20,54,23,80,35,76 B.20,54,23,80,35,76 C.80,23,35,76,20,54 C.80,23,35,76,20,54 D.20,35,23,80,54,76D.20,35,23,80,54,76第34页/共51页第三十五页，共51页。n n对n个元素的数组进行_，其平均时间复杂度和最坏情况(qngkung)下的时间复杂度都是 O(nlogn)n nA.希

27、尔排序n nB.快速排序n nC.堆排序n nD.选择排序第35页/共51页第三十六页，共51页。n n在最好和最坏情况下的时间复杂度均为O（nlogn）且稳定的排序方法(fngf)是_n nA.基数排序 B.快速排序 n nC.堆排序D.归并排序 第36页/共51页第三十七页，共51页。n n n n若排序前后关键字相同的两个元素相对位置不变，则称该排序方法是稳定(wndng)的。_ 排序是稳定(wndng)的。n nA.归并 B.快速 n nC.希尔 D.堆第37页/共51页第三十八页，共51页。n n n n（60）在其最好情况下的算法时间复杂度为n nO(n)n nA.插入排序(pi

28、x)n nB.归并排序(pi x)n nC.快速排序(pi x)n nD.堆排序(pi x)第38页/共51页第三十九页，共51页。n n n n对于有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分序列，最好采用_(59)_，使用分治(Divide and Conquer)策略的是_(60)_算法n n(59)A.希尔排序(pi x)B.直接插入排序(pi x)n n C.快速排序(pi x)D.堆排序(pi x)n n(60)A.冒泡排序(pi x)B.插入排序(pi x)n n C.快速排序(pi x)D.堆排序(pi x)第39页/共51页第四十页，共51页。n n在堆排序过

29、程中，由n个待排序的记录建成初始(ch sh)堆需要_次筛选。n n A、n B、n/2 C、log2n D、n-1第40页/共51页第四十一页，共51页。n n快速排序在_情况(qngkung)下最不利于发挥其长处。n n A、被排序的数据量很大 n n B、被排序的数据已基本有序n n C、被排序的数据完全无序 n n D、被排序的数据中最大的值与最小值相差不大。第41页/共51页第四十二页，共51页。n n n n对 n 个元素的数组进行 _,其平均时间复杂度和最坏情况下的时间复杂度都是 O(nlogn)n nA.希尔排序(pi x)B.快速排序(pi x)n nC.堆排序(pi x)D

30、.选择排序(pi x)第42页/共51页第四十三页，共51页。已知长度为12的表如下：Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec（1）建立相应的二叉排序(pi x)树（2）建立相应的平衡二叉树 知识要点：平衡二叉树又称AVL树，是具有如下性质的二叉树。树中每个结点的左、右子树深度之差的绝对值不大于1。第43页/共51页第四十四页，共51页。n nJan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,DecJan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec

31、AprAugDecNovFebJanSepMayJuneJulyOctMar第44页/共51页第四十五页，共51页。Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,DecJanFebMarAprMayJuneJulyAugAugAprFebAugAprFeb第45页/共51页第四十六页，共51页。JanAugMarAprMayJuneJulyFebSepOctJan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec第46页/共51页第四十七页，共51页。JanAugMarAprMayJuneJulyFebOc

32、tSepNovJan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec第47页/共51页第四十八页，共51页。JanAugMarAprMayJuneJulyFebOctSepNovJan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec第48页/共51页第四十九页，共51页。JanAugMarAprMayJuneJulyFebOctSepNovDecJan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec第49页/共51页第五十页，共51页。n n若关键字是非负整数，则

33、下列排序中平均速度最若关键字是非负整数，则下列排序中平均速度最快的排序是（快的排序是（）；若要求辅助空间为）；若要求辅助空间为O(1)O(1)，则，则平均速度最快的排序是（平均速度最快的排序是（）；若要求排序是稳）；若要求排序是稳定的，且关键字为实数，则平均速度最快的排序定的，且关键字为实数，则平均速度最快的排序是（是（）n nA.A.直接插入排序直接插入排序 B.B.直接选择直接选择(xu(xu nz)nz)排序排序 n nC.ShellC.Shell排序排序 D.D.冒泡排序冒泡排序n nE.E.快速排序快速排序 F.F.堆排序堆排序 n nG.G.归并排序归并排序 H.H.基数排序基数排序n nHHn nF Fn nGG第50页/共51页第五十一页，共51页。