2025年数据结构总复习题(JAVA) .pdfVIP

百学须先立志。——朱熹

一、填空题

1.栈和队列的共同特点是（只允许在端点处插入和删除元素）。

2.在深度为5的满二叉树中，叶子结点的个数为（31）

3.算法分析的目的是（分析算法的效率以求改进）。

4.由两个栈共享一个存储空间的好处是（节省存储空间，降低上溢发生的机

率）。

5.串的长度是（串中所含字符的个数）。

6.设有两个串p和q，求q在p中首次出现位置的运算称做（模式匹配）

7.N个顶点的连通图中边的条数至少为（N-1）。

8.N个顶点的强连通图的边数至少有（N）。

9.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（N）。

P259

10.假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为

（n(n-1)/2）。P292

11.在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，

其时间复杂度为O（n）。

12.在具有n个单元的循环队列中，队满时共有n-1个元素。

13.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出

度。

14.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度

递增的次序来得到最短路径的。

第1页，共5

学而不知道，与不学同；知而不能行，与不知同。——黄睎

15.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。

16．在一个循环队列中，队首指针指向队首元素的前一个位置。

17．在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动

的元素个数与表长和该元素在表中的位置有关。

18.线性表中结点的集合是有限的，结点间的关系是一对一的。

19.数据结构被形式地定义为（D,R），其中D是数据元素的有限集合，

R是D上的关系有限集合。

20.线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关

系，图形结构中元素之间存在多对多关系。

21.一个算法的效率可分为时间效率和空间效率。

22.在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称

为随机存取的数据结构。

23.在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，

其时间复杂度为O（n）。

24.在具有n个单元的循环队列中，队满时共有n-1个元素。

25.对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插

入和队首删除元素。

6-1

26.一棵深度为6的满二叉树有n+n=0+n=n-1=31个分支结点和2=32

1220

个叶子。

27.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出

第2页，共5

天将降大任于斯人也，必先苦其心志，劳其筋骨，饿其体肤，空乏其身，行拂乱其所为。——《孟子》