大学数据结构期末考试试题(有答案).docx
大学数据结构期末考试试题(有答案)
一、选择题（每题3分，共30分）
1.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的关系和运算等的学科。
A.数据元素
B.计算方法
C.逻辑存储
D.数据映像
答案：A
解析：数据结构研究的是数据元素以及它们之间的关系和运算等。计算方法侧重于算法的设计和分析，不是数据结构主要研究内容；逻辑存储是数据存储的一种方式，不全面；数据映像是关于数据在不同层面的映射，并非数据结构的核心定义。所以选A。
2.以下哪种数据结构不是线性结构（）。
A.栈
B.队列
C.树
D.线性表
答案：C
解析：线性结构的特点是数据元素之间存在一对一的线性关系。栈和队列都是特殊的线性表，它们的数据元素也是线性排列的。而树是一种非线性结构，树中节点之间存在一对多的层次关系。所以选C。
3.栈和队列的共同点是（）。
A.都是先进后出
B.都是先进先出
C.只允许在端点处插入和删除元素
D.没有共同点
答案：C
解析：栈是先进后出的数据结构，队列是先进先出的数据结构，A和B选项错误。栈只允许在栈顶进行插入和删除操作，队列只允许在队尾插入、队头删除，二者都只允许在端点处插入和删除元素。所以选C。
4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A.顺序表
B.双链表
C.带头结点的双循环链表
D.单循环链表
答案：A
解析：顺序表可以通过数组下标直接存取指定序号的元素，时间复杂度为O(1)；在最后进行插入和删除操作时，若不考虑扩容问题，时间复杂度也为O(1)。而链表（包括双链表、带头结点的双循环链表、单循环链表）在存取指定序号元素时需要从头节点开始遍历，时间复杂度为O(n)。所以选A。
5.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。
A.O(1)
B.O(n)
C.O(n^2)
D.O(log?n)
答案：B
解析：在有序单链表中插入一个新结点，需要遍历链表找到合适的插入位置，平均需要遍历n/2个节点，时间复杂度为O(n)。插入操作本身的时间复杂度为O(1)，但整体插入过程主要取决于查找插入位置的时间，所以选B。
6.已知一棵二叉树的前序遍历序列为ABCDEFG，中序遍历序列为CBDAEGF，则该二叉树的后序遍历序列为（）。
A.CDBGFEA
B.CDBFGEA
C.CDBAGFE
D.BCDAGFE
答案：A
解析：前序遍历的顺序是根节点左子树右子树，中序遍历的顺序是左子树根节点右子树。根据前序遍历序列的第一个元素A为根节点，在中序遍历序列中找到A，A左边的CBD为左子树节点，右边的EGF为右子树节点。然后对左子树和右子树分别重复上述过程构建二叉树，最后得到后序遍历序列（左子树右子树根节点）为CDBGFEA。所以选A。
7.对n个不同的关键字进行冒泡排序，在元素无序的情况下比较的次数为（）。
A.n+1
B.n
C.n1
D.n(n1)/2
答案：D
解析：冒泡排序在最坏情况下（元素无序），每一轮比较的次数依次为n1,n2,…,1。总的比较次数为1+2+…+(n1)，根据等差数列求和公式可得n(n1)/2。所以选D。
8.设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新的第i个元素）插入一个新元素，需向后移动（）个元素。
A.ni
B.ni+1
C.ni1
D.i
答案：B
解析：要在第i个元素之前插入一个新元素，从第i个元素开始到最后一个元素（共ni+1个元素）都需要向后移动一个位置。所以选B。
9.一个有向图G有n个顶点，其邻接矩阵为A，则图中第i个顶点的入度为（）。
A.第i行非零元素的个数
B.第i列非零元素的个数
C.第i行零元素的个数
D.第i列零元素的个数
答案：B
解析：在有向图的邻接矩阵中，第i列的元素表示其他顶点到第i个顶点的边的情况，第i列非零元素的个数就是指向第i个顶点的边的数量，即第i个顶点的入度。所以选B。
10.哈希表的平均查找长度（）。
A.与处理冲突方法有关而与表的长度无关
B.与处理冲突方法无关而与表的长度有关
C.与处理冲突方法和表的长度都有关
D.与处理冲突方法和表的长度都无关
答案：C
解析：哈希表的平均查找长度受到处理冲突方法的影响，不同的处理冲突方法（如开放定址法、链