数据结构总复习题JAVA.pdf

.

-

一、填空题

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算法求*一顶点到其余各顶点间的最短路径是按路径长度递

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

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的出

度。

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

.