杭州电子科技大学数据结构数据结构期末试题.docx
杭州电子科技大学数据结构数据结构期末试题
一、选择题（每题3分，共30分）
1.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的关系和运算等的学科。
A.数据元素
B.计算方法
C.逻辑存储
D.数据映像
答案：A
解析：数据结构研究数据元素、数据元素之间的关系以及对这些数据元素的运算。计算方法主要侧重于数值计算的算法；逻辑存储表述不准确；数据映像是数据库中的概念。所以选A。
2.以下属于线性结构的是（）。
A.树
B.图
C.栈
D.集合
答案：C
解析：线性结构的特点是数据元素之间存在一对一的线性关系。栈是一种特殊的线性表，遵循后进先出原则。树是一对多的层次关系，图是多对多的关系，集合中元素之间没有特定的顺序关系，不属于线性结构。所以选C。
3.若一个栈的输入序列是1,2,3,…,n，输出序列的第一个元素是n，则第i个输出元素是（）。
A.ni
B.ni+1
C.i
D.不确定
答案：B
解析：栈是后进先出的数据结构。输入序列是1,2,3,…,n，输出序列第一个元素是n，说明所有元素都已入栈。那么依次出栈的元素顺序为n,n1,n2,…,1。第i个输出元素就是ni+1。所以选B。
4.带头结点的单链表head为空的判定条件是（）。
A.head==NULL
B.headnext==NULL
C.headnext==head
D.head!=NULL
答案：B
解析：带头结点的单链表，头结点本身不存储数据元素，真正的数据从headnext开始。当headnext为NULL时，表示链表中没有数据节点，即链表为空。而head本身不为NULL，它是头结点的指针。所以选B。
5.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。
A.n
B.n+1
C.n1
D.2n
答案：C
解析：对于一个具有n个顶点的无向图，要使其连通，最少需要n1条边，形成一棵树的结构。当边数小于n1时，图一定不连通。所以选C。
6.对长度为n的有序单链表进行二分查找，其时间复杂度为（）。
A.O(n)
B.O(log?n)
C.O(n2)
D.O(1)
答案：A
解析：二分查找要求数据结构能够随机访问，而单链表只能顺序访问，不能进行高效的二分查找。在单链表中查找元素，需要从头节点开始依次遍历，时间复杂度为O(n)。所以选A。
7.以下排序算法中，不稳定的排序算法是（）。
A.冒泡排序
B.插入排序
C.选择排序
D.归并排序
答案：C
解析：排序算法的稳定性是指在排序过程中，相等元素的相对顺序保持不变。冒泡排序、插入排序和归并排序都是稳定的排序算法。选择排序在交换元素时，可能会改变相等元素的相对顺序，是不稳定的排序算法。所以选C。
8.若某二叉树的前序遍历序列为ABCD，中序遍历序列为BADC，则后序遍历序列为（）。
A.BDCA
B.BCDA
C.CDBA
D.DCBA
答案：A
解析：前序遍历的顺序是根节点左子树右子树，中序遍历的顺序是左子树根节点右子树。根据前序遍历序列ABCD可知A是根节点，再结合中序遍历序列BADC可知B是A的左子树，DC是A的右子树。对于右子树，前序遍历是CD，中序遍历是DC，可知C是根节点，D是C的左子树。由此可画出二叉树，其后序遍历顺序为BDCA。所以选A。
9.一个队列的入队序列是1,2,3,4，则队列的可能输出序列是（）。
A.4,3,2,1
B.1,2,3,4
C.3,1,2,4
D.2,3,4,1
答案：B
解析：队列是先进先出的数据结构，入队序列是1,2,3,4，那么出队序列也只能是1,2,3,4。选项A是栈的后进先出的输出情况；选项C和D不符合队列先进先出的原则。所以选B。
10.哈希表的平均查找长度（）。
A.与处理冲突的方法有关而与表的长度无关
B.与处理冲突的方法无关而与表的长度有关
C.与处理冲突的方法和表的长度都有关
D.与处理冲突的方法和表的长度都无关
答案：C
解析：哈希表的平均查找长度受处理冲突的方法影响，不同的处理冲突方法（如开放定址法、链地址法等）会导致不同的查找效率。同时，表的长度也会影响平均查找长度，表的长度不同，哈希冲突的概率也不同。所以选C。
二、填空题（每题3分，共30分）
1.数据的逻辑结构分为线性结构和__________。
答案：非线性结构
解析：数据的逻辑结构主要分