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

《东北大学20春学期《数据结构Ⅱ》平时在线作业1.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、20春学期《数据结构Ⅱ》在线平时作业1试卷总分:100得分:100一、单选题(共20道试题,共100分)1.适宜进行批量处理的文件类型是A.顺序文件B.索引顺序文件C.散列文件D.多关键字文件答案:A2.用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为A.9B.8C.6D.5答案:D3.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为A.9B.8C.5D.4答案:B4.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在A.BT[

2、i/2]B.BT[2*i]C.BT[2*i-1]D.BT[2*i+1]答案:D5.下列陈述中正确的是A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中最多只有两棵子树，并且有左右之分D.二叉树中必有度为2的结点答案:C6.设有一个顺序栈，6个元素1、2、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是A.6B.5C.3D.2答案:C7.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A.n-1B.nC.2n-1D.2n答案:B8.栈和队列都是A.顺序存储的线性结构B.限制存取位

3、置的非线性结构C.限制存取位置的线性结构D.链式存储的线性结构答案:C9.带行表的三元组表是稀疏矩阵的一种A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构答案:A10.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为A.O(n2)B.O(n)C.O(1)D.O(0)答案:B11.下面说法错误的是(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语

4、言的级别越高，执行效率就越低A.(1),(4)B.(1),(2)C.(3)D.(1)答案:A12.以下属于逻辑结构的是A.顺序表B.有序表C.哈希表D.单链表答案:B13.ALV树是一种平衡的二叉排序树，树中任一结点的A.左子树的高度均小于右子树的高度B.左子树的高度均大于右子树的高度C.左、右子树高度差的绝对值不超过1D.左、右子树的高度均相同答案:C14.栈的两种常用存储结构分别为A.顺序存储结构和链式存储结构B.顺序存储结构和散列存储结构C.链式存储结构和索引存储结构D.链式存储结构和散列存储结构答案:A15.在图采用邻接表存储时，求最小生成树的Prim算

5、法的时间复杂度为A.O(n+e)B.O(n3)C.O(n2)D.O(n)答案:A16.当采用分快查找时，数据的组织方式为A.数据分成若干块，每块（除最后一块外）中数据个数需相同B.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块C.数据分成若干块，每块内数据有序D.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块答案:D17.倒排文件的主要优点是A.节省存储空间B.便于进行文件的恢复C.便于进行插入和删除运算D.便于进行多关键字查询答案:D18.引起循环队列队头位置发生变化的操作是A.取队尾元素B.取队

6、头元素C.出队D.入队答案:C19.下面关于线性表的叙述中，错误的是A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，便于插入和删除操作。D.线性表采用链接存储，不必占用一片连续的存储单元。答案:B20.在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是A.5B.3C.2D.1答案:B