《数据结构Ⅱ》在线平时作业3答卷

1、数据结构在线平时作业3-00001试卷总分:100 得分:100一、单选题 (共 20 道试题,共 100 分)1.在待排关键字序列基本有序的前提下，效率最高的排序方法是A.直接插入排序B.快速排序C.直接选择排序D.归并排序答案:A2.一个具有1025个结点的二叉树的高h为A.11B.10C.11至1025之间D.10至1024之间答案:C3.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于A.1.0B.2.9C.3.4D.5.5答案:B4.一棵树高为K的完全二叉树至少的结点是A.2k 1B.2k-1 1C.2k-1D.2k答案:C5.在线

2、性表的下列运算中，不改变数据元素之间结构关系的运算是A.插入B.删除C.排序D.查找答案:D6.有关二叉树下列说法正确的是A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2答案:B7.若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向A.各自的头结点B.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点答案:B8.对长度为n的关键字序列进行堆排序的空间复杂度为A.O（log2n）B.O（1）C.O（n）D.O（n*log2n）答案:B9.多维数组之所以有行优先顺序

3、和列优先顺序两种存储方式是因为A.数组的元素处在行和列两个关系中B.数组的元素必须从左到右顺序排列C.数组的元素之间存在次序关系D.数组是多维结构，内存是一维结构答案:D10.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为A.O(1)B.O(logn)C.O(n)D.O(n logn)答案:B11.在一个单链表中，若删除*p结点的后继结点，则执行操作A.q=p-next;p-next=q-next;free(q);B.p=p-next;p-next=p-next-next;free(p);C.p-next=q-next;free(p-next);D.p=p-next-next;fre

4、e(p-next);答案:A12.为便于判别有向图中是否存在回路，可借助于A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.拓扑排序算法答案:D13.连通图是指图中任意两个顶点之间A.都连通的无向图B.都不连通的无向图C.都连通的有向图D.都不连通的有向图答案:A14.能进行二分查找的线性表,必须以A.顺序方式存储,且元素按关键字有序B.链式方式存储,且元素按关键字有序C.顺序方式存储,且元素按关键字分块有序D.链式方式存储,且元素按关键字分块有序答案:A15.二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，8，列下标为j=1，210。设每个字符占一个字节,若按行先存储，

5、元素A8，5的起始地址与A按列存储时起始地址相同的元素是A.A8，5B.A3，10C.A5，8D.A0，9答案:B16.下面的说法中正确的是 (1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。 (2)按二叉树定义，具有三个节点的二叉树共有6种。A.(1)，(2)B.(1)C.(2)D.(1)，(2)都错答案:B17.以下与数据的存储结构无关的术语是A.循环队列B.链表C.哈希表D.栈答案:D18.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法答案:B19.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为A.O(0)B.O(1)C.O(n)D.