大学计算机基础 第4章 数据结构--习题答案学习资料.doc

一、填空题

1．数据结构

2．数据的逻辑结构

3．线性结构、树形结构、图状结构、集合结构

4．顺序存储、链式存储

5．31

6．5

7．2i-1

8．先序遍历、中序遍历、后序遍历

9．0

10．指针

二、选择题

1-5:BDBAB6-11:BCBCBD

三、判断题

1-7:错对错对错对对

四、简答题

1.什么是栈？栈的操作特点是什么？

答案：栈是限定只能在一端进行插入和删除操作的线性表。操作特点是后进先出。

2.假定有四个元素A,B,C,D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。

答案：共14种：ABCD,CDBA,DCBA,BCDA,BDCA,BCAD,BADC

BACD,CBAD,CBDA,CDBA,ADCB,ACDB,ACBD

3．对于栈来说栈空和栈满的两个限制条件是什么？

答案：栈空条件：s—top=0，此时不能进行出栈操作

栈满条件：s—top=Maxsize-1，此时不能进行进栈操作

4.什么是队列？队列的操作特点是什么？

答案：队列是在一端进行插入操作，在另一端进行删除操作的线性表，操作特点是先进先出。

5.简述二叉树的性质

答案：(1)在二叉树中，第i层的结点总数不超过2i-1(i=1)；

(2)深度为h的二叉树最多有2h-1个结点(h=1)，最少有h个结点；

(3)如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

(4)具有n个结点的完全二叉树的深度为int（log2n）+1；

(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则如果I≠1，则其父结点的编号为int(I/2)；

如果2*I=N，则其左儿子的编号为2*I；否则无左儿子；

如果2*I+1=N，则其右儿子的结点编号为2*I+1；否则无右儿子。

6.一棵完全二叉树有10个结点，各结点按自上至下、由左至右编号为1、2、3……10。问该二叉树有几层？编号为5的结点的父结点是几号结点，5号结点有没有左孩子和右孩子？如果有，编号分别是多少？如果没有，为什么？

答案：

该二叉树有4层，[log210]+1=4

5号结点的父结点是2号结点。

5号结点有左孩子，编号是10

5号结点没有右孩子，因为5号结点的右孩子编号应该是2*5+1=11，11＞10，所以没有右孩子。

7.写出下面二叉树的三种遍历顺序。

答案：先序遍历序列：abdgcefhi

中序遍历序列：dgbaechif

后序遍历序列：gdbeihfca