川大《数据结构(1)》17秋在线作业12
《数据结构(1)》17秋在线作业1一、单选题：
1.在一个带有附加表头结点的单链表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;
2.中缀表达式2+X*(Y+3)的后缀形式是（ ）。 (满分:2)
A.3YX2+*+
B.Y3+X*2+
C.2XY3*++
D.2XY3+*+
3.一散列表长度m为100，采用除留余数法构造散列函数，即H(K)=K%P (P<=m),，为使散列函数具有较好的性能，P的选择应是（ ）。 (满分:2)
A.99
B.100
C.97
D.93
4.对线性表，在下列哪种情况下应当采用链表表示？ (满分:2)
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间
D.表中元素的个数不变
5.数据的基本单位是（ ）。 (满分:2)
A.数据项
B.数据类型
C.数据元素
D.数据变量
6.以下数据结构中哪一个是非线性结构？ (满分:2)
A.队列
B.栈
C.线性表
D.二叉树
7.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ ）。 (满分:2)
A.单链表
B.仅有头指针的单循环链表
C.双链表
D.仅有尾指针的单循环链表
8.下列关于数据结构的叙述中，正确的是（ ）。 (满分:2)
A.数组是不同类型值的集合
B.递归算法的程序结构比迭代算法的程序结构更为精炼
C.树是一种线性结构
D.用一维数组存储一棵完全二叉树是有效的存储方法
9.在一个单链表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;
10.对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为（ ）。 (满分:2)
A.24
B.25
C.98
D.99
11.如表r有100000个元素，前99999个元素递增有序，则采用（ ）方法比较次数较少。 (满分:2)
A.直接插入排序
B.快速排序
C.归并排序
D.选择排序
12.已知一个图的顶点集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
13.二维数组A按行优先顺序存储，若数组元素A的存储地址为1087，A的存储地址为1153，则数组元素A的存储地址为（ ）。 (满分:2)
A.1207
B.1209
C.1211
D.1213
14.含有10个结点的二叉树中，度为0的结点数为4，则度为2的点数为（ ）。 (满分:2)
A.3
B.4
C.5
D.6
15.设有一个二维数组A，假设A存放位置在644，A存放位置在676，每个元素占一个空间，则A存放位置在（ ）。 (满分:2)
A.688
B.678
C.692
D.696
16.从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。 (满分:2)
A.O(n)
B.O(1)
C.O(log<sub>2</sub>n)
D.O(n<sup>2</sup>)
17.树最适合用来表示（ ）。 (满分:2)
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
18.在线性表的下列运算中，不改变数据元素之间的结构关系的运算是（ ）。 (满分:2)
A.插入
B.删除
C.排序
D.查找
19.对一个算法的评价，不包括如下（ ）方面的内容。 (满分:2)
A.健壮性和可读性
B.并行性
C.正确性
D.时空复杂度
20.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素个数是（ ）。 (满分:2)
A.n-i
B.n-i+1
C.n-i-1
D.i
21.对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是（ ）。 (满分:2)
A.(e,f)
B.((e,f))
C.(f)
D.( )
22.在数据结构中，数据元素可由（ ）。 (满分:2)
A.实体
B.域
C.数据项
D.字段
23.下面关于广义表的叙述中，不正确的是（ ）。 (满分:2)
A.广义表可以是一个多层次的结构
B.广义表至少有一个元素
C.广义表可以被其他广义表所共享
D.广义表可以是一个递归表
24.AOV网是一种（ ）。 (满分:2)
A.有向图
B.无向图
C.无向无环图
D.有向无环图
25.若某二叉树结点的中序遍历的序列为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
二、多选题：
26.以下数据结构中哪一个是线性结构？ (满分:5)
A.有向图
B.队列
C.线索二叉树
D.线性表
E.栈
27.<p><span style=\\\FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA\\\>下面的二叉树中，是完全二叉树的有（ ）。</span></p><p><span style=\\\FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA\\\><img width=\\\460\\\ height=\\\125\\\ alt=\\\\\\ src=\\\http://file.open.com.cn/ItemDB/119293/b2268822-d1d3-4a2b-8c1c-10e6a37ec363/2016119153724740.jpg\\\ /></span></p> (满分:5)
A.A
B.B
C.C
D.D
28.以下哪些是队列的基本运算？ (满分:5)
A.在队列第i个元素之后插入一个元素
B.从队头删除一个元素
C.判断一个队列是否为空
D.读取队头元素的值(E)将队列中的元素排序
29.栈和队列的共同特点是（ ）。 (满分:5)
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
E.都可以采用顺序存储方式和链式存储方式
三、判断题：
30.用字符数组存储长度为n的字符串，数组长度至少为n+1。 (满分:2)
A.错误
B.正确
31.为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。 (满分:2)
A.错误
B.正确
32.二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。 (满分:2)
A.错误
B.正确
33.对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。 (满分:2)
A.错误
B.正确
34.线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。 (满分:2)
A.错误
B.正确
35.若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。 (满分:2)
A.错误
B.正确
36.顺序表用一维数组作为存储结构，因此顺序表是一维数组。 (满分:2)
A.错误
B.正确
37.一个广义表的表头总是一个广义表。 (满分:2)
A.错误
B.正确
38.线性表的长度是线性表所占用的存储空间的大小。 (满分:2)
A.错误
B.正确
39.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。 (满分:2)
A.错误
B.正确
40.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 (满分:2)
A.错误
B.正确
41.在采用线性探测法处理冲突的哈希表中，所有同义词在表中相邻。 (满分:2)
A.错误
B.正确
42.有回路的有向图不能完成拓扑排序。 (满分:2)
A.错误
B.正确
43.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。 (满分:2)
A.错误
B.正确
44.栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。 (满分:2)
A.错误
B.正确
《数据结构(1)》17秋在线作业2
一、单选题：
1.若有18个元素的有序表存放在一维数组A中，第一个元素放A中，现进行二分查找，则查找A的比较序列的下标依次为（ ）。 (满分:2)
A.1，2，3
B.9，5，2，3
C.9，5，3
D.9，4，2，3
2.在数据结构中，数据元素可由（ ）。 (满分:2)
A.实体
B.域
C.数据项
D.字段
3.设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。 (满分:2)
A.5
B.6
C.7
D.8
4.假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（ ）次探测。 (满分:2)
A.K-1次
B.K次
C.K＋l次
D.K(K+1)/2次
5.中缀表达式2+X*(Y+3)的后缀形式是（ ）。 (满分:2)
A.3YX2+*+
B.Y3+X*2+
C.2XY3*++
D.2XY3+*+
6.一散列表长度m为100，采用除留余数法构造散列函数，即H(K)=K%P (P<=m),，为使散列函数具有较好的性能，P的选择应是（ ）。 (满分:2)
A.99
B.100
C.97
D.93
7.设有关键码序列(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
8.对线性表进行二分法查找，其前提条件是（ ）。 (满分:2)
A.线性表以链接方式存储，并且按关键码值排好序
B.线性表以顺序方式存储，并且按关键码值的检索频率排好序
C.线性表以顺序方式存储，并且按关键码值排好序
D.线性表以链接方式存储，并且按关键码值的检索频率排好序
9.二维数组A按行优先顺序存储，若数组元素A的存储地址为1087，A的存储地址为1153，则数组元素A的存储地址为（ ）。 (满分:2)
A.1207
B.1209
C.1211
D.1213
10.已知一个图的顶点集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
11.如表r有100000个元素，前99999个元素递增有序，则采用（ ）方法比较次数较少。 (满分:2)
A.直接插入排序
B.快速排序
C.归并排序
D.选择排序
12.以下数据结构中哪一个是非线性结构？ (满分:2)
A.队列
B.栈
C.线性表
D.二叉树
13.对关键字序列(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)
14.下列关于数据结构的叙述中，正确的是（ ）。 (满分:2)
A.数组是不同类型值的集合
B.递归算法的程序结构比迭代算法的程序结构更为精炼
C.树是一种线性结构
D.用一维数组存储一棵完全二叉树是有效的存储方法
15.对一个算法的评价，不包括如下（ ）方面的内容。 (满分:2)
A.健壮性和可读性
B.并行性
C.正确性
D.时空复杂度
16.在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（ ）。 (满分:2)
A.i
B.i+1
C.n-i
D.n-i+1
17.下面关于图的存储的叙述中正确的是（ ）。 (满分:2)
A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。
C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
18.队列的特点是（ ）。 (满分:2)
A.先进后出
B.先进先出
C.任意位置进出
D.前面都不正确
19.含有10个结点的二叉树中，度为0的结点数为4，则度为2的点数为（ ）。 (满分:2)
A.3
B.4
C.5
D.6
20.在线性表的下列运算中，不改变数据元素之间的结构关系的运算是（ ）。 (满分:2)
A.插入
B.删除
C.排序
D.查找
21.对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是（ ）。 (满分:2)
A.(e,f)
B.((e,f))
C.(f)
D.( )
22.在一个带有附加表头结点的单链表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;
23.设Huffman树的叶子结点数为m，则结点总数为（ ）。 (满分:2)
A.2m
B.2m-1
C.2m+1
D.m+1
24.对n个记录进行堆排序，所需要的辅助存储空间为（ ）。 (满分:2)
A.<p>O（1og<sub>2</sub>n）</p>
B.O（n）
C.O（1）
D.O(n<sup>2</sup>)
25.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（ ）。 (满分:2)
A.m-n-1
B.n+1
C.m-n+1
D.m-n
二、多选题：
26.<p><span style=\\\FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA\\\>下面的二叉树中，是完全二叉树的有（ ）。</span></p><p><span style=\\\FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA\\\><img width=\\\460\\\ height=\\\125\\\ alt=\\\\\\ src=\\\http://file.open.com.cn/ItemDB/119293/b2268822-d1d3-4a2b-8c1c-10e6a37ec363/2016119153724740.jpg\\\ /></span></p> (满分:5)
A.A
B.B
C.C
D.D
27.以下数据结构中哪一个是线性结构？ (满分:5)
A.有向图
B.队列
C.线索二叉树
D.线性表
E.栈
28.栈和队列的共同特点是（ ）。 (满分:5)
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
E.都可以采用顺序存储方式和链式存储方式
29.下述哪些是顺序存储方式的优点？ (满分:5)
A.存储密度大
B.插入和删除运算方便
C.获取符合某种条件的元素方便
D.查找运算速度快
E.可以很方便地存取第i个元素
三、判断题：
30.顺序表用一维数组作为存储结构，因此顺序表是一维数组。 (满分:2)
A.错误
B.正确
31.线性表的长度是线性表所占用的存储空间的大小。 (满分:2)
A.错误
B.正确
32.线性表若采用链式存储表示, 在删除时不需要移动元素。 (满分:2)
A.错误
B.正确
33.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 (满分:2)
A.错误
B.正确
34.进行折半搜索的表必须是顺序存储的有序表。 (满分:2)
A.错误
B.正确
35.一个广义表的表头总是一个广义表。 (满分:2)
A.错误
B.正确
36.在采用线性探测法处理冲突的哈希表中，所有同义词在表中相邻。 (满分:2)
A.错误
B.正确
37.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 (满分:2)
A.错误
B.正确
38.链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。 (满分:2)
A.错误
B.正确
39.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。 (满分:2)
A.错误
B.正确
40.一个广义表((a),((b),c),(((d)))) 的表尾是((b),c),(((d)))。 (满分:2)
A.错误
B.正确
41.图G的某一最小生成树的代价一定小于其他生成树的代价。 (满分:2)
A.错误
B.正确
42.若仅知道某二叉树的中序遍历序列和后序遍历序列，则不能够确定此二叉树的层次遍历的序列。 (满分:2)
A.错误
B.正确
43.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。 (满分:2)
A.错误
B.正确
44.邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。 (满分:2)
A.错误
B.正确
页:
[1]