《数据结构复习神卷》由会员分享，可在线阅读，更多相关《数据结构复习神卷（51页珍藏版）》请在金锄头文库上搜索。
1、习题课3图、查找、内部排序图、查找、内部排序若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵_。A.第i行中值为1的元素个数B.所有值为1的元素个数C.第i行及第i列中值为1的总个数D.第i列中值为1的元素个数由由邻接矩接矩阵的定的定义可知，可知，对于无向于无向图，其，其邻接矩接矩阵第第i行元素的和即行元素的和即为顶点点i的度，的度，对于有向于有向图，其，其邻接矩接矩阵的第的第i行元素之和行元素之和为顶点点i的出度，而的出度，而邻接矩接矩阵的第的第i列列元素之和元素之和为顶点点i的入度的入度设一个包含N个顶点、E条边的简单有向图采用邻接矩阵存储结构（矩阵元素Aij等于1/0分别
2、表示顶点i与顶点j之间有/无弧），则该矩阵的元素数目为_,其中非零元素数目为_。A.E2B.N2C.N2-E2 D.N2+E2A.N B.N+E C.ED.NE采用邻接表表示一有向图，若图中某顶点的入度和出度分别为d1和d2，则该顶点对应的单链表的结点数为（）A.d1B.d2C.d1-d2D.d1+d2求单源点最短路径的迪杰斯特拉(Dijkstra)算法是按_的顺序求源点到各顶点的最短路径的A.路径长度递减B.路径长度递增C.顶点编号递减D.顶点编号递增kruskal算法的时间复杂度为（），它对（）图较为适合。Prim算法的时间复杂度为（），它对（）图较为适合。O(eloge)(n是顶点数、e
3、是边数)边稀疏O(n*n)边稠密求解每对结点之间的最短路径问题时，设有向图G=共有n个结点，结点编号1n，设C是G的成本邻接矩阵，用Dk(i,j)即为图G中结点i到j并且不经过编号比k还大的结点的最短路径的长度（Dn(i,j)即为图G中结点i到j的最短路径长度），则求解该问题的递推关系式为_ADk(i,j)=Dk-1(i,j)+C(i,j)BDk(i,j)=minDk-1(i,j),Dk-1(i,j)+C(i,j)CDk(i,j)=Dk-1(i,k)+Dk-1(k,j)DDk(i,j)=minDk-1(i,j),Dk-1(i,k)+Dk-1(k,j)有向图G=(V,A)，其中V=a,b,c,d
4、,e，A=,，对该图进行拓扑排序，下面序列中哪一个不是拓扑序列A.a,d,c,b,eB.d,a,b,c,eC.a,b,d,c,eD.a,b,c,e,d试述一种判定有向图G中是否有圈（回路）的方法拓扑序列算法对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_。A、nB、n+1C、n-1D、n+e拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定_。A.包含回路B.是强连通图C.是完全图D.是有向树判断题不是所有的不是所有的A
5、OV网都有一个拓扑序列网都有一个拓扑序列正确每个加权连通无向图的最小生成树都是惟一的每个加权连通无向图的最小生成树都是惟一的错误拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，_为图中所示有向图的一个拓扑序列。A.1234567B.1526374C.5126347D.51237641234567一个加权连通无向图的最小生成树可以使用（）生成；一项过程完工所需的最少时间等于某个（）A.Hash算法B.Dijkstra算法C.Prim算法D.Huffman算法A.AOE网中源点到汇点事件最多的路径的长度B.AOE网中源点到汇点的最长路径的长度C
6、.AOE网中源点到汇点的最短路径的长度D.AOE网中源点到汇点活动最多的路径的长度在活动图中，结点表示项目中各个工作阶段的里程碑，连接各个结点的边表示活动，边上的数字表示活动持续的时间。在下面的活动图中，从A到J的关键路径是_(16)_，关键路径长度是_(17)_，从E开始的活动启动的最早时间是_(18)_。(16)A.ABEGJB.ADFHJC.ACFGJD.ADFIJ(17)A.22B.49C.19D.35(18)A.10B.12C.13D.15 某工程计划图如下图所示，弧上的标记为作业编码及其需要的完成时间（天），作业E最迟应在第_天开始。A.7B.9C.12D.13某工程计划如下图所示
7、，各个作业所需的天数如下表所示，设该工程从第0天工，则该工程的最短工期是（）天，作业J最迟应在第（）天开工A.17B.18C.19D.20A.11B.13C.14D.16在11个元素的有序表A1.11中进行折半查找(low+high)/2)，查找元素A11时，被比较的元素的下标依次是_。A.6，8，10，11B.6，9，10，11C.6，7，9，11D.6，8，9，11结点数目为n的二叉查找树（二叉排序树）的最小高度为_、最大高度为_。A.nB.n/2C.log2nD.log2(n+1)A.nB.n/2C.log2nD.log2(n+1)构造一棵二叉排序树，对其进行前序遍历可得到如下元素下列：
8、50,45,35,15,40,46,65,75,70在平衡二叉树中，。A.任意结点的左、右子树结点数目相同B.任意结点的左、右子树高度相同C.任意结点的左右子树高度之差的绝对值不大于1D.不存在度为1的结点由元素序列（27,16,75,38,51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为2的结点）为_。A.27B.38C.51D.75下图所示平衡二叉树（树中任一结点的左右子树高度之差不超过1）中，结点A的右子树AR高度为h，结点B的左子树BL高度为h，结点C的左子树CL、右子树CR高度都为h-1。若在CR中插入一个结点并使得CR的高度增加1，则该二叉
9、树_A.以B为根的子二叉树变为不平衡B.以C为根的子二叉树变为不平衡C.以A为根的子二叉树变为不平衡D.仍然是平衡二叉树在存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。A.顺序（Sequence）B.链表（Link）C.索引（Index）D.散列（Hash）已知一个线性表（16,25,35,43,51,62,87,93），采用散列函数H(Key)=Keymod7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突（顺序地探查可用存储单元），则构造的哈希表为_，在该散列表上进行等概率成功查找的平均查找长度为_（为确定记录在查找表中的位置，需和给定关键字值进行比
10、较的次数的期望值为查找算法在查找成功时的平均查找长度）。A.(5*1+2+3+6)/8B.(5*1+2+3+6)/9C.(8*1)/8D.(8*1)/9设H(x)是一哈希函数，有K个不同的关键字（x1,x2,x3,xk）满足H(x1)=H(x2)=H(xk)，若用线性探测法将这K个关键字存入哈希表中，至少要探测（）次A.K-1B.KC.K+1D.K(k-1)/2x1计算hash值，找到自己的位置x2计算hash值，与x1冲突，向后再探测1次，共1次x3计算hash值，与x2冲突，向后再探测1次，向后与x1冲突，再探测1次，共2次。xk计算hash值，与xk-1冲突，向后再探测1次。向后与x1冲
11、突，再探测1次，共k-1次一共1+.+k-1=(1+k-1)*(k-1)/2=(k-1)k/2有关键字集合K=15,22,50,13,20,36,28,48,35,31,41,18采用散列存取，哈希表为HT0.14。设哈希函数H(K)=KMOD13，解决冲突采用开发定址法中的二次探测再散列的方法。试将K值填入HT表中，并把查找每个关键字所需比较次数m填入下表，并请计算出查找成功时的平均查找长度。已知一个线性表（38，25，74，63，52，48），假定采用散列函数h(key)=key%7计算散列地址，并散列存储在散列表A0.6中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平
12、均查找长度为_A.1.5B.1.7C.2.0D.2.3从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为（）A.插入排序B.选择排序C.希尔排序D.归并排序在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终的排序算法是（）A.冒泡排序B.基数排序C.快速排序D.归并排序请指出三个稳定和三个不稳定的内部排序方法基数排序、简单选择排序、插入排序、归并排序、冒泡排序快速排序、堆排序、希尔（Shell）排序快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少错误所需额外栈空间比堆排序所需空间要大若需在O(nlog2n)的时间
13、内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）A.快速排序B.堆排序C.归并排序D.直接插入排序如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快A.起泡排序B.快速排序C.Shell排序D.堆排序E.简单选择排序设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，在以下的排序方法中采用哪一种最好？为什么？A.快速排序B.归并排序C.堆排序D.基数排序E.Shell排序A可以每次对第一个子序列进行分割，直至子序列长度小于或等于10，若长度不足10，则对每两个子序列分割出相应长度的子序列即可。以关键字比较为基础的排序算法
14、在最坏情况下的计算时间下界为O(nlogn)。下列的排序算法中，最坏情况下计算时间可以达到O(nlogn)的是（）A.归并排序B.插入排序C.选择排序D.冒泡排序用冒泡排序的方法对n个记录进行排序，第一趟共要比较（）对元素。对n个数据进行排序，不稳定排序是（），快速排序是一种（），关键字序列（）是一个堆A.n-1B.n/2C.n+1D.nA.直接插入排序B.冒泡排序C.Shell排序D.归并排序A.插入排序B.交换排序C.枚举排序D.选择排序A.20,76,35,23,80,54B.20,54,23,80,35,76C.80,23,35,76,20,54D.20,35,23,80,54,76对
15、n个元素的数组进行_，其平均时间复杂度和最坏情况下的时间复杂度都是O(nlogn)A.希尔排序B.快速排序C.堆排序D.选择排序在最好和最坏最好和最坏情况下的时间复杂度均为O（nlogn）且稳定的排序方法是_A.基数排序B.快速排序C.堆排序D.归并排序若排序前后关键字相同的两个元素相对位置不变，则称该排序方法是稳定的。_排序是稳定的。A.归并B.快速C.希尔D.堆（60）在其最好情况下的算法时间复杂度为O(n)A.插入排序B.归并排序C.快速排序D.堆排序对于有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分序列，最好采用_(59)_，使用分治(DivideandConquer)策
16、略的是_(60)_算法(59)A.希尔排序B.直接插入排序C.快速排序D.堆排序(60)A.冒泡排序B.插入排序C.快速排序D.堆排序在堆排序过程中，由n个待排序的记录建成初始堆需要_次筛选。A、nB、n/2C、log2nD、n-1快速排序在_情况下最不利于发挥其长处。A、被排序的数据量很大B、被排序的数据已基本有序C、被排序的数据完全无序D、被排序的数据中最大的值与最小值相差不大。对n个元素的数组进行_,其平均时间复杂度和最坏情况下的时间复杂度都是O(nlogn)A.希尔排序B.快速排序C.堆排序D.选择排序已知已知长长度度为为12的表如下：的表如下：Jan,Feb,Mar,Apr,May,
17、June,July,Aug,Sep,Oct,Nov,Dec（1）建立相）建立相应应的二叉排序的二叉排序树树（2）建立相）建立相应应的平衡二叉的平衡二叉树树 知知识识要点：要点：平衡二叉平衡二叉树树又称又称AVL树树，是具有如下性，是具有如下性质质的二叉的二叉树树。树树中每个中每个结结点的左、右子点的左、右子树树深度之差的深度之差的绝对值绝对值不大于不大于1。vJan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, DecAprAugDecNovFebJanSepMayJuneJulyOctMarJan, Feb, Mar, Apr, M
18、ay, June, July, Aug, Sep, Oct, Nov, DecJanFebMarAprMayJuneJulyAugAugAprFebAugAprFebJanAugMarAprMayJuneJulyFebSepOctJan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, DecJanAugMarAprMayJuneJulyFebOctSepNovJan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, DecJanAugMarAprMayJuneJulyFebOctS
19、epNovJan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, DecJanAugMarAprMayJuneJulyFebOctSepNovDecJan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec若关键字是非负整数，则下列排序中平均速度最快的排序是（）；若要求辅助空间为O(1)，则平均速度最快的排序是（）；若要求排序是稳定的，且关键字为实数，则平均速度最快的排序是（）A.直接插入排序B.直接选择排序C.Shell排序D.冒泡排序E.快速排序F.堆排序G.归并排序H.基数排序HFG
