数据结构 练习题1答案 一、简答题
1．什么是有根的有向图？
答：在一个有向图中，若存在一个顶点V0，从该顶点有路经可以到达图中其他所有顶点，则称此有向图为有根的有向图，V0称作图的根。 2．什么是负载因子？
答：负载因子(load factor)，也称为装填因子，定义为：
? ? 散列表中已存入的结点个数 n ? 基本区域所能容纳的结点个数 m 3．试分析顺序存储结构的优缺点。 答：优点：⑴ 内存的存储密度高(d=1)；
⑵ 可以随机地存取表中的结点,与i的大小无关。
缺点：⑴ 进行插入和删除结点的运算时，往往会造成大量结点的移动，效率较低；
⑵ 顺序表的存储空间常采用静态分配，在程序运行前存储规模很难预先确定。估计过大将导致空间的浪费，估计小了，随着结点的不断插入，所需的存储空间超出了预先分配的存储空间，就会发生空间溢出。
4．算法的时间复杂度仅与问题的规模相关吗？
答：算法的时间复杂度不仅与问题的规模相关而且还与数据结构中的数据分布有关。 5．什么是线索二叉树(threaded binary tree)？
答：加进了线索的lchild-rchild存储表示的二叉树称作线索二叉树(threaded binary tree)， 简称为线索树。 6．什么是有向完全图(directed complete graph)？
答：在具有n个顶点的有向图中，其边数等于n(n-1)的有向图,称作有向完全图(directed complete graph)。 7．在链表中引入表头结点的优点(或好处)是什么?
答：增加表头结点的优点(或好处)是使得运算简单、处理方便。
8．请分别指出使快速排序算法的时间代价为最小和最大的两种待排序文件的初始状态。
答：时间代价为最小：每次递归调用都是将划分的区间分成长度相等的两部分，基准记录正好放在这两组的中间。
时间代价为最大：待排序文件的初始状态已为有序。 9．什么是二叉树(binary tree)？
答：二叉树(binary tree)是n(≥0)个结点的有限集合，这个集合或者是空集，或者是由一个根结点加上两棵不相交的分别称为这个根的左子树和右子树的二
叉树组成。
10．什么是无向完全图(undirected complete graph) ？
答：在具有n个顶点的无向图中，其边数等于n(n-1)/2的无向图称作无向完全图(undirected complete graph)，简称完全图。
11．试分析顺序存储结构和链接存储结构各自的优点。 答：顺序存储结构的优点：① 内存的存储密度高；
② 当结点等长时，可以随机地存取表中的结点。
链接存储结构的优点： ① 插入和删除结点的运算效率高；
② 采用动态分配，存储空间扩增方便。
12．为什么说冲突只能尽量地减少，但不可完全避免 ？
答：因为通常可能的关键字集合的规模要远远大于散列表的基本区域的容量，因此，要将可能的关键字集合中的关键字压缩存储到散列表的基本区域时，就不
可避免地会发生冲突，而只能设法减少冲突。
第 1 页 共 2 页 (xxxxxxxxx (高起本) )
二、单选题
1． D 2． C 3. C 4. C 5. D 6. D 7． B 8． C 9. B 10. B 11. C 12. B 13． D 14． C 15. D 16. C 17. D 18. C 三、判断题
1. ? 2． ? 3． ? 4. ? 5. ? 6. ? 7. ? 8． ? 9． ? 10. ? 11. ? 12. ? 13. ? 14． ? 15． ? 16. ? 17. ? 18. ? 四、填空题
1． 逻辑 2. 运算简单（或处理方便） 3. 中序序列 4. Ο( n2 ) ， 稠密。5. 交换排序
6．从任一结点出发都可访问到链表中的每一个元素 7. n2 + 1 8. 度； 出度。9. 93 10. 直接插入排序 11． 开始结点 12. n + 1 13. 带权的无向 14. 直接选择排序，直接插入排序( 最小的元素在最后时 )。15. 左 五、图示题
1．设待排序文件的初始排序码序列为 { 32, 38, 10, 53, 80, 69, 32, 05 }，写出采用冒泡排序算法排序时，每趟结束时的状态。 解：冒泡排序算法排序时，每趟结束时的状态如下：
R[ ]初态12345678第1趟12345678第2趟12345678第3趟12345678第4趟1234567832381053806932050532381053806932flag=10510323832538069flag=10510323238536980flag=10510323238536980flag=0排排排排2．设有关键字集合为 { 16,05,28,10,09,17 }，散列表的长度为8，用除留余数法构造散列函数，用线性探查法解决冲突，并按关键字在集合中的顺序插入，请画出此散列(哈希)表，并求出在等概率情况下查找成功的平均查找长度。 解：
keyn = 6；m = 8； h(key) = key % 716050512801100310902317034h(key)02比较次数1(a) 计算过程0 1 2 3 4 5 6 7281610090517(b) 散列表 ht[0 ..7]用线性探查法解决冲突平均查找长度ASL = (1+1+1+1+3+4)/6 = 11/6 ≈ 1.83
3．给定一组权W = { 3, 5, 10, 12, 15, 22 }，构造哈夫曼(Huffman)树，并计算它的带权外部路径长度WPL。 解： Huffman树： 27
22181215
810 35
4067
带权的外部路径长度：
i WPL = wli = 4×(3+5)+3×10+2×(12+15+22) = 32 + 30 + 2×49 = 160
i?0?m?14．已知一个有向图如右下图所示，请分别写出从顶点a出发进行深度优先遍历(DFS)和广度优先遍历(BFS)所得到的顶点序列及生成树(林)。（要求：有多个顶
点可供选择时，序号小的优先。） 解：
⑴ 深度优先遍历(DFS) ⑵ 广度优先遍历(BFS)
acbdefgih第 2 页 共 2 页 (xxxxxxxxx (高起本) )
顶点序列：abdcefigh 顶点序列：abcdefghi
生成树: 生成树:
badefgiabdefgicc5．设待排序文件的初始排序码序列为 { 28, 55, 36, 05, 43, 24, 62, 17 }，写出采用归并排序算法排序时，每趟结束时的状态。 hh解：
6．对于右下图所示的二叉树，请画出它的后序线索二叉树。 解：二叉树的结点后序序列为：DCBFGEA ( 4分)
后序线索二叉树为： ( 10分)
BE初始状态：第一趟归并后：282805555528360536053655432417244324621743176262第二趟归并后：第二趟归并后：0517242836435562A
AE
BCGFGCFDD六、算法题
1、二叉树以二叉链表(lchild-rchild表示法)作为存储结构，试编写计算二叉树中叶结点个数的算法(要求写出存储结构的描述)，并分析算法的时间复杂度。
解：存储结构描述如下：
const int MaxSize =100; typedef char datatype; typedef struct node {
datatype data; struct node *lchild, *rchild; } BTnode, *BinTree; BinTree root; BTnode* p;
int num; // 统计二叉树中叶结点个数的变量
进入算法时，指针root指向根结点
算法结束时，二叉树中分支结点个数保存在变量num中。
（说明：下面的算法和C/C++ 程序只要给出其中一种形式即可。） // 调用为InOrderCount (root, num)，mun的初值为0。
算法 计算二叉树中叶结点个数 C/C++ 程序：
InOrderCount (p, num) InOrderCount (BinTree p, int &num) { 1. 若p≠NULL if ( p!=NULL) {
则 ⑴ InOrderCount (p->lchild) InOrderCount (p->lchild); ⑵ 若p->lchild = NULL 且 if (p->lchild = = NULL &&
p->rchild = NULL p->rchild = = NULL))
则 num ← num+1 num++;
⑶ InOrderCount (p->rchild) InOrderCount (p->rchild);
} 2. [算法结束 ] ▍ }
第 3 页 共 2 页 (xxxxxxxxx (高起本) )
设二叉树中有n个结点，因为是遍历运算，故此算法的时间复杂度为：O(n)。 说明：答案不唯一，也可以用前序遍历或后序遍历
2、设有n个结点的二叉树用二叉链表(即lchild-rchild表示法)进行存储。编写算法：判断此二叉树是否是正则二叉树（即每个分支结点都恰有两个子女的二叉树）。请分析算法的时间复杂度。
解：typedef struct node {
Datatype data;
struct node *lchild, *rchild; } BTnode, *BinTree; BinTree root; BTnode *p;
SeqStack ST; 进入算法时，栈为空进入算法时栈为空,
算法结束时，是正则二叉树返回1，否则返回0。
（说明：下面的算法和C/C++ 程序只要给出其中一种形式即可。）
算法 判断二叉树是否是正则二叉树 C/C++ 程序：
PreOrder (root) int PreOrder (BinTree root) {
1. p ← root BTnode* p; SeqStack ST; ClearStack(ST); 2. 循环 当 (p≠NULL) 或 p = root;
(非StackEmpty(ST)) 时,执行 while ( (p!=NULL) || (!StackEmpty(ST)) ) { 若p≠NULL if (p!=NULL) {
则 ⑴ 若 (p->lchild≠NULL 且p->rchild=NULL) if ((p->lchild!=NULL && p->rchild=NULL)
或(p->lchild=NULL且p->rchild≠NULL) || (p->lchild = NULL && p->rchild!=NULL)) 则 return 0 return 0;
⑵ push(ST,p); p ← p->lchild push(ST,p); p = p->lchild; } 否则 pop(ST,p); else { pop(ST,p); p ← p->rchild p = p->rchild; } 3. return 1 } 4. [算法结束 ] ▍ return 1;
}
因为是遍历运算，有n个结点，所以算法的时间复杂度为：O(n)。
说明：答案不唯一，也可以用中序遍历或后序遍历。
3、设有用表头指针head指向的单链表，其数据域为整型。请编写算法，通过调整指针将数据域为负值的结点在链表中都排在非负值结点之前(要求写出存储结构的描述)。 解：
存储结构描述如下： typedef int datatype; typedef struct node { datatype data; struct node *next; } ListNode, *LinkList; ListNode *p, *q; LinkList head, rear;
具体算法如下：
算法 单链表的部分排序 C/C++ 程序：
PartSortLinkedList (head ) void PartSortLinkedList (LinkList& head ) { ⒈ 若head = NULL ListNode *p,*q,*rear;
则 算法结束 if (head == NULL) return;
⒉ p← head ->next; head ->next ← NULL; p = head ->next; head ->next = NULL; rear ← head rear = head; ⒊ 循环，当 p ≠ NULL 时，执行 while ( p!=NULL ) {
⑴ q ← p; p ← p ->next q = p; p = p ->next; ⑵ 若q->data < 0 //插表首 if (q->data < 0 ) {
headV headVVa0reara0a1pa1...an-1...an-1排 排第 4 页 共 2 页 (xxxxxxxxx (高起本) )
则q->next ← head; head ← q q->next = head; head = q;} 否则q->next ← NULL; //插表尾 else {
rear ->next ← q; q->next = NULL; rear ← q rear ->next = q; rear = q; } } 4. [算法结束 ] ▍ }
（注：上面的算法和C/C++ 程序只要给出其中一种形式即可。）
数据结构 练习题2答案 一、简答题
1．什么是满二叉树(full binary tree) ？
答：满二叉树(full binary tree) 是高度为h且有2h+1 -1个结点的二叉树。
2．什么是排序 (sorting) ？
答：排序就是将待排序文件中的记录按排序码不减(或不增)的次序排列起来。 3．什么样的图遍历后由所有顶点和遍历时所经过的边所构成的子图一定是生成树 ？
答：对于连通的无向图或强连通的有向图，从图的任何一个顶点出发；对于有根的有向图，从根出发；遍历后由所有顶点加上遍历时所经过的边所构成的子
图一定是生成树。
4．举例说明散列表的平均查找长度不随表中结点数目的增加而增加，而是随着负载因子的增大而增大。
答：与其他基于比较的查找方法(如顺序查找、折半查找等)相比，这是散列法的基本特征，它是一种与负载因子有关的查找方法。
例如，当m = 100, n = 50时与当m = 10000, n = 5000时，α = n/m = 0.5,即两者的平均查找长度相同。 由于平均查找长度ASL(α)是关于负载因子α的递增函数，显然平均查找长度随负载因子的增大而增大。 5．什么是存储密度( storage density) ？
答： 存储密度( storage density) 是数据本身所占的存储量与整个结构所占的存储量之比，即
d =
6．什么是最佳二叉排序树(optimal binary sort tree) ？
答：最佳二叉排序树(optimal binary sort tree)是平均比较次数最小，也就是平均查找长度ASLn为最小的二叉排序树。 7．求最小(代价)生成树的普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法各适用于什么样的图 ？
答：因为普里姆(Prim)算法只与顶点的个数有关所以它适用于稠密图；而克鲁斯卡尔(Kruskal)算法不仅与顶点的个数有关而且还与边的个数有关所以它适用于
稀疏图。
8．举例说明直接选择排序是否是稳定的排序方法。 答：直接选择排序不是稳定的排序方法。
例如，：
5 5* 1 ? [ 1 ] 5* 5 ? [ 1 5* ] 5
最后排序结果为：1, 5*, 5。
两个相同的排序码5与 5* ，经排序后改变了他们原来的相对次序。因此该排序算法是不稳定的。
二、单选题
1． D 2． D 3. D 4. B 5. C 6. D 7． A 8． A 9. B 10. D 11. C 12. B 三、判断题
第 5 页 共 2 页 (xxxxxxxxx (高起本) )
数据本身所占的存储量 整个结构所占的存储量
奥鹏东师 数据结构练习题答案.doc
