admin 管理员组文章数量: 1086019
2024年4月22日发(作者：unicode 解码)
一.单选题
（共44题,52.8分）
1
采用开放定址法处理散列表的冲突时,其平均查找长度( )。
•
A、
低于链接法处理冲突
•
B、
高于链接法处理冲突
•
C、
与链接法处理冲突相同
•
D、
高于二分查找
正确答案： B 我的答案：B得分： 1.2分
答案解析：
2
在二叉树结点的先序序列、中序序列和后序序列中,所有叶子结点的先后顺序( )。
•
A、
都不相同
•
B、
完全相同
•
C、
先序和中序相同,而与后序不同
•
D、
中序和后序相同,而与先序不同
正确答案： B 我的答案：B得分： 1.2分
答案解析：
3
对一个算法的评价,不包括如下( )方面的内容。
•
A、
健壮性和可读性
•
B、
并行性
•
C、
正确性
•
D、
时空复杂度
正确答案： B 我的答案：B得分： 1.2分
答案解析：
4
对于关键字序列(7,34,77,25,64,49,20,14)进行散列存储时,若选用H(K)=K%7作为散列函
数,则散列地址为0的元素有( )个。
•
A、
1
•
B、
2
•
C、
3
•
D、
4
正确答案： D 我的答案：得分： 0.0分
答案解析：
5
该二叉树有( )个叶子。
•
A、
3
•
B、
2
•
C、
5
•
D、
4
正确答案： A 我的答案：A得分： 1.2分
答案解析：
6
从二叉搜索树中查找一个元素时,其时间复杂度大致为( )。
•
A、
O(n)
•
B、
O(1)
C、
O(log
2
n)
D、
O(n
2
)
正确答案： C 我的答案：C得分： 1.2分
答案解析：
•
•
7
数据的基本单位是( )。
•
A、
数据项
•
B、
数据类型
•
C、
数据元素
•
D、
数据变量
正确答案： A 我的答案：A得分： 1.2分
答案解析：
8
设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。
•
A、
5
•
B、
6
•
C、
7
•
D、
8
正确答案： A 我的答案：A得分： 1.2分
答案解析：
9
对n个记录进行堆排序,所需要的辅助存储空间为( )。
A、
O(1og
2
n)
•
•
B、
O(n)
•
C、
O(1)
D、
O(n
2
)
正确答案： C 我的答案：C得分： 1.2分
答案解析：
•
10
设有一个二维数组A[m][n],假设A[0][0]存放位置在644,A[2][2]存放位置在676,每个元素
占一个空间,则A[3][3]存放位置在( )。
•
A、
688
•
B、
678
•
C、
692
•
D、
696
正确答案： C 我的答案：C得分： 1.2分
答案解析：
11
带有头结点的单循环链表的头指针为head,则该链表为空的判定条件是( )。
•
A、
head= =NULL
•
B、
head->next= =NULL
•
C、
head!=NULL
•
D、
head->next= =head
正确答案： D 我的答案：D得分： 1.2分
答案解析：
12
对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( )。
•
A、
(e,f)
•
B、
((e,f))
•
C、
(f)
•
D、
( )
正确答案： B 我的答案：B得分： 1.2分
答案解析：
13
由权值分别为3,8,6,2的叶子生成一棵哈夫曼树,它的带权路径长度为( )。
•
A、
11
•
B、
35
•
C、
19
•
D、
53
正确答案： B 我的答案：B得分： 1.2分
答案解析：
14
对线性表,在下列哪种情况下应当采用链表表示?( )
•
A、
经常需要随机地存取元素
•
B、
经常需要进行插入和删除操作
•
C、
表中元素需要占据一片连续的存储空间
•
D、
表中元素的个数不变
正确答案： B 我的答案：B得分： 1.2分
答案解析：
15
二维数组A[8][9]按行优先顺序存储,若数组元素A[2][3]的存储地址为1087,A[4][7]的存储
地址为1153,则数组元素A[6][7]的存储地址为( )。
•
A、
1207
•
B、
1209
•
C、
1211
•
D、
1213
正确答案： A 我的答案：A得分： 1.2分
答案解析：
16
对线性表进行二分法查找,其前提条件是( )。
•
A、
线性表以链接方式存储,并且按关键码值排好序
•
B、
线性表以顺序方式存储,并且按关键码值的检索频率排好序
•
C、
线性表以顺序方式存储,并且按关键码值排好序
•
D、
线性表以链接方式存储,并且按关键码值的检索频率排好序
正确答案： C 我的答案：C得分： 1.2分
答案解析：
17
一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是( )。
•
A、
2 3 1
•
B、
3 2 1
•
C、
3 1 2
•
D、
1 2 3
正确答案： C 我的答案：C得分： 1.2分
答案解析：
18
从L=((apple,pear),(orange,banana))中,取出banana元素的表达式为( )。
•
A、
head(tail(L))
•
B、
head(head(tail(L)))
•
C、
tail(head(tail(L)))
•
D、
head(tail(head(tail(L))))
正确答案： D 我的答案：D得分： 1.2分
答案解析：
19
设有关键码序列(q,g,m,z,a,n,p,x,h),下面的序列( )是从上述序列出发建堆的结果。
•
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
正确答案： B 我的答案：B得分： 1.2分
答案解析：
20
以下数据结构中哪一个是非线性结构?( )
•
A、
队列
•
B、
栈
•
C、
线性表
•
D、
二叉树
正确答案： D 我的答案：D得分： 1.2分
答案解析：
21
图所示二叉树结点的前序遍历的序列为( )。
•
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
•
•
正确答案： C 我的答案：C得分： 1.2分
22
AOV网是一种( )。
•
A、
有向图
•
B、
无向图
•
C、
无向无环图
•
D、
有向无环图
正确答案： D 我的答案：D得分： 1.2分
答案解析：
23
对关键字序列(56, 23, 78, 92, 88, 67, 19, 34)进行增量为3的一趟希尔排序的结果为( )。
•
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)
正确答案： D 我的答案：D得分： 1.2分
答案解析：
24
树最适合用来表示( )。
•
A、
有序数据元素
•
B、
无序数据元素
•
C、
元素之间具有分支层次关系的数据
•
D、
元素之间无联系的数据
正确答案： C 我的答案：C得分： 1.2分
答案解析：
25
在线性表的下列运算中,不改变数据元素之间的结构关系的运算是( )。
•
A、
插入
•
B、
删除
•
C、
排序
•
D、
查找
正确答案： D 我的答案：D得分： 1.2分
答案解析：
26
设Huffman树的叶子结点数为m,则结点总数为( )。
•
A、
2m
•
B、
2m-1
•
C、
2m+1
•
D、
m+1
正确答案： B 我的答案：B得分： 1.2分
答案解析：
27
有n个记录的文件,如关键字位数为d,基数为r,则基数排序共要进行( )遍分配与收集。
•
A、
n
•
B、
d
•
C、
r
•
D、
n - d
正确答案： B 我的答案：B得分： 1.2分
答案解析：
28
在数据结构中,数据元素可由( )。
•
A、
实体
•
B、
域
•
C、
数据项
•
D、
字段
正确答案： C 我的答案：C得分： 1.2分
答案解析：
29
中缀表达式2+X*(Y+3)的后缀形式是( )。
•
A、
3 Y X 2 + * +
•
B、
Y 3 + X * 2 +
•
C、
2 X Y 3 * + +
•
D、
2 X Y 3 + * +
正确答案： D 我的答案：C得分： 0.0分
答案解析：
30
在一个单链表HL中,若要在当前由指针p指向的结点后面插入一个由q指向的结点,则执行
如下( )语句序列。
•
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;
正确答案： D 我的答案：D得分： 1.2分
答案解析：
31
一散列表长度m为100,采用除留余数法构造散列函数,即H(K)=K%P (P<=m),,为使散列函
数具有较好的性能,P的选择应是( )。
•
A、
99
•
B、
100
•
C、
97
•
D、
93
正确答案： C 我的答案：C得分： 1.2分
答案解析：
32
队列的特点是( )。
•
A、
先进后出
•
B、
先进先出
•
C、
任意位置进出
•
D、
前面都不正确
正确答案： B 我的答案：B得分： 1.2分
答案解析：
33
若用邻接矩阵表示一个有向图,则其中每一列包含的″1″的个数为( )。
•
A、
图中每个顶点的入度
•
B、
图中每个顶点的出度
•
C、
图中每个顶点的度
•
D、
图中连通分量的数目
正确答案： A 我的答案：A得分： 1.2分
答案解析：
34
若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则
查找A[3]的比较序列的下标依次为( )。
•
A、
1,2,3
•
B、
9,5,2,3
•
C、
9,5,3
•
D、
9,4,2,3
正确答案： D 我的答案：D得分： 1.2分
答案解析：
35
在一个带有附加表头结点的单链表HL中,若要向表头插入一个由指针p指向的结点,则执行
( )。
•
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;
正确答案： B 我的答案：D得分： 0.0分
答案解析：
36
以下21-23题基于下面的叙述：若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、
G，后序遍历的序列为B、D、C、A、F、G、E。
则该二叉树结点的前序遍历的序列为( )。
•
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
•
•
正确答案： C 我的答案：C得分： 1.2分
37
该二叉树的按层遍历的序列为( )。
•
A、
E、G、F、A、C、D、B
•
•
•
B、
E、A、C、B、D、G、F
•
•
•
C、
E、A、G、C、F、B、D
•
•
•
D、
E、G、A、C、D、F、B
•
•
正确答案： C 我的答案：C得分： 1.2分
38
如表r有100000个元素,前99999个元素递增有序,则采用( )方法比较次数较少。
•
A、
直接插入排序
•
B、
快速排序
•
C、
归并排序
•
D、
选择排序
正确答案： A 我的答案：A得分： 1.2分
答案解析：
39
若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则最节
省运算时间的存储方式是( )。
•
A、
单链表
•
B、
仅有头指针的单循环链表
•
C、
双链表
•
D、
仅有尾指针的单循环链表
正确答案： D 我的答案：D得分： 1.2分
答案解析：
40
对一棵有100个结点的完全二叉树按层编号,根结点编号为1,则编号为49的结点的父结点
的编号为( )。
•
A、
24
•
B、
25
•
C、
98
•
D、
99
正确答案： A 我的答案：A得分： 1.2分
答案解析：
41
若有序表为(b, c, d, e, f, g, q, r, s, t),则在二分查找关键字b的过程中,先后进行比较的关键
字依次为( )。
•
A、
f,c,b
•
B、
f,d,b
•
C、
g,c,b
•
D、
g,d,b
正确答案： A 我的答案：A得分： 1.2分
答案解析：
42
下面关于图的存储的叙述中正确的是( )。
•
A、
用邻接表法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关。
•
B、
用邻接表法存储图,占用的存储空间大小与图中边数和结点个数都有关。
•
C、
用邻接矩阵法存储图,占用的存储空间大小与图中结点个数和边数都有关。
•
D、
用邻接矩阵法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关。
正确答案： B 我的答案：B得分： 1.2分
答案解析：
43
从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动的元素个数是( )。
•
A、
n-i
•
B、
n-i+1
•
C、
n-i-1
•
D、
i
正确答案： A 我的答案：A得分： 1.2分
答案解析：
44
对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K % 9作为散列函数,则
散列地址为1的元素有( )个。
•
A、
1
•
B、
2
•
C、
3
•
D、
4
正确答案： D 我的答案：D得分： 1.2分
答案解析：
二.多选题
（共5题,6.0分）
1
以下序列中,是堆(大顶堆或小顶堆)的有( )。
•
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}
正确答案： ACDE 我的答案：得分： 0.0分
答案解析：
2
以下哪些是队列的基本运算?( )
•
A、
在队列第i个元素之后插入一个元素
•
B、
从队头删除一个元素
•
C、
判断一个队列是否为空
•
D、
读取队头元素的值
•
E、
将队列中的元素排序
正确答案： BCD 我的答案：得分： 0.0分
答案解析：
3
栈和队列的共同特点是( )。
•
A、
只允许在端点处插入和删除元素
•
B、
都是先进后出
•
C、
都是先进先出
•
D、
没有共同点
•
E、
都可以采用顺序存储方式和链式存储方式
正确答案： AE 我的答案：得分： 0.0分
答案解析：
4
以下数据结构中哪一个是线性结构?( )
•
A、
有向图
•
B、
队列
•
C、
线索二叉树
•
D、
线性表
•
E、
栈
正确答案： BDE 我的答案：得分： 0.0分
答案解析：
5
对一个算法的评价,主要包括如下( )方面的内容。
•
A、
健壮性和可读性
•
B、
并行性
•
C、
正确性
•
D、
时空复杂度
•
E、
界面友好性
正确答案： ACD 我的答案：得分： 0.0分
答案解析：
三.判断题
（共31题,41.2分）
1
为度量一个搜索算法的效率,需要在时间和空间两个方面进行分析。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
2
在顺序表中,逻辑上相邻的元素在物理位置上不一定相邻。
我的答案：
×
得分： 1.2分正确答案：
×
答案解析：
3
二维数组是数组元素为一维数组的线性表,因此二维数组元素之间是线性结构。
我的答案：
×
得分： 1.2分正确答案：
×
答案解析：
4
线性表若采用链式存储表示, 在删除时不需要移动元素。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
5
线性表的长度是线性表所占用的存储空间的大小。
我的答案：
×
得分： 1.2分正确答案：
×
答案解析：
6
用边表示活动的网络（AOE网）的关键路径是指从源点到终点的路径长度最长的路径。
我的答案：
√
得分： 1.2分正确答案：
√
7
用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中的顶
点个数有关,而与图的边数无关。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
8
邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶
点数的平方）。
我的答案：
√
得分： 1.2分正确答案：
√
9
在一棵二叉树中,假定每个结点只有左子女,没有右子女,对它分别进行前序遍历和后序遍历,
则具有相同的结果。
我的答案：
×
得分： 1.2分正确答案：
×
答案解析：
10
已知指针P指向链表L中的某结点,执行语句P:=P®NEXT不会删除该链表中的结点。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
11
若仅知道某二叉树的中序遍历序列和后序遍历序列,则不能够确定此二叉树的层次遍历的序
列。
我的答案：
×
得分： 1.2分正确答案：
×
答案解析：
12
在用循环单链表表示的链式队列中,可以不设队头指针,仅在链尾设置队尾指针。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
13
邻接表只能用于有向图的存储,邻接矩阵对于有向图和无向图的存储都适用。
我的答案：
×
得分： 1.2分正确答案：
×
答案解析：
14
进行折半搜索的表必须是顺序存储的有序表。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
15
一个广义表((a),((b),c),(((d)))) 的表尾是((b),c),(((d)))。
我的答案：
√
得分： 0.0分正确答案：
×
16
装载因子是散列表的一个重要参数,它反映了散列表的装满程度。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
17
链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
18
在采用线性探测法处理冲突的哈希表中,所有同义词在表中相邻。
我的答案：
×
得分： 1.2分正确答案：
×
答案解析：
19
线性表若采用链式存储表示时,其存储结点的地址可连续也可不连续。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
20
快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
21
若一棵二叉树的任一非叶子结点的度为2,则该二叉树为满二叉树。
我的答案：
×
得分： 1.2分正确答案：
×
答案解析：
22
顺序表用一维数组作为存储结构,因此顺序表是一维数组。
我的答案：
×
得分： 1.2分正确答案：
×
答案解析：
23
栈和队列都是顺序存取的线性表,但它们对存取位置的限制不同。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
24
有回路的有向图不能完成拓扑排序。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
25
使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
26
在线性链表中删除某个结点时,只需将被删结点释放。
我的答案：
×
得分： 1.2分正确答案：
×
答案解析：
27
一个广义表的表头总是一个广义表。
我的答案：
×
得分： 1.2分正确答案：
×
答案解析：
28
堆排序是一种稳定的排序算法。
我的答案：
×
得分： 1.2分正确答案：
×
答案解析：
29
数据的逻辑结构是指各数据元素之间的逻辑关系,是用户根据应用需要建立的。
我的答案：
√
得分： 1.2分正确答案：
√
答案解析：
30
存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。
我的答案：
√
得分： 1.2分正确答案：
√
31
对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。
我的答案：
×
得分： 5.2分正确答案：
×
版权声明：本文标题：四川大学2021计算数据结构考试题2(含答案100分) 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1713786532a651465.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论