[四川农业大学]《数据结构（本科）》18年12月在线作业(100分）

hezuo001

【奥鹏】[四川农业大学]《数据结构（本科）》18年12月在线作业
试卷总分:100    得分:100
第1题,一个关键字序列为{46，79，56，38，40，84}，采用快速排序以位于最左位置的元素为基准而得到的第一次划分结果为（   )
A、{38，46，79，56，40，84}
B、{38，79，56，46，40，84}
C、{40，38，46，56，79，84}
D、{38，46，56，79，40，84}



第2题,对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（  ）
A、DBFEAC
B、DFEBCA
C、BDFECA
D、BDEFAC



第3题,对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为(  )
A、R[0]，R[1]，R[2]，R[3]
B、R[0]，R[13]，R[2]，R[3]
C、R[6]，R[2]，R[4]，R[3]
D、R[6]，R[4]，R[2]，R[3]



第4题,一个二叉树按顺序方式存储在如下的一个维数组中,0   1   2   3     4   5    6   7    8   9   10   11  12   13  14A B C D  E F  G   H  I J则结点E在二叉树的第（    ）层。
A、1
B、2
C、3
D、4



第5题,下列存储形式中不是树的存储形式(  )
A、双亲表示法
B、孩子兄弟表示法
C、顺序表示法
D、广义表表示法



第6题,深度为8的二叉树至多有（   ）个结点
A、7
B、15
C、127
D、255



第7题,一组记录的关键字经一趟二路归并排序后得到含有5个长度为2的有序表如下：［25，48］，［16，35］，［79，82］，［23，40］，［36，72］，在此基础上按二路归并排序方法再对该序列进行一趟归并后的结果为(  )
A、16，25，35，48，23，40，79，82，36，72
B、16，25，35，48，23，40，79，82，72，36
C、16，25，48，35，79，82，23，36，40，72
D、16，25，35，48，79，23，36，40，72，82



第8题,设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（   ）
A、front=front+1
B、front=(front+1)%(m-1)
C、front=(front-1)%m
D、front=(front+1)%m



第9题,设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为(  )
A、O（nlog2e）
B、O（n+e）
C、O(ne)
D、O(n2)



第10题,n个顶点的有向完全图中含有向边的数目最多为（  )
A、n-1
B、n
C、n(n-1)/2
D、n(n-1)



第11题,设有整型二维数组M[7][6]，每个元素（整数）占4个存储单元，元素按行的顺序存储，数组的起始地址为1000，元素M[5][3]的地址是（  )
A、1032
B、1132
C、1192
D、1232



第12题,对5个不同的数据元素进行直接插入排序，最多需要进行（   ）次比较
A、8
B、10
C、15
D、25



第13题,链式栈与顺序栈相比，一个比较明显的优点是(  )
A、插入操作更加方便
B、通常不会出现栈满的情况
C、不会出现栈空的情况
D、删除操作更加方便



第14题,对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是(  )
A、直接选择排序
B、直接插入排序
C、快速排序
D、起泡排序



第15题,假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（   )
A、O(n)
B、O(e)
C、O(n+e)
D、O(n×e)



第16题,设有一个含有n 个(n2)关键字的有序表，分别用顺序查找法和二分查找法查找一个给定的关键字，比较次数分别为s和h，在查找成功的情况下，s和h的关系是(  )
A、s = h
B、s  h
C、s  h
D、不能确定



第17题,向顺序栈中压入新元素时，应当(  )
A、先移动栈顶位置，再存入元素
B、先存入元素，再移动栈顶位置
C、先后次序无关紧要
D、同时进行



第18题,向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（   ）个元素。
A、8
B、63.5
C、63
D、7



第19题,AVL树是一种平衡的二叉排序树，树中任一结点的(  )
A、左、右子树的高度均相同
B、左、右子树高度差的绝对值不超过1
C、左子树的高度均大于右子树的高度
D、左子树的高度均小于右子树的高度



第20题,依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是（  )
A、X
B、Y
C、Z
D、W