12_2017数据结构(第2版)_在线作业_4.docx

数据结构(第2版)_在线作业_4一、单选题1.(5分)一个加权连通无向图的最小生成树可以用（?）算法生成。?A.?Hash算法?B.?Prim算法?C.?Huffman算法?D.?Dijkstra算法纠错得分：?5知识点：?5.1 图的基本术语与定义展开解析2.(5分)在一个具有n个顶点的有向完全图中，含有边的总数为（?）。?A.?n(n+1)/2?B.?n?C.?n(n-1)?D.?n(n-1)/2纠错得分：?5知识点：?5.1 图的基本术语与定义展开解析3.(5分)下面（?）的时间复杂度最好。?A.?O(n)?B.?O(n2)?C.?O(lg(n))?D.?O(nlg(n))纠错得分：?5知识点：?1.3 C程序与例题展开解析4.(5分)给定关键字序列{6,3,8,4,2,9,7,1,5,12}，应用排序二叉树建立索引，查找任意数据最高的数据比较判定次数不会超过（?）次。?A.?10?B.?5?C.?6?D.?4纠错得分：?5知识点：?6.2 查找算法展开解析5.(5分)在规定顺序循环队列一般状态队首指针指向第一个数据元素之前的空位，队尾指针指向末尾元素的前提下，从一个顺序循环队列中出队元素时，首先需要（?）。?A.?取出队尾指针指定的元素?B.?后移队首指针?C.?前移队首指针?D.?取出队首指针指定的元素纠错得分：?5知识点：?3.1 顺序存储结构队列展开解析6.(5分)带头结点的链表L为空的判定条件为（?）。?A.?L==NULL?B.?L！=NULL?C.?L-next==NULL?D.?L-next==L纠错得分：?5知识点：?2.3 链接存储结构线性表展开解析7.(5分)两个具有n结点的（n1）二叉树的先序遍历序列和后序遍历序列的结点顺序正好相反，则该二叉树除叶子结点外，每个结点（?）。?A.?都有左右两个子树?B.?仅有一个子树?C.?仅有右子树?D.?仅有左子树纠错得分：?5知识点：?4.2 二叉树展开解析8.(5分)已知带权无向图如下，该图最小生成树中各边上的权值之和为（?）。??A.?43?B.?31?C.?36?D.?38纠错得分：?5知识点：?5.1 图的基本术语与定义展开解析9.(5分)下列数据序列对中，（?）是进行一趟快速排序的结果。?A.?{36,10,81},85,{30,50,92,95}?B.?{30,50,36,10},85,{92,81,95}?C.?{50,36,10,81},85,{30,92,95}?D.?{30,50,36,10,81},85,{92,95}纠错得分：?5知识点：?7.4 快速排序展开解析10.(5分)对下图从顶点a出发进行深度优先遍历，不可能的深度优先遍历结点序列为（?）。??A.?adefbc?B.?adcefb?C.?adbefc?D.?adcbfe纠错得分：?5知识点：?5.3 图的遍历展开解析11.(5分)下述编码中不是前缀编码的是（?）。?A.?{1,01,000,001}?B.?{0,10,110,111}?C.?{0,01,00,11}?D.?{00,01,10,11}纠错得分：?5知识点：?4.1 树的基本概念展开解析12.(5分)线性表是（?）。?A.?一个有限序列，可以为空?B.?一个无限序列，可以为空?C.?一个有限序列，不能为空?D.?一个无限序列，不能为空纠错得分：?5知识点：?2.2 顺序存储结构线性表展开解析13.(5分)设链表中指针p指向结点ai，指针q指向将要插入的新结点x，若要将新结点插入到ai与ai+1之间，所需要进行的操作顺序为（?），（?）。?A.?q-next=NULL，p-next = q?B.?q-next=p-next，p-next =p-next-next?C.?q-next=p-next，p-next = q?D.?q-next=p，p-next = q纠错得分：?5知识点：?2.3 链接存储结构线性表展开解析14.(5分)利用3,6,8,12,5,7作为叶子结点的权重，生成一棵Huffman树，该树的深度为（?）。?A.?3?B.?4?C.?6?D.?5纠错得分：?5知识点：?4.4 Huffman树及应用展开解析15.(5分)设有数据逻辑结构为：line=(D,R);?D={d1,d2,d3,d4,d5,d6,d7,d8,d9,d10}?R={d5,d1,d1,d3,d3,d8,d8,d2,d2,d7,d7,d4,d4,d6,d6,d9,d9,d10}?试分析该数据结构属于哪种逻辑结构？（?）?A.?线型逻辑结构?B.?网络结构?C.?非线性逻辑结构?D.?树结构纠错得分：?5知识点：?1.2 基本概念和术语展开解析16.(5分)判断下列程序段的时间复杂度数量级（?）。for(i=1;in;i++)?