计算机习题答案 - 20140621

2.1 什么是数据结构？它对算法有什么影响？ 答：

数据结构是指同一数据对象中各数据元素间存在的关系，可以看作是相互之间存在着某种特定关系的数据元素的集合。

对算法是影响：算法的效率与数据结构有关，数据结构的选择对算法实现的效率起至关重要的作用。

2.2何谓算法？它与程序有何区别？

算法是解决某一特定类型问题的有限运算序列。

和程序的区别：一个程序包括数据结构和算法两个方面的内容，算法是程序的一个要素。

2.6 数据的存储结构主要有哪两种?它们之间的本质区别是什么？

数据的存储结构主要有顺序存储结构和链式存储结构。

本质区别：顺序存储结构的存储空间是连续的，数据元素间的逻辑关系借助存储的相对位臵来表示；链式存储结构不需要一组连续的存储单元，其数据元素可以分散存放在存储空间中，其数据元素之间的逻辑关系借助指针来表示。

2.12 试编写算法求已知单链表的长度，并考虑表空的情况

int GetListLength(Node* pHead) { }

return i; int i = 0;

Node* pCur = pHead; while (pCur != NULL) { i++;

pCur = pCur->next; }

2.13 试编写算法删除单链表中的第K个节点

// 2.13 删除单链表中的第k个节点。注： 节点序号从1开始 void RemoveNode(Node*& pHead, int k) {

Node* pPre = NULL; Node* pCur = NULL; pCur = pHead; int i = 1;

while (pCur != NULL) {

// 不是要删的节点序号，则继续下一个节点

if (k != i) {

pPre = pCur;

pCur = pCur->next;

1

i++; continue;

}

// 要删除的就是第一个节点 if (k == 1) { pHead = pCur->next; } else {

// 要删除的是中间某个节点 pPre->next = pCur->next; }

delete pCur;

}

}

2.14 已知一单向链表中数值已按递增有序排列，先要插入一个新节点，并使插入后链表仍为有序序列// 可参考胶片19页 Typedef struct tagNode {

Int data; Node* next; }Node;

void InsertNode(Node*& pHead, Node* pNewNode) {

// 链表为空时，将该节点作为链表的第一个节点 if (pHead == NULL) {

pHead = pNewNode; return; }

Node* pPre = NULL; Node* pCur = pHead; while(pCur != NULL) { // 新节点的数据比单链表的头节点的数据小，则将新节点插入到最开头 if (pCur->data > pNewNode->data) { pNewNode->next = pCur; pHead = pNewNode; break;

}

2

}

} return;

Node* pNext = pCur->next;

// 将新节点插入到单链表的表尾 if (pNext == NULL) { }

// 将新节点插入到单链表的中间 if (pNext->data > pNewNode->data) { }

pPre = pCur; pCur = pNext;

pNewNode->next = pNext; pCur->next = pNewNode; break;

pCur->next = pNewNode; break;

2.28 将下列的一般树化为二叉树

转换后的二叉树如右图所示

转换后

2.30 设一棵二叉树其中序和后序遍历为，中序：BDCEAFHG 后序：DECBHGFA画出这棵二叉树的逻辑结构，并写出先序遍历结果。

先序遍历：ABCDEFGH。其逻辑结构如下：

3

A B F C G D E H

2.32 给定一组元素｛17，28,36,54,30,27,94,15,21,83,40｝，画出由此生成的二叉排序树。

2.33 定一组权值W={8，2，5，3，2，17，4}，画出由此生成的哈夫曼树。 生成的哈夫曼树为：

或者

2.34 有一图如下图所示：

由节点V1 作深度优先搜索和广度优先搜索。

深度： 1 5 4 3 2 10 11 12 13 14 15 6 7 8 9 18 19 20 16 17 广度： 1 8 7 6 5 17 18 9 16 15 10 2 14 13 20 19 11 4 3 12 3

2.42 对于给定的一组关键字：41，62，13，84，35，96，57，39，79，61，15，83。分别写出：插入排序，简单选择排序、堆排序、冒泡排序、快速排序、二叉树排序的排序过程，并对排序方法进行分析。

4

插入

13 41 62 84 35, 96,57,39, 79,61,15,83 13 35 41 62 84 96 57 39 79 61 15 83 13 35 41 57 62 84 96 39 79 61 15 83 13 35 39 41 57 62 84 96 79 61 15 83 13 35 39 41 57 62 79 84 96 61 15 83 13 35 39 41 57 61 62 79 84 96 15 83 13 15 35 39 41 57 61 62 79 84 96 83 13 15 35 39 41 57 61 62 79 83 84 96

对于具有n个记录的文件，要进行n-1趟排序 就地排序

稳定的排序方法

简单选择排序

41 62 13 84 35 96 57 39 79 61 15 83 13 41 62 84 35 96 57 39 79 61 15 83 13 15 41 62 84 35 96 57 39 79 61 83 13 15 35 41 62 84 96 57 39 79 61 83 13 15 35 39 41 62 84 96 57 79 61 83 13 15 35 39 41 57 62 84 96 79 61 83 13 15 35 39 41 57 61 62 84 96 79 83 13 15 35 39 41 57 61 62 79 84 96 83 13 15 35 39 41 57 61 62 79 83 84 96

堆排序

41 62 13 84 35 96 57 39 79 61 15 83

96, 84, 83, 79, 62, 61, 57, 41, 39, 35, 15, 13

冒泡排序

41, 13, 62, 35, 84, 57, 39, 79, 61, 15, 83, 96 13, 41, 35, 62, 57, 39, 79, 61, 15, 83, 84, 96 13, 35, 41, 57, 39, 62, 61, 15, 79, 83, 84, 96 13, 35, 41, 39, 57, 61, 15, 62, 79, 83, 84, 96 13, 35, 39, 41, 57, 15, 61, 62, 79, 83, 84, 96 13, 35, 39, 41, 15, 57, 61, 62, 79, 83, 84, 96 13, 35, 39, 15, 41, 57, 61, 62, 79, 83, 84, 96 13, 35, 15, 39, 41, 57, 61, 62, 79, 83, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 83, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 83, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 83, 84, 96 13, 15, 35, 39, 41, 57, 61, 62, 79, 83, 84, 96

快速排序

13, 35, 39, 15, 41, 96, 57, 83, 79, 61, 84, 62 13, 35, 39, 15, 41, 96, 57, 83, 79, 61, 84, 62 13, 15, 35, 39, 41, 96, 57, 83, 79, 61, 84, 62

5

本文来源：https://www.bwwdw.com/article/8h8f.html