数据结构与算法(吴跃)习题.pptVIP

已知一有向图的邻接表存储结构如图所示。 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（） a.v1,v2,v3,v5.v4 b.v1,v2,v3,v4,v5 c.v1,v3,v4,v5,v2 d.v1,v4,v3,v5,v2 1 2 3 4 5 3 2 4 4 5 2 4 C 已知一有向图的邻接表存储结构如图所示。 根据有向图的广度优先遍历算法，从顶点v1出发，所得到的顶点序列是（） a.v1,v2,v3,v4,v5 b.v1,v3,v2,v4,v5 c.v1,v2,v3,v5,v4 dv1,v4,v3,v5,v2 1 2 3 4 5 3 2 4 4 5 2 4 B 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（） a 先序遍历 b中序遍历 c后序遍历 d按层遍历 采取邻接表存储的图的广度优先遍历算法类似于二叉树的（） a 先序遍历 b中序遍历 c后续遍历 d 按层遍历 A D 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。 A．栈 B. 队列 C. 树 D. 图 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。 A．栈 B. 队列 C. 树 D. 图 B A 判定一个有向图是否存在回路除了可以利用拓扑排序方法之外，还可以利用（） a求关键路径的方法 b 求最短路径的dijkstra方法 C广度优先遍历法 d深度优先遍历法 任何一个无向连通图的最小生成树（ ） A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 D B 在无权图G的邻接矩阵A中，若（vi,vj）或vi,vj属于图G的边集合，则对应元素A[i][j]等于（）否则等于（） 已知一个图用邻接矩阵表示，计算第i个结点的入度的方法是_____________删除所有从第i个结点出发的边的方法是___________ 1 0 第i列非零元素之和 将矩阵第i行全部置为零 如果n个顶点的图是一个环，则它有 ____棵生成树。 n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为_______。 n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 。 设有一稀疏图G，则G采用 存储较省空间。 设有一稠密图G，则G采用 存储较省空间。 n O(n2) O(n+e) 邻接表 邻接矩阵 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 的次序来得到最短路径的。 拓扑排序算法是通过重复选择具有 个前驱顶点的过程来完成的 递增 0 在数据的存放无规律而言的线性表中进行检索的最佳方法是__________ 顺序查找法适合于存储结构为（）的线性表 a散列存储 b顺序存储或链接存储 c压缩存储 d索引存储 对线性表进行二分查找时，要求线性表必须（） a以顺序方式存储 b 以链接方式存储 c以顺序方式存储，且结点按关键字有序排序 d以链接方式存储，且结点按关键字有序排序 顺序查找 b C 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（） a. n b. n/2 c (n+1)/2 d .(n-1)/2 采用二分法查找长度为n的线性表时，每个元素的平均查找长度为（） a .O(n2) b O(nlog2n) c O(n) d O(log2n) 二分法查找和二叉排序树的时间性能（） a 相同 b不相同 C d b 有一个有序表为(n=13) {1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值82为的结点时（）次比较后查找成功 a 1 b 2 c 4 d 8 设哈希表长m＝14，哈希函数H（key）＝key％11。表中已有4个结点： addr（15）＝4 addr（38）＝5 addr（61）＝6 addr（84）＝7 其余地址为空,如用二次探测再散列处理冲突，关键字为49的结点的地址是（） a 8 b3 c5 d9 C d 有一个长度为12的有序表，按二分查找发对该表进行查找，在表内个元素等概率情况下查找成功所需的平均比较次数为（） a 35/12 b 37/12 c 39/