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

《天大15秋季《数据结构》在线作业二答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《数据结构》在线作业二一、单选题（共40道试题，共100分。）1.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。.n.（n-1）的平方.n-1.n的平方正确答案：2.对于一个有向图，若一个顶点的入度为kl，、出度为k2,则对应逆邻接表中该顶点单链表屮的结点数为（）。.kl.k2.kl-k2.kl+k2正确答案.•3.顺序查找法适合于存储结构为（）的线性表。.散列存储.顺序存储或链接存储.压缩存储.索引存储正确答案：4.下述几种排序方法中，平均查找长度最小的是（）。.插入排序.选择排序.快速排序.归并排序正确答案：5.树最适合用來表示（）。.有序数据元素.无

2、序数据元素.元素之间具有分支层次关系的数据.元素之间无联系的数据正确答案：6.有8个结点的无向图最多有（）条边。.14.28.56.112正确答案.•1.有一个有序表为{1，3，9，12,32,41,45，62,75,77,82，95，100},当二分查找值82为的结点吋，（）次比较后查找成功。.1.2.4.8正确答案：2.设哈希表长m=14,哈希函数H（ky）=ky%ll。表中己有4个结点：r（15）=4;r（38）=5;r（61）=6;r（84）=7,如用二次探测再散列处理冲突，关键字为49的结点的地址是（）。.8.3.5.9正确答案：3.在一个阁屮，所有顶点的度数之和等于所有

3、边数的（）倍。.1/2.1.2.4正确答案.•4.一组记录的关键码为（46,79，56，38，40，84）,则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。38,40,46,56,79,8440,38,46,79,56,8440,38,46,56,79,8440,38,46,84,56,79正确答案：5.在一个具有n个顶点的无向图中，要连通全部顶点至少耑要（）条边。.n.n+1.n-1.n/2正确答案：6.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。.求关键路径的方法.求最短路径的ijkstr方法.宽度优先遍历算法.深度优先遍历算法正确答

4、案：7.下而不正确的说法是（）。.在0网中，减小一个关键活动上的权值后，整个工期也就相应减小.0网工程工期为关键活动上的权之和.在关键路径上的活动都是关键活动，而关键活动也必在关键路径上.以上都不对正确答案：1.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。.1/2.1.2.4正确答案：2.对线性表进行二分查找时，要求线性表必须（）。.以顺序方式存储.以链接方式存储.以顺序方式存储，且结点按关键字有序排序.以链接方式存储，且结点按关键字有序排序正确答案：3.对于一个具有n个顶点和条边的无向图，若采用邻接表表示，则所有邻接表中的接点总数是（）。./2.2.n+正确

5、答案.•4.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。.0（n2）.0（nlog2n）.0（n）.0（log2n）正确答案：5.—个有n个顶点的无向连通图，它所包含的连通分量个数为（）。.0.1.n.n+1正确答案：6.对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（）。.静态查找表.动态查找表.静态查找表与动态查找表.两种表都不适合正确答案：7.把一棵树转换为二叉树后，这棵二叉树的形态是（）。.唯一的.有多种.有多种，但根结点都没有左孩子.有多种，但根结点都没有右孩子正确答案：1.对于一个有向图，若一个

6、顶点的入度为kl,、出度为k2,则对应邻接表中该顶点单链表中的结点数为（）。.kl.k2.kl-k2.kl+k2正确答案：2.一组记录的排序码为（46,79,56,38,40,84）,则利用堆排序的方法建立的初始堆(),079,46,56,38,40,8038,46,:56,79,40,84,84,79,56,46,40,3884,56,79,40,46,38正确答案.•3.堆的形状是一棵（）。.二叉排序树.满二叉树.完全二叉树.平衡二叉树正确答案：4.快速排序方法在（）情况下最不利于发挥其长处。.要排序的数据量太大.要排序的数据中含有多个相同值.要排序的数据己基本有序.要排序的数

7、据个数为奇数正确答案：5.一组记录的排序码为（25,48，16,35，79,82,23,40,36,72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（）。16,25,35,48,23,40,79,82,36,7216,25,35,48,79,82,23,36,40,7216,25,48,35,79,82,23,36,40,7216,25,35,48,79,23,36,40,72,82正确答案：6.采用顺序查找方法查找长度为n的线性表