复习数据结构习题解答.pdf

习题解答

1．空格串是由空格组成的串，空串是不含任何字符的串，因此空格串和空串不是一个

概念。

2．从整体上看，数据在存储器内有两种存放的方式：一是集中存放在一个连续的内存存

储区中；一是利用存储器中的零星区域，分散地存放在内存的各个地方。

3．如果一棵满二叉树的深度为6，那么它共有63个结点，有32个叶结

3．限定插入和删除操作只能在一端进行的线性表，被称为是栈。

nn

4．在数据结构中，把（≥0）棵互不相交的树的集合称为森林。树中一个结点的子树

中的任何结点，都被称作是该结点的子孙结点。

nij

5．在一个阶方阵A中，若所有元素都有性质：a=a(1≤,≤n)，就称其为对称矩

ijji

阵。

6．在有向图中，把从顶点v到顶点v的弧记为v，v，而把从顶点v到顶点v的弧

ijijji

记为v，v，这是两条不同的弧。

ji

7．如果查找只是为了得知是否成功或获取相应的记录信息，并不去改变查找表的内容，那

么这种查找称为静态查找；如果查找过程会伴随着对数据元素的变更，那么这种查找称为

动态查找。

8.前序遍历序和中序遍序列相同的二叉树为树中的任何一个节点无左孩子

1.若已知一个栈的输入序列为1,2,3,...n,其输出序列为p1,p2,p3,pn。若p1=n,则pi为

＿n-i+1＿＿＿。

2.循环队列用数组a[m]存放其元素值,已知尾指针是rear,元素个数是qlen,则当前队列中的首指针

为(Max+Sq-rear-sq-qlen)%max

＿＿＿＿。

3.按照二叉树的定义,具有3个结点的二叉树有＿5＿＿＿种。

4.从逻辑关系上讲,数据结构主要分为两大类,它们是＿＿＿＿和＿＿＿＿。

5.在有向图中，把从顶点v到顶点v的弧记为v，v，而把从顶点v到顶点v的弧记为

ijijji

v，v，这是两条不同的弧。

ji

6.已知完全二叉树的第八层有8个结点,则其叶子结点数是＿＿＿＿。

nn

7．在数据结构中，把（≥0）棵互不相交的树的集合称为森林，树中一个结点的子树

中的任何结点，都被称作是该结点的子孙结点。

8．在一个具有4个顶点的无向图中，要连通全部顶点，，至少需要3条边。

9．对关键字序列22、86、19、49、12、30、65、35、18做一趟排序后，得到的结果是18、

12、19、22、49、30、65、35、86。因此，可以认为采用的排序方法是快速排序。

nij

10．在一个阶方阵A中，若所有元素都有性质：a=a(1≤,≤n)，就称其为对称

ijji

矩阵。

11．如果查找只是为了得知是否成功或获取相应的记录信息，并不去改变查找表的内容，那