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

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

《复习数据结构习题解答.docx》由会员分享，可在线阅读，更多相关《复习数据结构习题解答.docx（23页珍藏版）》请在冰点文库上搜索。

复习数据结构习题解答

习题解答

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

2．从整体上看，数据在存储器内有两种存放的方式：

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

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

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

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

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

5．在一个n阶方阵A中，若所有元素都有性质：

aij=aji（1≤i,j≤n），就称其为对称矩阵。

6．在有向图中，把从顶点vi到顶点vj的弧记为，而把从顶点vj到顶点vi的弧记为，这是两条不同的弧。

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.在有向图中，把从顶点vi到顶点vj的弧记为，而把从顶点vj到顶点vi的弧记为，这是两条不同的弧。

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

7．在数据结构中，把n（n≥0）棵互不相交的树的集合称为森林，树中一个结点的子树中的任何结点，都被称作是该结点的子孙结点。

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

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

因此，可以认为采用的排序方法是快速排序。

10．在一个n阶方阵A中，若所有元素都有性质：

aij=aji（1≤i,j≤n），就称其为对称矩阵。

11．如果查找只是为了得知是否成功或获取相应的记录信息，并不去改变查找表的内容，那么这种查找称为静态查找；如果查找过程会伴随着对数据元素的变更，那么这种查找称为动态查找。

答案：

1、n-i+12、（Max+Sq->rear-sq->qlen）%max

3、54、线性关系和非线性关系5、、6、68

7、森林、子孙8、39、快速排序10、对称11、静态、动态

1.前序遍历序和中序遍序列相同的二叉树为

2.无向图G用邻接矩阵A{1...n，1...n}存储。

其第i列的所有非零元素个数等于顶点i的。

3.由带权为３，９，６，２，５的５个叶子结点构成一棵哈夫曼树，则其带权路径长度为＿＿．

4.设有有空栈，栈顶指针指向100H（十六进制），现有输入序列为1，2，3，4，经过Push，Push，Pop，Push，Pop，Push，Push后，输出序列为。

5.在一棵树中，结点没有前驱结点。

6.具有64有结点的完全二叉树的深度为。

7.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，需次比较可检索成功。

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

9．若经过某种排序之后，那些有相同关键字值的记录间的相对位置保持不变，那么称这种排序方法是稳定的。

10．线性表中数据元素的个数n称为线性表的长度

11．所谓“数组”，是指n（n>1）个具有相同类型的数据的有序集合。

12．在具有n个数据结点的循环队列中，队满时共有n-1个数据元素。

13．在无向图中，若从顶点vi到顶点vj之间有路径存在，则称vi与vj是连通的。

14．在一个n阶方阵A中，若所有元素都有性质：

aij=aji（1≤i,j≤n），就称其为对称矩阵。

答案：

1.树中的任何一个节点无左孩子2.度3.554.5，4，1或2,3,5，4，15.根6.77.28.空格、不含任何字符

9.稳定10.长度11.相同12.n-113．路径14.对称

1．线性表中数据元素的个数n称为线性表的长度

2．结点数为7的二叉树的高度最矮是5，最高是7。

3．字符串中任意多个连续字符所组成的子序列，被称作是这个串的“子串”，这个字符串本身则称为“主串”。

4．树中除根结点外，其他结点有且只有一个前驱结点，但可以有零个或多个后继结点。

5．所谓“数组”，是指n（n>1）个具有相同类型的数据的有序集合。

6．在具有n个数据结点的循环队列中，队满时共有n-1个数据元素。

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

8．若经过某种排序之后，那些有相同关键字值的记录间的相对位置保持不变，那么称这种排序方法是稳定的。

9．在数据结构中，把n（n≥0）棵互不相交的树的集合称为森林。

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

10．选择排序方法是从未排序的序列中挑选出元素，然后将其依次放入排好序的序列的一端。

11．从整体上看，数据在存储器内有两种存放的方式：

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

1．线性表中数据元素的个数n称为线性表的长度。

2．队列中，允许进行删除的一端称为队首。

3．结点数为7的二叉树的高度最矮是3，最高是7。

4．将一棵完全二叉树按层次进行编号。

那么，对编号为i的结点，如果有左孩子，则左孩子的编号应该是2i；如果有右孩子，则右孩子的编号应该是2i+1。

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

6．对于一个无向图，其邻接矩阵中第i行（或第i列）里非零或非∞元素的个数，正好是第i个顶点vi的度。

7．在无向图中，若顶点vi和vj之间有一条边（vi，vj）存在，那么则称顶点vi和vj互为邻接点。

8．在无向图中，若从顶点vi到顶点vj之间有路径存在，则称vi与vj是连通的。

9．在一个n阶方阵A中，若所有元素都有性质：

aij=aji（1≤i,j≤n），就称其为对称矩阵。

10．选择排序方法是从未排序的序列中挑选出元素，然后将其依次放入排好序的序列的一端。

11．如果操作顺序是先让字母A、B、C进栈，做两次出栈；再让字母D、E、F进栈，做一次出栈；最后让字母G进栈，做三次出栈。

最终这个堆栈从栈顶到栈底的余留元素应该是DA。

二、选择

1．若一个栈的进栈序列是1、2、3、4，那么要求出栈序列为3、2、1、4时，进、出栈操作的顺序应该是A。

（注：

所给顺序中，I表示进栈操作，O表示出栈操作）

A．IIIOOOIOB．IOIOIOIOC．IIOOIOIOD．IOIIIOOO

2．在所给的4棵二叉树中，C不是完全二叉树。

3．在一棵二叉树中，第5层上的结点数最多是C个。

A．8B．15C．16D．32

4．在长度为n的顺序表中，往其第i个元素（1≤i≤n）之前插入一个新的元素时，需要往后移动B个元素。

A．n-iB．n-i+1C．n-i-1D．i

5．用某种排序方法对序列：

24、84、21、47、16、28、66、35、20进行排序，序列的变化情况为：

24，84，21，47，16，28，66，35，20

20，16，21，24，47，28，66，35，84

16，20，21，24，35，28，47，66，84

16，20，21，24，28，35，47，66，84

那么，这里采用的排序方法是C。

A．直接插入排序B．冒泡排序C．快速排序D．选择排序

6．采用顺序查找法查找长度为n的线性表时，其平均查找长度为C。

A．nB．n/2C．（n+1）/2D．（n-1）/2

7．D是图状关系的特例。

A．只有线性关系B．只有树型关系

C．线性关系和树型关系都不D．线性关系和树型关系都

8．有下面的算法段：

for（i=0;i

k++;

其时间复杂度为B。

A．O

（1）B．O（n）C．O（log2n）D．O（n2）

9．下面，对非空线性表特点的论述，C是正确的。

A．所有结点有且只有一个直接前驱

B．所有结点有且只有一个直接后继

C．每个结点至多只有一个直接前驱，至多只有一个直接后继

D．结点间是按照1对多的邻接关系来维系其逻辑关系的

10．一个栈的元素进栈序列是a、b、c、d、e，那么下面的C不能做为一个出栈序列。

A．e、d、c、b、aB．d、e、c、b、a

C．d、c、e、a、bD．a、b、c、d、e

1．在计算递归函数时,如不使用递归过程,则一般情况下必须借助于＿＿＿＿数据结构。

（A）队列（B）广义表（C）二叉树（D）栈

2.一个队列的输入序列是adcb，则队列的输出序列是＿＿＿＿。

（A）adcb（B）bcda（C）dcba（D）cbad

3．有32个结点的完全二叉树的深度为＿＿＿＿（根的层次为1）。

（A）8（B）7（C）6（D）5

4．一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列是＿＿＿＿。

（A）23415（B）54231（C）23145（D）15432

5.数组a[5][6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续单元中，则元素a[2][5]的地址为＿＿＿＿

（A）1175（B）1180（C）1205（D）1210

6．串的模式匹配是指＿＿＿＿。

（A）判断两个串是否相等（C）找某字符在主串中第一次出现的位置

（B）对两个串比较大小（D）找某子串在主串中第一次出现的第一个字符位置

7.．对关键字序列：

46、79、56、38、40、84采用快速排序方法。

若以46为枢轴，那么一次划分后的结果应该是D。

A．38，40，46，79，56，84B．38，40，46，84，56，79

C．40，38，46，79，84，56D．40，38，46，56，79，84

8.栈操作的原则是＿＿＿＿。

（A）先进先出（B）后进先出（C）只能进行插入（D）只能进行删除

9．将一棵有50个结点的完全二叉树按层编号，那么编号为25的结点是B。

A．无左、右孩子B．有左孩子，无右孩子

C．有右孩子，无左孩子D．有左、有孩子

10．在长度为n的顺序表中，往其第i个元素（1≤i≤n）之前插入一个新的元素时，需要往后移动B个元素。

A．n-iB．n-i+1C．n-i-1D．i

1、D2、A3、C4、B5、B6、D7、D8、B9、B10B

1.在无向图中，定义顶点Vi与Vj之间的路径为从Vi到达Vj的一个。

（A）顶点序列（B）边序列（C）权值总和（D）边的条数

2.设键字序列为３，７，６，９，８，１，４，５，２，则对它们进行排序的最小交换次数是＿＿.

（Ａ）８　　　　（Ｂ）７　　　（Ｃ）６√　　　（Ｄ）９

3．如果只想到1024个元素组成的序列中前5个最小元素，那么用（）方法最快。

（A）起泡排序（B）快速排序（C）堆排序（D）直接选择排序

4．设有一个栈，元素的进栈顺序为Ａ，Ｂ，Ｃ，Ｄ，Ｅ，＿是不可能的出栈序列．

（Ａ）ＡＢＣＤＥ　　　　　　　　　　（B）BCDEA

（Ｃ）ＥＡＢＣＤ　　　　　　　（Ｄ）ＥＤＣＢＡ

5.一个具有n个顶点的无向图中，要连通全部顶点至少需要条边。

（A）n（B）n+1（C）n/2（D）n-1

6.串的逻辑结构与的逻辑结构不同。

（A）线性表（B）栈（C）队列（D）树

7.已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为。

（A）4（B）5（C）6（D）7

8.在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0

的结点个数为_________.

（A）4（B）5（C）6（D）7

9．若一个栈的进栈序列是1、2、3、4，那么要求出栈序列为3、2、1、4时，进、出栈操作的顺序应该是A。

（注：

所给顺序中，I表示进栈操作，O表示出栈操作）

A．IIIOOOIOB．IOIOIOIOC．IIOOIOIOD．IOIIIOOO

10．在所给的4棵二叉树中，C不是完全二叉树。

1.（A）2.（Ｃ）3.（D）4.（Ｃ）5.（D）6.（D）7.（B）8.（C）

9.（A）10.（Ｃ）

1．有下面的算法段：

for（i=0;i

k++;

其时间复杂度为B。

A．O

（1）B．O（n）C．O（log2n）D．O（n2）

2．下面，对非空线性表特点的论述，C是正确的。

A．所有结点有且只有一个直接前驱

B．所有结点有且只有一个直接后继

C．每个结点至多只有一个直接前驱，至多只有一个直接后继

D．结点间是按照1对多的邻接关系来维系其逻辑关系的

3．将一棵有50个结点的完全二叉树按层编号，那么编号为25的结点是B。

A．无左、右孩子B．有左孩子，无右孩子

C．有右孩子，无左孩子D．有左、有孩子

4．一棵二叉树度2的结点数为7，度1的结点数为6。

那么它的叶结点数是C。

A．6B．7C．8D．9

5．对于一个有向完全图来说，它的每个不同顶点对之间，都存在有两条弧。

因此，有n个顶点的有向完全图包含有A条边。

A．n（n-1）B．n（n+1）C．n（n-1）/2

6．从待排序序列中依次取出元素与已排好序的序列里的元素进行比较，并存放到已排序序列的正确位置上，这种排序方法是A。

A．直接插入排序B．交换排序C．冒泡排序D．选择排序

7．下列说法中，正确的是A。

A．树的先序遍历序列与其对应的二叉树的先序遍历序列相同

B．树的先序遍历序列与其对应的二叉树的后序遍历序列相同

C．树的后序遍历序列与其对应的二叉树的先序遍历序列相同

D．树的后序遍历序列与其对应的二叉树的后序遍历序列相同

8．当两个元素出现逆序时就交换它们的位置，这种排序方法是C。

A．直接插入排序B．冒泡排序C．交换排序D．选择排序

9．在对线性表进行折半查找时，要求线性表必须B。

A．以顺序方式存储

B．以顺序方式存储，且结点按关键字有序排列

C．以链式方式存储

D．以链式方式存储，且结点按关键字有序排列

10．从链栈中删除一个结点时，操作顺序应该是A。

A．先保存被删结点的值，再修改栈顶指针

B．先修改栈顶指针，再保存被删结点的值

C．无须修改栈顶指针的值

D．谁先谁后没有关系

1．链栈与顺序栈相比，一个较为明显的优点是D。

A．通常不会出现栈空的情形B．插入操作更加便利

C．删除操作更加便利D．通常不会出现栈满的情形

2．在一个无向图中，所有顶点的度数之和，是其所有边数之和的C倍。

A．1/2B．1C．2D．4

3．对关键字序列：

46、79、56、38、40、84采用快速排序方法。

若以46为枢轴，那么一次划分后的结果应该是D。

A．38，40，46，79，56，84B．38，40，46，84，56，79

C．40，38，46，79，84，56D．40，38，46，56，79，84

4．D是图状关系的特例。

A．只有线性关系B．只有树型关系

C．线性关系和树型关系都不D．线性关系和树型关系都

5．在长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要往前移动A个元素。

A．n-iB．n-i+1C．n-i-1D．i

6．在一个循环顺序队列里，队首指针Cq_front总是指向B。

A．队首元素B．队首元素的前一个队位

C．任意位置D．队首元素的后一个队位

7．深度为6的二叉树，最多可以有A个结点。

A．63B．64C．127D．128

8．设有一个5阶上三角矩阵A，将其元素按列优先顺序存放在一维数组B中。

已知每个元素占用2个存储单元，B[1]的地址是100。

那么A[3][4]的地址是A。

A．116B．118C．120D．122

9．在对线性表进行折半查找时，要求线性表必须B。

A．以顺序方式存储

B．以顺序方式存储，且结点按关键字有序排列

C．以链式方式存储

D．以链式方式存储，且结点按关键字有序排列

10．将一棵有50个结点的完全二叉树按层编号，那么编号为25的结点是B。

A．无左、右孩子B．有左孩子，无右孩子

C．有右孩子，无左孩子D．有左、有孩子

11．当线性表的数据元素个数基本稳定、很少进行插入和删除操作，但却要求以最快的速度存取表中的元素时，我们应该对该表采用顺序存储结构。

四、应用

1．若元素进栈的序列是1、2、3、…、n，有一个出栈序列的第1个元素是n。

那么，这个出栈序列的第i个元素是什么？

答：

由于栈具有“先进后出”的特性，因此只有将1、2、3、…、n依次都进栈后，出栈序列的第1个元素才能是n。

所以，在这个出栈序列里，第个i元素应该是n-i+1。

2．有人说，有一棵结点数为n>1的二叉树，只包含有一个叶结点。

这可能吗？

如果可能的话，这样一棵二叉树应该是个什么样子呢？

答：

这是完全可能的，这种二叉树是从根结点开始只有左子树，或只有右子树的单支二叉树，如图所示。

3．权值序列为：

10、16、20、6、30、24，请用图示来表达构造一棵哈夫曼树的全过程。

答：

构造这棵哈夫曼树的全过程如下所示。

4．已知一棵树的孩子链表表示法如图6-24所示，试画出该树。

图6-24一棵树的孩子链表表示法

答：

该树形状如下图所示。

5．有如图7-23所示的一个无向图，给出它的邻接矩阵以及从顶点v1出发的深度优先遍历序列。

答：

它的邻接矩阵如图所示。

从顶点v1出发的深度优先遍历序列为：

v1->v2->v4->v5->v7->v6->v3

注意，该序列是不唯一的。

6．有两个关键字序列：

3、10、12、22、36、18、28、40和5、8、11、15、23、20、32、7。

试问谁是堆，谁不是堆？

把不是堆的序列通过筛选将它调整为一个堆。

答：

依照序列的顺序，画出对应的完全二叉树如（a）和（b）所示。

可以看出，（a）是一个堆，（b）则不是，因为结点7破坏了堆的性质。

为此，先将7和15对换，如图（c）所示；然后再将7和8对换，如图（d）所示。

这时，序列2就被调整为是一个堆了。

1．对于树的各种遍历，哪一种遍历是

（1）首先访问树的根结点？

（2）位于最左边的结点最先访问？

（3）根结点最后访问？

（4）最右边的结点最后访问？

答：

（1）层次遍历和先序遍历总是首先访问树的根结点；

（2）后序遍历总是最先访问位于树最左边的结点；（3）后序遍历总是最后访问树的根结点；（4）前序遍历总是最后访问树的最右边的结点。

2．试述栈与队列各自具有什么样的逻辑特点？

它们之间又有什么共同点？

答：

对于栈来说，由于只能在栈顶处进行插入和删除操作，这就使得数据元素到达栈（即往栈里插入元素）的顺序与数据元素离开栈（即从栈里删除元素）的顺序恰好相反。

所以，堆栈的逻辑特点是后进先出（LIFO），或先进后出（FILO）。

而对队列来说，插入在一端进行，删除在另一端进行，这就使得数据元素到达队列（即往队列里插入元素）的顺序与数据元素离开队列（即从队列里删除元素）的顺序是完全一致的。

所以，队列的逻辑特点是先进先出（FIFO）或后进后出（LILO）。

它们之间的共同之处是插入和删除只能在表的端点处进行（要知道，对于线性表，可以在表的任何位置处插入和删除）。

3．设有6个元素a1、a2、a3、a4、a5、a6，它们以此顺序依次进栈。

假定要求它们的出栈顺序是a4、a3、a2、a6、a5、a1，那么应该如何安排push和pop操作序列？

答：

所需的push和pop操作序列如下：

push，push，push，push，pop，pop，pop，push，push，pop，pop，pop

4．有两个关键字序列：

3、10、12、22、36、18、28、40和5、8、11、15、23、20、32、7。

试问谁是堆，谁不是堆？

把不是堆的序列通过筛选将它调整为一个堆。

答：

依照序列的顺序，画出对应的完全二叉树如（a）和（b）所示。

可以看出，（a）是一个堆，（b）则不是，因为结点7破坏了堆的性质。

为此，先将7和15对换，如图（c）所示；然后再将7和8对换，如图（d）所示。

这时，序列2就被调整为是一个堆了。

5．给出如图6-27所示树的先序遍历序列和后序遍历序列。

答：

该树的先序遍历序列为：

A-B-E-F-K-L-M-C-G-D-H-I-J；该树的后序遍历序列是：

E-K-M-L-F-B-G-C-H-I-J-D-A。

6．有人说，有一棵结点数为n>1的二叉树，只包含有一个叶结点。

这可能吗？

如果可能的话，这样一棵二叉树应该是个什么样子呢？

答：

这是完全可能的，这种二叉树是从根结点开始只有左子树，或只有右子树的单支二叉树，如图所示。

1.已知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，请构造出该二叉树。

（5分）

参考答案及评分标准：

2.已知图如下：

答案：

（1）试求图的邻接矩阵表示。

（2）试求图的邻接表表示。

答：

（1）邻接矩阵表示：

ABCDEF

------------------------

A|011000

B|001001

C|000100

D|000001

E|000101

F|000000

（2）邻接表表