20春学期《数据结构Ⅱ》在线平时作业3

20春学期数据结构在线平时作业3试卷总分:100 得分:100一、单选题 (共 20 道试题,共 100 分)1.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为A.DEFBCAB.DEBFCAC.DEBCFAD.DEBAFC答案:A2.下述哪一条是顺序存储结构的优点A.插入运算方便B.存储密度大C.可方便地用于各种逻辑结构的存储表示D.删除运算方便答案:B3.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为A.n-i+1B.n-iC.i-1D.i答案:A4.在线性表的下列运算中，不改变数据元素之间结构关系的运算是A.查找B.插入C.排序D.删除答案:A5.引入二叉线索树的目的是A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除答案:A6.快速排序在最坏情况下的时间复杂度是A.O(nlog2n)B.O(n2log2n)C.O(n2)D.O(log2n)答案:C7.在计算机内实现递归算法时所需的辅助数据结构是A.队列B.树C.栈D.图答案:C8.在一个带权连通图G中，权值最小的边一定包含在G的A.深度优先生成森林中B.深度优先生成树中C.最小生成树中D.广度优先生成树中答案:C9.对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为A.(23，56，78，66，88，92，19，34)B.(19，23，67，56，34，78，92，88)C.(19，23，56，34，78，67，88，92)D.(19，23，34，56，67，78，88，92)答案:B10.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是A.不确定B.2C.1D.0答案:B11.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为A.(v0，v1，v5，v2，v3，v4)B.(v0，v1，v4，v5，v2，v3)C.(v0，v1，v2，v5，v4，v3)D.(v0，v1，v2，v3，v4，v5)答案:D12.下列关键字序列中，构成小根堆的是A.84，62，58，46，41，37，28，15B.84，46，62，41，28，58，15，37C.15，28，46，37，84，58，62，41D.15，28，46，37，84，41，58，62答案:C13.队列和栈的主要区别是A.限定插入和删除的位置不同B.逻辑结构不同C.所包含的运算个数不同D.存储结构不同答案:A14.对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为A.（8，7，6，5，4，3，2，1）B.（2，1，4，3，5，7，8，6）C.（1，4，3，2，5，7，8，6）D.（1，2，3，4，5，6，7，8）答案:B15.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是A.顺序查找B.散列查找C.分块查找D.二分查找答案:B16.如果将矩阵Ann的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=(a11,a21,…,an1),( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是A.tail (head (tail (L)B.head (tail (head (L)C.head (head (tail (L)D.head (head(head(L)答案:B17.上溢现象通常出现在A.顺序栈的出栈操作过程中B.顺序栈的入栈操作过程中C.链栈的出栈操作过程中D.链栈的入栈操作过程中答案:B18.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少的结点数有A.h+1B.2h-1C.2h+1D.2h答案:B19.下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)的是A.直接选择排序B.快速排序C.堆排序D.冒泡排序答案:C20.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是A.后序B.先序C.从根开始的层次遍历D.中序答案:A