2012秋数据 数据结构 部分答案

答案： ABCDCD

1.[3.5.1] 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的________

A. A. 行号

B. B. 列号

C. C. 元素值

D. D. 地址

2. [3.5.2] 设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为_______。

A. A. O(1)

B. B. O(n)

C. C. O(n2)

D. D. O(log2n)

3.[10.3.1] 将5个不同的数据进行排序，至多需要比较_______次。

A. A. 8

B. B. 9

C. C. 10

D. D. 25

4.[10.3.2] 从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为_________

A. A. 希尔排序

B. B. 归并排序

C. C. 插入排序

D. D. 选择排序

5.[10.3.3] 快速排序在下列哪种情况下最易发挥其长处?

A. A. 被排序的数据中含有多个相同排序码

B. B. 被排序的数据已基本有序

C. C. 被排序的数据完全无序

D. D. 被排序的数据中的最大值和最小值相差悬殊

6.[10.3.4] 外排序是指_______________________

A. A. 在外存上进行的排序方法

B. B. 不需要使用内存的排序方法

C. C. 数据量很大，需要人工干预的排序方法

D. D. 排序前后数据在外存，排序时数据调入内存的排序方法

下载office文档附件

7. 2012秋数据结构操作题

所有操作题题目均在附件中。

作业通过附件的形式提交（格式请务必使用doc格式，不要使用docx格式），请同学直接通过本系统进行网上作业提交。本课程不接收其它任何形式的作业提交（如邮件、论坛发贴等）。

上传附件时，请按照“作业系统使用说明”中的方法正确操作。

8. [3.1] 已知一个稀疏矩阵如下图所示：(参见教科书上第三章【习题 3-1】)

0 4 0 0 0 0 0

0 0 0 -3 0 0 1

8 0 0 0 0 0 0

0 0 0 5 0 0 0

0 -7 0 0 0 2 0

0 0 0 6 0 0 0

具有6行×7列的一个稀疏矩阵

(1)写出它的三元组线性表；

(2)给出它的顺序存储表示；

(3)给出它的转置矩阵的三元组线性表和顺序存储表示；

1、写出它的三元组线性表。 解：((1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,2,-7),(5,6,2),(6,4,6)) 2、给出它的顺序存储表示。 解： 下标 Row Col Val 1 1 2 4 2 2 4 -3 3 2 7 1 4 3 1 8 5 4 4 5 6 5 2 -7 7 5 6 2 8 6 4 6   3、给出它的转置矩阵的三元组线性表和顺序存储表示。 解： 三元组线性表：((1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1)) 顺序存储表示： 下标 Row Col Val 1 1 3 8 2 2 1 4 3 2 5 -7 4 4 2 -3 5 4 4 5 6 4 6 6 7 6 5 2 8 7 2 1

9. [3.3] 分别计算出下列每个广义表的长度和深度。(参见教科书上第三章【习题 3.2】)

(1) A=(())

(2) B=(a,b,c)

(3) C=(a,(b,(c)))

(4) D=((a,b),(c,d))

(5) E=(a,(b,(c,d)),(e))

(6) F=((a,(b,(),c),((d),e)))

(1) A：长度：1 深度：2 (2) B：长度：3 深度：1 (3) C：长度：2 深度：3 (4) D：长度：2 深度：2 (5) E：长度：3 深度：3 (6) F：长度：1 深度：4

10. [3.4] 设A={1,2,3}，B={3,4,5}，求下列结果：

(1) A + B （集合的并）

(2) A * B （集合的交）

(3) A - B （集合的差）

(1)集合的并A+B={1,2,3,4,5} (2)集合的交A*B={3} (3)集合的差A-B={1,2}

11.[5.1] 填在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？

结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个分支结点。

12.[5.2] 已知完全二叉树第8层有8个叶子结点，则完全二叉树的叶子结点数是多少？说明计算过程。

第8层有8个结点的完全二叉树共有8层，上面7层每一层结点都是满的，第7层的结点数是2i-1=27-1=64,其中4个结点有8个结点，则完全二叉树的叶子结点数＝64-4+8=68个

13. [5.5] 判断题

（ ）1.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。

（ ）2.二叉树中所有结点个数是2-1，其中k是树的深度。

（ ）3.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（ ）4.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2-1个结点。 （ ）5.具有12个结点的完全二叉树有5个度为2的结点。

（ × ）1.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。 （应当是二叉排序树的特点） （ × ）2.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2k-1） （ × ）3.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ × ）4.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。（应2i-1） （ √ ）5.具有12个结点的完全二叉树有5个度为2的结点。最快方法：用叶子数＝

[n/2]＝6，再求n2=n0-1=5 k-1i

14.[10.1] 已知序列{17，18，60，40，7，32，73，65，85}，请给出采用气泡排序法对该序列作升序排列时的每一趟的结果

第一趟：7，17，18，60，40，32，65，73，85 第二趟：7，17，18，32，60，40，65，73，85 第三趟：7，17，18，32，40，60，65，73，85 第四趟：没有交换元素，排序结束。

15. [10.2] 判断下列序列是否为堆（小顶堆或大顶堆），如果不是，则按算法把它调整为堆。

(1) (100,86,48,73,35,39,42,57,66,21)

(2) (12,70,33,65,24,56,48,92,86,33)

(1)是大顶堆 (2)不是堆，70和24交换后，该序列调整为小顶堆

各位同学：每隔20分钟，请务必点击页面左下角的'临时保存'按钮，保存您的作业！

倒计时:8分58秒