川大17春《数据结构(1)》在线作业12答案
《数据结构(1)》17春在线作业1一、单选题：
1.k层（根为第1层）二叉树的结点总数最多为( )。 (满分:2)
A. 2k-1
B. 2K+1
C. 2K-1
D. 2k-1
2.下面关于图的存储的叙述中正确的是( )。 (满分:2)
A. 用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
B. 用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。
C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D. 用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
3.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序( )。 (满分:2)
A. 都不相同
B. 完全相同
C. 先序和中序相同，而与后序不同
D. 中序和后序相同，而与先序不同
4.对n个记录进行堆排序，所需要的辅助存储空间为( )。 (满分:2)
A. O（1og2n）
B. O（n）
C. O（1）
D. O(n2)
5.下列关于数据结构的叙述中，正确的是( )。 (满分:2)
A. 数组是不同类型值的集合
B. 递归算法的程序结构比迭代算法的程序结构更为精炼
C. 树是一种线性结构
D. 用一维数组存储一棵完全二叉树是有效的存储方法
6.对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为( )。 (满分:2)
A. 24
B. 25
C. 98
D. 99
7.已知一个图的顶点集V={1
2
3
4
5
6
7}；边集E={(1
2)3
(1
3)5
(1
4)8
(2
5)10
(2
3)6
(3
4)15
(3
5)12
(3
6)9
(4
6)4
(4
7)20
(5
6)18
(6
7)25}，用克鲁斯卡尔算法得到最小生成树，则在最小生成树中依次得到的各条边为( )。 (满分:2)
A.(1
2)3
(4
6)4
(1
3)5
(1
4)8
(2
5)10
(4
7)20
B.(1
2)3
(4
6)4
(1
3)5
(2
3)6
(1
4)8
(3
6)9
C.(1
2)3
(1
3)5
(1
4)8
(4
6)4
(2
5)10
(4
7)20
D.(1
2)3
(1
3)5
(1
4)8
(2
5)10
(4
6)4
(4
7)20
8.有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行( )遍分配与收集。 (满分:2)
A. n
B. d
C. r
D. n-d
9.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是( )。 (满分:2)
A. m-n-1
B. n+1
C. m-n+1
D. m-n
10.对广义表L=((a
b)
(c
d)
(e
f))执行操作tail(tail(L))的结果是( )。 (满分:2)
A.(e
f)
B.((e
f))
C.(f)
D.( )
11.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。 (满分:2)
A. p=q; p->next=q;
B. p->next=q; q->next=p;
C. p->next=q->next; p=q;
D. q->next=p->next; p->next=q;
12.由权值分别为3
8
6
2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 (满分:2)
A. 11
B. 35
C. 19
D. 53
13.含有10个结点的二叉树中，度为0的结点数为4，则度为2的点数为( )。 (满分:2)
A. 3
B. 4
C. 5
D. 6
14.在线性表的下列运算中，不改变数据元素之间的结构关系的运算是( )。 (满分:2)
A. 插入
B. 删除
C. 排序
D. 查找
15.数据的基本单位是( )。 (满分:2)
A. 数据项
B. 数据类型
C. 数据元素
D. 数据变量
16.对于关键字序列（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有( )个。 (满分:2)
A. 1
B. 2
C. 3
D. 4
17.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面的序列( )是从上述序列出发建堆的结果。 (满分:2)
A. a，g，h，m，n，p，q，x，z
B. a，g，m，h，q，n，p，x，z
C. g，m，q，a，n，p，x，h，z
D. h，g，m，p，a，n，q，x，z
18.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 (满分:2)
A. HL=p;p->next=HL;
B. p->next=HL->next;HL->next=p;
C. p->next=HL;p=HL;
D. p->next=HL;HL=p;
19.对线性表进行二分法查找，其前提条件是( )。 (满分:2)
A. 线性表以链接方式存储，并且按关键码值排好序
B. 线性表以顺序方式存储，并且按关键码值的检索频率排好序
C. 线性表以顺序方式存储，并且按关键码值排好序
D. 线性表以链接方式存储，并且按关键码值的检索频率排好序
20.带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是( )。 (满分:2)
A. head==NULL
B. head->next==NULL
C. head!=NULL
D. head->next==head
21.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素个数是( )。 (满分:2)
A. n-i
B. n-i+1
C. n-i-1
D. i
22.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是( )。 (满分:2)
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
23.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 (满分:2)
A. O(n)
B. O(1)
C. O(log2n)
D. O(n2)
24.设有一个二维数组A(m>3)，假设A存放位置在600，A存放位置在678，每个元素占一个空间，则A的存放位置是( )。 (满分:2)
A. 658
B. 648
C. 633
D. 653
25.设Huffman树的叶子结点数为m，则结点总数为( )。 (满分:2)
A. 2m
B. 2m-1
C. 2m+1
D. m+1
二、多选题：
1.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列为( )。 (满分:5)
A. 3，2，6，1，4，5
B. 3，4，2，1，6，5
C. 1，2，5，3，4，6
D. 5，6，4，2，3，1
E. 6，5，4，3，2，1
2.以下数据结构中哪一个是线性结构？ (满分:5)
A. 有向图
B. 队列
C. 线索二叉树
D. 线性表
E. 栈
3.以下哪些是队列的基本运算？ (满分:5)
A. 在队列第i个元素之后插入一个元素
B. 从队头删除一个元素
C. 判断一个队列是否为空
D. 读取队头元素的值(E)将队列中的元素排序
4.以下序列中，是堆（大顶堆或小顶堆）的有( )。 (满分:5)
A. {15
26
38
49
27
51
39
62}
B. {15
23
71
94
72
68
26
73}
C. {15
27
26
49
38
62
39
51}
D. {15
23
26
68
94
72
71
73}
E. {94
72
73
26
71
23
68
15}
三、判断题：
1.用字符数组存储长度为n的字符串，数组长度至少为n+1。 (满分:2)
A. 错误
B. 正确
2.图G的某一最小生成树的代价一定小于其他生成树的代价。 (满分:2)
A. 错误
B. 正确
3.若仅知道某二叉树的中序遍历序列和后序遍历序列，则不能够确定此二叉树的层次遍历的序列。 (满分:2)
A. 错误
B. 正确
4.已知指针P指向链表L中的某结点，执行语句P：=P?NEXT不会删除该链表中的结点。 (满分:2)
A. 错误
B. 正确
5.二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。 (满分:2)
A. 错误
B. 正确
6.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。 (满分:2)
A. 错误
B. 正确
7.一个广义表((a)
((b)
c)
(((d)))) 的表尾是((b)
c)
(((d)))。 (满分:2)
A. 错误
B. 正确
8.为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。 (满分:2)
A. 错误
B. 正确
9.在采用线性探测法处理冲突的哈希表中，所有同义词在表中相邻。 (满分:2)
A. 错误
B. 正确
10.使用三元组表示稀疏矩阵中的非零元素能节省存储空间。 (满分:2)
A. 错误
B. 正确
11.快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。 (满分:2)
A. 错误
B. 正确
12.栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。 (满分:2)
A. 错误
B. 正确
13.线性表的长度是线性表所占用的存储空间的大小。 (满分:2)
A. 错误
B. 正确
14.快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。 (满分:2)
A. 错误
B. 正确
15.顺序表用一维数组作为存储结构，因此顺序表是一维数组。 (满分:2)
A. 错误
B. 正确
《数据结构(1)》17春在线作业2
一、单选题：
1.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 (满分:2)
A. 5
B. 6
C. 7
D. 8
2.设有一个二维数组A，假设A存放位置在644，A存放位置在676，每个元素占一个空间，则A存放位置在( )。 (满分:2)
A. 688
B. 678
C. 692
D. 696
3.若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E，则该二叉树结点的前序遍历的序列为( )。 (满分:2)
A. E、G、F、A、C、D、B
B. E、A、G、C、F、B、D
C. E、A、C、B、D、G、F
D. E、G、A、C、D、F、B
4.AOV网是一种( )。 (满分:2)
A. 有向图
B. 无向图
C. 无向无环图
D. 有向无环图
5.一散列表长度m为100，采用除留余数法构造散列函数，即H(K)=K%P(P<=m)
，为使散列函数具有较好的性能，P的选择应是( )。 (满分:2)
A. 99
B. 100
C. 97
D. 93
6.假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行( )次探测。 (满分:2)
A. K-1次
B. K次
C. K＋l次
D. K(K+1)/2次
7.在数据结构中，数据元素可由( )。 (满分:2)
A. 实体
B. 域
C. 数据项
D. 字段
8.若有序表为（b
c
d
e
f
g
q
r
s
t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为( )。 (满分:2)
A. f
c
b
B. f
d
b
C. g
c
b
D. g
d
b
9.在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为( )。 (满分:2)
A. i
B. i+1
C. n-i
D. n-i+1
10.队列的特点是( )。 (满分:2)
A. 先进后出
B. 先进先出
C. 任意位置进出
D. 前面都不正确
11.树最适合用来表示( )。 (满分:2)
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
12.采用开放定址法处理散列表的冲突时，其平均查找长度( )。 (满分:2)
A. 低于链接法处理冲突
B. 高于链接法处理冲突
C. 与链接法处理冲突相同
D. 高于二分查找
13.二维数组A按行优先顺序存储，若数组元素A的存储地址为1087，A的存储地址为1153，则数组元素A的存储地址为( )。 (满分:2)
A. 1207
B. 1209
C. 1211
D. 1213
14.对线性表，在下列哪种情况下应当采用链表表示？ (满分:2)
A. 经常需要随机地存取元素
B. 经常需要进行插入和删除操作
C. 表中元素需要占据一片连续的存储空间
D. 表中元素的个数不变
15.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( )。 (满分:2)
A. 2 3 1
B. 3 2 1
C. 3 1 2
D. 1 2 3
16.对关键字序列(56
23
78
92
88
67
19
34)进行增量为3的一趟希尔排序的结果为( )。 (满分:2)
A.(19
23
56
34
78
67
88
92)
B.(23
56
78
66
88
92
19
34)
C.(19
23
34
56
67
78
88
92)
D.(19
23
67
56
34
78
92
88)
17.对一个算法的评价，不包括如下( )方面的内容。 (满分:2)
A. 健壮性和可读性
B. 并行性
C. 正确性
D. 时空复杂度
18.如表r有100000个元素，前99999个元素递增有序，则采用( )方法比较次数较少。 (满分:2)
A. 直接插入排序
B. 快速排序
C. 归并排序
D. 选择排序
19.若有18个元素的有序表存放在一维数组A中，第一个元素放A中，现进行二分查找，则查找A的比较序列的下标依次为( )。 (满分:2)
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
20.若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为( )。 (满分:2)
A. 图中每个顶点的入度
B. 图中每个顶点的出度
C. 图中每个顶点的度
D. 图中连通分量的数目
21.中缀表达式2+X*(Y+3)的后缀形式是( )。 (满分:2)
A. 3YX2+*+
B. Y3+X*2+
C. 2XY3*++
D. 2XY3+*+
22.若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。则该二叉树结点的前序遍历的序列为( )。 (满分:2)
A. E、G、F、A、C、D、B
B. E、A、G、C、F、B、D
C. E、A、C、B、D、G、F
D. E、G、A、C、D、F、B
23.以下数据结构中哪一个是非线性结构？ (满分:2)
A. 队列
B. 栈
C. 线性表
D. 二叉树
24.下面关于广义表的叙述中，不正确的是( )。 (满分:2)
A. 广义表可以是一个多层次的结构
B. 广义表至少有一个元素
C. 广义表可以被其他广义表所共享
D. 广义表可以是一个递归表
25.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H(K)=K % 9作为散列函数，则散列地址为1的元素有( )个。 (满分:2)
A. 1
B. 2
C. 3
D. 4
二、多选题：
1.对一个算法的评价，主要包括如下( )方面的内容。 (满分:5)
A. 健壮性和可读性
B. 并行性
C. 正确性
D. 时空复杂度
E. 界面友好性
2.下面的二叉树中，是完全二叉树的有( )。 (满分:5)
A. A
B. B
C. C
D. D
3.栈和队列的共同特点是( )。 (满分:5)
A. 只允许在端点处插入和删除元素
B. 都是先进后出
C. 都是先进先出
D. 没有共同点
E. 都可以采用顺序存储方式和链式存储方式
4.下述哪些是顺序存储方式的优点？ (满分:5)
A. 存储密度大
B. 插入和删除运算方便
C. 获取符合某种条件的元素方便
D. 查找运算速度快
E. 可以很方便地存取第i个元素
三、判断题：
1.对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。 (满分:2)
A. 错误
B. 正确
2.邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。 (满分:2)
A. 错误
B. 正确
3.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 (满分:2)
A. 错误
B. 正确
4.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。 (满分:2)
A. 错误
B. 正确
5.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。 (满分:2)
A. 错误
B. 正确
6.进行折半搜索的表必须是顺序存储的有序表。 (满分:2)
A. 错误
B. 正确
7.链式栈与顺序栈相比
一个明显的优点是通常不会出现栈满的情况。 (满分:2)
A. 错误
B. 正确
8.在线性链表中删除某个结点时，只需将被删结点释放。 (满分:2)
A. 错误
B. 正确
9.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 (满分:2)
A. 错误
B. 正确
10.线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。 (满分:2)
A. 错误
B. 正确
11.存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。 (满分:2)
A. 错误
B. 正确
12.一个广义表的表头总是一个广义表。 (满分:2)
A. 错误
B. 正确
13.线性表若采用链式存储表示
在删除时不需要移动元素。 (满分:2)
A. 错误
B. 正确
14.有回路的有向图不能完成拓扑排序。 (满分:2)
A. 错误
B. 正确
15.若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。 (满分:2)
A. 错误
B. 正确
转载请注明无忧答案网
在做作业，求解题参考资料。
页:
[1]