软件开发技术基础 第4版 习题答案 -第2章.docx

第2章习题参考解答

一、名词解释

线性表：线性数据结构是由有限个元素组成的有序序列，记作（a0,a1,…,an）。除了a0和an之外，任意元素ai都有一个直接前趋ai-1和一个直接后继ai+1。a0无前趋，an无后继。

栈：是限制在表的一端进行插入和删除操作的线性表。

队列：是只能在表的一端进行插入，而在另一端进行删除操作的线性表。

完全二叉树：从满二叉树叶子所在的层次中，自右向左连续缺少若干叶子所得到的二叉树被称为完全二叉树。

带权路径长度：二叉树有n个带有权值的叶子结点，每个叶子到根的路径长度乘以其权值之和称为二叉树带权路径长度。

无向图：若图是由一些顶点和边构成则称之为无向图。

图中的路径:在图中，若从顶点vi出发，沿一些边或弧，经过顶点vp1，vp2，…，vpm，到达顶点vj。则称顶点序列(vi，vp1，vp2，…，vpm，vj)为从顶点vi到顶点vj的路径。

生成树: 在无向图中，一个连通图的生成树是它的极小连通子图，它包含了所有顶点以及足以够成一棵树的边，并且这些边使得任意两顶点相互连通。

平均查找长度:是为了确定数据元素在查找表中的位置，需要将给定值和表中的数据元素的关键字进行比较的次数的期望值。

图中的弧:若顶点x到y是的一条单向通路，则称为弧，用x，y表示。

连通图:在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi与vj是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图。

二、填空题

1.算法效率的衡量主要有两个指标：时间复杂度和空间复杂度。

2．采用顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也相邻。

3．单链表用一组地址任意的存储单元存放线性表中的数据元素。其逻辑上相邻的元素的物理位置不一定相邻。

4．单链表每个结点都包含数据域和指针域两部分。

5．为了能顺次访问单链表的每个结点，需要保存单链表第一个结点的存储地址。这个地址称为单链表的头指针。

6．为了操作上的方便，可以在单链表的头部增加一个特殊的结点，称为头结点。该结点的数据域为空。

7．树有且只有一个根结点，没有孩子结点的结点可称为叶子，二叉树的每个结点至多只有两棵子树。

8．图结构又可分为无向图和有向图两大类。在图结构中，数据元素通常称为顶点；两个数据元素间的联系在有向图中称为弧，在无向图中称为边。

三、判断题

（1）线性表每个结点都有一个前趋和一个后继。（错）

（2）二叉树不能用顺序方式存储。（错）

（3）哈夫曼树又称最小生成树。（错）

（4）图的深度优先遍历优于广度优先遍历。（错）

（5）平均查找长度就是时间复杂度。（错）

（6）冒泡排序的时间复杂度优于简单选择排序。（错）

四、选择题

1.一个有头结点的单链表中,P为指向头结点的指针,则首元(位于头结点之后)指针可表示为()。

A.P.next.nextB.PC.P.dataD.P.next

答：D

2.数列4321依次执行入栈操作，在入栈过程中可以随时执行出栈操作，则其出栈顺序可能是（）。

A.1423B.2413C.1234D.4132

答：C

3.具有35个结点的完全二叉树的深度为（）。

A.4B.6C.8D.12

答：B

4.对长度为12的有序表进行二分查找，在等概率情况下，查找成功的ASL为（）。

A.37/12B.39/11C.34/12D.33/11

答：A

5．一棵完全二叉树共有200个数据元素，自上而下自左向右编号，则第67号点的右孩子是（）号。

A．134 B.135C.136 D.137

答：B

6.二叉树的中序遍历顺序为abcd，先序遍历顺序为cabd,则二叉树是下列（）。

abcdc

a

b

c

d

c

a

d

b

a

b

d

c

c

a

b

d

A.B.C.D.

答：B

7.下列哪一种形式可能是一个图的生成树（）

A.