202010月西工大课程考试《数据结构》答案

对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为()。R[0]，R[1]，R[2]，R[3]R[0]，R[13]，R[2]，R[3]R[6]，R[2]，R[4]，R[3]R[6]，R[4]，R[2]，R[3]答案：C若二叉树中度为2的结点有15个，度为1的结点有10个该树有()个叶结点。TOC\o"1-5"\h\z25303116答案：D下列排序算法中，()算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。堆排序冒泡排快速排序SHELL排序答案：C下列陈述中正确的是()。二叉树是度为2的有序树二叉树中结点只有一个孩子时无左右之分二叉树中必有度为2的结点二叉树中最多只有两棵子树，并且有左右之分设有向图有n个顶点和e条边，进行拓扑排序时总的计算时间为()。O(loge)O(en)O(elogn)O(n+e)答案：D散列表的平均查找长度()。与处理冲突方法有关而与表的长度无关与处理冲突方法无关而与表的长度有关与处理冲突方法有关且与表的长度有关与处理冲突方法无关且与表的长度无关答案：C快速排序算法在最好情况下的时间复杂度为()。O(n)O(nlog2n)O(n2)O(log2n)答案：A已知广义表a=((a,b,c),(d,e,f)),从a中取出原子e的运算是()。tail(head(a))b.head(tail(a))head(tail(tail(head(a))))head(tail(tail(a)))关键路径是事件结点网络中()。最短的回路最长的回路从开始结点到完成结点的最长路径从开始结点到完成结点的最短路径答案：B一个无向连通图的生成树是含有该连通图的全部顶点的()。极小连通子图极小子图极大连通子图极大子图答案：A设有向图有n个顶点和e条边，进行拓扑排序时总的计算时间为()。O(loge)O(en)O(elogn)O(ne)答案：D下列说法中不正确的是()。图的遍历过程中每一顶点仅被访问一次遍历图的基本方法有深度优先搜索和广度优先搜索两种图的深度优先搜索的方法不适用于有向图图的深度优先搜索是一个递归过程答案：C常采用下面几种方式解决散列法中出现的冲突问题()。数字分析法、除余法、平方取中法数字分析法、除余法、线性探测法数字分析法、线性探测法、多重散列法线性探测法、多重散列法、链地址法答案：D在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作()型调整以使其平衡。TOC\o"1-5"\h\zLLLRRLRR答案：B用一维数组存放的一棵完全二叉树ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列()。TOC\o"1-5"\h\zHIDJKEBLFGCAABCDEFGHIJKLHDIBJEKALFCGABCDEGFHJIKL答案：A散列表的平均查找长度()。与处理冲突方法有关而与表的长度无关与处理冲突方法无关而与表的长度有关与处理冲突方法有关且与表的长度有关与处理冲突方法无关且与表的长度无关关键路径是事件结点网络中（）。最短的回路最长的回路从开始结点到完成结点的最长路径从开始结点到完成结点的最短路径答案：C数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用（）排序算法最节省时间。堆排序希尔排序快速排序直接选择排序答案：A数据表A中有00个元素，如果仅要求求出其中最大的10个元素，则采用（）排序。堆排序希尔排序快速排序直接选择排序答案：A关键路径是事件结点网络中（）。最短的回路最长的回路从开始结点到完成结点的最长路径从开始结点到完成结点的最短路径一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为()。n*nn*(n+1)/2(n+1)*(n+1)/2(n-1)*n/2答案：B数据结构中，从逻辑上可以把数据结构分成()。动态结构和静态结构紧凑结构和非紧凑结构线性结构和非先性结构内部结构和外部结构答案：C二叉树在线索化后，仍不能有效求解的问题是()。先序线索二叉树中求先序后继中序线索二叉树中求中序后继中序线索二叉树中求中序前趋后序线索二叉树中求后序后继答案：D对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为()。R[0]，R[1]，R[2]，R[3]R[0]，R[13]，R[2]，R[3]R[6]，R[2]，R[4]，R[3]R[6]，R[4]，R[2]，R[3]快速排序算法在最好情况下的时间复杂度为()。TOC\o"1-5"\h\zO(n)O(nlog2n)O(n2)O(log2n)答案：A在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为()。e2en2-en2-2e答案：D广义表运算式tail[((a,b),(c,d))]的结果为()。TOC\o"1-5"\h\zc,d(c,d)((c,d))d,c答案：C若二叉树中度为2的结点有15个，度为1的结点有10个该树有()个结点。25303141对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为()。R[0]，R[1]，R[2]，R[3]R[0]，R[13]，R[2]，R[3]R[6]，R[2]，R[4]，R[3]R[6]，R[4]，R[2]，R[3]答案：C若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有()个结点。TOC\o"1-5"\h\z15161734答案：D对于单链表形式的队列，队空的条件是()。F=R=nullF=RF尹null且R=nullR-F=1答案：A深度为6的二叉树至多有结点数为()。TOC\o"1-5"\h\z16306331若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有()个结点。TOC\o"1-5"\h\z15161734答案：D在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该()。只有左子树上的所有结点只有左子树上的部分结点只有右子树上的所有结点只有右子树上的部分结点答案：A对有序表18，20，25，34，48，62，74，85用二分查找法查找85，所需的比较次数为()。TOC\o"1-5"\h\z1次2次3次4次答案：D树型结构最适合用来描述()。有序的数据元素无序的数据元素数据元素之间的具有层次关系的数据数据元素之间没有关系的数据设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主序，A11为第一个元素，其存储地址为1,每个元素占1个地址空间，则A82的地址为()。TOC\o"1-5"\h\z1330180答案：B常采用下面几种方式解决散列法中出现的冲突问题：()数字分析法、除余法、平方取中法数字分析法、除余法、线性探测法数字分析法、线性探测法、多重散列法线性探测法、多重散列法、链地址法答案：D有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主序，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为()。TOC\o"1-5"\h\z13331840答案：B计算机识别、存储和加工处理的对象被统称为()。数据数据元素数据结构数据类型线性表的顺序存储结构是一种()存取结构。随即存取顺序存取索引存取散列存取答案：A下述排序算法中，稳定的是()。直接选择排序表插入排序快速排序堆排序答案：B广义表运算式tail[((a,b),(c,d))]的结果为()。TOC\o"1-5"\h\zc,d(c,d)((c,d))d,c答案：C</p>下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(log2n)的是()。堆排序冒泡排直接选择排序快速排序对有序表18,20,25,34,48,62,74,85用二分查找法查找85，所需的比较次数为()。TOC\o"1-5"\h\z1次2次3次4次答案：D设有向图G中顶点数为n，图G最多有()条边。nn-1n*(n-1)/2n*(n-1)答案：D下面关于哈夫曼树的说法，不正确的是()。对应于一组权值构造出的哈夫曼树一般