数据结构期末复习题 .pdfVIP

练习题：

一、填空题

1、元素项是数据的最小单位，数据元素是讨论数据结构时涉及的最小数据单位。

2、设一棵完全二叉树具有100个结点，则此完全二叉树有49个度为2的结点。

3、在用于表示有向图的邻接矩阵中，对第i列的元素进行累加，可得到第i个顶点的出度。

4、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有12个叶子

的结点。

n=n0+n1+n2+…+nm(1)

又有除根结点外,树中其他结点都有双亲结点,且是唯一的(由树中的分支表示),所以,有双亲的结点数为：

n-1=0*n0+1*n1+2*n2+…+m*nm(2)

联立(1)(2)方程组可得：

叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm

5、有一个长度为20的有序表采用二分查找方法进行查找，共有4个元素的查找长度为3。

6、对于双向链表，在两个结点之间插入一个新结点需要修改的指针共4个。

删除一个结点需要修改的指针共2个。

7、已知广义表LS=(a,(b,c,d),e)，它的深度是2，长度是3。

8、循环队列的引入是为了克服假溢出。

9、表达式a*(b+c)-d/f的后缀表达式是abc+*df/-。

10、数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度。

11、设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是

r-next=s;r=s;r-next=null;

12、设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过

PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是23，而栈顶指针值是1012_H。设栈为顺序栈，每

个元素占4个字节。

13、模式串P=‘abaabcac’的next函数值序列为

14、任意连通图的连通分量只有一个，即是自身。

15、栈的特性是先进后出。

16、串的长度是包含的元素个数。

17、如果一个有向图中没有回路，则该图的全部顶点可能排成一个拓扑序列。

18、在具有n个叶子结点的哈夫曼树中，分支结点总数为n-1。176

19、在线性表的散列存储中，装填因子又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元

素的个数，则等于n/m。

20、排序的主要目的是为了以后对已排序的数据元素进行查找。

21、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1),在给定值为

x的结点后插入一个新结点的时间复杂度为O(n)。

22、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要

移动元素的个数是n/2。

23、两个栈共享空间时栈满的条件top1=top2-1。

24、深度为H的完全二叉树至少有H个结点；至多有2^H-1个结点；H和结点总数N之间的关系是

H=[log2n]+1。150

25、在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是136811

131619

26、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较7次就可以断定数

据元素X是否在查找表中。

26、数据结构被形式地定义为（D,R），其中D和R的含义是（D是数据元素的集合，R是数据关系的集合）。

数据的逻辑结构包括哪四种类型（集合类型，线性结构，树形结构，图状结构）。从存储结构的概念上讲，

顺序表是线性表的（顺序存储结构），链表是（链式存储结构）。

27、根据初始关键字序列(17，25，3，39，12)建立的二叉排序树的高度为3。

27、算法的五个重要特性有哪些。（有穷性、确定性、可行性、输入、输出）。抽象数据类型是指一个（数学

模型）以及定义在该模型上的（一组操作）。

28、设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角上元素）存放在n(n+1)

个连