广西工学院《数据结构与算法》考试试题2010(A)-答案解析最新(7)

堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。 3. 排序过程：

堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。 【示例】：对关键字序列42，13，91，23，24，16，05，88建堆

10、对以下四组原始数据用快速排序法排序， D 组的情况速度最慢。

A. 19 23 03 15 07 21 28 B. 23 21 28 15 19 03 07 C. 19 07 15 28 23 21 03 D. 03 07 15 19 21 23 28

还是要熟悉快速排序的过程：D答案中13应改为03，4组都一样的数据，序列不一样。

11、对于已排好序的、具有12个数据元素的线性表，采用冒泡排序方法排序时最少需

要 比较。

A. 1 B. 144 C. 11 D. 66

考冒泡排序法：熟悉算法过程（最好是把程序写出来），就得出答案了。

For(i=0;i<n-1;i++) For(j=0;j<n-1-I;j++) If(a[j]>a[j+1]则交换

注意：如果按照一般的冒泡排序，则答案是：D：11+10+。。。+1=66 但稍微优化一下冒泡排序法，答案是C Int f=0;

For(i=0;i<n-1;i++) { For(j=0;j<n-1-I;j++)

If(a[j]>a[j+1])则{F=1；交换} if(！f)break;

//如果第一趟排序，发现已经是有序，则退出了，只比较了第一趟的11次

}

（这一题有争议，我的意见是看题目的意思，趋向于答案C）

12、在一个有n（n≥1）个顶点的有向图中，边数最多为

A、n-1 B、n n(n-1)/2

有向图的特征：画一个图，就得到答案了。 4个结点，12条边

C、n(n-1) D、

13、在有n个结点的二叉链表中，值为非空的链域的个数为 A 。

A. n-l B. 2n-l C. n＋l D. 2n＋1

二叉链表的特征：n个结点，则链指针有所指的为n-1,:2叉链表，则总链域个数2n，头指针指向根结点，其余n-1个结点，共需要n-1个指针域（非空），注意，空链域个数：2n-（n-1）=n+1 (原有答案出错)

14、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中 D 。 A. 第i行非∞的元素之和 B. 第i列非∞的元素之和

C. 第i行非∞且非0的元素个数 D. 第i列非∞且非O的元素个数

有向图中，结点i的入度就是指向 i结点的弧的条数,而邻接矩阵是行数据中非0非无穷元素个数为i的

出度，列才为入度（原有答案出错）。

15、从下图中顶点A出发，采用深度优先遍历，则下列各顶点序列中，不是遍历结果的

是

A、ABCDEGF B、ABFDCGE C、AGDEBFC D、AFDGECB

图的深度优先和广度优先都要弄清楚。深度优先为相连访问（注意退回到还有连接结点没有访问过的那个结点上，广度优先为层次访问,先访问的结点其子树也先访问（子树访问无次序，仅对下层访问有影响）（最好先把层次图画出）。

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科广西工学院《数据结构与算法》考试试题2010(A)-答案解析最新(7)全文阅读和word下载服务。