数据结构与算法练习题+参考答案.docx
数据结构与算法练习题+参考答案
一、单选题
1.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的关系和运算等的学科。
A.操作对象
B.计算方法
C.逻辑存储
D.数据映象
答案：A
解析：数据结构研究的是操作对象以及对象之间的关系和运算，所以选A。
2.算法分析的目的是（）。
A.找出数据结构的合理性
B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进
D.分析算法的易读性和文档性
答案：C
解析：算法分析主要是分析算法的时间复杂度和空间复杂度等效率指标，目的是对算法进行改进，所以选C。
3.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续或不连续都可以
答案：D
解析：链式存储结构中，节点的存储单元地址可以是连续或不连续的，通过指针来连接节点，所以选D。
4.栈和队列的共同点是（）。
A.都是先进后出
B.都是先进先出
C.只允许在端点处插入和删除元素
D.没有共同点
答案：C
解析：栈是后进先出，队列是先进先出，但它们都只允许在端点处进行插入和删除操作，所以选C。
5.一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（）。
A.edcba
B.decba
C.dceab
D.abcde
答案：C
解析：根据栈的后进先出原则，对各选项进行分析。C选项中，d先出栈，说明a、b、c已入栈，此时栈内元素从栈顶到栈底为c、b、a，接着c出栈，然后e入栈出栈，此时栈内元素为b、a，下一个出栈元素只能是b，而不是a，所以C选项不可能。
6.带头结点的单链表head为空的判定条件是（）。
A.head==NULL
B.head-next==NULL
C.head-next==head
D.head!=NULL
答案：B
解析：带头结点的单链表，头结点本身不存储数据，当head-next==NULL时，表示链表中没有数据节点，即链表为空，所以选B。
7.树最适合用来表示（）。
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
答案：C
解析：树的结构特点就是元素之间具有分支层次关系，所以选C。
8.深度为5的二叉树至多有（）个节点。
A.16
B.32
C.31
D.10
答案：C
解析：深度为k的二叉树，最多节点数为$2^k-1$，当k=5时，$2^5-1=31$，所以选C。
9.对线性表进行二分查找时，要求线性表必须（）。
A.以顺序方式存储
B.以链式方式存储
C.以顺序方式存储，且数据元素有序
D.以链式方式存储，且数据元素有序
答案：C
解析：二分查找的前提是线性表以顺序方式存储且数据元素有序，这样才能通过比较中间元素来缩小查找范围，所以选C。
10.若一个有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑排序（）。
A.一定存在
B.一定不存在
C.不一定存在
D.无法确定
答案：A
解析：主对角线以下元素均为零的有向图是有向无环图，有向无环图一定存在拓扑排序，所以选A。
11.下面关于图的存储的叙述中，正确的是（）。
A.用邻接矩阵法存储图，占用的存储空间数只与图中顶点数有关，而与边数无关
B.用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，而与顶点数无关
C.用邻接表法存储图，占用的存储空间数只与图中顶点数有关，而与边数无关
D.用邻接表法存储图，占用的存储空间数只与图中边数有关，而与顶点数无关
答案：A
解析：邻接矩阵是一个$n×n$的矩阵，$n$为顶点数，所以占用的存储空间只与顶点数有关，与边数无关，选A。
12.哈希表的平均查找长度（）。
A.与处理冲突方法有关而与表的长度无关
B.与处理冲突方法无关而与表的长度有关
C.与处理冲突方法有关且与表的长度有关
D.与处理冲突方法无关且与表的长度无关
答案：C
解析：不同的处理冲突方法会影响哈希表的查找效率，同时表的长度也会对平均查找长度产生影响，所以选C。
13.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。
A.希尔排序
B.冒泡排序
C.插入排序
D.选择排序
答案：C
解析：插入排序的基本思想就是从未排序序列中取元素插入到已排序序列的正确位置，所以选C。
14.快速排序在下列哪种情况下最易发挥其长处（）。
A.被排序的数据中含有多个相同排序码
B.被排序的数据已基本有序
C.被排