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

数据结构_作业一
1.[判断题] 层次遍历初始堆可以得到一个有序的序列。（  ）
奥鹏作业答案
    A.正确
    B.错误
    正确答案:——B——
2.[判断题] 快速排序是排序算法中平均性能最好的一种排序。（  ）
    A.正确
    B.错误
    正确答案:——A——
3.[判断题] 设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（  ）
    A.正确
    B.错误
    正确答案:——A——
4.[判断题] 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。(  )
    A.正确
    B.错误
    正确答案:————
5.[判断题] 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（  ）
    A.正确
    B.错误
    正确答案:————
6.[判断题] 堆是完全二叉树，完全二叉树不一定是堆。（  ）
    A.正确
    B.错误
    正确答案:————
7.[判断题] 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（  ）
    A.正确
    B.错误
    正确答案:————
8.[判断题] 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（  ）    奥鹏作业答案q 7 6 12960 2 1
    A.正确
    B.错误
    正确答案:————
9.[判断题] 哈夫曼树中没有度数为1的结点。（  ）
    A.正确
    B.错误
    正确答案:————
10.[判断题] 线性表中的所有元素都有一个前驱元素和后继元素。（  ）
    A.正确
    B.错误
    正确答案:————
11.[判断题] 中序遍历二叉排序树可以得到一个有序的序列。（  ）
    A.正确
    B.错误
    正确答案:————
12.[判断题] 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（  ）
    A.正确
    B.错误
    正确答案:————
13.[判断题] 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（  ）
    A.正确
    B.错误
    正确答案:————
14.[判断题] 二维数组和多维数组均不是特殊的线性结构。（  ）
    A.正确
    B.错误
    正确答案:————
15.[判断题] 希尔排序算法的时间复杂度为O(n2)。(  )
    A.正确
    B.错误
    正确答案:————
16.[判断题] 对链表进行插入和删除操作时不必移动链表中结点。(  )
    A.正确
    B.错误
    正确答案:————
17.[单选题] 设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（  ）存储方式最节省运算时间。
    A.单向链表
    B.单向循环链表
    C.双向链表
    D.双向循环链表
    正确答案:————
18.[单选题] 用某种排序方法对线性表（25，87，21，47，15，27，63，35，20）进行排序时，元素序列的变化情况如下：  （1）25，87，21，47，15，27，63，35，20  （2）20，15，21，25，47，27，63，35，87  （3）15，20，21，25，35，27，47，63，87  （4）15，20，21，25，27，35，47，63，87  则采用的排序方法是___________排序长度为4。
    A.交换排序法
    B.选择排序法
    C.插入排序
    D.选择排序
    正确答案:————
19.[单选题] 设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是（   ）。
    A.A，B，C，D
    B.A，C，D，B
    C.D，C，B，A
    D.D，A，B，C
    正确答案:————
20.[单选题] 设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（  ）。
    A.20
    B.256
    C.512
    D.1024
    正确答案:————
21.[单选题] 设完全无向图中有n个顶点，则该完全无向图中有（  ）条边。
    A.n(n-1)/2
    B.n(n-1)
    C.n(n+1)/2
    D.(n-1)/2
    正确答案:————
22.[单选题] 设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（  ）。
    A.front-＞next=s；front=s；
    B.s-＞next=rear；rear=s；
    C.rear-＞next=s；rear=s；
    D.s-＞next=front；front=s；
    正确答案:————
23.[单选题] 单链表的存储密度
    A.大于1
    B.等于1
    C.小于1
    D.不能确定
    正确答案:————
24.[单选题] 设无向图G中有n个顶点，则该无向图的最小生成树上有（  ）条边。
    A.n
    B.n-1
    C.2n
    D.2n-1
    正确答案:————
25.[单选题] 设有n个待排序的记录关键字，则在堆排序中需要（  ）个辅助记录单元。
    A.1
    B.n
    C.nlog2n
    D.n2
    正确答案:————
26.[单选题] 设二维数组A[0..m-1][0..m-1]按行优先顺序存储，则元素A[j]的地址为
    A.LOG(A[0][0])+(i*m+j)
    B.LOG(A[0][0])+(i*n+j)
    C.LOG(A[0][0])+[(i-1)*n+j-1]
    D.LOG(A[0][0])+[(i-1)*m+j-1]
    正确答案:————
27.[单选题] 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是
    A.访问第i个结点（1≤i≤n）
    B.在第i个结点后插入一个新结点（1≤i≤n）
    C.删除第i个结点（1≤i≤n）
    D.将n个结点从小到大排序
    正确答案:————
28.[单选题] 一个队列的入队序列是1，2，3，4，则队列的输出序列是
    A.1，2，3，4
    B.4，3，2，1
    C.1，4，3，2
    D.3，2，4，1
    正确答案:————
29.[单选题] 若线性表最常用的操作是存取第i个元素的值，则采用_______存储方式节省时间。
    A.单链表
    B.双链表
    C.单循环链表
    D.顺序表
    正确答案:————
30.[单选题] 若要唯一地确定一棵二叉树，只需知道该二叉树的
    A.前序序列
    B.中序序列
    C.前序和后序序列
    D.中序和后序序列
    正确答案:————
31.[单选题] 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉树中有（  ）个度数为0的结点。
    A.5
    B.6
    C.7
    D.8
    正确答案:————
32.[单选题] 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是
    A.希尔排序
    B.冒泡排序
    C.插入排序
    D.选择排序
    正确答案:————
33.[单选题] 设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（  ）。
    A.R-F
    B.F-R
    C.(R-F+M)％M
    D.(F-R+M)％M
    正确答案:————
34.[单选题] 设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（  ）。
    A.N0=N1+1
    B.N0=Nl+N2
    C.N0=N2+1
    D.N0=2N1+l
    正确答案:————
35.[单选题] 带头结点的单链表head为空的判定条件是
    A.head=NULL;
    B.head-＞next=NULL;
    C.head-＞next=head;
    D.head!=NULL;
    正确答案:————
36.[单选题] 设某有向图中有n个顶点，则该有向图对应的邻接表中有（  ）个表头结点。
    A.n-1
    B.n
    C.n+1
    D.2n-1
    正确答案:————
37.[单选题] 设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（  ）。
    A.O(n+e)
    B.O(n2)
    C.O(ne)
    D.O(n3)
    正确答案:————
38.[单选题] 设某棵三叉树中有40个结点，则该三叉树的最小高度为（  ）。
    A.3
    B.4
    C.5
    D.6
    正确答案:————
39.[单选题] 栈和队列的共同特点是(      )。
    A.只允许在端点处插入和删除元素
    B.都是先进后出
    C.都是先进先出
    D.没有共同点
    正确答案:————
40.[单选题] 下列说法中错误的是
    A.串是一种特殊的线性表
    B.串中不能没有字符
    C.串中可以有字母
    D.串长大于或等于0
    正确答案:————

，附件是答案，请