数据结构复习神卷

《数据结构复习神卷》由会员分享，可在线阅读，更多相关《数据结构复习神卷（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分别表示顶点i与顶点j之间有/无弧），则该矩阵的元素数目为_, 其中非零元素数目为_ 。A. E2 B. N2 C. N2-

2、E2 D. N2+E2 A. N B. N+E C. E D. NE,采用邻接表表示一有向图，若图中某顶点的入度和出度分别为d1和d2，则该顶点对应的单链表的结点数为（ ）A.d1 B.d2 C.d1-d2 D.d1+d2,求单源点最短路径的迪杰斯特拉(Dijkstra)算法是按_的顺序求源点到各顶点的最短路径的A. 路径长度递减B. 路径长度递增C. 顶点编号递减D. 顶点编号递增,kruskal算法的时间复杂度为（ ），它对（ ）图较为适合。Prim算法的时间复杂度为（ ），它对（ ）图较为适合。O(eloge) (n是顶点数、e是边数)边稀疏O(n*n)边稠密,求解每对结点之间的最短路径

3、问题时，设有向图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,e，A=,，对该图进行拓扑排序，下面序列中哪一

4、个不是拓扑序列A.a,d,c,b,e B.d,a,b,c,e C.a,b,d,c,e D.a,b,c,e,d试述一种判定有向图G中是否有圈（回路）的方法拓扑序列算法,对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_。 A、n B、n+1 C、n-1 D、n+e,拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定_。A. 包含回路 B. 是强连通图 C. 是完全图 D. 是有向树,判断题不是所有的AOV网都有一个拓扑序列正

5、确 每个加权连通无向图的最小生成树都是惟一的错误,拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，_为图中所示有向图的一个拓扑序列。A. 1 2 3 4 5 6 7 B . 1 5 2 6 3 7 4 C. 5 1 2 6 3 4 7 D. 5 1 2 3 7 6 4,一个加权连通无向图的最小生成树可以使用（ ）生成；一项过程完工所需的最少时间等于某个（ ）A.Hash算法 B.Dijkstra算法 C.Prim算法 D.Huffman算法A.AOE网中源点到汇点事件最多的路径的长度B.AOE网中源点到汇点的最长路径的长度C.AOE网中源点

6、到汇点的最短路径的长度D.AOE网中源点到汇点活动最多的路径的长度,在活动图中，结点表示项目中各个工作阶段的里程碑，连接各个结点的边表示活动，边上的数字表示活动持续的时间。在下面的活动图中，从 A 到 J 的关键路径是 _ (16) _ ，关键路径长度是 _(17) _ ，从 E 开始的活动启动的最早时间是 _(18) _ 。,A.ABEGJ B.ADFHJ C.ACFGJ D.ADFIJ,A.22 B.49 C.19 D.35,A.10 B.12 C.13 D.15,某工程计划图如下图所示，弧上的标记为作业编码及其需要的完成时间（天），作业E最迟应在第_天开始。 A. 7 B. 9 C. 1

7、2 D. 13,某工程计划如下图所示，各个作业所需的天数如下表所示，设该工程从第 0 天工，则该工程的最短工期是 （）天，作业 J 最迟应在第 （） 天开工A. 17B. 18C.19 D.20A. 11B. 13C.14 D.16,在11个元素的有序表A1.11中进行折半查找(low+high)/2)，查找元素A11时，被比较的元素的下标依次是_。A. 6，8，10，11 B. 6，9，10，11C.6，7，9，11 D. 6，8，9，11,结点数目为n 的二叉查找树（二叉排序树）的最小高度为_、最大高度为_。A. n B. n/2 C. log2n D. log2(n+1)A. n B.

8、n/2 C. log2n D. log2(n+1),构造一棵二叉排序树，对其进行前序遍历可得到如下元素下列：50,45,35,15,40,46,65,75,70,在平衡二叉树中， 。A. 任意结点的左、右子树结点数目相同B. 任意结点的左、右子树高度相同C. 任意结点的左右子树高度之差的绝对值不大于1D. 不存在度为1的结点,由元素序列（ 27,16,75,38,51 ）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为 2 的结点）为 _ 。 A.27 B.38 C.51 D.75,下图所示平衡二叉树（树中任一结点的左右子树高度之差不超过 1）中，结点A的右

9、子树 AR 高度为 h，结点 B 的左子树 BL 高度为 h，结点 C 的左子树 CL、右子树 CR高度都为 h-1。若在 CR 中插入一个结点并使得 CR 的高度增加 1，则该二叉树 _ A. 以 B 为根的子二叉树变为不平衡B. 以 C 为根的子二叉树变为不平衡C. 以 A 为根的子二叉树变为不平衡D. 仍然是平衡二叉树,在 存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。A. 顺序（Sequence） B. 链表（Link） C. 索引（Index）D. 散列（Hash）,已知一个线性表（16, 25, 35, 43, 51, 62, 87, 93），采用散列函数H(

10、Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突（顺序地探查可用存储单元），则构造的哈希表为_，在该散列表上进行等概率成功查找的平均查找长度为_（为确定记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值为查找算法在查找成功时的平均查找长度）。,(5*1+2+3+6) / 8(5*1+2+3+6) / 9 (8*1) / 8 (8*1) / 9,设H(x)是一哈希函数，有K个不同的关键字（x1,x2,x3,xk）满足H(x1)=H(x2)=H(xk)，若用线性探测法将这K个关键字存入哈希表中，至少要探测（ ）次A.K-1 B.K C.K+1

11、 D.K(k-1)/2x1计算hash值，找到自己的位置x2计算hash值，与x1冲突，向后再探测1次，共1次x3计算hash值，与x2冲突，向后再探测1次，向后与x1冲突，再探测1次，共2次。xk计算hash值，与xk-1冲突，向后再探测1次。向后与x1冲突，再探测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)=K MOD 13，解决冲突采用开发定址法中的二次探测再散列的方法。试将K值填入HT表中，并把查找每个关键

12、字所需比较次数m填入下表，并请计算出查找成功时的平均查找长度。,已知一个线性表（38，25，74，63，52，48），假定采用散列函数h(key)=key%7计算散列地址，并散列存储在散列表A0.6中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为_A. 1.5B. 1.7C. 2.0D. 2.3,从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为（ ）A.插入排序 B.选择排序 C.希尔排序 D.归并排序,在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终的排序算法是（ ）A.冒泡排序 B.基

13、数排序 C.快速排序 D.归并排序,请指出三个稳定和三个不稳定的内部排序方法基数排序、简单选择排序、插入排序、归并排序、冒泡排序快速排序、堆排序、希尔（Shell）排序,快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少错误 所需额外栈空间比堆排序所需空间要大若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）A.快速排序 B.堆排序 C.归并排序 D.直接插入排序,如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快A.起泡排序 B.快速排序 C.Shell排序 D.堆排序 E.简单选择排序,设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，在以下的排序方法中采用哪一种最好？为什么？A.快速排序 B.归并排序 C.堆排序 D.基数排序 E.Shell排序A可以每次对第一个子序列进行分割，直至子序列长度小于或等于10，若长度不足10，则对每两个子序列分割出相应长度的子序列即可。,以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下列的排序算法中，最坏情况下计算时间可以达到O(nlogn)的是（ ）A.归并排序 B.插入排序 C.选择排序 D.冒泡排序,