杭州电子科技大学数据结构数据结构试题及答案.docx
杭州电子科技大学数据结构数据结构试题及答案
一、选择题（每题3分，共30分）
1.算法的时间复杂度取决于（）。
A.问题的规模
B.待处理数据的初态
C.计算机的配置
D.A和B
答案：D
解析：算法的时间复杂度不仅与问题的规模有关，还和待处理数据的初始状态有关。例如，在排序算法中，对于不同初始顺序的数据，其时间复杂度可能不同。而计算机的配置影响的是算法的执行时间，并非时间复杂度，时间复杂度是一个理论上的度量。
2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续或不连续都可以
答案：D
解析：链式存储结构是通过指针来连接各个节点，节点在内存中的存储位置是随机的，不要求地址连续。可以是连续的，也可以是不连续的，只要通过指针能正确连接各个节点即可。
3.栈和队列的共同点是（）。
A.都是先进先出
B.都是先进后出
C.只允许在端点处插入和删除元素
D.没有共同点
答案：C
解析：栈是先进后出的数据结构，队列是先进先出的数据结构，所以A和B选项错误。栈只允许在栈顶进行插入和删除操作，队列只允许在队尾插入、队头删除元素，它们都只允许在端点处进行插入和删除操作，所以C选项正确。
4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？（）。脚注(10)表示用10进制表示。
A.688
B.678
C.692
D.696
答案：C
解析：设数组按行优先存储，对于二维数组A[m][n]，若A[0][0]的存储地址为LOC(0,0)，则A[i][j]的存储地址LOC(i,j)=LOC(0,0)+(in+j)d（d为每个元素所占空间）。已知A[0][0]存放位置在644，A[2][2]存放位置在676，可得676=644+(2n+2)1，解得n=15。那么A[3][3]的存储地址为644+(315+3)1=692。
5.对二叉树从1开始进行连续编号，要求每个节点的编号大于其左右孩子的编号，同一节点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）遍历实现编号。
A.先序
B.中序
C.后序
D.层次
答案：C
解析：后序遍历的顺序是左子树右子树根节点。按照后序遍历的顺序对节点进行编号，由于先遍历左右孩子，再遍历根节点，所以能保证每个节点的编号大于其左右孩子的编号，并且在同一节点的左右孩子中，左孩子先被访问，编号小于右孩子的编号。
6.有8个结点的无向图最多有（）条边。
A.14
B.28
C.56
D.112
答案：B
解析：对于无向图，边数的计算公式为$n(n1)/2$（n为节点数）。当n=8时，边数为$8\times(81)/2=28$。
7.已知一个有序表为(13,18,24,35,47,50,62,83,90,115,134)，当用二分法查找值为90的元素时，查找成功的比较次数为（）。
A.1
B.2
C.3
D.4
答案：C
解析：二分查找的基本思想是每次将待查找区间缩小一半。第一次比较中间元素50，9050，在右半区间查找；第二次比较右半区间的中间元素90，找到目标元素，所以比较次数为3次。
8.堆是一种（）排序。
A.插入
B.选择
C.交换
D.归并
答案：B
解析：堆排序是选择排序的一种。它通过构建最大堆或最小堆，每次从堆中选择最大或最小的元素，然后调整堆结构，重复这个过程直到排序完成。
9.若一个有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑排序（）。
A.一定存在
B.一定不存在
C.不一定存在
D.无法确定
答案：A
解析：主对角线以下元素均为零的有向图是一个有向无环图（DAG）。有向无环图一定存在拓扑排序，因为拓扑排序的定义就是对有向无环图的顶点进行排序，使得对于每一条有向边(u,v)，顶点u在排序中都出现在顶点v之前。
10.下列排序算法中，（）排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A.选择
B.冒泡
C.归并
D.堆
答案：C
解析：选择排序每一趟会选出最小（或最大）的元素放到其最终位置；冒泡排序每一趟会将一个最大（或最小）的元素“浮”到最终位置；堆排序每一趟会将堆顶元素（最大或最小）放到其最终位置。而归并排序是将多个有序子序列合并