川大《数据结构2264》17秋在线作业12题目
《数据结构2264》17秋在线作业1一、单选题：
1.在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（ ）。 (满分:2) A.i
B.i+1
C.n-i D.n-i+1
2.数据的基本单位是（ ）。 (满分:2)
A.数据项
B.数据类型
C.数据元素
D.数据变量
3.对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为（ ）。 (满分:2)
A.24
B.5
C.98
D.99
4.在数据结构中，数据元素可由（ ）。 (满分:2)
A.实体
B.域
C.数据项
D.字段
5.若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。\\n则该二叉树结点的前序遍历的序列为（ ）。 (满分: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
6.队列的特点是（ ）。 (满分:2)
A.先进后出
B.先进先出
C.任意位置进出
D.前面都不正确
7.二维数组A按行优先顺序存储，若数组元素A的存储地址为1087，A的存储地址为1153，则数组元素A的存储地址为（ ）。 (满分:2)
A.1207
B.1209
C.1211
D.1213
8.若有序表为（ ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（ ）。 (满分:2)
A.f,c,b
B.f,d,b
C.g,c,b
D.g,d,b
9.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ ） (满分:2)
A.都不相同
B.完全相同
C.先序和中序相同，而与后序不同
D.中序和后序相同，而与先序不同
10.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ ）。 (满分:2)
A.2 3 1
B.3 2 1
C.3 1 2
D.1 2 3
11.设有一个二维数组A （ ），假设A存放位置在600，A存放位置在678，每个元素占一个空间，则A的存放位置是（ ）。 (满分:2)
A.658
B.648
C.633
D.653
12.从一个长度为n的顺序表中删除第i个元素（ ）时，需向前移动的元素个数是（ ）。 (满分:2)
A.n-i
B.n-i+1
C.n-i-1
D.i
13.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（ ）。 (满分:2)
A.11
B.35
C.19
D.53
14.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ ）。 (满分:2)
A.单链表
B.仅有头指针的单循环链表
C.双链表
D.仅有尾指针的单循环链表
15.在一个单链表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;
16.假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（ ）次探测。 (满分:2)
A.K-1次
B.K次
C.K＋l次
D.K(K+1)/2次
17.带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（ ）。 (满分:2)
A.head= =NUL
B.head->next= =NULL
C.head!=NULL
D.head->next= =head
18.对线性表，在下列哪种情况下应当采用链表表示？（ ） (满分:2)
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间
D.表中元素的个数不变
19.有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（ ）遍分配与收集。 (满分:2)
A.n
B.d
C.r
D.n - d
20.设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。 (满分:2)
A.5
B.6
C.7
D.8
21.一散列表长度m为100，采用除留余数法构造散列函数，即H（ ）=K%P （ ）,，为使散列函数具有较好的性能，P的选择应是（ ）。 (满分:2)
A.99
B.100
C.97
D.93
22.设Huffman树的叶子结点数为m，则结点总数为（ ）。 (满分:2)
A.2m
B.2m-1
C.2m+1
D.m+1
23.对于线性表（ ）进行散列存储时，若选用H（ ）=K % 9作为散列函数，则散列地址为1的元素有（ ）个。 (满分:2)
A.1
B.2
C.3
D.4
24.从L=（ ）,（ ）)中，取出banana元素的表达式为（ ）。 (满分:2)
A.head(tail(L))
B.head(head(tail(L)))
C.tail(head(tail(L)))
D.head(tail(head(tail(L))))
25.以下数据结构中哪一个是非线性结构？（ ） (满分:2)
A.队列
B.栈
C.线性表
D.二叉树
二、多选题：
26.若进栈序列为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
27.栈和队列的共同特点是（ ）。 (满分:5)
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
E.都可以采用顺序存储方式和链式存储方式
28.以下序列中，是堆（ ）的有（ ）。 (满分: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}
29.以下哪些是队列的基本运算？（ ） (满分:5)
A.在队列第i个元素之后插入一个元素
B.从队头删除一个元素
C.判断一个队列是否为空
D.读取队头元素的值
E.将队列中的元素排序
三、判断题：
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，则该二叉树为满二叉树。 (满分:2)
A.错误
B.正确
37.一个广义表（ ）,（ ）,c),（ ）))) 的表尾是（ ）,c),（ ）))。 (满分: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.正确
《数据结构2264》17秋在线作业2
一、单选题：
1.AOV网是一种（ ）。 (满分:2)
A.有向图
B.无向图
C.无向无环图
D.有向无环图
2.含有10个结点的二叉树中，度为0的结点数为4，则度为2的点数为（ ）。 (满分:2)
A.3
B.4
C.5
D.6
3.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ ）。 (满分:2)
A.单链表
B.仅有头指针的单循环链表
C.双链表
D.仅有尾指针的单循环链表
4.若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ ）。 (满分:2)
A.图中每个顶点的入度
B.图中每个顶点的出度
C.图中每个顶点的度
D.图中连通分量的数目
5.对广义表L=（ ）,（ ）,（ ）执行操作tail（ ）的结果是（ ）。 (满分:2)
A.(e,f)
B.((e,f))
C.(f)
D.( )
6.对线性表，在下列哪种情况下应当采用链表表示？（ ） (满分:2)
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间
D.表中元素的个数不变
7.对n个记录进行堆排序，所需要的辅助存储空间为（ ）。 (满分:2)
A.O（1og2n
B.O（n）
C.O（1）
D.O（n2）
8.对于关键字序列（ ）进行散列存储时，若选用H（ ）=K%7作为散列函数，则散列地址为0的元素有（ ）个。 (满分:2)
A.1
B.2
C.3
D.4
9.对线性表进行二分法查找，其前提条件是（ ）。 (满分:2)
A.线性表以链接方式存储，并且按关键码值排好序
B.线性表以顺序方式存储，并且按关键码值的检索频率排好序
C.线性表以顺序方式存储，并且按关键码值排好序
D.线性表以链接方式存储，并且按关键码值的检索频率排好序
10.在一个单链表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;
11.队列的特点是（ ）。 (满分:2)
A.先进后出
B.先进先出
C.任意位置进出
D.前面都不正确
12.在数据结构中，数据元素可由（ ）。 (满分:2)
A.实体
B.域
C.数据项
D.字段
13.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ ）。 (满分:2)
A.2 3 1
B.3 2 1
C.3 1 2
D.1 2 3
14.对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为（ ）。 (满分:2)
A.24
B.5
C.98
D.99
15.二维数组A按行优先顺序存储，若数组元素A的存储地址为1087，A的存储地址为1153，则数组元素A的存储地址为（ ）。 (满分:2)
A.1207
B.1209
C.1211
D.1213
16.设Huffman树的叶子结点数为m，则结点总数为（ ）。 (满分:2)
A.2m
B.2m-1
C.2m+1
D.m+1
17.在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（ ）。 (满分:2)
A.i
B.i+1
C.n-i
D.n-i+1
18.有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（ ）遍分配与收集。 (满分:2)
A.n
B.d
C.r
D.n - d
19.数据的基本单位是（ ）。 (满分:2)
A.数据项
B.数据类型
C.数据元素
D.数据变量
20.采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。 (满分:2)
A.低于链接法处理冲突
B.高于链接法处理冲突
C.与链接法处理冲突相同
D.高于二分查找
21.设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。 (满分:2)
A.5
B.6
C.7
D.8
22.下列关于数据结构的叙述中，正确的是（ ）。 (满分:2)
A.数组是不同类型值的集合
B.递归算法的程序结构比迭代算法的程序结构更为精炼
C.树是一种线性结构
D.用一维数组存储一棵完全二叉树是有效的存储方法
23.对于线性表（ ）进行散列存储时，若选用H（ ）=K % 9作为散列函数，则散列地址为1的元素有（ ）个。 (满分:2)
A.1
B.2
C.3
D.4
24.在一个带有附加表头结点的单链表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;
25.对关键字序列（ ）进行增量为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)
二、多选题：
26.下述（ ）是顺序存储方式的优点。 (满分:5)
A.存储密度大
B.插入和删除运算方便
C.获取符合某种条件的元素方便
D.查找运算速度快
E.可以很方便地存取第i个元素
27.栈和队列的共同特点是（ ）。 (满分:5)
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
E.都可以采用顺序存储方式和链式存储方式
28.若进栈序列为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
29.以下序列中，是堆（ ）的有（ ）。 (满分: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}
三、判断题：
30.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。 (满分:2)
A.错误
B.正确
31.顺序表用一维数组作为存储结构，因此顺序表是一维数组。 (满分:2)
A.错误
B.正确
32.有回路的有向图不能完成拓扑排序。 (满分:2)
A.错误
B.正确
33.已知指针P指向链表L中的某结点，执行语句P：=P?NEXT不会删除该链表中的结点。 (满分:2)
A.错误
B.正确
34.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 (满分:2)
A.错误
B.正确
35.一个广义表（ ）,（ ）,c),（ ）))) 的表尾是（ ）,c),（ ）))。 (满分: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]