《【奥鹏】东大21春学期《数据结构Ⅱ》在线平时作业2》由会员分享，可在线阅读，更多相关《【奥鹏】东大21春学期《数据结构Ⅱ》在线平时作业2（8页珍藏版）》请在金锄头文库上搜索。
1、【奥鹏】东大21春学期数据结构在线平时作业2试卷总分100 得分100一、单选题 (共 20 道试题,共 100 分)1.下列程序段 for(i=1;i=n;i+) AI,j=0; 的时间复杂度是A.O(1)B.O(0)C.O(1+n)D.O(n)答案D2.以下数据结构中，属于线性结构的是A.广义表B.二叉树C.稀疏矩阵D.串答案A3.某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子答案B4.在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作A.s-next=p-nex
2、t;p-next=s;B.s-next=p; q-next=sC.q-next=s;s-next=p;D.p-next=s;s-next=q;答案B5.在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的值表示答案C6.已知一个散列表如图所示，其散列函数为H(key)=key11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为A.2B.3C.8D.9答案C7.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rea
3、r和front的值分别为A.1和 5B.2和4C.4和2D.5和1答案B8.引入二叉线索树的目的是A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲D.使二叉树的遍历结果唯一答案A9.下面说法错误的是 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低A.(1)B.(1),(2)C.(1),(4)D.(3)答案C10.有关二叉树下列说法正确的是A
4、.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2答案B11.按排序过程中依据的原则分类，快速排序属于A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法答案C12.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是A.10B.11C.12D.15答案A13.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为A.4B.5C.8D.9答案C14.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为A.O(n) O(n)B.O(n) O(1)C.O(1) O(n)D.
5、O(1) O(1)答案C15.判断两个串大小的基本准则是A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小答案D16.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA答案B17.在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为A.4，4，3B.4，3，3C.3，4，4D.3，3，4答案B18.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的A.层次遍历算法B.前序遍历算法C.中序遍历算法D.后序遍历算法答案C19.如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为A.插入排序B.归并排序C.冒泡排序D.堆排序答案A20.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A.nB.2n-1C.2nD.n-1答案A
