数据结构期末考试试题及答案

数据结构期末考试试题及答案一、单项选择题（每小题1分，共20分）下列各题A、B、C、D四个选项中只有一个正确答案，将正确选项的标号填在答题纸相应位置。

1.下列术语中，属于数据逻辑结构的是（）

A.顺序表B.哈希表C.有序表D.单链表

2.在长度为n的顺序表中第i个位置（1≤i≤n+1）插入一个新元素，算法的平均时间复杂度是（）

A.O(1)B.O(n)C.O(n²)D.O(logn)

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

A.栈是先进后出的线性表B.栈可用于表达式求值问题C.递归过程的实现需要用到栈D.栈只能采用顺序存储结构

4.某循环队列采用数组存储，数组长度为m，约定队头指针front指向队头元素的位置，队尾指针rear指向队尾元素的下一个存储位置，则判断队满的条件是（）

A.rear==frontB.(rear+1)%m==frontC.(front+1)%m==rearD.rear==m

5.主串为“ababcabcacbab”，模式串为“ababaa”，按照KMP算法的next数组定义（next[0]=-1），该模式串的next数组值为（）

A.-1,0,0,1,2,3B.-1,0,1,1,2,3C.-1,0,1,2,3,0D.-1,0,0,1,2,2

6.二维数组A[10][10]按行优先顺序存储，每个元素占2个存储单元，若已知A[0][0]的存储地址为100，则元素A[3][4]的存储地址为（）

A.154B.166C.168D.172

7.深度为k的完全二叉树，最少包含的结点个数是（）

A.2ᵏ-1B.2ᵏ⁻¹-1C.2ᵏD.2ᵏ⁻¹

8.某二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则该二叉树的后序遍历序列为（）

A.CBEFDAB.CBFEDAC.FEDCBAD.不确定

9.平衡二叉树插入结点后，若在根结点的左子树的左子树上插入结点导致不平衡，需要进行的旋转操作是（）

A.单次左旋B.单次右旋C.先左后右双向旋转D.先右后左双向旋转

10.下列关于哈夫曼树的描述中，错误的是（）

A.哈夫曼树是带权路径长度最小的二叉树B.哈夫曼树中没有度为1的结点C.一棵哈夫曼树中，n个叶子结点的总结点数是2n-1D.哈夫曼树一定是满二叉树

11.下列关于有向图邻接矩阵存储的描述中，正确的是（）

A.邻接矩阵一定是对称矩阵B.邻接矩阵中第i行非零元素的个数等于顶点i的出度C.邻接矩阵中第i列非零元素的个数等于顶点i的出度D.存储所需的空间大小只和顶点数无关，和边数有关

12.图的广度优先搜索遍历算法中，需要用到的辅助数据结构是（）

A.栈B.队列C.树D.哈希表

13.若一个有8个顶点的无向连通图是一棵树，该图包含的边数最少是（）

A.6B.7C.8D.9

14.对长度为14的有序顺序表进行折半查找，查找失败时最多需要比较的次数是（）

A.3B.4C.5D.6

15.下列方法中，不属于散列表冲突处理方法的是（）

A.链地址法B.开放定址法C.除留余数法D.二次探测法

16.二叉排序树查找的最坏时间复杂度是（）

A.O(1)B.O(logn)C.O(n)D.O(nlogn)

17.下列排序算法中，属于不稳定排序的是（）

A.冒泡排序B.直接插入排序C.归并排序D.堆排序

18.快速排序算法在下列哪种情况下执行效率最高（）

A.待排序序列基本有序B.待排序序列完全逆序C.每次划分后得到的两个子序列长度大致相等D.待排序序列中元素值全部相等

19.下列排序算法中，空间复杂度为O(1)的是（）

A.快速排序B.堆排序C.归并排序D.基数排序

20.对于n个结点的序列，建初始堆的时间复杂度是（）

A.O(logn)B.O(n)C.O(nlogn)D.O(n²)

二、多项选择题（每小题3分，共15分）下列各题五个选项中有至少两个正确答案，多选、少选、错选均不得分，将正确选项的标号填在答题纸相应位置。

1.下列属于线性结构的数据结构有（）

A.栈B.队列C.串D.二叉树E.树

2.下列关于栈和队列的描述中，正确的有（）

A.栈和队列都是操作受限的线性表B.栈和队列既可以顺序存储，也可以链式存储C.栈的特点是先进后出，队列的特点是先进先出D.栈只允许在栈顶插入和删除元素E.队列允许在队头插入、队尾删除元素

3.下列关于二叉树性质的描述中，正确的有（）

A.在非空二叉树中，度为0的结点数比度为2的结点数多1B.满二叉树一定是完全二叉树C.完全二叉树一定是满二叉树D.深度为h的满二叉树的结点总数为2ʰ-1E.完全二叉树中，若结点编号为i（根结点编号为1），则其左孩子编号一定是2i

4.下列关于图的遍历与连通性的描述中，正确的有（）

A.深度优先搜索遍历可以用递归实现B.广度优先搜索遍历按层次访问图的顶点C.强连通分量是针对有向图定义的概念D.连通分量是无向图中的极大连通子图E.任何连通图的最小生成树都是唯一的

5.下列排序算法中，平均时间复杂度为O(nlogn)的有（）

A.快速排序B.堆排序C.归并排序D.冒泡排序E.直接选择排序

三、判断题（每小题1分，共10分）正确打√，错误打×，将答案填在答题纸相应位置。

1.二维数组在逻辑上每个元素最多只有一个前驱和一个后继，因此属于线性结构。

2.采用牺牲一个存储单元法判断队空队满的循环队列，队列中实际存储的元素个数最多不超过数组长度减1。

3.空串和由多个空格组成的空格串是同一个概念。

4.哈夫曼编码中，字符出现的频率越高，对应的编码长度越短。

5.任何有向图都可以得到有效的拓扑排序序列。

6.对同一个无向图进行深度优先遍历，得到的遍历序列一定是唯一的。

7.折半查找既可以用于有序顺序表，也可以用于有序链表。

8.任何二叉排序树的中序遍历序列一定是递增有序序列。

9.堆排序是稳定的排序算法。

10.大顶堆中，根结点的值一定是整个堆中所有结点的最大值。

四、简答题（每小题5分，共20分）请将答案写在答题纸相应位置。

1.简述线性表的顺序存储结构和链式存储结构各自的优缺点，以及适用场景。

2.请给出完全二叉树的定义，简述完全二叉树的两个典型性质。

3.简述迪杰斯特拉（Dijkstra）算法求解单源最短路径的核心思想。

4.简述分治法求解问题的三个基本步骤，并列举两个数据结构中使用分治法的典型算法。

五、应用题（每小题10分，共20分）请将解答过程写在答题纸相应位置。

1.给定一组叶子结点的权值集合为{2,3,5,7,8,10}，要求按照哈夫曼算法构造一棵哈夫曼树，画出最终的哈夫曼树结构，计算该哈夫曼树的带权路径长度WPL，并给出每个权值对应的哈夫曼编码（约定左分支编码为0，右分支编码为1）。

2.已知带权无向图G的顶点集合为V={v₁,v₂,v₃,v₄,v₅}，边集合为E={(v₁,v₂,3),(v₁,v₃,1),(v₁,v₄,5),(v₂,v₃,1),(v₂,v₅,4),(v₃,v₄,2),(v₄,v₅,3)}，要求写出G的邻接矩阵，按照克鲁斯卡尔（Kruskal）算法给出G的最小生成树的构造过程，画出最终的最小生成树，并计算最小生成树的总权值。

六、算法设计题（共15分）请按要求解答下列问题。

已知一个不带头结点的单链表，所有结点的值为整型，可能存在多个值相同的结点，要求设计算法删除所有值重复的结点，仅保留第一次出现该值的结点。要求：（1）说明你的算法设计思路；（2）写出完整的算法代码，采用C语言风格描述，结点结构体定义为typedefstructNode{intdata;structNode*next;}Node;；（3）分析你所设计算法的时间复杂度和空间复杂度。参考答案一、单项选择题C解析：逻辑结构是对数据元素之间逻辑关系的抽象描述，与存储方式无关，顺序表、哈希表、单链表都是具体的存储实现，只有有序表是按元素值有序组织的逻辑结构，因此选C。B解析：插入新元素需要移动平均n/2个元素，因此平均时间复杂度为O(n)，选B。D解析：栈既可以顺序存储，也可以采用链式存储结构实现，因此D错误。B解析：该约定下，队满条件为(rear+1)\%m==front，选B。A解析：按照next数组的计算规则，模式串索引从0开始：next[0]=-1，j=0,k=-1，next[1]=0，比较p[0]和p[1]，a≠b，所以next[2]=0，再比较p[0]和p[2]，a=a，所以next[3]=1，再比较p[1]和p[3]，b=b，next[4]=2，再比较p[2]和p[4]，a=a，next[5]=3，因此结果为-1,0,0,1,2,3，选A。C解析：行优先存储下，A[i][j]的地址为：首地址+(i10+j)2，代入i=3,j=4得100+(310+4)2=100+68=168，选C。D解析：深度为k的完全二叉树，前k-1层是满二叉树，共有2ᵏ⁻¹-1个结点，第k层最少有1个结点，因此总结点最少是(2ᵏ⁻¹-1)+1=2ᵏ⁻¹，选D。A解析：先序第一个结点A是根，中序中CBA在A左，EDF在A右；左子树先序是BC，根B，C在B左；右子树先序DEF，根D，E在D左，F在D右，因此后序遍历顺序是C→B→E→F→D→A，即CBEFDA，选A。B解析：LL型不平衡需要单次右旋，LR型需要先左后右，RR型单次左旋，RL先右后左，选B。D解析：哈夫曼树每次合并两个结点，所有结点度都是0或2，但是哈夫曼树不一定是满二叉树，比如权值{1,2,3,4}构造的哈夫曼树就不是满二叉树，因此D错误，选D。B解析：有向图的邻接矩阵不一定对称，第i行非零元素个数是顶点i的出度，第i列非零元素个数是入度，邻接矩阵存储的空间大小是n²，只和顶点数有关，和边数无关，因此B正确，选B。B解析：广度优先遍历需要按层次访问，用队列保存已访问顶点的邻接点，选B。B解析：树的性质是n个顶点的树有n-1条边，8个顶点就是7条边，选B。B解析：折半查找的最大比较次数为⌈log₂(n+1)⌉，n=14，log₂15≈3.91，向上取整为4，选B。C解析：除留余数法是构造散列函数的方法，不是处理冲突的方法，选C。C解析：当二叉排序树退化为单链表时，查找需要遍历所有结点，最坏时间复杂度为O(n)，选C。D解析：堆排序在调整堆的过程中会交换相同值结点的相对位置，因此是不稳定排序，冒泡、直接插入、归并都是稳定排序，选D。C解析：快速排序的时间复杂度取决于划分是否均匀，每次划分得到长度相近的两个子序列时，递归深度最低，执行效率最高，选C。B解析：快速排序的空间复杂度为O(logn)（递归栈开销），归并排序需要O(n)的辅助空间，基数排序需要O(n)的辅助空间，堆排序只需要常数级别的辅助空间，空间复杂度为O(1)，选B。B解析：建堆过程是从最后一个非叶子结点开始向下调整，总的时间复杂度是O(n)，选B。

###二、多项选择题答案：ABC解析：树和二叉树是层次结构，属于非线性结构，栈、队列、串都是线性结构，选ABC。答案：ABCD解析：队列只允许在队尾插入，队头删除元素，E选项描述错误，其余ABCD都正确。答案：ABDE解析：完全二叉树不一定是满二叉树，只有满二叉树要求最后一层全满，完全二叉树允许最后一层结点从左到右排列，有空缺，因此C错误，其余ABDE都正确。答案：ABCD解析：当图中多条边权值相同时，可能得到不同的最小生成树，但总权值相同，因此最小生成树不一定唯一，E错误，其余ABCD都正确。答案：ABC解析：冒泡排序和直接选择排序的平均时间复杂度都是O(n²)，快速排序、堆排序、归并排序的平均时间复杂度都是O(nlogn)，选ABC。

###三、判断题√解析：二维数组可以看作线性结构的推广，每个元素除边界外只有一个前驱和一个后继，属于线性结构，本题说法正确。√解析：牺牲一个存储单元的循环队列，用空出一个位置区分队空和队满，因此最多存储m-1个元素，本题说法正确。×解析：空串长度为0，没有任何字符，空格串长度是空格的个数，二者不是同一个概念，本题说法错误。√解析：哈夫曼编码构造过程中，频率越高的字符越靠近根结点，路径越短，编码长度越短，本题说法正确。×解析：只有有向无环图才能进行拓扑排序，有环的有向图无法得到有效的拓扑排序，本题说法错误。×解析：遍历序列取决于顶点的存储顺序，如果邻接表中顶点的邻接点顺序不同，得到的遍历序列也会不同，因此不是唯一的，本题说法错误。×解析：折半查找需要随机访问元素，有序链表不支持随机访问，因此无法使用折半查找，本题说法错误。√解析：二叉排序树的定义是左子树所有结点小于根，右子树所有结点大于根，因此中序遍历左根右得到的序列一定是递增有序的，本题说法正确。×解析：堆排序是不稳定排序，会改变相同值结点的相对位置，本题说法错误。√解析：大顶堆的定义是每个结点的值都不小于其孩子结点的值，因此根结点一定是最大值，本题说法正确。

###四、简答题参考答案：（1）顺序存储结构优点：可以随机访问任意位置的元素，存储密度高，不需要额外空间存储结点之间的关系；缺点：插入和删除操作需要移动大量元素，预分配空间时如果空间过大浪费内存，过小容易溢出，不适合动态增长的线性表。（2分）（2）链式存储结构优点：不需要预分配空间，插入和删除操作只需要修改指针，不需要移动元素，适合动态变化的线性表；缺点：无法随机访问，需要额外空间存储指针，存储密度低。（2分）（3）适用场景：顺序存储适合元素个数变化不大，以查找访问为主的场景；链式存储适合元素个数动态变化，以插入删除为主的场景。（1分）参考答案：定义：深度为k的二叉树，若其结点编号和深度为k的满二叉树中编号从1到n的结点位置一一对应，则该二叉树是完全二叉树。（2分）性质：（1）n个结点的完全二叉树的深度为⌊log₂n⌋+1；（2）若对完全二叉树的结点按层编号，编号为i的结点，其左孩子编号为2i，右孩子编号为2i+1，父结点编号为⌊i/2⌋（i>1）；（3）若结点编号i>n/2，则该结点一定是叶子结点。答对任意两个性质即可得3分。参考答案：迪杰斯特拉算法用于求解带权有向图中单源点到其他所有顶点的最短路径，要求所有边权值为正。核心思想是：（1）将顶点分为两个集合，S集合存放已经找到最短路径的顶点，T集合存放还未找到最短路径的顶点，初始时S只包含源点；（2分）（2）每次从T集合中选择到源点路径长度最短的顶点u，将u加入S集合；（2分）（3）更新T集合中剩余顶点到源点的最短路径长度，若经过顶点u到达顶点v的路径长度比原来v的最短路径更短，则更新v的最短路径长度；重复上述过程，直到所有顶点都加入S集合为止。（1分）参考答案：分治法的核心思想是将一个难以直接解决的大问题，分解为若干个规模较小、性质相同的子问题，递归解决子问题，再合并子问题的解得到原问题的解。三个基本步骤：（1）分解：将原问题分解为多个规模较小、性质相同的子问题；（2）解决：若子问题规模足够小，直接解决，否则递归解决每个子问题；（3）合并：将各个子问题的解合并得到原问题的解。（3分）典型算法：快速排序、归并排序、折半查找，任意答对两个即可得2分。

###五、应用题参考答案：构造哈夫曼树的过程：每次选取两个权值最小的结点合并，新结点权值为两个权值之和。合并2和3得到新结点权值5；新集合为{5,5,7,8,10}；再合并5和5得到新结点10，新集合为{7,8,10,10}；合并7和8得到新结点15，新集合为{10,10,15}；合并10和10得到新结点20，新集合为{15,20}；合并得到根结点35。（4分）哈夫曼树结构：根结点35，左孩子15，右孩子20；15左孩子7，右孩子8；20左孩子10，右孩子10；左子树的10左孩子为之前合并2和3得到的5结点，右孩子为叶子结点10；5结点左孩子为叶子2，右孩子为叶子3。（3分，结构描述正确即可得分）带权路径长度WPL=23+33+53+72+82+102=6+9+15+14+16+20=80。（1分）哈夫曼编码（左0右1）：2:000，3:001，5:010，7:100，8:101，10:011，编码符合哈夫曼树结构即可得分。（1分）参考答案：邻接矩阵（顶点顺序v₁到v₅，无边权值记为∞，对角线为0）：

0（3分）克鲁斯卡尔算法构造过程：将所有边按权值从小到大排序：权值1（v₁-v₃）、权值1（v₂-v₃）、权值2（v₃-v₄）、权值3（v₁-v₂）、权值3（v₄-v₅）、权值4（v₂-v₅）、权值5（v₁-v₄）。（2分）依次选边：选v₁-v₃（权1，无环），选v₂-v₃（权1，无环），选v₃-v₄（权2，无环），选v₁-v₂会生成环，跳过，选v₄-v₅（权3，无环），此时所有5个顶点都连通，构造结束。（3分）最小生成树总权值=1+1+2+3=7。（2分）

###六、算法设计题算法思路：采用双重循环的思路，外层指针p指向当前需要保留的结点，内层指针q从p->next开始遍历p后面的所有结点，若q结点的值和p结点的值相同，则删除q结点，否则继续后移q，直到遍历完整个链表；之后p后移一位，重复上述过程，直