贵州2025自考[计算机科学]数据结构易错题专练.docxVIP

第PAGE页共NUMPAGES页

贵州2025自考[计算机科学与技术]数据结构易错题专练

一、单项选择题（每题2分，共20题）

1.在线性表中进行插入和删除操作时，效率最高的存储结构是（）。

A.顺序表

B.链表

C.数组

D.哈希表

2.若线性表L的长度为n，则删除L中第i个元素（1≤i≤n）时，需要向前移动的元素个数为（）。

A.n

B.n-i

C.i-1

D.i

3.下列关于栈的描述中，错误的是（）。

A.栈是先进后出的线性表

B.栈具有记忆性

C.栈只能在一端进行插入或删除操作

D.栈可以用于表达式求值

4.在队列中，进行插入操作的端称为（）。

A.队头

B.队尾

C.根节点

D.叶节点

5.一个栈的输入序列为1,2,3,4,5，输出的序列为3,5,4,2,1，则栈的最大容量为（）。

A.2

B.3

C.4

D.5

6.下列关于队列的描述中，正确的是（）。

A.队列是先进先出的线性表

B.队列是后进先出的线性表

C.队列具有记忆性

D.队列只能在一端进行插入或删除操作

7.在树形结构中，一个节点的子节点个数称为（）。

A.树的深度

B.树的度

C.树的宽度

D.树的路径

8.深度为k的满二叉树共有（）。

A.2^k-1个节点

B.2^k个节点

C.k2-1个节点

D.k2个节点

9.在二叉有哪些信誉好的足球投注网站树中，对于任何节点，其左子树中的所有节点的值均小于该节点的值，其右子树中的所有节点的值均大于该节点的值，该性质称为（）。

A.完全二叉树性质

B.满二叉树性质

C.二叉有哪些信誉好的足球投注网站树性质

D.平衡二叉树性质

10.在哈希表中，解决冲突的常用方法有（）。

A.开放定址法

B.链地址法

C.双哈希法

D.以上都是

二、填空题（每空2分，共10空）

1.线性表有两种存储结构：__________和__________。

2.栈的两种基本操作是__________和__________。

3.队列的两种基本操作是__________和__________。

4.在树形结构中，根节点的度称为__________。

5.在二叉有哪些信誉好的足球投注网站树中，对于任何节点，其左子树中的所有节点的值均__________该节点的值，其右子树中的所有节点的值均__________该节点的值。

6.哈希表的冲突解决方法主要有__________和__________。

7.一个深度为5的满二叉树共有__________个节点。

8.在哈希表中，装填因子α的定义为__________。

9.在链表中，插入或删除操作的时间复杂度为__________。

10.在树形结构中，叶节点的度为__________。

三、简答题（每题5分，共5题）

1.简述栈和队列的区别。

2.简述线性表和树的区别。

3.简述哈希表的工作原理。

4.简述二叉有哪些信誉好的足球投注网站树的性质。

5.简述满二叉树和完全二叉树的区别。

四、应用题（每题10分，共3题）

1.已知一个栈的输入序列为1,2,3,4,5，请写出其可能的所有输出序列。

2.已知一个二叉有哪些信誉好的足球投注网站树的部分节点如下：

5

/\

37

/\\

248

请画出该二叉有哪些信誉好的足球投注网站树，并写出其前序遍历、中序遍历和后序遍历的结果。

3.已知一个哈希表的大小为10，哈希函数为H(key)=key%10，解决冲突的方法为链地址法，请画出插入以下键值后的哈希表：32,15,28,5,47。

答案与解析

一、单项选择题

1.B

解析：链表在插入和删除操作时不需要移动元素，效率高于顺序表和数组；哈希表虽然效率高，但不是线性表。

2.B

解析：删除第i个元素时，需要将i后面的元素向前移动一个位置。

3.D

解析：栈可以用于表达式求值，但不是唯一的应用场景；栈的其他性质均正确。

4.B

解析：队列的插入操作在队尾进行。

5.C

解析：输出序列为3,5,4,2,1，说明栈的最大容量为4（3入栈，3出栈，5入栈，5出栈，4入栈，4出栈，2入栈，2出栈，1入栈，1出栈）。

6.A

解析：队列是先进先出的线性表。

7.B

解析：节点的子节点个数称为树的度。

8.A

解析：满二叉树的节点数为2^k-1。

9.C

解析：二叉有哪些信誉好的足球投注网站树的性质是左子树所有节点值小于根节点值，右子树所有节点值大于根节点值。

10.D

解析：哈希表的冲突解决方法包括开放定址法、链地址法、双哈希法等。

二、填空题

1.顺序存储结构，链式存储结构

2.入栈，出栈

3.入队，出队

4.根节点的度

5.小于，大于

6.开放定址法，链地址法

7.31

8.哈希表中已存储的键值个数除以哈希表的大小

9.O(1)

10.0

三、简答