东北大学20春《数据结构Ⅱ》平时在线作业1答案

1、东北大学20春数据结构平时在线作业1答案适宜进行批量处理的文件类型是A.顺序文件B.索引顺序文件C.散列文件D.多关键字文件用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为A.9B.8C.6D.5若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为A.9B.8C.5D.4假设一棵完全二叉树按层次遍历的顺序依次存放在数组BTm中，其中根结点存放在BT0，若BTi中的结点有左孩子，则左孩子存放在A.BTi/2B.BT2*iC.BT2*i-1D.BT2*i+1下列陈述中正确的是A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中

2、最多只有两棵子树，并且有左右之分D.二叉树中必有度为2的结点设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是A.6B.5C.3D.2将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A.n-1B.nC.2n-1D.2n栈和队列都是A.顺序存储的线性结构B.限制存取位置的非线性结构C.限制存取位置的线性结构D.链式存储的线性结构带行表的三元组表是稀疏矩阵的一种A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为A

3、.O(n2)B.O(n)C.O(1)D.O(0)下面说法错误的是(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界(4)同一个算法，实现语言的级别越高，执行效率就越低A.(1),(4)B.(1),(2)C.(3)D.(1)以下属于逻辑结构的是A.顺序表B.有序表C.哈希表D.单链表ALV树是一种平衡的二叉排序树，树中任一结点的A.左子树的高度均小于右子树的高度B.左子树的高度均大于右子树的高度C.左、右子树高度差的绝对值不超过1D.左、右子树的高度均

4、相同栈的两种常用存储结构分别为A.顺序存储结构和链式存储结构B.顺序存储结构和散列存储结构C.链式存储结构和索引存储结构D.链式存储结构和散列存储结构在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为A.O(n+e)B.O(n3)C.O(n2)D.O(n)当采用分快查找时，数据的组织方式为A.数据分成若干块，每块(除最后一块外)中数据个数需相同B.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序D.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块倒排文件的主要优点是A.节省存储空间B.便于进行文件的恢复C.便于进行插入和删除运算D.便于进行多关键字查询引起循环队列队头位置发生变化的操作是A.取队尾元素B.取队头元素C.出队D.入队下面关于线性表的叙述中，错误的是A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链接存储，便于插入和删除操作D.线性表采用链接存储，不必占用一片连续的存储单元在目标串T0.n-1=xwxxyxy中，对模式串P0.m-1=xy 进行子串定位操作的结果是A.5B.3C.2D.1 参考答案：A参考答案：D参考答案：B参考答案：D参考答案：C参考答案：C参考答案：B