习 题 二
1 简述下列术语：线性表，顺序表，链表。
线性表：最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。 顺序表：是指用一组连续的存储单元一次存储线性表中的数据元素。物理结构和逻辑结构都相邻。
链表：逻辑结构相邻的数据元素物理结构不一定相邻。采用指针的形式连接起来。
2 何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?
不需要经常大量的修改表或需要随机存取的情况下可以选用顺序表；
相反需要经常大量的修改表，但不是频繁的随机存取的情况下可选用链式表。
3 在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?
答：平均需要移动n/2个结点。表的长度，和要插入的位置。
4 链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?
答：有序。有序性体现在通过指针数据元素有序的相连。物理上不一定要相邻。
5 设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。 Status ListInsert(SqList &L,int i,ElemType e) { if((i>L.length+1)||i<1) return ERROR; if(L.length>=L.listsize) { newbase=(ElemType *)realloc((L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(-1); L.elem=newbase; L.listsize+=LISTINCREMENT; } ElemType *q,*p; q=&L.elem[i-1]; for(p=&L.elem[L.length-1];p>=q;p--) *(p+1)=*p; *q=e; L.length++; return OK; }
9 设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。
void ListInsert(SqList A,SqList B,SqList C) { ElemType *p,*q,*s; P=&A; q=&B; s=&C; while(p.next!=NULL||q.next!=NULL) { if(p.next.data<=q.next.data) { if(s.next!=NULL) p.next=s.next; s.next=p.next; p++; } else { if(s.next!=NULL) q.next=s.next; s.next=q.next; q++; } } while(p.next!=NULL) { p.next=s.next; s.next=p.next; } while(q.next!=NULL) { q.next=s.next; s.next=q.next; }
习 题 三
1 设有一个栈，元素进栈的次序为a, b, c。问经过栈操作后可以得到哪些输出序列？
Abc,acb,bac,bca,cba.
2 循环队列的优点是什么?如何判断它的空和满?
优点：可以克服顺序队列的“假上溢”现象，能够使存储队列的向量空间得到充分
利用。
判断循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：
一是另设一布尔变量来区别队列的空和满。二是约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。三是设置一计数器记录队列中元
素的总数，不仅可判别空或满，还可以得到队列中元素的个数 。
3 设有一个静态顺序队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？
队列为空：front=rear。队满：rear=MAX -1或front=rear (队首指针front ，一个队尾指针rear)
4 设有一个静态循环队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？
循环队列为空：front=rear 。 循环队列满：(rear+1)%MAX=front。 (队首指针front ，一个队尾指针rear)
5 利用栈的基本操作，写一个返回栈S中结点个数的算法int StackSize(SeqStack S) ，并说明S为何不作为指针参数的算法? intStackSize (SeqStack S) {//计算栈中结点个数 int n=0;
if(!EmptyStack(&S)) {
Pop(&S); n++; }
return n; }
上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数。
7 设Q[0,6]是一个静态顺序队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。 a, b, c, d入队 a, b, c出队
i , j , k , l , m入队 d, i出队
n, o, p, q, r入队
图解：
8 假设Q[0,5]是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。 d, e, b, g, h入队 d, e出队
i , j , k , l , m入队 b出队
n, o, p, q, r入队 图解：
习 题 四
⑵ 解释下列每对术语的区别：空串和空白串；主串和子串；目标串和模式串。
解：空串和空白串的区别：空串不含任何字符，它的长度为0，而空白串含有一个空格，它的长度为1.
主串和子串的区别：主串是相对于子串而言的，子串是主串中连续的一段，是主串的一个子集。
目标串和模式串的区别：目标串是在模式匹配中的主串，是相对于模式串运算的母串，而模式串是子串，是在主串中运算的子串。
⑵ 若x和y是两个采用顺序结构存储的串，写一算法比较这两个字符串是否相等。 解：
int streql(Hstring x, Hstring y) if(x[0]!=y[0]) return (0); else i=1;
while(x[i]==y[i]&&i if(i== x[0]) return (1) else return (0) 习 题 五 ⑴ 什么是广义表？请简述广义表与线性表的区别？ 广义表是零至多个元素的有限序列，广义表中的元素可以是原子，也可以是子表。从“元素的有限序列”角度看，广义表满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于扩充的线性结构（只不过元素并不具有同一类型：可以是原子，也可以是广义表）。当广义表中的元素都是原子时，广义表就蜕变为线性表。 广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表 ⑵ 一个广义表是(a, (a, b), d, e, (a, (i, j), k)) ，请画出该广义表的链式存储结构。 图解： 10a110a10b∧10d10e11∧10a10i10j∧10k∧ ⑶ 设有二维数组a[6][8]，每个元素占相邻的4个字节，存储器按字节编址，已知a的起始地址是1000，试计算： ① 数组a的最后一个元素a[5][7]起始地址； ② 按行序优先时，元素a[4][6]起始地址； ③ 按行序优先时，元素a[4][6]起始地址。 LOC(a[5][7])=LOC(a[0][0])+47*4=1188 LOC(a[4][6])=LOC(a[0][0])+(4?8+6)?4=1152 LOC(a[4][6])=LOC(a[0][0])+（6*6+4）?4=1160 ⑸ 设有稀疏矩阵B如下图所示，请画出该稀疏矩阵的三元组表和十字链表存储结构。 图解： 12331-3384432462521865467573-3 图中未标记空指针，作业中请注意标记 习 题 六 ⑴ 假设在树中， 结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为 { (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) } ，用树型表示法表示该树，并回答下列问题： ① 哪个是根结点? 哪些是叶子结点? 哪个是g的双亲? 哪些是g的祖先? 哪些是g的孩子? 那些是e的子孙? 哪些是e的兄弟? 哪些是f的兄弟? ② b和n的层次各是多少? 树的深度是多少? 以结点c为根的子树的深度是多少? ⑵ 一棵深度为h的满k叉树有如下性质： 第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。 如果按层次顺序(同层自左至右)从1开始对全部结点编号，问： ① 各层的结点数是多少? ② 编号为i的结点的双亲结点(若存在)的编号是多少? ③ 编号为i的结点的第j个孩子结点(若存在)的编号是多少? ④ 编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? ⑶ 设有如图6-27所示的二叉树。 ① 分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。 ② 写出该二叉树的先序、中序、后序遍历序列。 ⑷ 已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。 ⑸ 设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA ，请画出这棵二叉树，然后给出该树的先序序列。 ⑹ 已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca，请画出这棵二叉树对应的中序线索树和后序线索树。 ⑺ 以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法。 ⑻ 设图6-27所示的二叉树是森林F所对应的二叉树，请画出森林F。 ⑼ 设有一棵树，如图6-28所示。 ① 请分别用双亲表示法、孩子表示法、孩子兄弟表示法给出该树的存储结构。 ② 请给出该树的先序遍历序列和后序遍历序列。 ③ 请将这棵树转换成二叉树。 ⑽ 设给定权值集合w={3,5,7,8,11,12} ，请构造关于w的一棵huffman树，并求其加权路径长度WPL 。 ⑾ 假设用于通信的电文是由字符集{a, b, c, d, e, f, g, h}中的字符构成， 这8个字符在电文中出现的概率分别为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10} 。 ① 请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。 ② 求出每个字符的huffman编码 习 题 七 ⑴ 分析并回答下列问题： ① 图中顶点的度之和与边数之和的关系? ② 有向图中顶点的入度之和与出度之和的关系? ③ 具有n个顶点的无向图，至少应有多少条边才能确保是一个连通图? 若采用邻接矩阵表示，则该矩阵的大小是多少? ④ 具有n个顶点的有向图，至少应有多少条弧才能确保是强连通图的? 为什么? ⑵ 设一有向图G=(V,E)，其中V={a,b,c,d,e} ， E={ ① 请画出该有向图，并求各顶点的入度和出度。 ② 分别画出有向图的正邻接链表和逆邻接链表。 ⑶ 对图7-27所示的带权无向图。 ① 写出相应的邻接矩阵表示。 ② 写出相应的边表表示。 ③ 求出各顶点的度。 ⑷ 已知有向图的逆邻接链表如图7-28所示。 ① 画出该有向图。 ② 写出相应的邻接矩阵表示。 ③ 写出从顶点a开始的深度优先和广度优先遍历序列。 ④ 画出从顶点a开始的深度优先和广度优先生成树。 ⑸ 一个带权连通图的最小生成树是否唯一?在什么情况下可能不唯一? ⑹ 对于图7-27所示的带权无向图。 ① 按照Prime算法给出从顶点2开始构造最小生成树的过程。 ② 按照Kruskal算法给出最小生成树的过程。 ⑺ 已知带权有向图如图7-29所示，请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度，给出相应的求解步骤。 ⑻ 已知带权有向图如图7-30所示，请利用Floyd算法求出每对顶点之间的最短路径及路径长度。 ⑼ 一个AOV网用邻接矩阵表示，如图7-31。用拓扑排序求该AOV网的一个拓扑序列，给出相应的步骤。 ⑽ 拓扑排序的结果不是唯一的，请给出如图7-32所示的有向图的所有可能的拓扑序列。 ⑾ 请在深度优先搜索算法的基础上设计一个对有向无环图进行拓扑排序的算法。 ⑿ 设计一个算法利用图的遍历方法输出一个无向图G中从顶点Vi到Vj的长度为S的简单路径，设图采用邻接链表作为存储结构。 ⒀ 假设一个工程的进度计划用AOE网表示，如图7-33所示。 ① 求出每个事件的最早发生时间和最晚发生时间。 ② 该工程完工至少需要多少时间? ③ 求出所有关键路径和关键活动。 习 题 九 ⑴ 对于一个有n个元素的线性表，若采用顺序查找方法时的平均查找长度是什么？若结点是有序的，则采用折半查找法是的平均查找长度是什么? ⑵ 设查找表采用单链表存储，请分别写出对该表进行顺序查找的静态查找和动态查找的算法。 ⑶ 设二叉排序树中的关键字互不相同：则 ① 最小元素无左孩子，最大元素无右孩子，此命题是否正确？ ② 最大和最小元素一定是叶子结点吗？ ③ 一个新结点总是插入在叶子结点上吗？ ⑷ 试比较哈希表构造时几种冲突处理方法的优点和缺点。 ⑸ 将关键字序列(10, 2, 26, 4, 18, 24, 21, 15, 8, 23, 5, 12, 14)依次插入到初态为空的二叉排序树中，请画出所得到的树T； 然后画出删除10之后的二叉排序树T1 ； 若再将10插入到T1中得到的二叉排序树T2是否与T1相同? 请给出T2的先序、中序和后序序列。 ⑹ 设有关键字序列为：(Dec, Feb, Nov, Oct, June, Sept, Aug, Apr, May, July, Jan, Mar) ，请手工构造一棵二叉排序树。该树是平衡二叉排序树? 若不是，请为其构造一棵平衡二叉排序树。 ⑺ 设关键字序列是(19, 14, 23, 01, 68, 84, 27, 55, 11, 34, 79)，散列表长度是11，散列函数是H(key)=key MOD 11， ① 采用开放地址法的线性探测方法解决冲突，请构造该关键字序列的哈希表。 ② 采用开放地址法的二次探测方法解决冲突，请构造该关键字序列的哈希表。 ⑻ 试比较线性索引和树形索引的优点和缺点。 ⑼ 设关键字序列是(19, 24, 23, 17, 38, 04, 27, 51, 31, 34, 69)，散列表长度是11，散列函数是H(key)=key MOD 11， ① 采用开放地址法的线性探测方法解决冲突，请构造该关键字序列的哈希表。 ② 求出在等概率情况下，该方法的查找成功和不成功的平均查找长度ASL。 ⑽ 下图是一棵3阶B_树，请画出插入关键字B,L,P,Q后的树形。 习 题 十 ⑴ 回答下列各题： ① 从未排序序列中挑选元素，并将其依次放入到已排序序列中(初始时为空)的一端的方法是什么？ ② 在待排序的元素基本有序的前提下，效率最高的排序方法是什么? ③ 从未排序序列中依次取出元素与已排序序列 (初始时为空)中的元素进行比较，将其放入已排序序列的正确位置方法是什么？ ④ 设有1000个元素， 希望采用最快的速度挑选出其中前10个最大的元素， 最好的方法是什么? ⑵ 若对关键字序列为(54, 37, 93, 25, 17, 68, 58, 41, 76)的一组记录进行快速排序时，递归调用使用的栈所能到达的最大深度是多少?共需递归调用多少次?其中第二次递归调用是对哪组记录进行排序? ⑶ 在堆排序，快速排序和归并排序中，若只从存储空间考虑，应选择哪种方法；若只从排序结果的稳定性考虑，应选择哪种方法；若只从平均情况下排序最快考虑，应选择哪种方法； ⑷ 设有关键字序列为(14, 17, 53, 35, 9, 32, 68, 41, 76, 23)的一组记录，请给出用希尔排序法(增量序列是5, 3, 1)排序时的每一躺结果。 ⑸ 设有关键字序列为(14, 17, 53, 35, 9, 37, 68, 21, 46)的一组记录，请给出冒泡排序法排序时的每一躺结果。 ⑹ 设有关键字序列为(14, 17, 53, 35, 9, 37, 68, 21, 46)的一组记录，利用快速排序法进行排序时，请给出以第一个记录为基准得到的一次划分结果。 ⑺ 设关键字序列为(14, 17, 53, 35, 9, 37, 68, 21)的一组记录，请给出按非递增采用堆排序时的每一躺结果。 ⑻ 设关键字序列为(314, 617, 253, 335, 19, 237, 464, 121, 46, 231, 176, 344)的一组记录，请给出采用基数排序时的每一躺结果。 ⑼ 将哨兵放在R[n]中，被排序的记录存放在R[1…n-1]中，重写直接插入排序算法。 ⑽ 实际中常采用单链表存储数据记录，请写出排序记录的结构的定义并修改。