东北师范《数据结构》2022年春学期在线作业2答卷
数据结构19春在线作业2-0004
试卷总分:100得分:100
一、单选题 (共 20 道试题,共 60 分)
1.递归过程的完成需用到 ( )。
A.线性表
B.链表
C.栈
D.行列
正确答案
2.鄙人列状况中，可称为二叉树的是 ( )。
A.每个结点至多有两棵子树的树
B.哈夫曼树
C.每个结点至多有两棵子树的有序树
D.每个结点只要一棵右子树
正确答案:
3.通过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,\'a\'); push(ST,\'b\'); pop(ST,x);
A.a
B.b
C.1
D.2
正确答案:
4.若要求尽能够快地对序列进行安稳的排序，则应选 () 。
A.疾速排序
B.归并排序
C.起泡排序
D.希尔排序
正确答案:
5.一个算法大概是（）。
A.程序
B.疑问求解过程的描绘
C.要满意五个根本特性
D.A和C
正确答案:
6.判别头绪二叉树中某结点p有左后代的条件是 ( )。
A.p ! = NULL
B.p->lchild ! = NULL
C.p->ltag = = 0
D.p->ltag = = 1
正确答案
7.二叉树在中序头绪化后，仍不能有用求解的疑问是 ( )。
A.求指定结点的前序后继
B.求指定结点的中序前驱
C.求指定结点的中序后继
D.求指定结点的后序后继
正确答案来自熊猫题库（www.188open.com）
8.次序文件选用次序结构完成文件的存储，对大型的次序文件的少数修正，要求从头仿制整个文件，价值很高，选用 () 的方法可下降所需的价值。
A.附加文件
B.按关键词巨细排序
C.按记载输入先后排序
D.接连排序
正确答案:
9.广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ()。
A.( g )
B.( d )
C.c
D.d
正确答案来自熊猫题库（www.188open.com）
10.( ) 的遍历仍需求栈的撑持。
A.前序头绪二叉树
B.中序头绪二叉树
C.后序头绪二叉树
D.前三种均需求
正确答案
11.头绪二叉树是一种 ( ) 结构。
A.逻辑
B.物理
C.逻辑和存储
D.线性
正确答案:
12.有一个100*90的稀少矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表明该矩阵时，所需的字节数是 () 。
A.60
B.66
C.18000
D.33
正确答案:
13.就排序算法所用的辅助空间而言，堆排序、疾速排序、归并排序的关系是 () 。
A.堆排序＜疾速排序＜归并排序
B.堆排序＜归并排序＜疾速排序
C.堆排序＞归并排序＞疾速排序
D.堆排序＞疾速排序＞归并排序
正确答案:
14.下列说法不正确的是 ()。
A.图的遍历是从给定的源点动身每个极点仅被拜访一次
B.遍历的根本方法有两种：深度优先遍历和广度优先遍历
C.图的深度优先遍历不适用于有向图
D.图的深度优先遍历是一个递归过程
正确答案
15.在一个图中，一切极点的度数之和等于图的边数的几倍 ()。
A.1/2
B.1
C.2
D.4
正确答案
16.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前刺进s所指结点，则履行 ( )。
A.p->next = s; s->next = q;
B.s->next = p->next; p->next = s;
C.p->next = s->next; s->next = p;
D.q->next = s; s->next = p;
正确答案来自熊猫题库（www.188open.com）
17.在对n个元素的序列进行排序时，堆排序所需求的附加存储空间是 ()。
A.O(log2n )
B.O( 1 )
C.O(n )
D.O(nlog2n )
正确答案:
18.已知一个次序存储的线性表，设每个结点占c个单元，若榜首个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。
A.LOC(a0)+(i-1)*c
B.LOC(a0)+i*c
C.LOC(a0)-i*c
D.LOC(a0)+(i+1)*c
正确答案:
19.分块查找要求表中的结点 ()。
A.悉数无序
B.块之间无序
C.悉数有序
D.块之间有序
正确答案来自熊猫题库（www.188open.com）
20.下面关于串的叙说中，哪一个是不正确的? ( )
A.串是字符的有限序列
B.空串是由空格构成的串
C.形式匹配是串的一种重要运算
D.串既能够选用次序存储，也能够选用链式存储
正确答案:
二、答案来历：熊猫题库（www.188open.com） (共 20 道试题,共 40 分)
21.二叉树按某种次第头绪化后，任一结点均有指向其前序结点和后继结点的头绪。
答案:错误
22.在履行某个排序算法过程中，呈现了排序码朝着它终究排序方位相反的方向移动，则该算法是不安稳的。
答案:错误
23.非空的二叉树必定满意：某结点若有左后代，则其间序前驱必定没有右后代。
答案:正确
24.数组是同类型值的调集。
答案:错误
25.用链表 ( lchild-rchild表明法 ) 存储的包括n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
答案:正确
26.链表中的表头指针与表头结点起到一样的效果。
答案:错误
27.栈和行列的存储方法，既能够是次序方法，又能够是链式方法。
答案:正确
28.一个有向图的邻接表和逆邻接表中结点的个数能够不等。
答案:错误
29.对巨细均为n的有序表和无序表别离进行次序查找，在等概率查找的状况下，关于查找成功，它们的均匀查找长度是一样的，而关于查找失利，它们的均匀查找长度是不一样的。
答案:正确
30.任何无向图都存在生成树。
答案:错误
31.在彻底二叉树中，若一个结点没有左后代，则它必是树叶。
答案:正确
32.链表中的表头结点仅起到标识的效果。
答案:错误
33.将一棵树转成二叉树，根结点没有右子树。
答案:正确
34.连通重量是无向图中的极大连通子图。
答案:正确
35.所谓取广义表的表尾即是回来广义表中最终一个元素。
答案:错误
36.需求凭借于一个栈来完成DFS算法。
答案:正确
37.有必要把一般的树变换成二叉树后才干进行存储。
答案:错误
38.关于刺进、删去运算来说，连接存储结构必定优于次序存储结构。
答案:正确
39.后序头绪二叉树是不完善的，要对它进行遍历，还需求运用栈。
答案:正确
40.二维以上的数组其实是一种特别的广义表。
答案:正确
试卷总分:100得分:100
一、单选题 (共 20 道试题,共 60 分)
1.递归过程的完成需用到 ( )。
A.线性表
B.链表
C.栈
D.行列
正确答案
2.鄙人列状况中，可称为二叉树的是 ( )。
A.每个结点至多有两棵子树的树
B.哈夫曼树
C.每个结点至多有两棵子树的有序树
D.每个结点只要一棵右子树
正确答案:
3.通过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,\'a\'); push(ST,\'b\'); pop(ST,x);
A.a
B.b
C.1
D.2
正确答案:
4.若要求尽能够快地对序列进行安稳的排序，则应选 () 。
A.疾速排序
B.归并排序
C.起泡排序
D.希尔排序
正确答案:
5.一个算法大概是（）。
A.程序
B.疑问求解过程的描绘
C.要满意五个根本特性
D.A和C
正确答案:
6.判别头绪二叉树中某结点p有左后代的条件是 ( )。
A.p ! = NULL
B.p->lchild ! = NULL
C.p->ltag = = 0
D.p->ltag = = 1
正确答案
7.二叉树在中序头绪化后，仍不能有用求解的疑问是 ( )。
A.求指定结点的前序后继
B.求指定结点的中序前驱
C.求指定结点的中序后继
D.求指定结点的后序后继
正确答案来自熊猫题库（www.188open.com）
8.次序文件选用次序结构完成文件的存储，对大型的次序文件的少数修正，要求从头仿制整个文件，价值很高，选用 () 的方法可下降所需的价值。
A.附加文件
B.按关键词巨细排序
C.按记载输入先后排序
D.接连排序
正确答案:
9.广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ()。
A.( g )
B.( d )
C.c
D.d
正确答案来自熊猫题库（www.188open.com）
10.( ) 的遍历仍需求栈的撑持。
A.前序头绪二叉树
B.中序头绪二叉树
C.后序头绪二叉树
D.前三种均需求
正确答案
11.头绪二叉树是一种 ( ) 结构。
A.逻辑
B.物理
C.逻辑和存储
D.线性
正确答案:
12.有一个100*90的稀少矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表明该矩阵时，所需的字节数是 () 。
A.60
B.66
C.18000
D.33
正确答案:
13.就排序算法所用的辅助空间而言，堆排序、疾速排序、归并排序的关系是 () 。
A.堆排序＜疾速排序＜归并排序
B.堆排序＜归并排序＜疾速排序
C.堆排序＞归并排序＞疾速排序
D.堆排序＞疾速排序＞归并排序
正确答案:
14.下列说法不正确的是 ()。
A.图的遍历是从给定的源点动身每个极点仅被拜访一次
B.遍历的根本方法有两种：深度优先遍历和广度优先遍历
C.图的深度优先遍历不适用于有向图
D.图的深度优先遍历是一个递归过程
正确答案
15.在一个图中，一切极点的度数之和等于图的边数的几倍 ()。
A.1/2
B.1
C.2
D.4
正确答案
16.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前刺进s所指结点，则履行 ( )。
A.p->next = s; s->next = q;
B.s->next = p->next; p->next = s;
C.p->next = s->next; s->next = p;
D.q->next = s; s->next = p;
正确答案来自熊猫题库（www.188open.com）
17.在对n个元素的序列进行排序时，堆排序所需求的附加存储空间是 ()。
A.O(log2n )
B.O( 1 )
C.O(n )
D.O(nlog2n )
正确答案:
18.已知一个次序存储的线性表，设每个结点占c个单元，若榜首个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。
A.LOC(a0)+(i-1)*c
B.LOC(a0)+i*c
C.LOC(a0)-i*c
D.LOC(a0)+(i+1)*c
正确答案:
19.分块查找要求表中的结点 ()。
A.悉数无序
B.块之间无序
C.悉数有序
D.块之间有序
正确答案来自熊猫题库（www.188open.com）
20.下面关于串的叙说中，哪一个是不正确的? ( )
A.串是字符的有限序列
B.空串是由空格构成的串
C.形式匹配是串的一种重要运算
D.串既能够选用次序存储，也能够选用链式存储
正确答案:
二、答案来历：熊猫题库（www.188open.com） (共 20 道试题,共 40 分)
21.二叉树按某种次第头绪化后，任一结点均有指向其前序结点和后继结点的头绪。
答案:错误
22.在履行某个排序算法过程中，呈现了排序码朝着它终究排序方位相反的方向移动，则该算法是不安稳的。
答案:错误
23.非空的二叉树必定满意：某结点若有左后代，则其间序前驱必定没有右后代。
答案:正确
24.数组是同类型值的调集。
答案:错误
25.用链表 ( lchild-rchild表明法 ) 存储的包括n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
答案:正确
26.链表中的表头指针与表头结点起到一样的效果。
答案:错误
27.栈和行列的存储方法，既能够是次序方法，又能够是链式方法。
答案:正确
28.一个有向图的邻接表和逆邻接表中结点的个数能够不等。
答案:错误
29.对巨细均为n的有序表和无序表别离进行次序查找，在等概率查找的状况下，关于查找成功，它们的均匀查找长度是一样的，而关于查找失利，它们的均匀查找长度是不一样的。
答案:正确
30.任何无向图都存在生成树。
答案:错误
31.在彻底二叉树中，若一个结点没有左后代，则它必是树叶。
答案:正确
32.链表中的表头结点仅起到标识的效果。
答案:错误
33.将一棵树转成二叉树，根结点没有右子树。
答案:正确
34.连通重量是无向图中的极大连通子图。
答案:正确
35.所谓取广义表的表尾即是回来广义表中最终一个元素。
答案:错误
36.需求凭借于一个栈来完成DFS算法。
答案:正确
37.有必要把一般的树变换成二叉树后才干进行存储。
答案:错误
38.关于刺进、删去运算来说，连接存储结构必定优于次序存储结构。
答案:正确
39.后序头绪二叉树是不完善的，要对它进行遍历，还需求运用栈。
答案:正确
40.二维以上的数组其实是一种特别的广义表。
答案:正确
