1、习题一1 填空题(1) (数据元素、或元素、或结点、或顶点、或记录）是数据的基本单位，在计算机程序中作为一个整体进行考虑和处理。(2)（数据项、或字段）是数据的最小单位， （数据元素 ）是讨论数据结构时涉及的最小数据单位。(3)从逻辑关系上讲，数据结构主要分为( 集合)、( 线性结构) 、(树结构)和(图)。 (4)数据的存储结构主要有（顺序存储结构）和（链式存储结构 ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（数据元素）和（它们之间的关系 ） 。 (5) 算法具有 5 个特性，分别是（ 输入） 、 （输出） 、 （有穷性） 、 （确定性） 、 （可行性） 。 (6) 算法的描述
2、方法通常有(自然语言) 、(流程图) 、(程序设计语言)、( 伪代码)4 种，其中，(伪代码)被称为算法语言。(7) 一般情况下，一个算法的时间复杂度是算法（输入规模）的函数。(8) 设待处理问题的规模为 n,若一个算法的时间复杂度为一个常数，则表示成数量级的形式为 (O(1)，若为 n*log25n, 则表示成数量级的形式为 (O(n*log2n)。2. 选择题: (1) C, D (2) B (3) B (4) A (5) D (6) A (7) C (8) C, E 习题二1. 填空题(1) 在顺序表中，等概率情况下，插入和删除一个元素平均需移动(表长的一半)个元素，具体移动元素的个数与
3、(表的长度)和(数据元素所在的位置) 有关。(2) 一个顺序表的第一个元素的存储地址是 100，每个数据元素的长度是 2，则第 5 个数据元素的存储地址是（108） 。 (3) 设单链表中指针 p 指向单链表的一个非空结点 A，若要删除结点 A 的直接后继，则需要修改指针的操作为（p-next=(p-next)-next, 或者 q=p-next; p-next=q-next） 。 (4) 单链表中设置头结点的作用是( 方便运算, 减少程序的复杂性，使得空表和非空表处理统一)。(5) 非空的循环单链表由头指针 head 指示，则其尾结点( 由指针 p 所指)满足(p-next=head)。(6
4、) 在有尾指针 rear 指示的循环单链表中，在表尾插入一个结点 s 的操作序列是（s-next=rear-next; rear-next=s; rear=s） ，删除开始结点的操作序列是（q=rear-next-next; rear-next-next=q-next; delete q;） 。注：假设此循环单链表有表头结点(7) 一个具有 n 个结点的单链表，在 p 所指结点后插入一个新结点 s 的时间复杂性为（ O(1)） ；在给定值 x 的结点后插入一个新结点的时间复杂性为( O(n) ） 。(8) 可由一个尾指针惟一确定的链表有( 循环链表)、(双链表) 、(双循环链表)。2. 选择题
5、: (1) A,B (2) D (3) B (4) A (5) A (6) D (7) B (8) B (9) C (10) B (11) B (12) D (13) A (14) A5. 算法设计(1) 设计一个时间复杂度为 O(n)的算法。实现将数组 An中所有元素循环左移 k 个位置。算法思想：要使 a1akak+1an - ak+1ana1ak,可以先让 a1akak+1an-aka1anak+1,再让 ak a1 anak+1 - ak+1ana1ak ，参见第 1 章 16 页的思想火花算法：void converse(T a, int i, int j)for(s=i; s; s
6、-data=x; s-next=first; first=s; else p=first ; j=0; while (p j+; if (!p) throw “插入位置值太大“;else s=new Node; s-data=x; s-next=p-next; p-next=s; (4) 试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。算法思想：顺序表的程序参见题（1）的 converse.单链表的程序如下，设单链表有表头结点.void LinkList:converse() p=first-next; first-next=NULL;while(p)q=p-next; p-
7、next=first-next;first-next=p;p=q;(5) 假设在长度大于 1 的循环链表中，既无头结点也无头指针， s 为指向链表中某个结点的指针，试编写算法删除结点 s 的前驱结点。 void LinkList:deleteS(Node *s)p=s;while(p-next-next!=s) p=p-next; q=p-next; p-next=q-next;delete q; (6) 已知一单链表中的数据元素含有三类字符：字母、数字和其它字符。试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。算法思想：1）构造 3 个带表头结点的循环链表，分别为 zifu，s
8、huzi 和 qita； 2）遍历单链表，按单链表中的当前数据元素的分类插入相应的链表void fl(Node* zifu, Node *shuzi, Node *qita) s=new Node; s-next=s; zifu=s; s=new Node; s-next=s; shuzi=s;s=new Node; s-next=s; qita=s;a=zifu; b=shuzi; c=qita;p=first-next; /设单链表带头结点 while(p) q=p; p=p-next; if(q-data=a a-next=q; a=q;else if(q-data=0 b-next=q
9、; b=q;else q-next=c-next; c-next=q; c=q;delete first;(7) 设单链表以非递减有序排列，设计算法实现在单链表中删除相同的多余结点。解： void LinkList:deleteALL() p=first-next; /假设单链表带表头结点。while(p) if(p-next!=NULL p-next=q-next; delete q;else p=p-next;(8) 判断带头结点的双循环链表是否对称。解 bool LinkList:equal(DulNode *first) p=first-next; q=first-prior;whil
10、e(p!=q q=q-prior;else return 0;return 1;-习题三1 填空题(1) 设有一个空栈，栈顶指针为 1000H，经过 push、push、pop、push、pop 、push 、push 后，栈顶指针为(1003H)。(2) 栈结构通常采用的两种存储结构是( 顺序存储结构和链接存储结构顺序栈和链栈)，其判定栈空的条件分别是(top=-1, top=NULL), 判断栈满的条件分别是(top=MaxSize-1, 内存满/ 内存无可用空间)。(3) (栈 )可作为实现递归函数调用的一种数据结构。(4) 表达式 a*(b+c)-d 的后缀表达式是(abc+*d-)
11、。(5) 栈和队列是两种特殊的线性表，栈的操作特性是( 后进先出)，队列的操作特性是(先进先出)，栈和队列的主要区别在于(插入、删除运算的限定不一样 )。(6) 循环队列的引入是为了克服( 假溢出 )。(7) 一维数组 Datan用来表示循环队，队头指针 front 和队尾指针 rear 定义为整型变量，计算队中元素个数的公式是( (rear-front+n)%n )。 (8) 用循环链表表示的队列长度为 n，若只设头指针，则出队和入队的时间复杂度分别是( O(1) )和 ( O(n) )。2. 选择题: (1) C (2) D (3) C (4) B (5) B (6) B (7) D (8
12、) A (9) C 4.解答下列问题(1) 不可以, 因为有序列 C, A, B. 可以, push, push, push, pop, pop, pop, push, pop, push, pop.(2) 见书本 (3) 栈顶元素是 6, 栈底元素是 1.(4) 队尾元素是 9, 队头元素是 5. (5) 合法, 不合法.习题四1. 填空题(1) 串是一种特殊的线性表，其特殊性体现在( 数据元素的类型为字符型 )。(2) 两个串相等的充分必要条件是( 它们的长度相等且对应位置的字符相同 )。 (3) 数组通常只有两种运算，分别是( 存取 )和( 修改 )，这决定了数组通常采用（ 顺序存储）结
13、构来实现存储。(4) (1140)(5)设有一个 10 阶的对称矩阵 A 采用压缩存储，第一个元素 A00的存储地址为 d， 每个元素占用1 个地址空间，则元素 A85的存储地址为( d+41 )。 (6) 稀疏矩阵一般压缩存储方法有两种，分别是( 三元组顺序表 )和( 十字链表 )。 2. 选择题: (1) B (2) D, E, K (3) B (4) XXX (5) D (6) C (7) D5(2). 设计一个求矩阵 A=(aij)nXm 所有鞍点的算法，并分析最坏情况下的时间复杂度。算法思想 2：附加两个数组 Bn和 Cm，Bi 用来存第 i 行的最小值，Cj用来存第 j 列的最小元
14、素值。如果 Aij= Bi=Cj，则 Aij一定为马鞍点。viod maandian2(A ,int m,int n)int Bn,Cm,i,j;for(i=0;iAij) Bi=Aij;for(j=0;j=0）个( 互不相交) 的有限集合，每个集合又是一棵树。(2) 树中某结点的子树的个数称为该结点的（ 度 ） ，子树的根结点称为这个结点的( 孩子结点 ),该结点称为其子树根结点的（双亲结点）. (3) 一棵二叉树的第 i（i 1）层上最多有( 2i-1 )个结点,一棵有 n(n0)个结点的满二叉树共有( (n+1)/2 )个叶子结点和( (n-1)/2 )个非终端结点。 (4) 设高度为
15、h 的二叉树只有度为 0 的和度为 2 的结点，该二叉树的结点数可能达到的最大值是( 2h-1 ),最小值是（ 2 h -1 ） 。 (5)深度为 k 的二叉树中，所含叶子的个数最多为(2 k-1).(6)具有 100 个结点的完全二叉树的叶子结点数为(50)。 (7) 已知一棵度为 3 的树有 2 个度为 1 的结点，3 个度为 2 的结点，4 个度为 3 的结点。则该树有(12) 个叶子结点。 (8) 某二叉树的前序遍历序列是 ABCDEFG,中序遍历序列是 CBDAFGE,则其后序遍历序列是( CDBGFEA )。(9)在具有 n 个结点的二叉链表中，共有（ 2n )个指针域，其中( n
16、-1 )个指针域用于指向其左右孩子，剩下的( n+1 )个指针域则是空的。 (10)在有 n 个叶子的哈夫曼树中，叶子结点总数为 ( n ),分支结点总数为（ n-1 ） 。 2. 选择题: (1) D (2) D (3) B (4) C (5) B,C (6) D (7) A (8) A,B (9) D,A (10) B (11) B (12) C (13) D (14) C4. 解答下列问题(3) 已知一棵度为 m 的树中：n 1 个度为 1 的结点，n 2 个度为 2 的结点，n m 个度为 m 的结点，问该树中共有多少个叶子结点？解：设该树中共有 n0 个叶子结点。则该树中总结点个数为
17、 n= n0+ n1 + nm.而分支数为 n-1= n1 +2n2 +3n3 + mnm,所以 n0 =1+n2 +2n3 + (m-1)nm (4) 已知一棵二叉树的中序和后序序列为 CBEDAFIGH 和 CEDBIFHGA,试构造该二叉树。(5) 给出叶子结点的权值集合为 W=5,2,9,11, 8,3,7的哈夫曼树的构造过程。 5 算法设计(1) 设计算法求二叉树的结点个数. 注：本算法可以用二叉树遍历的所有算法，只要把 cout 语句换成结点的计数就可以了，但是要注意递归中的计数变量应该是外部变量。如 int num=0;int BiTree:count(BiNode *rt) c
18、ountsub(rt); return num;void BiTree:countSub(BiNode *rt) if (rt !=NULL) num+; countSub (rt-lchild); countSub (rt-rchild); 其他解法二：用前序遍历的非递归算法 int BiTree:CountPreOrder(BiNode *rt) top= -1; p=rt; num=0;/采用顺序栈 s，并假定不会发生上溢while (p!=NULL | | top!= -1) while (p!= NULL) /找此结点的最左边的后代 num+; /访问s+top=p; /此结点进栈
19、p=p-lchild; /转移到左儿子子树 if (top!= -1) p=stop-; p=p-rchild; return num; / coutdata”改成判断此结点是否为叶子结点。 void BiTree:leaf(BiNode *rt) if (rt=NULL) return; else if(rt-lchild=NULL PostOrder(rt-lchild); PostOrder(rt-rchild); (3) 设计算法求二叉树的深度. 注：本算法也可以用二叉树遍历的所有算法。但是在用前序和中序算法时要注意深度如何来确定。 int BiTree:depth(BiNode *r
20、t) if (rt =NULL) return 0; else hl= depth(rt-lchild); hr= depth(rt-rchild);return (hlhr)?hl+1:hr+1; (4) 设计算法: 输出二叉树后序遍历的逆序. 解法思想: 太简单啦！ 前序遍历是先遍历右子树即可.void BiTree:PostOrder_1(BiNode *rt) if (rt=NULL) return; else coutdata; PostOrder(rt-rchild); PostOrder(rt-lchild); (5) 以二叉链表为存储结构，编写算法求二叉树中值 x 的结点的双亲
21、. void BiTree:PreOrder_Parent(BiNode *rt) top= -1; p=rt;/采用顺序栈 s，并假定不会发生上溢while (p!=NULL | | top!= -1) while (p!= NULL) if(rt-lchild!=NULL if(rt-rchild!=NULL s+top=p; /此结点进栈 p=p-lchild; /转移到左儿子子树 if (top!= -1) p=stop-; p=p-rchild; (6) 以二叉链表为存储结构，在二叉树中删除以值 x 为根结点的子树. void BiTree:DeleteX(BiNode *rt, T
22、 x) if(rt=NULL) return; if(rt-data=x) Release(rt);elseDeleteX(rt-lchild, x);DeleteX(rt-rchild, x); (7) 一棵具有 n 个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历. 算法思想: 套用前序遍历的原程序，注意查找左右孩子结点的地址和判别孩子是否存在的方法。注：根结点的下标是 1。 void BiTree:PreOrder_Seq(int rt) top= -1; p=rt; /采用顺序栈 s，并假定不会发生上溢while (pdata”改成左右孩子指针交换即可。 void BiT
23、ree:PostOrderChange(BiNode *rt) if (rt=NULL) return; else PostOrder(rt-lchild); PostOrder(rt-rchild); temp=rt-lchild;rt-lchild=rt-rchild;rt-rchild=temp; 习题 6 1.填空题设无向图 G 中顶点数为，则图 G 至少有（0 ）条边，至多有（ n(n-1)/2）条边；若 G 为有向图，则至少有（ 0）条边，至多有（ n(n-1) ）条边。 任何连通图的连通分量只有一个，即是（它本身） 。 图的存储结构主要有两种，分别是（邻接矩阵）和（邻接表） 。
24、已知无向图的顶点数为，边数为，其邻接表表示的空间复杂度为（O(n+e)） 。 已知一个图的邻接矩阵表示，计算第个顶点的入度的方法是（矩阵中第 j-1 列的非 0 元素个数） 。 有向图用邻接矩阵 存储，其第行的所有元素之和等于顶点的（出度） 。 图的深度优先遍历类似于树的（前序）遍历，它所用的数据结构是（栈） ；图的广度优先遍历类似于树的（层序）遍历，它所用的数据结构是（队列） 。 对于含有个顶点条边的连通图，利用rim 算法求最小生成树的时间复杂度为（O(n 2)） ，利用 Kruscal 算法求最小生成树的时间复杂度为（ O(elog2e)） 。 如果一个有向图不存在（有向回路） ，则该图
25、的全部顶点可以排成一个拓扑序列。 在一个有向图中，若存在弧、 ，则在其拓扑序列中，顶点 vi ,vj , vk 的相对次序为（v i ,vj , vk ） 。 2. 选择题: (1) C (2) A,G (3) C (4) B (5) D (6) C,F (7) B (8) D (9) A (10) A (11) A (12) C (13) A (14) C,C,F (15) B4. 解答下列问题 (1) n 个顶点的无向图,采用邻接表存储, 回答下列问题: 图中有多少条边?答: 邻接表中所有边表结点的个数的一半. 任意两个顶点 i 和 j 是否有边相连?答: 查找第 i 个边表的结点中是否有
26、邻接点域值为 j 的结点. 如果有,则它们之间有边;否则,无边. 任意一个顶点的度是多少?答: 此顶点对应的边表中结点的个数. (2) n 个顶点的无向图,采用邻接矩阵存储, 回答下列问题: 图中有多少条边?答: 邻接矩阵中所有元素和的一半. 任意两个顶点 i 和 j 是否有边相连?答: 如果第 i 行第 j 列的元素值为 1,则它们之间有边;否则, 无边. 任意一个顶点的度是多少?答: 此顶点对应的行中元素之和. (3) 证明：生成树中最长路径的起点和终点的度均为 1.证明：设一棵树的最长路径 P=v1v2vk。若 v1 的度至少为 2，不妨设 u(v2)是它的另外一个邻点。若uv 1, v
27、2, , vk, 则此树中包含圈，矛盾；否则 uv1v2vk 是一条更长的路，同样矛盾。所以 v1 的度为 1. 类似可以证明 vk 的度为 1. (5) 图 6-50 所示是一个无向带权图，请分别用 rim 算法和ruscal 算法求最小生成树。 习题 71. 填空题 (1) 顺序查找技术适合于存储结构为（各种形式）的线性表，而折半查找技术适合于存储结构为（顺序存储）的线性表，并且表中的元素必须是（有序的） 。(2) 设有一个已按各元素值排好序的线性表，长度为 125，用折半查找法查找与给定值相等的元素，若查找成功，则至少需要比较(1 )次，至多需要比较(7)次。(3) 对于数列25, 30
28、, 8, 5, 1, 27, 24, 10, 20, 21, 9, 28, 7, 13, 15,假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（8 ） 。若按二叉排序树组织该数列，则查找一个数的平均比较次数为（59/15） 。(4) 长度为 20 的有序表采用折半查找，共有（ 4）个元素的查找长度为 3。(5) 假设数列25, 43, 62, 31, 48, 56,采用散列函数为 H(k)=k mod 7, 则元素 48 的同义词是（62） 。(6) 在散列技术中，处理冲突的主要方法是（开放地址法）和（拉链法） 。(7) 在各种查找方法中，平均查找长度与结
29、点个数无关的查找方法是（散列查找） 。(8) 与其他方法比较，散列查找法的特点是（记录的存储位置与关键码之间建立了一个确定的对应关系，平均查找长度与结点个数无关） 。2. 选择题: (1) B (2) D,D (3) A,B (4) D (5) A (6) C (7) C (8) B (9) D (10) A (11) C (12) C4解答下列问题 (1) 分别画出在线性表(a,b,c,d,e,f,g)中进行折半查找关键码 e 和 g 的过程。解：d-f-e 和 d-f-g(2) 画出长度为 10 的折半查找判定树，并求出等概率时查找成功和不成功的平均查找长度。等概率时查找成功平均查找长度=
30、(1*1+2*2+4*3+3*4)/10=29/10等概率时不成功的平均查找长度=(5*4+6*5)/11=50/11(3) 将数列(24,15,38,27,76,130,121)的各个元素依次插入一颗初始为空的二叉排序树中， 请画出最后的结果并求等概率情况下查找成功的平均查找长度。AVL=(1+2*2+3*3+4+5)/7(4) 已知一棵二叉排序树的结构如图 7-30 所示，结点的值为 18，请标出各点的值。答：见题上图习题 81.填空题(1) 排序的主要目的是为了以后对已排序的数据元素进行( 查找 )。(2) 对 n 个元素进行起泡排序，在( 关键码有序) 的情况下比较的次数最少，其比较次数为 (O(n)。在(关键码逆序)情况下比较次数最多，其比较次数为( O(n2)。(3) 对一组记录(54,38,96,23,15,72,60,45,83) 进行直接插入排序，当把第 7 个记录 60 插入到有序表时, 为寻找插入位置需比较( 3 )次。(4) 对一组记录(54,38,96,23,15,72,60,45,83) 进行快速排序，在递归调用中使用的栈所能达到的最大
