天大15秋季《数据结构》在线作业二答案

谋学网《数据结构》在线作业二一、单选题（共40道试题，共100分。）1.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。.n.(n-1)的平方.n-1.n的平方正确答案：2.对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为（）。.k1.k2.k1-k2.k1+k2正确答案：3.顺序查找法适合于存储结构为（）的线性表。.散列存储.顺序存储或链接存储.压缩存储.索引存储正确答案：4.下述几种排序方法中，平均查找长度最小的是（）。.插入排序.选择排序.快速排序.归并排序正确答案：5.树最适合用来表示（）。.有序数据元素.无序数据元素.元素之间具有分支层次关系的数据.元素之间无联系的数据正确答案：6.有8个结点的无向图最多有（）条边。.14.28.56谋学网正确答案：7.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，（）次比较后查找成功。.1.2.4.8正确答案：8.设哈希表长m=14，哈希函数H(ky)=ky%11。表中已有4个结点：r(15)=4;r(38)=5;r(61)=6;r(84)=7，如用二次探测再散列处理冲突，关键字为49的结点的地址是（）。.8.3.5.9正确答案：9.在一个图中，所有顶点的度数之和等于所有边数的（）倍。.1/2.1.2.4正确答案：10.一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。.38，40，46，56，79，84.40，38，46，79，56，84.40，38，46，56，79，84.40，38，46，84，56，79正确答案：11.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。.n.n+1.n-1.n/2正确答案：12.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。.求关键路径的方法.求最短路径的ijkstr方法.宽度优先遍历算法.深度优先遍历算法正确答案：13.下面不正确的说法是（）。.在O网中，减小一个关键活动上的权值后，整个工期也就相应减小谋学网网工程工期为关键活动上的权之和.在关键路径上的活动都是关键活动，而关键活动也必在关键路径上.以上都不对正确答案：14.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。.1/2.1.2.4正确答案：15.对线性表进行二分查找时，要求线性表必须（）。.以顺序方式存储.以链接方式存储.以顺序方式存储，且结点按关键字有序排序.以链接方式存储，且结点按关键字有序排序正确答案：16.对于一个具有n个顶点和条边的无向图，若采用邻接表表示，则所有邻接表中的接点总数是（）。./2..2.n+正确答案：17.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。.O（n2）.O(nlog2n).O(n).O(log2n)正确答案：18.一个有n个顶点的无向连通图，它所包含的连通分量个数为（）。.0.1.n.n+1正确答案：19.对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（）。.静态查找表.动态查找表.静态查找表与动态查找表.两种表都不适合正确答案：20.把一棵树转换为二叉树后，这棵二叉树的形态是（）。谋学网唯一的.有多种.有多种，但根结点都没有左孩子.有多种，但根结点都没有右孩子正确答案：21.对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为（）。.k1.k2.k1-k2.k1+k2正确答案：22.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。.79，46，56，38，40，80.38，46,56，79，40，84，.84，79，56，46，40，38.84，56，79，40，46，38正确答案：23.堆的形状是一棵（）。.二叉排序树.满二叉树.完全二叉树.平衡二叉树正确答案：24.快速排序方法在（）情况下最不利于发挥其长处。.要排序的数据量太大.要排序的数据中含有多个相同值.要排序的数据已基本有序.要排序的数据个数为奇数正确答案：25.一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（）。.16，25，35，48，23，40，79，82，36，72.16，25，35，48，79，82，23，36，40，72.16，25，48，35，79，82，23，36，40，72.16，25，35，48，79，23，36，40，72，82正确答案：26.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）..n.n/2.(n+1)/2.(n-1)/2谋学网正确答案：27.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。.希尔排序.起泡排序.插入排序.选择排序正确答案：28.任何一个无向连通图的最小生成树（）。.只有一棵.有一棵或多棵.一定有多棵.可能不存在正确答案：29.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）。.插入排序.选择排序.快速排序.归并排序正确答案：30.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。.先序遍历.中序遍历.后序遍历.按层遍历正确答案：31.关键路径是事件结点网络中（）。.从源点到汇点的最长路径.从源点到汇点的最短路径.最长的回路.最短的回路正确答案：32.解决散列法中出现的冲突问题常采用的方法是（）。.数字分析法、除余法、平方取中法.数字分析法、除余法、线性探测法.数字分析法、线性探测法、多重散列法.线性探测法、多重散列法、链地址法正确答案：33.散列表的平均查找长度（）。.与处理冲突方法有关而与表的长度无关.与处理冲突方法无关而与表的长度有关.与处理冲突方法有关而与表的长度有关.与处理冲突方法无关而与表的长度无关谋学网正确答案：34.一个有n个顶点的无向图最多有（）条边。.n.n(n-1).n(n-1)/2.2n正确答案：35.二叉树是非线性数据结构，所以（）。.它不能用顺序存储结构存储.它不能用链式存储结构存储.顺序存储结构和链式存储结构都能存储.顺序存储结构和链式存储结构都不能使用正确答案：36.对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为（）。.从第0个元素往后查找该数据元素.从第1个元素往后查找该数据元素.从第n个元素往开始前查找该数据元素.与查找顺序无关正确答案：37.用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：⑴25，84，21，47，15，27，68，35，20；⑵20，15，21，25，47，27，68，35，84；⑶15，20，21，25，35，27，47，68，84；⑷15，20，21，25，27，35，47，68，84。则所采用的排序方法是（）。.选择排序.希尔排序.归并排序.快速排序正确答案：38.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论（）是正确的。.树的先根遍历序列与其对应的二叉树的先序遍历序列相同.树的后根遍历序列与其对应的二叉树的后序遍历序列相同.树的先根遍历序列与其对应的二叉树的中序遍历序列相同.以上都不对正确答案：39.下述几种排序方法中，要求内存量最大的是（）。.插入排序.选择排序.快速排序.归并排序正确答案：40.具有4个顶点的无向完全图有（）条边。谋学网正确答案：