[四川农业大学]《数据结构(专科)》20年6月作业考核

【奥鹏】-[四川农业大学]《数据结构（专科）》20年6月作业考核 试卷总分:100 得分:100

第1题,一组记录的关键字经一趟二路归并排序后得到含有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 正确答案:D

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

正确答案:C

第3题,一个关键字序列为{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} 正确答案:C

第4题,与数据元素本身的形式、内容、相对位置、个数无关的是数据的( ) A、存储结构 B、逻辑结构 C、算法 D、操作 正确答案:B

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

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

C、n(n-1)/2 D、n(n-1) 正确答案:A

第7题,对有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] 正确答案:C

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

第9题,一个二叉树按顺序方式存储在如下的一个维数组中,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

正确答案:B

第10题,设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[ ]A[0][0]存入B[0]中，则A[8][5]在B[ ]中（ ) A、32 B、33 C、41 D、65

正确答案:C

第11题,用链表表示线性表的优点是( ) A、便于随机存取

B、花费的存储空间比顺序表少 C、便于插入与删除

D、数据元素的物理顺序与逻辑顺序相同 正确答案:C

第12题,设数组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 正确答案:D

第13题,若让元素1，2，3依次进栈，则出栈次序不可能出现种情况( ) A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，2 正确答案:C

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

第15题,右图中的拓扑序列为（ ) A、C1，C2，C6，C7，C5，C4，C3 B、C1，C2，C6，C3，C4，C5，C7 C、C1，C4，C2，C3，C5，C6，C7 D、C5，C7，C4，C1，C2，C6，C3 正确答案:D

第16题,AVL树是一种平衡的二叉排序树，树中任一结点的( ) A、左、右子树的高度均相同

B、左、右子树高度差的绝对值不超过1 C、左子树的高度均大于右子树的高度 D、左子树的高度均小于右子树的高度 正确答案:B

第17题,设某算法的问题规模函数f(n)=300n2+8000n+900，则它的渐进时间复杂度为（ ) A、O(n3) B、O(n2) C、O(n) D、O(1) 正确答案:B

第18题,线性表是一个具有n个（ ）的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 正确答案:C

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

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