武汉理工大20春《数据结构》作业二

数据结构_作业二
1.[判断题] 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（  ）
奥鹏作业答案
    A.正确
    B.错误
    正确答案:——A——
2.[判断题] 线性表的顺序存储结构比链式存储结构更好。（  ）
    A.正确
    B.错误
    正确答案:——B——
3.[判断题] 快速排序是排序算法中平均性能最好的一种排序。（  ）
    A.正确
    B.错误
    正确答案:——A——
4.[判断题] 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（  ）
    A.正确
    B.错误
    正确答案:————
5.[判断题] 子串“ABC”在主串“AABCABCD”中的位置为2。(  )
    A.正确
    B.错误
    正确答案:————
6.[判断题] 线性表中的所有元素都有一个前驱元素和后继元素。（  ）
    A.正确
    B.错误
    正确答案:————
7.[判断题] 调用一次深度优先遍历可以访问到图中的所有顶点。（  ）
    A.正确
    B.错误
    正确答案:————
8.[判断题] 非空的双向循环链表中任何结点的前驱指针均不为空。（  ）
    A.正确
    B.错误
    正确答案:————
9.[判断题] 层次遍历初始堆可以得到一个有序的序列。（  ）
    A.正确   
    B.错误
    正确答案:————
10.[判断题] 设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（  ）
    A.正确
    B.错误
    正确答案:————
11.[判断题] 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（  ）
    A.正确
    B.错误
    正确答案:————
12.[判断题] 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（  ）
    A.正确
    B.错误
    正确答案:————
13.[判断题] 对连通图进行深度优先遍历可以访问到该图中的所有顶点。（  ）
    A.正确
    B.错误
    正确答案:————
14.[判断题] 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（  ）
    A.正确
    B.错误
    正确答案:————
15.[判断题] 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（  ）
    A.正确
    B.错误
    正确答案:————
16.[判断题] 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（  ）
    A.正确
    B.错误
    正确答案:————
17.[单选题] 图G的某一最小生成树的代价一定小于其他生成树的代价
    A.一定是
    B.肯定不是
    C.不一定是
    D.都不对
    正确答案:————
18.[单选题] 设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（  ）存储方式最节省运算时间。
    A.单向链表
    B.单向循环链表
    C.双向链表
    D.双向循环链表
    正确答案:————
19.[单选题] 下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是
    A.堆排序
    B.冒泡排序
    C.直接选择排序
    D.快速排序
    正确答案:————
20.[单选题] 设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（  ）。
    A.log2n+1
    B.log2n-1
    C.log2n
    D.log2(n+1)
    正确答案:————
21.[单选题] 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉树中有（  ）个度数为0的结点。
    A.5
    B.6
    C.7
    D.8
    正确答案:————
22.[单选题] 设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（  ）。
    A.top=top+1;
    B.top=top-1;
    C.top-＞next=top;
    D.top=top-＞next;
    正确答案:————
23.[单选题] 深度为k的完全二叉树中最少有（  ）个结点。
    A.2k-1-1
    B.2k-1
    C.2k-1+1
    D.2k-1
    正确答案:————
24.[单选题] 设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（  ）。
    A.s-＞next=p-＞next；p-＞next=-s
    B.q-＞next=s； s-＞next=p
    C.p-＞next=s-＞next；s-＞next=p
    D.p-＞next=s；s-＞next=q
    正确答案:————
25.[单选题] 设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（  ）。
    A.O(n+e)
    B.O(n2)
    C.O(ne)
    D.O(n3)
    正确答案:————
26.[单选题] 下面程序的时间复杂度为（  ）  for（i=1，s=0； i＜=n； i++） {t=1；for(j=1；j＜=i；j++) t=t*j；s=s+t；}
    A.O(n)
    B.O(n2)
    C.O(n3)
    D.O(n4)
    正确答案:————
27.[单选题] 设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（  ）。
    A.99
    B.97
    C.91
    D.93
    正确答案:————
28.[单选题] 设有6个结点的无向图，该图至少应有(      )条边才能确保是一个连通图。
    A.5
    B.6
    C.7
    D.8
    正确答案:————
29.[单选题] 设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（  ）次。
    A.25
    B.10
    C.7
    D.1
    正确答案:————
30.[单选题] 设顺序表的长度为n，则顺序查找的平均比较次数为（  ）。
    A.n
    B.n/2
    C.(n+1)/2
    D.(n-1)/2
    正确答案:————
31.[单选题] 设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（  ）方法可以达到此目的。
    A.快速排序
    B.堆排序
    C.归并排序
    D.插入排序
    正确答案:————
32.[单选题] 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为( )
    A.O（1）
    B.O（n）
    C.O（1og2n）
    D.O（n2）
    正确答案:————
33.[单选题] 设一棵二叉树的深度为k，则该二叉树中最多有（  ）个结点。
    A.2k-1
    B.2k
    C.2k-1
    D.2k-1
    正确答案:————
34.[单选题] 下列四种排序中（  ）的空间复杂度最大。
    A.插入排序
    B.冒泡排序
    C.堆排序
    D.归并排序
    正确答案:————
35.[单选题] 二叉树的第k层的结点数最多为(  )。
    A.2k-1
    B.2K+1
    C.2K-1
    D.2k-1
    正确答案:————
36.[单选题] 设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（  ）。
    A.5，3，4，6，1，2
    B.3，2，5，6，4，1
    C.3，1，2，5，4，6
    D.1，5，4，6，2，3
    正确答案:————
37.[单选题] 设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（  ）。
    A.Nl+N2+……+Nm
    B.l+N2+2N3+3N4+……+(m-1)Nm
    C.N2+2N3+3N4+……+(m-1)Nm
    D.2Nl+3N2+……+(m+1)Nm
    正确答案:————
38.[单选题] 函数substr(“DATASTRUCTURE”，5，9)的返回值为（  ）。
    A.“STRUCTURE”
    B.“DATA”
    C.“ASTRUCTUR”
    D.“DATASTRUCTURE”
    正确答案:————
39.[单选题] 两个字符串相等的充要条件是（  ）。
    A.两个字符串的长度相等
    B.两个字符串中对应位置上的字符相等
    C.同时具备(A)和(B)两个条件
    D.以上答案都不对
    正确答案:————
40.[单选题] 在二叉排序树中插入一个关键字值的平均时间复杂度为（  ）。
    A.O(n)
    B.O(1og2n)
    C.O(nlog2n)
    D.O(n2)
    正确答案:————