西南交大网院数据结构第四次作业.docx

西南交大网院数据结构第4次作业 （注意：若有主观题目，请按照题目，离线完成，完成后纸质上交学习中心，记录成绩。在线只需提交客观题答案。)本次作业是本门课程本学期的第4次作业，注释如下： 一、单项选择题(只有一个选项正确，共28道小题)1.?在一个无向图中，所有顶点的度数之和等于所有边的【??? ?】倍。??(A)?1/2??(B)?1??(C)?2??(D)?4你选择的答案：?C??[正确]正确答案：C解答参考：2.?在一个有向图中，所有顶点的入度数之和等于所有顶点的出度之和的【?????】倍。??(A)?1/2??(B)?1??(C)?2??(D)?4你选择的答案：?B??[正确]正确答案：B解答参考：3.?一个有n个顶点的无向图最多有【???】条边。??(A)?n??(B)?n(n-1)??(C)?n(n-1)/2??(D)?2n你选择的答案：?C??[正确]正确答案：C解答参考：4.?具有4个顶点的无向完全图有【?】条边。??(A)?6??(B)?12??(C)?16??(D)?20你选择的答案：?A??[正确]正确答案：A解答参考：5.?具有6个顶点的无向图至少应有【?】条边才能确保是一个连通图。??(A)?5??(B)?6??(C)?7??(D)?8你选择的答案：?A??[正确]正确答案：A解答参考：6.?对某个无向图的邻接矩阵来说，【??】。??(A)?第i行上的非0元素个数等于第i列上非0元素个数??(B)?矩阵中非0元素个数等于图中的边数??(C)?第i行、第i列上非0元素个数等于顶点vi的度数??(D)?矩阵中非全0行的行数等于图中的顶点数你选择的答案：?A??[正确]正确答案：A解答参考：7.?顺序查找法适合于存储结构为【?】的查找表。??(A)?散列存储??(B)?顺序存储或链式存储??(C)?压缩存储??(D)?索引存储你选择的答案：?B??[正确]正确答案：B解答参考：8.?对查找表进行折半查找时，要求查找表必须【?】。??(A)?以顺序方式存储??(B)?以顺序方式存储，且结点按关键字有序排列??(C)?以链式方式存储??(D)?以链式方式存储，且结点按关键字有序排列你选择的答案：?[前面作业中已经做正确]??[正确]正确答案：B解答参考：9.?采用顺序查找法查找长度为n的查找表时，每个元素查找的平均查找长度为【?】。??(A)?n??(B)?n/2??(C)?(n+1)/2??(D)?(n-1)/2你选择的答案：?C??[正确]正确答案：C解答参考：10.?采用折半查找法查找长度为n的查找表时，每个元素查找的平均查找长度为【?】。??(A)?O(n2)??(B)?O(nlog2n)??(C)?O(n)??(D)?O(log2n)你选择的答案：?D??[正确]正确答案：D解答参考：11.?采用分块查找时，若查找表中有625个元素，查找每个元素的概率相同，假设对索引表和块都采用顺序查找，每块应分【??】个结点最佳。??(A)?10??(B)?25??(C)?6??(D)?625你选择的答案：?B??[正确]正确答案：B解答参考：12.?查找n个元素的有序表时，最有效的查找方法是【??】。??(A)?顺序查找??(B)?分块查找??(C)?折半查找??(D)?二叉排序树你选择的答案：?[前面作业中已经做正确]??[正确]正确答案：C解答参考：13.?如果要求一个查找表既能快速查找，又能适应动态变化的要求，可以采用【?】查找方法。??(A)?分块??(B)?顺序??(C)?折半??(D)?散列你选择的答案：?[前面作业中已经做正确]??[正确]正确答案：A解答参考：14.?在关键字随即分布的情况下，用二叉排序树的方法进行查找，其查找长度与【?】量级相当。??(A)?顺序查找??(B)?折半查找??(C)?分块查找??(D)?前三个都不正确你选择的答案：?B??[正确]正确答案：B解答参考：15.?查找效率最高的二叉排序树是【?】。??(A)?所有结点的左子树都为空的二叉排序树??(B)?所有结点的右子树都为空的二叉排序树??(C)