计算机习题答案_20140621..docVIP

2.1 什么是数据结构？它对算法有什么影响？ 答： 数据结构是指同一数据对象中各数据元素间存在的关系，可以看作是相互之间存在着某种特定关系的数据元素的集合。 对算法是影响：算法的效率与数据结构有关，数据结构的选择对算法实现的效率起至关重要的作用。 2.2何谓算法？它与程序有何区别？ 算法是解决某一特定类型问题的有限运算序列。 和程序的区别：一个程序包括数据结构和算法两个方面的内容，算法是程序的一个要素。 2.6 数据的存储结构主要有哪两种?它们之间的本质区别是什么？ 数据的存储结构主要有顺序存储结构和链式存储结构。 本质区别：顺序存储结构的存储空间是连续的，数据元素间的逻辑关系借助存储的相对位置来表示；链式存储结构不需要一组连续的存储单元，其数据元素可以分散存放在存储空间中，其数据元素之间的逻辑关系借助指针来表示。 2.12 试编写算法求已知单链表的长度，并考虑表空的情况 int GetListLength(Node* pHead) { int i = 0; Node* pCur = pHead; while (pCur != NULL) { i++; pCur = pCur-next; } return i; } 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; 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; } Node* pNext = pCur-next; // 将新节点插入到单链表的表尾 if (pNext == NULL) { pCur-next = pNewNode; break; } // 将新节点插入到单链表的中间 if (pNext-data pNewNode-data) { pNewNode-next = pNext; pCur-next = pNewNode; break; } pPre = pCur; pCur = pNext; } return; } 2.28 将下列的一般树化为二叉树 转换后的二叉树如右图所示 转换后 2.30 设一棵二叉树其中序和后序遍历为，中序：BDCEAFHG 后序：DECBHGFA画出这棵二叉树的逻辑结构，并写出先序遍历结果。 先序遍历：ABCDEFGH。其逻辑结构如下： 2.32 给定一组元素｛17，28,36,54,30,27,94,15,21,83,40｝，画出由此生成的二叉排序树。 2.33 定一组权值W={8，2，5，3，2，17，4}，画出由此生成的哈夫曼树。 生成的哈夫曼树为： 或者