做球迷网站,wordpress 添加附件,wordpress软件站模板,做58同城那样的网站数据结构#xff08;C语言版#xff09;#xff08;第2版#xff09;课后习题答案 李冬梅 2015.3 目 录 第 1 章 绪论 1 第 2 章 线性表 5 第 3 章 栈和队列 13 第 4 章 串、数组和广义表 26 第 5 章 树和二叉树 33 第 6 章 图 43 第 7 章 查找 54 第 8 章 排序 65… 数据结构C语言版第2版课后习题答案 李冬梅 2015.3 目 录 第 1 章 绪论 1 第 2 章 线性表 5 第 3 章 栈和队列 13 第 4 章 串、数组和广义表 26 第 5 章 树和二叉树 33 第 6 章 图 43 第 7 章 查找 54 第 8 章 排序 65 第 1 章 绪论 1. 简述下列概念数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案 数据是客观事物的符号表示指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数文本编辑所用到的字符串多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素是数据的基本单位在计算机中通常作为一个整体进行考虑和处理。在有些情况下数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象如一个学生记录树中棋盘的一个格局状态、图中的一个顶点等。 数据项是组成数据元素的、有独立含义的、不可分割的最小单位。例如学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象是性质相同的数据元素的集合是数据的一个子集。例如整数数据对象是集合 N{0±1±2…}字母字符数据对象是集合 C{‘A’ ‘B’…‘Z’ ‘a’ ‘b’…‘z’}学生基本信息表也可是一个数据对象。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。换句话说数据结构是带“结构”的数据元素的集合“结构”就是指数据元素之间存在的关系。 逻辑结构从逻辑关系上描述数据它与数据的存储无关是独立于计算机的。因此数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构数据对象在计算机中的存储表示也称为物理结构。 抽象数据类型由用户定义的表示应用问题的数学模型以及定义在这个模型上的一组操作的总称。具体包括三部分数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 试举一个数据结构的例子叙述其逻辑结构和存储结构两方面的含义和相互关系。答案 例如有一张学生基本信息表包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素学生记录按顺序号排列形成了学生基本信息记录的线性序列。对于整个表来说只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录则称为顺序存储结构如果存储单元不连续而是随机存放各个记录然后用指针进行链接则称为链式存储结构。 即相同的逻辑结构可以对应不同的存储结构。 3简述逻辑结构的四种基本关系并画出它们的关系图。 答案 1 集合结构 数据元素之间除了“属于同一集合”的关系外别无其他关系。例如确定一名学生是否为班级成员只需将班级看做一个集合结构。 2 线性结构 数据元素之间存在一对一的关系。例如将学生信息数据按照其入学报到的时间先后顺序进行排列将组成一个线性结构。 3 树结构 数据元素之间存在一对多的关系。例如在班级的管理体系中班长管理多个组长每位组长管理多名组员从而构成树形结构。 4 图结构或网状结构 数据元素之间存在多对多的关系。例如多位同学之间的朋友关系任何两位同学都可以是朋友从而构成图形结构或网状结构。 其中树结构和图结构都属于非线性结构。 四类基本逻辑结构关系图 4. 存储结构由哪两种基本的存储方法实现答案 1 顺序存储结构 顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系通常借助程序设计语言的数组类型来描述。 2 链式存储结构 顺序存储结构要求所有的元素依次存放在一片连续的存储空间中而链式存储结构无需占用一整块存储空间。但为了表示结点之间的关系需要给每个结点附加指针字段用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。 选择题 在数据结构中从逻辑上可以把数据结构分成 。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构答案C 2 与数据元素本身的形式、内容、相对位置、个数无关的是数据的 。 A存储结构 B存储实现 C逻辑结构 D运算实现答案C 3 通常要求同一逻辑结构中的所有数据元素具有相同的特性这意味着 。 A数据具有同一特点 B不仅数据元素所包含的数据项的个数要相同而且对应数据项的类型要一致 C每个数据元素都一样 D数据元素所包含的数据项的个数要相等答案B 4 以下说法正确的是 。 A数据元素是数据的最小单位B数据项是数据的基本单位 C数据结构是带有结构的各数据项的集合 D一些表面上很不相同的数据可以有相同的逻辑结构答案D 解释数据元素是数据的基本单位数据项是数据的最小单位数据结构是带有结构的各数据元素的集合。 5 算法的时间复杂度取决于 。 A问题的规模 B待处理数据的初态 C计算机的配置 DA 和 B答案D 解释算法的时间复杂度不仅与问题的规模有关还与问题的其他因素有关。如某些排序的算法其执行时间与待排序记录的初始状态有关。为此有时会对算法有最好、最坏以及平均时间复杂度的评价。 以下数据结构中 是非线性数据结构 A树 B字符串 C队列 D栈答案A 试分析下面各程序段的时间复杂度。 1x90; y100; while(y0) if(x100) {xx-10;y--;} else x;答案O(1) 解释程序的执行次数为常数阶。 2 for (i0; in; i) for (j0; jm; j) a[i][j]0; 答案O(m*n) 解释语句 a[i][j]0;的执行次数为 m*n。 3 s0; for i0; in; i) for(j0; jn; j) sB[i][j]; sums;答案O(n2) 解释语句 sB[i][j];的执行次数为 n2 。 4 i1; while(in) ii*3; 答案O(log3n) 解释语句 ii*3;的执行次数为 ëlog3nû。 5 x0; for(i1; in; i) for (j1; jn-i; j) x; 答案O(n2) 解释语句 x;的执行次数为 n-1n-2……1 n(n-1)/2。 6xn; //n1 y0; while(x≥(y1)* (y1)) y; 答案O( ) 解释语句 y;的执行次数为 ë û。 第 2 章 线性表 1. 选择题 顺序表中第一个元素的存储地址是 100每个元素的长度为 2则第 5 个元素的地址是 。 A110 B108 C100 D120 答案B 解释顺序表中的数据连续存储所以第 5 个元素的地址为1002*4108。 2 在 n 个结点的顺序表中算法的时间复杂度是 O(1)的操作是 。 A. 访问第 i 个结点1≤i≤n和求第 i 个结点的直接前驱2≤i≤n B. 在第 i 个结点后插入一个新结点1≤i≤n C. 删除第 i 个结点1≤i≤n D. 将 n 个结点从小到大排序 答案A 解释在顺序表中插入一个结点的时间复杂度都是 O(n2)排序的时间复杂度为 O(n2)或 O(nlog2n)。顺序表是一种随机存取结构访问第 i 个结点和求第 i 个结点的直接前驱都可以直接通过数组的下标直接定位时间复杂度是 O(1)。 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变平均要移动 的元素个数为 。 A8 B63.5 C63 D7 答案B 解释平均要移动的元素个数为n/2。 4 链接存储的存储结构所占存储空间 。 A. 分两部分一部分存放结点值另一部分存放表示结点间关系的指针 B. 只有一部分存放结点值 C. 只有一部分存储表示结点间关系的指针 D. 分两部分一部分存放结点值另一部分存放结点所占单元数 答案A 5 线性表若采用链式存储结构时要求内存中可用存储单元的地址 。 A. 必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续或不连续都可以 答案D 6 线性表在 情况下适用于使用链式结构实现。 A. 需经常修改中的结点值 需不断对进行删除插入 C中含有大量的结点 中结点结构复杂 答案B 解释链表最大的优点在于插入和删除时不需要移动数据直接修改指针即可。 7 单链表的存储密度 。 A. 大于 1 B等于 1 C 小于 1 D不能确定 答案C 解释存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比假设单链表一个结点本身所占的空间为 D指针域所占的空间为 N则存储密度为D/(DN)一定小于 1。 将两个各有 n 个元素的有序表归并成一个有序表其最少的比较次数是 。 An B2n-1 C2n Dn-1 答案A 解释当第一个有序表中所有的元素都小于或大于第二个表中的元素只需要用第二个表中的第一个元素依次与第一个表的元素比较总计比较 n 次。 9 在一个长度为 n 的顺序表中在第 i 个元素1≤i≤n1之前插入一个新元素时须向后移动 个元素。 An-i Bn-i1 C n-i-1 DI 答案B (10) 线性表 L(a1a2,……an)下列说法正确的是 。 A每个元素都有一个直接前驱和一个直接后继 B线性表中至少有一个元素 C表中诸元素的排列必须是由小到大或由大到小 D 除第一个和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接 后继。 答案D (11) 创建一个包括 n 个结点的有序单链表的时间复杂度是 。 AO(1) BO(n) CO(n2) DO(nlog2n) 答案C 解释单链表创建的时间复杂度是 O(n)而要建立一个有序的单链表则每生成一个新结点时需要和已有的结点进行比较 确定合适的插入位置 所以时间复杂度是 O(n2)。 以下说法错误的是 。 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 B. 顺序存储的线性表可以随机存取 C由于顺序存储要求连续的存储区域所以在存储管理上不够灵活 D线性表的链式存储结构优于顺序存储结构 答案D 解释链式存储结构和顺序存储结构各有优缺点有不同的适用场合。 (13) 在单链表中要将 s 所指结点插入到 p 所指结点之后其语句应为 。 As-nextp1; p-nexts; B(*p).nexts; (*s).next(*p).next; Cs-nextp-next; p-nexts-next; Ds-nextp-next; p-nexts; 答案D (14) 在双向链表存储结构中删除 p 所指的结点时须修改指针 。 Ap-next-priorp-prior; p-prior-nextp-next; Bp-nextp-next-next; p-next-priorp; Cp-prior-nextp; p-priorp-prior-prior; Dp-priorp-next-next; p-nextp-prior-prior; 答案A (15) 在双向循环链表中在 p 指针所指的结点后插入 q 所指向的新结点其修改指针的操作是 。 Ap-nextq; q-priorp; p-next-priorq; q-nextq; Bp-nextq; p-next-priorq; q-priorp; q-nextp-next; Cq-priorp; q-nextp-next; p-next-priorq; p-nextq; Dq-priorp; q-nextp-next; p-nextq; p-next-priorq;答案C 算法设计题 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。 [题目分析] 合并后的新表使用头指针 Lc 指向pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点从第一个结点开始进行比较当两个链表 La 和 Lb 均为到达表尾结点时依次摘取其中较小者重新链接在 Lc 表的最后。如果两个表中的元素相等只摘取 La表中的元素删除 Lb 表中的元素这样确保合并后表中无重复的元素。当一个表到达表尾结点为空时将非空表的剩余元素直接链接在 Lc 表的最后。 [算法描述] void MergeList(LinkList La,LinkList Lb,LinkList Lc) {//合并链表 La 和 Lb合并后的新表使用头指针 Lc 指向 paLa-next; pbLb-next; //pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点 LcpcLa; //用 La 的头结点作为 Lc 的头结点 while(pa pb) {if(pa-datapb-data){pc-nextpa;pcpa;papa-next;} //取较小者 La 中的元素将 pa 链接在 pc 的后面pa 指针后移 else if(pa-datapb-data) {pc-nextpb; pcpb; pbpb-next;} //取较小者 Lb 中的元素将 pb 链接在 pc 的后面pb 指针后移 else //相等时取 La 中的元素删除 Lb 中的元素 {pc-nextpa;pcpa;papa-next; qpb-next;delete pb ;pb q; } } pc-nextpa?pa:pb; //插入剩余段 delete Lb; //释放 Lb 的头结点 } 将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。 [题目分析] 合并后的新表使用头指针 Lc 指向pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点从第一个结点开始进行比较当两个链表 La 和 Lb 均为到达表尾结点时依次摘取其中较小者重新链接在 Lc 表的表头结点之后如果两个表中的元素相等只摘取 La 表中的元素保留 Lb 表中的元素。当一个表到达表尾结点为空时将非空表的剩余元素依次摘取链接在 Lc 表的表头结点之后。 [算法描述] void MergeList(LinkList La, LinkList Lb, LinkList Lc, ) {//合并链表 La 和 Lb合并后的新表使用头指针 Lc 指向 paLa-next; pbLb-next; //pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点 LcpcLa; //用 La 的头结点作为 Lc 的头结点 Lc-nextNULL; while(pa||pb ) {//只要存在一个非空表用 q 指向待摘取的元素 if(!pa) {qpb; pbpb-next;} //La 表为空用 q 指向 pbpb 指针后移 else if(!pb) {qpa; papa-next;} //Lb 表为空用 q 指向 papa 指针后移 else if(pa-datapb-data) {qpa; papa-next;} //取较小者包括相等La 中的元素用 q 指向 papa 指针后移 else {qpb; pbpb-next;} //取较小者 Lb 中的元素用 q 指向 pbpb 指针后移 q-next Lc-next; Lc-next q; //将 q 指向的结点插在 Lc 表的表头结点之后 } delete Lb; //释放 Lb 的头结点 } 已知两个链表 A 和 B 分别表示两个集合其元素递增排列。请设计算法求出 A 与 B的交集并存放于 A 链表中。 [题目分析] 只有同时出现在两集合中的元素才出现在结果表中,合并后的新表使用头指针 Lc 指向。 pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点从第一个结点开始进行比较当两个链表 La 和 Lb 均为到达表尾结点时如果两个表中相等的元素时摘取 La 表中的元素删除 Lb 表中的元素如果其中一个表中的元素较小时删除此表中较小的元素此表的工作指针后移。当链表 La 和 Lb 有一个到达表尾结点为空时依次删除另一个非空表中的所有元素。 [算法描述] void Mix(LinkList La, LinkList Lb, LinkList Lc) { paLa-next;pbLb-next; pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点 LcpcLa; //用 La 的头结点作为Lc 的头结点 while(papb) { if(pa-datapb-data)∥交集并入结果表中。 { pc-nextpa;pcpa;papa-next; upb;pbpb-next; delete u;} else if(pa-datapb-data) {upa;papa-next; delete u;} else {upb; pbpb-next; delete u;} } while(pa) {upa; papa-next; delete u;}∥ 释放结点空间 while(pb) {upb; pbpb-next; delete u;}∥释放结点空间 pc-nextnull;∥置链表尾标记。 delete Lb; //释放 Lb 的头结点 } 已知两个链表 A 和 B 分别表示两个集合其元素递增排列。请设计算法求出两个集合 A 和 B 的差集即仅由在 A 中出现而不在 B 中出现的元素所构成的集合并以同样的形式存储同时返回该集合的元素个数。 [题目分析] 求两个集合 A 和 B 的差集是指在 A 中删除 A 和 B 中共有的元素即删除链表中的相应结点,所以要保存待删除结点的前驱使用指针 pre 指向前驱结点。pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点从第一个结点开始进行比较当两个链表 La 和 Lb 均为到达表尾结点时如果 La 表中的元素小于 Lb 表中的元素pre 置为 La 表的工作指针 pa 删除Lb 表中的元素如果其中一个表中的元素较小时删除此表中较小的元素此表的工作指针后移。当链表 La 和 Lb 有一个为空时依次删除另一个非空表中的所有元素。 [算法描述] void DifferenceLinkList La, LinkList Lb,int *n {∥差集的结果存储于单链表 La 中*n 是结果集合中元素个数调用时为 0 paLa-next; pbLb-next; ∥pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点 preLa; ∥pre 为 La 中 pa 所指结点的前驱结点的指针 whilepapb {ifpa-dataq-data{prepa;papa-next;*n;} ∥ A 链表中当前结点指针后移 else ifpa-dataq-dataqq-next; ∥B 链表中当前结点指针后移 else {pre-nextpa-next; ∥处理 AB 中元素值相同的结点应删除 upa; papa-next; delete u;} ∥删除结点 } } 5 设计算法将一个带头结点的单链表 A 分解为两个具有相同结构的链表 B、C其中 B 表的结点为 A 表中值小于零的结点而 C 表的结点为 A 表中值大于零的结点链表 A 中的元素为非零整数要求 B、C 表利用A 表的结点。 [题目分析] B 表的头结点使用原来 A 表的头结点为 C 表新申请一个头结点。从 A 表的第一个结点开始依次取其每个结点 p判断结点 p 的值是否小于 0利用前插法将小于 0 的结点插入 B 表,大于等于 0 的结点插入 C 表。 [算法描述] void DisCompose(LinkedList A) { BA; B-next NULL; ∥B 表初始化 Cnew LNode;∥为 C 申请结点空间 C-nextNULL; ∥C 初始化为空表 pA-next; ∥p 为工作指针 while(p! NULL) { rp-next; ∥暂存 p 的后继 if(p-data0) {p-nextB-next; B-nextp; }∥将小于 0 的结点链入 B 表,前插法 else {p-nextC-next; C-nextp; }∥将大于等于 0 的结点链入 C 表,前插法 pr;∥p 指向新的待处理结点。 } } 6 设计一个算法通过一趟遍历在单链表中确定值最大的结点。 [题目分析] 假定第一个结点中数据具有最大值依次与下一个元素比较若其小于下一个元素则设其下一个元素为最大值反复进行比较直到遍历完该链表。 [算法描述] ElemType Max (LinkList L ){ if(L-nextNULL) return NULL; pmaxL-next; //假定第一个结点中数据具有最大值 pL-next-next; while(p ! NULL ){//如果下一个结点存在 if(p-data pmax-data) pmaxp;//如果 p 的值大于 pmax 的值则重新赋值 pp-next;//遍历链表 } return pmax-data; 7 设计一个算法通过遍历一趟将链表中所有结点的链接方向逆转仍利用原表的存储空间。 [题目分析] 从首元结点开始逐个地把链表 L 的当前结点 p 插入新的链表头部。 [算法描述] void inverse(LinkList L) {// 逆置带头结点的单链表 L pL-next; L-nextNULL; while ( p) { qp-next; // q 指向*p 的后继 p-nextL-next; L-nextp; // *p 插入在头结点之后 p q; } } 8 设计一个算法删除递增有序链表中值大于 mink 且小于 maxk 的所有元素mink和 maxk 是给定的两个参数其值可以和表中的元素相同也可以不同 。 [题目分析] 分别查找第一个值mink 的结点和第一个值 ≥maxk 的结点再修改指针删除值大于 mink 且小于 maxk 的所有元素。 [算法描述] void delete(LinkList L, int mink, int maxk) { pL-next; //首元结点 while (p p-datamink) { prep; pp-next; } //查找第一个值mink 的结点 if (p) {while (p p-datamaxk) pp-next; // 查找第一个值 ≥maxk 的结点 qpre-next; pre-nextp; // 修改指针 while (q!p) { sq-next; delete q; qs; } // 释放结点空间 }//if } 9 已知 p 指向双向循环链表中的一个结点其结点结构为 data、prior、next 三个域写出算法 change(p),交换 p 所指向的结点和它的前缀结点的顺序。 [题目分析] 知道双向循环链表中的一个结点与前驱交换涉及到四个结点 p 结点前驱结点前驱的前驱结点后继结点六条链。 [算法描述] void ExchangeLinkedList p ∥p 是双向循环链表中的一个结点本算法将 p 所指结点与其前驱结点交换。 {qp-llink q-llink-rlinkp ∥p 的前驱的前驱之后继为 p p-llinkq-llink ∥p 的前驱指向其前驱的前驱。 q-rlinkp-rlink ∥p 的前驱的后继为 p 的后继。 q-llinkp ∥p 与其前驱交换 p-rlink-llinkq ∥p 的后继的前驱指向原 p 的前驱 p-rlinkq ∥p 的后继指向其原来的前驱 }∥算法 exchange 结束。 10 已知长度为 n 的线性表 A 采用顺序存储结构请写一时间复杂度为 O(n)、空间复杂度为 O(1)的算法该算法删除线性表中所有值为 item 的数据元素。 [题目分析] 在顺序存储的线性表上删除元素通常要涉及到一系列元素的移动删第 i 个元素第 i1 至第 n 个元素要依次前移。本题要求删除线性表中所有值为 item 的数据元素并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针i1jn从两端向中间移动凡遇到值 item 的数据元素时直接将右端元素左移至值为 item 的数据元素位置。 [算法描述] void DeleteElemType A[ ]int n ∥A 是有 n 个元素的一维数组本算法删除 A 中所有值为 item 的元素。 {i1jn∥设置数组低、高端指针下标。 whileij {whileij A[i]!itemi ∥若值不为 item左移指针。 ifijwhileij A[j]itemj--∥若右端元素为 item指针左移 ifijA[i]A[j--]} 第 3 章 栈和队列 1. 选择题 1 若让元素 12345 依次进栈则出栈次序不可能出现在 种情况。 A54321B21543 C43125 D23541答案C 解释栈是后进先出的线性表不难发现 C 选项中元素 1 比元素 2 先出栈违背了栈的后进先出原则所以不可能出现 C 选项所示的情况。 2 若已知一个栈的入栈序列是 123…n其输出序列为 p1p2p3…pn若 p1n则 pi 为 。 Ai Bn-i Cn-i1 D不确定答案C 解释栈是后进先出的线性表一个栈的入栈序列是 123…n而输出序列的第一个元素为 n说明123…n 一次性全部进栈再进行输出所以 p1np2n-1… pin-i1。 3 数组用来表示一个循环队列为当前队列头元素的前一位置为队尾元素的位置假定队列中元素的个数小于计算队列中元素个数的公式为 。 Ar-f B(nf-r)%n Cnr-f Dnr-f)%n答案D 解释对于非循环队列尾指针和头指针的差值便是队列的长度而对于循环队列差值可能为负数所以需要将差值加上 MAXSIZE本题为 n然后与 MAXSIZE本题为 n求余即nr-f)%n。 4 链式栈结点为(data,link)top 指向栈顶.若想摘除栈顶结点 并将删除结点的值保存到 x 中,则应执行操作 。 A. xtop-data;toptop-link Btoptop-link;xtop-link Cxtop;toptop-link Dxtop-link 答案A 解释xtop-data 将结点的值保存到 x 中toptop-link 栈顶指针指向栈顶下一结点即摘除栈顶结点。 5 设有一个递归算法如下 int fact(int n) { //n 大于等于 0 if(n0) return 1; else return n*fact(n-1); } 则计算 fact(n)需要调用该函数的次数为 。 A n1 B n-1 C n D n2 答案A 解释特殊值法。设 n0易知仅调用一次 fact(n)函数故选 A。 6 栈在 中有所应用。 A. 递归调用 B函数调用 C表达式求值 D前三个选项都有答案D 解释递归调用、函数调用、表达式求值均用到了栈的后进先出性质。 为解决计算机主机与打印机间速度不匹配问题通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 。 A. 队列 B栈 C 线性表 D有序表答案A 解释解决缓冲区问题应利用一种先进先出的线性表而队列正是一种先进先出的线 性表。 设栈 S 和队列 Q 的初始状态为空元素 e1、e2、e3、e4、e5 和 e6 依次进入栈 S一个元素出栈后即进入 Q若 6 个元素出队的序列是 e2、e4、e3、e6、e5 和 e1则栈 S 的容量至少应该是 。 A2 B3 C4 D 6 答案B 解释元素出队的序列是 e2、e4、e3、e6、e5 和 e1可知元素入队的序列是 e2、e4、 e3、e6、e5 和 e1即元素出栈的序列也是 e2、e4、e3、e6、e5 和 e1而元素 e1、e2、e3、 e4、e5 和 e6 依次进入栈易知栈 S 中最多同时存在 3 个元素故栈S 的容量至少为 3。 9 若一个栈以向量 V[1..n]存储初始栈顶指针 top 设为 n1则元素 x 进栈的正确操作是( )。 A. top; V[top]x; BV[top]x; top; Ctop--; V[top]x; DV[top]x; top--;答案C 解释初始栈顶指针 top 为 n1说明元素从数组向量的高端地址进栈又因为元素存储在向量空间 V[1..n]中所以进栈时 top 指针先下移变为 n之后将元素 x 存储在 V[n]。 10 设计一个判别表达式中左右括号是否配对出现的算法采用 数据结构最佳。 A. 线性表的顺序存储结构 B队列 C. 线性表的链式存储结构 D. 栈答案D 解释利用栈的后进先出原则。 11 用链接方式存储的队列在进行删除运算时 。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改答案D 解释一般情况下只修改头指针但是当删除的是队列中最后一个元素时队尾指 针也丢失了因此需对队尾指针重新赋值。 12 循环队列存储在数组 A[0..m]中则入队时的操作为 。 A. rearrear1 B. rear(rear1)%(m-1) C. rear(rear1)%m D. rear(rear1)%(m1)答案D 解释数组 A[0..m]中共含有 m1 个元素故在求模运算时应除以 m1。 13 最大容量为 n 的循环队列队尾指针是 rear队头是 front则队空的条件是 。 A. (rear1)%nfront B. rearfront Crear1front D. (rear-l)%nfront答案B 解释 最大容量为 n 的循环队列队满条件是(rear1)%nfront 队空条件是 rearfront。 14 栈和队列的共同点是 。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点答案C 解释栈只允许在栈顶处进行插入和删除元素队列只允许在队尾插入元素和在队头删除元素。 15一个递归算法必须包括 。 A. 递归部分 C. 迭代部分答案B B. 终止条件和递归部分 D. 终止条件和迭代部分 2. 算法设计题 1 将编号为 0 和 1 的两个栈存放于一个数组空间 V[m]中栈底分别处于数组的两端。当第 0 号栈的栈顶指针 top[0]等于-1 时该栈为空当第 1 号栈的栈顶指针 top[1]等于 m 时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下 Typedef struct {int top[2],bot[2]; //栈顶和栈底指针 SElemType *V; //栈数组 int m; //栈最大可容纳元素个数 }DblStack [题目分析] 两栈共享向量空间将两栈栈底设在向量两端初始时左栈顶指针为-1右栈顶为 m。两栈顶指针相邻时为栈满。两栈顶相向、迎面增长栈顶指针指向栈顶元素。 [算法描述] (1) 栈初始化 int Init() {S.top[0]-1; S.top[1]m; return 1; //初始化成功 } (2) 入栈操作 int push(stk S ,int i,int x) ∥i 为栈号i0 表示左栈i1 为右栈x 是入栈元素。入栈成功返回 1失败返回 0 {if(i0||i1){ cout“栈号输入不对”endl;exit(0);} if(S.top[1]-S.top[0]1) {cout“栈已满”endl;return(0);} switch(i) {case 0: S.V[S.top[0]]x; return(1); break; case 1: S.V[--S.top[1]]x; return(1); } }∥push (3) 退栈操作 ElemType pop(stk S,int i) ∥退栈。i 代表栈号i0 时为左栈i1 时为右栈。退栈成功时返回退栈元素 ∥否则返回-1 {if(i0 || i1){cout“栈号输入错误”endlexit(0);} switch(i) {case 0: if(S.top[0]-1) {cout“栈空”endlreturn-1} else return(S.V[S.top[0]--]); case 1: if(S.top[1]m { cout“栈空”endl; return(-1);} else return(S.V[S.top[1]]); }∥switch }∥算法结束 (4) 判断栈空 int Empty(); {return (S.top[0]-1 S.top[1]m); } [算法讨论] 请注意算法中两栈入栈和退栈时的栈顶指针的计算。左栈是通常意义下的栈而右栈入栈操作时其栈顶指针左移减 1退栈时栈顶指针右移加 1。 2 回文是指正读反读均相同的字符序列如“abba”和“abdba”均是回文但“ good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示将一半字符入栈) [题目分析] 将字符串前一半入栈然后栈中元素和字符串后一半进行比较。即将第一个出栈元素和后一半串中第一个字符比较若相等则再出栈一个元素与后一个字符比较……直至栈空结论为字符序列是回文。在出栈元素与串中字符比较不等时结论字符序列不是回文。 [算法描述] #define StackSize 100 //假定预分配的栈空间最多为 100 个元素 typedef char DataType;//假定栈元素的数据类型为字符 typedef struct {DataType data[StackSize]; int top; }SeqStack; int IsHuiwen( char *t) {//判断 t 字符向量是否为回文若是返回 1否则返回 0 SeqStack s; int i , len; char temp; InitStack( s); lenstrlen(t); //求向量长度 for ( i0; ilen/2; i)//将一半字符入栈 Push( s, t[i]); while( !EmptyStack( s)) {// 每弹出一个字符与相应字符比较 tempPop (s); if( temp!S[i]) return 0 ;// 不等则返回 0 else i; } return 1 ; // 比较完毕均相等则返回 1 } 设从键盘输入一整数的序列a1, a2, a3…an试编写算法实现用栈结构存储输入的整数当 ai≠-1 时将ai 进栈当 ai-1 时输出栈顶整数并出栈。算法应对异常情况入栈满等给出相应的信息。 [算法描述] #define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s 是元素为整数的栈本算法进行入栈和退栈操作。 {int top0; //top 为栈顶指针定义 top0 时为栈空。 for(i1; in; i) //n 个整数序列作处理。 {cinx); //从键盘读入整数序列。 if(x!-1) // 读入的整数不等于-1 时入栈。 if(topmaxsize-1){cout“栈满”endl;exit(0);} else s[top]x; //x 入栈。 else //读入的整数等于-1 时退栈。 {if(top0){ cout“栈空”endl;exit(0);} else cout“ 出栈元素是” s[top--]endl;} } }//算法结束。 4 从键盘上输入一个后缀表达式试编写算法计算表达式的值。规定逆波兰表达式的长度不超过一行以$符作为输入结束操作数之间用空格分隔,操作符只可能有、-、*、 /四种运算。例如234 342*$。 [题目分析] 逆波兰表达式(即后缀表达式)求值规则如下设立运算数栈 OPND,对表达式从左到右扫描(读入)当表达式中扫描到数时压入 OPND 栈。当扫描到运算符时从 OPND 退出两个数进行相应运算结果再压入 OPND 栈。这个过程一直进行到读出表达式结束符$这时 OPND栈中只有一个数就是结果。 [算法描述] float expr( ) //从键盘输入逆波兰表达式以‘$’表示输入结束本算法求逆波兰式表达式的值。 float OPND[30]; // OPND 是操作数栈。 init(OPND); //两栈初始化。 float num0.0; //数字初始化。 cinx;//x 是字符型变量。 while(x!’$’) {switch {case‘0’x’9’: while((x’0’x’9’)||x’.’) //拼数 if(x!’.’) //处理整数 {numnum*10ord(x)-ord(‘0’); cinx;} else //处理小数部分。 {scale10.0; cinx; while(x’0’x’9’) {numnum(ord(x)-ord(‘0’)/scale; scalescale*10; cinx; } }//else push(OPND,num); num0.0;//数压入栈下个数初始化 case x‘ ’:break; //遇空格继续读下一个字符。 case x‘’:push(OPND,pop(OPND)pop(OPND));break; case x‘-’:x1pop(OPND);x2pop(OPND);push(OPND,x2 -x1);break; case x‘*’:push(OPND,pop(OPND)*pop(OPND));break; case x‘/’:x1pop(OPND);x2pop(OPND);push(OPND,x2/x1);break; default: //其它符号不作处理。 }//结束 switch cinx;//读入表达式中下一个字符。 }//结束 whilex‘$’ cout“后缀表达式的值为”pop(OPND); }//算法结束。 [算法讨论]假设输入的后缀表达式是正确的未作错误检查。算法中拼数部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符认为是数。这种字符的序号减去字符‘ 0’的序号得出数。对于整数每读入一个数字字符前面得到的部分数要乘上 10 再加新读入的数得到新的部分数。当读到小数点认为数的整数部分已完要接着处理小数部分。小数部分的数要除以 10或10 的幂数变成十分位百分位千分位数等等与前面部分数相加。在拼数过程中若遇非数字字符表示数已拼完将数压入栈中并且将变量 num 恢复为 0准备下一个数。这时对新读入的字符进入‘’、‘-’、‘*’、‘/’及空格的判断因此在结束处理数字字符的 case 后不能加入 break 语句。 5 假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列称可以操作的序列为合法序列否则称为非法序列。 ①下面所示的序列中哪些是合法的 A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO ②通过对①的分析写出一个算法判定所给的操作序列是否合法。若合法返回 true否则返回 false假定被判定的操作序列已存入一维数组中。 答案 ①A 和 D 是合法序列B 和 C 是非法序列。 ②设被判定的操作序列已存入一维数组 A 中。 int Judge(char A[]) //判断字符数组 A 中的输入输出序列是否是合法序列。如是返回 true否则返回 false。 {i0; //i 为下标。 jk0; //j 和 k 分别为 I 和字母 O 的的个数。 while(A[i]!‘\0’) //当未到字符数组尾就作。 {switch(A[i]) {case‘I’: j; break; //入栈次数增 1。 case‘O’: k; if(kj){cout“序列非法”ednlexit(0);} } i; //不论 A[i]是‘I’或‘O’指针 i 均后移。} if(j!k) {cout“序列非法”endlreturn(false);} else { cout“ 序列合法”endlreturn(true);} }//算法结束。 [算法讨论]在入栈出栈序列即由‘ I’和‘O’组成的字符串的任一位置入栈次数 ‘I’的个数都必须大于等于出栈次数即‘ O’的个数否则视作非法序列立即给出信息退出算法。整个序列即读到字符数组中字符串的结束标记‘\0’入栈次数必须等于出栈次数题目中要求栈的初态和终态都为空否则视为非法序列。 (6假设以带头结点的循环链表表示队列并且只设一个指针指向队尾元素站点(注意不设头指针) 试编写相应的置空队、判队空 、入队和出队等算法。 [题目分析] 置空队就是建立一个头节点并把头尾指针都指向头节点头节点是不存放数据的判队空就是当头指针等于尾指针时队空入队时将新的节点插入到链队列的尾部同时将尾指针指向这个节点出队时删除的是队头节点要注意队列的长度大于 1 还是等于 1 的 情况这个时候要注意尾指针的修改如果等于 1则要删除尾指针指向的节点。 [算法描述] //先定义链队结构: typedef struct queuenode {Datatype data; struct queuenode *next; }QueueNode; //以上是结点类型的定义 typedef struct {queuenode *rear; }LinkQueue; //只设一个指向队尾元素的指针 (1) 置空队 void InitQueue( LinkQueue *Q) { //置空队就是使头结点成为队尾元素 QueueNode *s; Q-rear Q-rear-next;//将队尾指针指向头结点 while (Q-rear!Q-rear-next)//当队列非空将队中元素逐个出队 {sQ-rear-next; Q-rear-nexts-next; delete s; }//回收结点空间 } (2) 判队空 int EmptyQueue( LinkQueue *Q) { //判队空。当头结点的 next 指针指向自己时为空队 return Q-rear-next-nextQ-rear-next; } (3) 入队 void EnQueue( LinkQueue *Q, Datatype x) { //入队。也就是在尾结点处插入元素 QueueNode *pnew QueueNode;//申请新结点 p-datax; p-nextQ-rear-next;//初始化新结点并链入 Q-rear-nextp; Q-rearp;//将尾指针移至新结点 } (4) 出队 Datatype DeQueue( LinkQueue *Q) {//出队,把头结点之后的元素摘下 Datatype t; QueueNode *p; if(EmptyQueue( Q )) Error(Queue underflow); pQ-rear-next-next; //p 指向将要摘下的结点 xp-data; //保存结点中数据 if (pQ-rear) {//当队列中只有一个结点时p 结点出队后要将队尾指针指向头结点 Q-rear Q-rear-next; Q-rear-nextp-next; } else Q-rear-next-nextp-next;//摘下结点 p delete p;//释放被删结点 return x; } 7假设以数组 Q[m]存放循环队列中的元素, 同时设置一个标志 tag以 tag 0 和 tag 1 来区别在队头指针(front)和队尾指针(rear)相等时队列状态为“空”还是“满”。试编写与 此结构相应的插入(enqueue)和删除(dlqueue)算法。 [算法描述] (1) 初始化 SeQueue QueueInit(SeQueue Q) {//初始化队列 Q.frontQ.rear0; Q.tag0; return Q; } (2) 入队 SeQueue QueueIn(SeQueue Q,int e) {//入队列 if((Q.tag1) (Q.rearQ.front)) cout队列已满endl; else {Q.rear(Q.rear1) % m; Q.data[Q.rear]e; if(Q.tag0) Q.tag1; //队列已不空 } return Q; } (3) 出队 ElemType QueueOut(SeQueue Q) {//出队列 if(Q.tag0) { cout队列为空endl; exit(0);} else {Q.front(Q.front1) % m; eQ.data[Q.front]; if(Q.frontQ.rear) Q.tag0; //空队列 } return(e); } (8如果允许在循环队列的两端都可以进行插入和删除操作。要求 ① 写出循环队列的类型定义 ② 写出“从队尾删除”和“从队头插入”的算法。 [题目分析] 用一维数组 v[0..M-1]实现循环队列 其中 M 是队列长度。设队头指针 front 和队尾指针 rear约定 front 指向队头元素的前一位置rear 指向队尾元素。定义 frontrear 时为队空(rear1)%mfront 为队满。约定队头端入队向下标小的方向发展队尾端入队向下标大的方向发展。 [算法描述] ① #define M 队列可能达到的最大长度 typedef struct {elemtp data[M]; int front,rear; }cycqueue; ② elemtp delqueue ( cycqueue Q) //Q 是如上定义的循环队列本算法实现从队尾删除若删除成功返回被删除元素否则给出出错信息。 {if (Q.frontQ.rear) { cout队列空endl; exit(0);} Q.rear(Q.rear-1M)%M; //修改队尾指针。return(Q.data[(Q.rear1M)%M]); //返回出队元素。 }//从队尾删除算法结束 void enqueue (cycqueue Q, elemtp x) // Q 是顺序存储的循环队列本算法实现“从队头插入”元素 x。 {if (Q.rear(Q.front-1M)%M) { cout队满endl; exit(0);) Q.data[Q.front]x; //x 入队列 Q.front(Q.front-1M)%M; //修改队头指针。 }// 结束从队头插入算法。 9 已知 Ackermann 函数定义如下: ① 写出计算 Ack(m,n)的递归算法并根据此算法给出出 Ack(2,1)的计算过程。 ② 写出计算 Ack(m,n)的非递归算法。 [算法描述] int Ack(int m,n) {if (m0) return(n1); else if(m!0n0) return(Ack(m-1,1)); else return(Ack(m-1,Ack(m,m-1)); }//算法结束 ① Ack(2,1)的计算过程 Ack(2,1) Ack(1,Ack(2,0)) //因 m0,n0 而得 Ack(1,Ack(1,1)) //因 m0,n0 而得 Ack(1,Ack(0,Ack(1,0))) // 因 m0,n0 而得 Ack(1,Ack(0,Ack(0,1))) // 因 m0,n0 而得 Ack(1,Ack(0,2)) // 因 m0 而得 Ack(1,3) // 因 m0 而得 Ack(0,Ack(1,2)) //因 m0,n0 而得 Ack(0,Ack(0,Ack(1,1))) //因 m0,n0 而得 Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因 m0,n0 而得 Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因 m0,n0 而得 Ack(0,Ack(0,Ack(0,2))) //因 m0 而得 Ack(0,Ack(0,3)) //因 m0 而得 Ack(0,4) //因 n0 而得 5 //因 n0 而得 ② int Ackerman(int m, int n) {int akm[M][N];int i,j; for(j0;jN;j) akm[0][j]j1; for(i1;im;i) {akm[i][0]akm[i-1][1]; for(j1;jN;j) akm[i][j]akm[i-1][akm[i][j-1]]; } return(akm[m][n]); }//算法结束 10 已知 f 为单链表的表头指针, 链表中存储的都是整型数据试写出实现下列运算的递归算法 ① 求链表中的最大整数 ② 求链表的结点个数 ③ 求所有整数的平均值。 [算法描述] ① int GetMax(LinkList p) { if(!p-next) return p-data; else { int maxGetMax(p-next); return p-datamax ? p-data:max; } } ② int GetLength(LinkList p) { if(!p-next) return 1; else { } } ③ return GetLength(p-next)1; double GetAverage(LinkList p , int n) { if(!p-next) return p-data; else { } } double aveGetAverage(p-next,n-1); return (ave*(n-1)p-data)/n; 第 4 章 串、数组和广义表 1. 选择题 1 串是一种特殊的线性表其特殊性体现在 。 A. 可以顺序存储 B 数据元素是一个字符 C可以链式存储 D 数据元素可以是多个字符若答案B 2 串下面关于串的的叙述中 是不正确的 A. 串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串既可以采用顺序存储也可以采用链式存储答案B 解释空格常常是串的字符集合中的一个元素有一个或多个空格组成的串成为空格串零个字符的串成为空串其长度为零。 3串“ababaaababaa”的 next 数组为 。 A012345678999 B012121111212 C011234223456 D0123012322345 答案C 4串“ababaabab”的 nextval 为 。 A010104101 B010102101 C010100011 D010101011 答案A 5 串的长度是指 。 A串中所含不同字母的个数 B串中所含字符的个数 C串中所含不同字符的个数 D串中所含非空格字符的个数答案B 解释串中字符的数目称为串的长度。 6 假设以行序为主序存储二维数组 Aarray[1..100,1..100]设每个数据元素占 2 个存储单元基地址为 10则LOC[5,5] 。 A808 B818 C1010 D1020 答案B 解释以行序为主则 LOC[5,5][5-1*1005-1]*210818。 7 设有数组 A[i,j]数组的每个元素长度为 3 字节i 的值为 1 到 8j 的值为 1 到 10数组从内存首地址BA 开始顺序存放当用以列为主存放时元素 A[5,8]的存储首地址为 。 ABA141 BBA180 CBA222 DBA225 答案B 解释以列序为主则 LOC[5,8][8-1*85-1]*3BABA180。 8 设有一个 10 阶的对称矩阵 A采用压缩存储方式以行序为主存储a11 为第一元素其存储地址为 1每个元素占一个地址空间则 a85 的地址为 。 A13 B32 C33 D40 答案C 9 若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素(包括主对角线上所有 元素)依次存放于一维数组 B[1..(n(n1))/2]中则在 B 中确定 aij ij的位置 k 的关系为 。 A. i*(i-1)/2j Bj*(j-1)/2i Ci*(i1)/2j Dj*(j1)/2i 答案B 10 二维数组 A 的每个元素是由 10 个字符组成的串其行下标 i0,1,…,8,列下标 j1,2,…,10。若 A 按行先存储元素A[8,5]的起始地址与当 A 按列先存储时的元素 的起始地址相同。设每个字符占一个字节。 AA[8,5] BA[3,10] C. A[5,8] DA[0,9] 答案B 解释设数组从内存首地址 M 开始顺序存放若数组按行先存储元素 A[8,5]的起始地址为M[8-0*105-1]*1M84若数组按列先存储易计算出元素 A[3,10]的起始地址为M[10-1*93-0]*1M84。故选 B。 设二维数组 A[1.. m1.. n]即 m 行 n 列按行存储在数组 B[1.. m*n]中则二维数组元素 A[i,j]在一维数组 B 中的下标为 。 A(i-1)*nj B(i-1)*nj-1 Ci*(j-1) Dj*mi-1 答案A 解释特殊值法。取 ij1易知 A[1,1]的的下标为 1四个选项中仅有 A 选项能确定的值为 1故选 A。 数组 A[0..4,-1..-3,5..7]中含有元素的个数 。 A55 B45 C36 D16 答案B 解释共有 5*3*345 个元素。 广义表 A(a,b,(c,d),(e,(f,g)))则 Head(Tail(Head(Tail(Tail(A))))) 的值为 。 A(g) B(d) Cc Dd 答案D 解释 Tail(A)(b,(c,d),(e,(f,g))) Tail(Tail(A))( (c,d),(e,(f,g))) Head(Tail(Tail(A))) (c,d)Tail(Head(Tail(Tail(A))))(d)Head(Tail(Head(Tail(Tail(A)))))d。 广义表((a,b,c,d))的表头是 表尾是 。 Aa B( ) C(a,b,c,d) D(b,c,d) 答案C、B 解释 表头为非空广义表的第一个元素 可以是一个单原子 也可以是一个子表 ((a,b,c,d))的表头为一个子表(a,b,c,d)表尾为除去表头之外由其余元素构成的表表为一定是个广义表((a,b,c,d))的表尾为空表( )。 设广义表 L((a,b,c))则 L 的长度和深度分别为 。 A.1 和 1 B1 和 3 C1 和 2 D2 和 3 答案C 解释广义表的深度是指广义表中展开后所含括号的层数广义表的长度是指广义表中所含元素的个数。根据定义易知 L 的长度为 1深度为 2。 2. 应用题 1 已知模式串 t‘abcaabbabcab’写出用 KMP 法求得的每个字符对应的 next 和 nextval函数值。 答案 模式串 t 的 next 和 nextval 值如下 j 1 2 3 4 5 6 7 8 9 10 11 12 t 串 a b c a a b b a b c a b next[j] 0 1 1 1 2 2 3 1 2 3 4 5 nextval[j] 0 1 1 0 2 1 3 0 1 1 0 5 2 设目标为 t“abcaabbabcabaacbacba”,模式为 p“abcabaa” ① 计算模式 p 的 naxtval 函数值 ② 不写出算法,只画出利用 KMP 算法进行模式匹配时每一趟的匹配过程。答案 ① p 的 nextval 函数值为 0110132。p 的 next 函数值为 0111232。 ② 利用 KMP(改进的 nextval)算法每趟匹配过程如下第一趟匹配 abcaabbabcabaacbacba abcab(i5,j5) 第二趟匹配 abcaabbabcabaacbacba abc(i7,j3) 第三趟匹配 abcaabbabcabaacbacba a(i7,j1) 第四趟匹配 abcaabbabcabaac bacba (成功) abcabaa(i15,j8) 3 数组 A 中每个元素 A[i,j]的长度均为 32 个二进位,行下标从-1 到 9列下标从 1到 11从首地址 S 开始连续存放主存储器中主存储器字长为 16 位。求 ① 存放该数组所需多少单元 ② 存放数组第 4 列所有元素至少需多少单元 ③ 数组按行存放时元素 A[7,4]的起始地址是多少 ④ 数组按列存放时元素 A[4,7]的起始地址是多少答案 每个元素 32 个二进制位主存字长 16 位故每个元素占 2 个字长行下标可平移至 1到 11。 1242 222 3s182 4s142 (4) 请将香蕉 banana 用工具 H( )—Head( )T( )—Tail( )从 L 中取出。 L(apple,(orange,(strawberry,(banana)),peach),pear) 答案HHTHTHTL 3. 算法设计题 1 写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件字符串中的合法字符为 A-Z 这 26 个字母和 0-9 这 10 个数字。 [题目分析] 由于字母共 26 个加上数字符号 10 个共 36 个所以设一长 36 的整型数组 前 10 个分量存放数字字符出现的次数余下存放字母出现的次数。从字符串中读出数字字符时字符的 ASCII 代码值减去数字字符 ‘0’ 的 ASCII 代码值得出其数值(0..9)字母的 ASCII 代码值减去字符‘A’的 ASCII 代码值加上 10存入其数组的对应下标分量中。遇其它符号不作处理直至输入字符串结束。 [算法描述] void Count //统计输入字符串中数字字符和字母字符的个数。 int inum[36] char ch fori0i36inum[i]// 初始化 whilechgetchar!‘#’ //‘#’表示输入字符串结束。 if‘0’ch‘9’ich48;num[i] // 数字字符 else if‘A’ch‘Z’ich-6510;num[i]// 字母字符 fori0i10i // 输出数字字符的个数 cout“数字”i “的个数”num[i]endl; fori10i36i// 求出字母字符的个数 cout“字母字符”i55 “的个数”num[i]endl; 2 写一个递归算法来实现字符串逆序存储要求不另设串存储空间。 [题目分析]实现字符串的逆置并不难但本题“要求不另设串存储空间”来实现字符串逆序存储即第一个输入的字符最后存储最后输入的字符先存储使用递归可容易做到。 [算法描述] void InvertStore(char A[]) //字符串逆序存储的递归算法。 {char ch; static int i 0;//需要使用静态变量 cinch; if (ch! .) //规定.是字符串输入结束标志 {InvertStore(A); A[i] ch;//字符串逆序存储 } A[i] \0; //字符串结尾标记 } 编写算法实现下面函数的功能。函数 void insert(char*s,char*t,int pos)将字符串 t 插入到字符串 s 中插入位置为pos。假设分配给字符串 s 的空间足够让字符串 t插入。说明不得使用任何库函数 [题目分析]本题是字符串的插入问题要求在字符串 s 的 pos 位置插入字符串 t。首先应查找字符串 s 的 pos 位置将第pos 个字符到字符串 s 尾的子串向后移动字符串 t 的长度然后将字符串 t 复制到字符串 s 的第 pos 位置后。 对插入位置 pos 要验证其合法性小于 1 或大于串 s 的长度均为非法因题目假设给字符串 s 的空间足够大故对插入不必判溢出。 [算法描述] void insert(char *s,char *t,int pos) //将字符串 t 插入字符串 s 的第 pos 个位置。 {int i1,x0; char *ps,*qt; //pq 分别为字符串 s 和 t 的工作指针 if(pos1) {cout“pos 参数位置非法”endl;exit(0);} while(*p!’\0’ipos) {p;i;} //查 pos 位置 //若 pos 小于串 s 长度则查到 pos 位置时ipos。 if(*p /0) { coutpos位置大于字符串 s 的长度;exit(0);} else //查找字符串的尾 while(*p! /0) {p; i;} //查到尾时i 为字符‘\0’的下标p 也指向‘\0’。 while(*q! \0) {q; x; } //查找字符串 t 的长度 x循环结束时 q 指向\0。 for(ji;jpos ;j--){*(px)*p; p--;}//串 s 的 pos 后的子串右移空出串 t 的位 置。 q--; //指针 q 回退到串 t 的最后一个字符 for(j1;jx;j) *p--*q--; //将 t 串插入到 s 的 pos 位置上 [算法讨论] 串 s 的结束标记(\0)也后移了而串 t 的结尾标记不应插入到 s 中。 4 已知字符串 S1 中存放一段英文写出算法 format(s1,s2,s3,n),将其按给定的长度 n 格式化成两端对齐的字符串 S2, 其多余的字符送 S3。 [题目分析]本题要求字符串 s1 拆分成字符串 s2 和字符串 s3要求字符串 s2“按给定长度 n 格式化成两端对齐的字符串”即长度为 n 且首尾字符不得为空格字符。算法从左到右扫描字符串 s1找到第一个非空格字符计数到 n第 n 个拷入字符串 s2 的字符不得为空格然后将余下字符复制到字符串 s3 中。 [算法描述] void format (char *s1,*s2,*s3) //将字符串 s1 拆分成字符串 s2 和字符串 s3要求字符串 s2 是长 n 且两端对齐 {char *ps1, *qs2; int i0; while(*p! \0 *p ) p;//滤掉 s1 左端空格 if(*p \0) {cout字符串 s1 为空串或空格串endl;exit(0); } while( *p!\0 in){*q*p; q; p; i;} //字符串 s1 向字符串 s2 中复制 if(*p \0){cout字符串 s1 没有n个有效字符endl; exit(0);} if(*(--q) ) //若最后一个字符为空格则需向后找到第一个非空格字符 {p-- ; //p 指针也后退 while(*p *p!\0) p;//往后查找一个非空格字符作串 s2 的尾字符 if(*p\0) {couts1 串没有n个两端对齐的字符串endl; exit(0);} *q*p; //字符串 s2 最后一个非空字符 *(q)\0; //置 s2 字符串结束标记 } *qs3;p; //将 s1 串其余部分送字符串 s3。 while (*p! \0) {*q*p; q; p;} *q\0; //置串 s3 结束标记 } 5 设二维数组 a[1..m, 1..n] 含有 m*n 个整数。 ① 写一个算法判断 a 中所有元素是否互不相同?输出相关信息(yes/no) ② 试分析算法的时间复杂度。 ① [题目分析]判断二维数组中元素是否互不相同只有逐个比较,找到一对相等的元素就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次在当前行每个元素要同本行后面的元素比较一次下面第一个循环控制变量 p 的for 循环然后同第 i1行及以后各行元素比较一次这就是循环控制变量 k 和 p 的二层 for 循环。 [算法描述] int JudgEqual(ing a[m][n],int m,n) //判断二维数组中所有元素是否互不相同如是返回 1否则返回 0。 {for(i0;im;i) for(j0;jn-1;j) {for(pj1;pn;p) //和同行其它元素比较 if(a[i][j]a[i][p]) {cout“no”; return(0); } //只要有一个相同的就结论不是互不相同 for(ki1;km;k) //和第 i1 行及以后元素比较 for(p0;pn;p) if(a[i][j]a[k][p]) { cout“no”; return(0); } }// for(j0;jn-1;j) cout“yes”; return(1); //元素互不相同 }//算法 JudgEqual 结束 ②二维数组中的每一个元素同其它元素都比较一次数组中共 m*n 个元素第 1 个元素同其它 m*n-1 个元素比较第 2 个元素同其它 m*n-2 个元素比较……第 m*n-1 个元素同最后一个元素(m*n) 比较一次, 所以在元素互不相等时总的比较次数为 (m*n-1)(m*n-2)… 21m*n(m*n-1)/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在(m*n-1)个位置上均可能相同,这时的平均比较次数约为m*n(m*n-1)/4总的时间复杂度是 O(n4)。 (6)设任意 n 个整数存放于数组 A(1:n)中试编写算法将所有正数排在所有负数前面 要求算法复杂度为 0(n)。 [题目分析]本题属于排序问题只是排出正负不排出大小。可在数组首尾设两个指针 i 和 ji 自小至大搜索到负数停止j 自大至小搜索到正数停止。然后 i 和 j 所指数据交换继续以上过程直到 ij 为止。 [算法描述] void Arrange(int A[],int n) //n 个整数存于数组 A 中本算法将数组中所有正数排在所有负数的前面 {int i0,jn-1,x; //用类 C 编写数组下标从 0 开始 while(ij) {while(ij A[i]0) i; while(ij A[j]0) j--; if(ij) {xA[i]; A[i]A[j]; A[j--]x; }//交换 A[i] 与 A[j] }// while(ij) }//算法 Arrange 结束. [算法讨论]对数组中元素各比较一次比较次数为 n。最佳情况(已排好,正数在前,负数在后)不发生交换最差情况(负数均在正数前面)发生 n/2 次交换。用类 c 编写数组界偶是 0..n-1。空间复杂度为 O(1). 第 5 章 树和二叉树 1. 选择题 1 把一棵树转换为二叉树后这棵二叉树的形态是 。 A唯一的 有多种 C有多种但根结点都没有左孩子 有多种但根结点都没有右孩子答案A 解释因为二叉树有左孩子、右孩子之分故一棵树转换为二叉树后这棵二叉树的形态是唯一的。 2 由 3 个结点可以构造出多少种不同的二叉树 A2 B3 C4 D5答案D 解释五种情况如下 3 一棵完全二叉树上有 1001 个结点其中叶子结点的个数是 。 A250 B 500 C254 D501 答案D 解释设度为 0 结点叶子结点个数为 A度为 1 的结点个数为 B度为 2 的结点个数为 C有 AC1ABC1001可得 2CB1000由完全二叉树的性质可得 B0 或 1又因为 C 为整数所以 B0C500A501即有 501 个叶子结点。 一个具有 1025 个结点的二叉树的高 h 为 。 A11 B10 C11 至 1025 之间 D10 至 1024 之间答案C 解释若每层仅有一个结点则树高 h 为 1025且其最小树高为 ëlog21025û 111即 h 在 11 至 1025 之间。 5 深度为 h 的满 m 叉树的第 k 层有 个结点。(1kh) Amk- 1 Bmk-1 Cmh- 1 Dmh-1答案A 解释深度为 h 的满 m 叉树共有 mh-1 个结点第 k 层有 mk-1 个结点。 6 利用二叉链表存储树则根结点的右指针是 。 A. 指向最左孩子 B指向最右孩子 C空 D非空答案C 解释利用二叉链表存储树时右指针指向兄弟结点因为根节点没有兄弟结点故根 节点的右指针指向空。 对二叉树的结点从 1 开始进行连续编号要求每个结点的编号大于其左、右孩子的编号同一结点的左右孩子中其左孩子的编号小于其右孩子的编号可采用 遍历实现编号。 先序 B. 中序 C. 后序 D. 从根开始按层次遍历答案C 解释 根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树 即后序遍历二叉树。 8 若二叉树采用二叉链表存储结构要交换其所有分支结点左、右子树的位置利用 遍历方法最合适。 A. 前序 B中序 C后序 D按层次答案C 解释 后续遍历和层次遍历均可实现左右子树的交换不过层次遍历的实现消耗比后续大后序遍历方法最合适。 9 在下列存储形式中 不是树的存储形式 A. 双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法答案D 解释树的存储结构有三种双亲表示法、孩子表示法、孩子兄弟表示法 其中孩子兄弟表示法是常用的表示法任意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。 10 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反则该二叉树一定满足 。 A. 所有的结点均无左孩子 B所有的结点均无右孩子 C只有一个叶子结点 D是任意一棵二叉树 答案C 解释因为先序遍历结果是“中左右”后序遍历结果是“左右中”当没有左子树时就是“ 中右”和“右中” 当没有右子树时就是“中左”和“左中”。则所有的结点均无左孩子或所有的结点均无右孩子均可所以 A、B 不能选又所有的结点均无左孩子与所有的结点均无右孩子时均只有一个叶子结点故选 C。 11 设哈夫曼树中有 199 个结点则该哈夫曼树中有 个叶子结点。 A99 B100 C101 D102 答案B 解释在哈夫曼树中没有度为 1 的结点只有度为 0叶子结点和度为 2 的结点。设叶子结点的个数为 n0度为 2 的结点的个数为 n2由二叉树的性质 n0n21则总结点数 n n0n22*n0-1得到 n0100。 若 X 是二叉中序线索树中一个有左孩子的结点且 X 不为根则 X 的前驱为 。 AX 的双亲 BX 的右子树中最左的结点 CX 的左子树中最右结点 DX 的左子树中最右叶结点 答案C 13 引入二叉线索树的目的是 。 A. 加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删 除 C为了能方便的找到双亲 D使二叉树的遍历结果唯一答案A 14 设 F 是一个森林B 是由 F 变换得的二叉树。若 F 中有 n 个非终端结点则 B 中 右指针域为空的结点有 个。 A. n− 1 Bn Cn 1 Dn 2答案C 15nn≥2个权值均不相同的字符构成哈夫曼树关于该树的叙述中错误的是 。 A该树一定是一棵完全二叉树 B. 树中一定没有度为 1 的结点 C树中两个权值最小的结点一定是兄弟结点 D树中任一非叶结点的权值一定不小于下一层任一结点的权值答案A 解释哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树所以树中一定没有度为 1 的结点、两个权值最小的结点一定是兄弟结点、任一非叶结点的权值一定不小于下一层任一结点的权值。 2. 应用题 1 试找出满足下列条件的二叉树 ① 先序序列与后序序列相同 ②中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④中序序列与层次遍历序列相同 答案先序遍历二叉树的顺序是“根—左子树—右子树”中序遍历“左子树— 根—右子树”后序遍历顺序是“左子树—右子树―根根据以上原则有 ① 或为空树或为只有根结点的二叉树 ② 或为空树或为任一结点至多只有左子树的二叉树 ③ 或为空树或为任一结点至多只有右子树的二叉树 ④ 或为空树或为任一结点至多只有右子树的二叉树 2 设一棵二叉树的先序序列 A B D F C E G H 中序序列 B F D A G E H C ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。 ③将这棵二叉树转换成对应的树或森林。答案 ① ② ③ 3 假设用于通信的电文仅由 8 个字母组成字母在电文中出现的频率分别为 0.070.190.020.060.320.030.210.10。 ① 试为这 8 个字母设计赫夫曼编码。 ② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例比较两种方案的优缺点。答案方案 1哈夫曼编码 先将概率放大 100 倍以方便构造哈夫曼树。 w{7,19,2,6,32,3,21,10}按哈夫曼规则【[2,36], (7,10)】, ……19, 21, 32 100 40 60 19 21 32 28 17 11 7 10 6 5 2 3 方案比较 方案 1 的 WPL2(0.190.320.21)4(0.070.060.10)5(0.020.03)1.440.920.252.61 方案 2 的 WPL3(0.190.320.210.070.060.100.020.03)3 结论哈夫曼编码优于等长二进制编码 4 已知下列字符 A、B、C、D、E、F、G 的权值分别为 3、12、7、4、2、811试填写出其对应哈夫曼树 HT 的存储结构的初态和终态。 答案初态: weight parent lchild rchild 1 3 0 0 0 2 12 0 0 0 3 7 0 0 0 4 4 0 0 0 5 2 0 0 0 6 8 0 0 0 7 11 0 0 0 8 0 0 0 9 0 0 0 10 0 0 0 11 0 0 0 12 0 0 0 13 0 0 0 终态 weight parent lchild rchild 1 3 8 0 0 2 12 12 0 0 3 7 10 0 0 4 4 9 0 0 5 2 8 0 0 6 8 10 0 0 7 11 11 0 0 8 5 9 5 1 9 9 11 4 8 10 15 12 3 6 11 20 13 9 7 12 27 13 2 10 13 47 0 11 12 3. 算法设计题 以二叉链表作为二叉树的存储结构编写以下算法 1 统计二叉树的叶结点个数。 [题目分析]如果二叉树为空返回 0如果二叉树不为空且左右子树为空返回 1如果二叉树不为空且左右子树不同时为空返回左子树中叶子节点个数加上右子树中叶子节点个数。 [算法描述] int LeafNodeCount(BiTree T) { if(TNULL) return 0; //如果是空树则叶子结点个数为 0 else if(T-lchildNULLT-rchildNULL) return 1; //判断结点是否是叶子结点左孩子右孩子都为空若是则返回 1 else return LeafNodeCount(T-lchild)LeafNodeCount(T-rchild); } 2 判别两棵树是否相等。 [题目分析]先判断当前节点是否相等(需要处理为空、是否都为空、是否相等)如果当前节点不相等直接返回两棵树不相等;如果当前节点相等那么就递归的判断他们的左 右孩子是否相等。 [算法描述] int compareTree(TreeNode* tree1, TreeNode* tree2) //用分治的方法做比较当前根然后比较左子树和右子树 {bool tree1IsNull (tree1NULL); bool tree2IsNull (tree2NULL); if(tree1IsNull ! tree2IsNull) { return 1; } if(tree1IsNull tree2IsNull) {//如果两个都是 NULL则相等 return 0; }//如果根节点不相等直接返回不相等否则的话看看他们孩子相等不相等 if(tree1-c ! tree2-c) { return 1; } return (compareTree(tree1-left,tree2-left)compareTree(tree1-right,tree2-right)) (compareTree(tree1-left,tree2-right)compareTree(tree1-right,tree2-left)); }//算法结束 3 交换二叉树每个结点的左孩子和右孩子。 [题目分析]如果某结点左右子树为空返回否则交换该结点左右孩子然后递归交换左右子树。 [算法描述] void ChangeLR(BiTree T) { BiTree temp; if(T-lchildNULLT-rchildNULL) return; else { temp T-lchild; T-lchild T-rchild; T-rchild temp; }//交换左右孩子 ChangeLR(T-lchild); //递归交换左子树 ChangeLR(T-rchild); //递归交换右子树 } 设计二叉树的双序遍历算法双序遍历是指对于二叉树的每一个结点来说先访问这个结点再按双序遍历它的左子树然后再一次访问这个结点接下来按双序遍历它的右子树。 [题目分析]若树为空返回若某结点为叶子结点则仅输出该结点否则先输出该结点递归遍历其左子树再输出该结点递归遍历其右子树。 [算法描述] void DoubleTraverse(BiTree T) { if(T NULL) return; else if(T-lchildNULLT-rchildNULL) coutT-data; //叶子结点输出 else { coutT-data; DoubleTraverse(T-lchild); //递归遍历左子树 coutT-data; DoubleTraverse(T-rchild); //递归遍历右子树 } } 5 计算二叉树最大的宽度二叉树的最大宽度是指二叉树所有层中结点个数的最大值。 [题目分析] 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法记下各层结点数每层遍历完毕若结点数大于原先最大宽度则修改最大宽度。 [算法描述] int Width(BiTree bt)//求二叉树 bt 的最大宽度 {if (btnull) return (0); //空二叉树宽度为 0 else {BiTree Q[];//Q 是队列元素为二叉树结点指针容量足够大 front1;rear1;last1; //front 队头指针,rear 队尾指针,last 同层最右结点在队列中的位置 temp0; maxw0; //temp 记局部宽度, maxw 记最大宽度 Q[rear]bt; //根结点入队列 while(frontlast) {pQ[front]; temp; //同层元素数加 1 if (p-lchild!null) Q[rear]p-lchild; //左子女入队 if (p-rchild!null) Q[rear]p-rchild; //右子女入队 if (frontlast) //一层结束 {lastrear; if(tempmaxw) maxwtemp; //last 指向下层最右元素, 更新当前最大宽度 temp0; }//if }//while return (maxw); }//结束 width 6 用按层次顺序遍历二叉树的方法统计树中具有度为 1 的结点数目。 [题目分析] 若某个结点左子树空右子树非空或者右子树空左子树非空则该结点为度为 1 的结点 [算法描述] int Level(BiTree bt) //层次遍历二叉树并统计度为 1 的结点的个数 {int num0; //num 统计度为 1 的结点的个数 if(bt){QueueInit(Q); QueueIn(Q,bt);//Q 是以二叉树结点指针为元素的队列 while(!QueueEmpty(Q)) {pQueueOut(Q); coutp-data; //出队,访问结点 if(p-lchild !p-rchild ||!p-lchild p-rchild)num; //度为 1 的结点 if(p-lchild) QueueIn(Q,p-lchild); //非空左子女入队 if(p-rchild) QueueIn(Q,p-rchild); //非空右子女入队 } // while(!QueueEmpty(Q)) }//if(bt) return(num); }//返回度为 1 的结点的个数 求任意二叉树中第一条最长的路径长度并输出此路径上各结点的值。 [题目分析]因为后序遍历栈中保留当前结点的祖先的信息用一变量保存栈的最高栈顶指针每当退栈时栈顶指针高于保存最高栈顶指针的值时则将该栈倒入辅助栈中辅助栈始终保存最长路径长度上的结点直至后序遍历完毕则辅助栈中内容即为所求。 [算法描述] void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度 {BiTree pbt,l[],s[]; //l, s 是栈元素是二叉树结点指针l 中保留当前最长路径中的结点 int itop0,tag[],longest0; while(p || top0) {while(p) {s[top]ptag[top]0; pp-Lc;} //沿左分枝向下 if(tag[top]1) //当前结点的右分枝已遍历 {if(!s[top]-Lc !s[top]-Rc) //只有到叶子结点时才查看路径长度 if(toplongest) {for(i1;itop;i) l[i]s[i]; longesttop; top--;} //保留当前最长路径到 l 栈记住最高栈顶指针退栈 } else if(top0) {tag[top]1; ps[top].Rc;} //沿右子分枝向下 }//while(p!null||top0) }//结束 LongestPath 8 输出二叉树中从每个叶子结点到根结点的路径。 [题目分析]采用先序遍历的递归方法当找到叶子结点*b 时由于*b 叶子结点尚未添加到 path 中因此在输出路径时还需输出 b-data 值。 [算法描述] void AllPath(BTNode *b,ElemType path[],int pathlen) {int i; if (b!NULL) {if (b-lchildNULL b-rchildNULL) //*b 为叶子结点 {cout b-data 到根结点路径: b-data; for (ipathlen-1;i0;i--) cout endl; } else {path[pathlen]b-data; //将当前结点放入路径中 pathlen; //路径长度增 1 AllPath(b-lchild,path,pathlen); //递归扫描左子树 AllPath(b-rchild,path,pathlen); //递归扫描右子树 pathlen--; //恢复环境 } }// if (b!NULL) }//算法结束 第 6 章 图 1. 选择题 1 在一个图中所有顶点的度数之和等于图的边数的 倍。 A1/2 B1 C2 D4答案C 2 在一个有向图中所有顶点的入度之和等于所有顶点的出度之和的 倍。 A1/2 B1 C2 D4 答案B 解释有向图所有顶点入度之和等于所有顶点出度之和。 3 具有 n 个顶点的有向图最多有 条边。 An Bn(n-1) Cn(n1) Dn2 答案B 解释有向图的边有方向之分即为从 n 个顶点中选取 2 个顶点有序排列结果为 n(n-1)。 4n 个顶点的连通图用邻接距阵表示时该距阵至少有 个非零元素。 An B2(n-1) Cn/2 Dn2 答案B 5G 是一个非连通无向图共有 28 条边则该图至少有 个顶点。 A7 B8 C9 D10 答案C 解释8 个顶点的无向图最多有 8*7/228 条边再添加一个点即构成非连通无向图故至少有 9 个顶点。 6 若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点则该图一定是 图。 A. 非连通 B连通 C强连通 D有向答案B 解释即从该无向图任意一个顶点出发有到各个顶点的路径所以该无向图是连通图。 7 下面 算法适合构造一个稠密图 G 的最小生成树。 A. Prim 算法 BKruskal 算法 CFloyd 算法 DDijkstra 算法答案A 解释Prim 算法适合构造一个稠密图 G 的最小生成树Kruskal 算法适合构造一个稀疏图 G 的最小生成树。 8 用邻接表表示图进行广度优先遍历时通常借助 来实现算法。 A. 栈 B. 队列 C. 树 D图答案B 解释广度优先遍历通常借助队列来实现算法深度优先遍历通常借助栈来实现算法。 9 用邻接表表示图进行深度优先遍历时通常借助 来实现算法。 A. 栈 B. 队列 C. 树 D图答案A 解释广度优先遍历通常借助队列来实现算法深度优先遍历通常借助栈来实现算法。 10 深度优先遍历类似于二叉树的 。 A. 先序遍历 B中序遍历 C后序遍历 D层次遍历答案A 11 广度优先遍历类似于二叉树的 。 A. 先序遍历 B中序遍历 C后序遍历 D层次遍历答案D 12 图的 BFS 生成树的树高比 DFS 生成树的树高 。 A. 小 B相等 C小或相等 D大或相等答案C 13 已知图的邻接矩阵如图 6.30 所示 则从顶点 v0 出发按深度优先遍历的结果是 。 图 6.30 邻接矩阵 14 已知图的邻接表如图 6.31 所示则从顶点 v0 出发按广度优先遍历的结果是 按深度优先遍历的结果是 。 图 6.31 邻接表 A0 1 3 2 B0 2 3 1 C0 3 2 1 D0 1 2 3 答案D、D 15 下面 方法可以判断出一个有向图是否有环。 A. 深度优先遍历 B拓扑排序 C求最短路径 D求关键路径答案B 应用题 1 已知图 6.32 所示的有向图请给出 ① 每个顶点的入度和出度 ② 邻接矩阵 ③ 邻接表 ④ 逆邻接表。 图 6.32 有向图 图 6.33 无向网 答案 2 已知如图 6.33 所示的无向网请给出 ① 邻接矩阵 ② 邻接表 ③ 最小生成树答案 ① ③ é¥ ê ê ê 3 ê ê ê¥ ê ê ê¥ ê êë¥ ② ¥ù ú ú 5 ú ú ú ¥ú ú ú 6 ú ú ¥úû a → b 4 → c 3 b → a 4 → c 5 → d 5 → e 9 c → a 3 → b 5 → d 5 → h 5 d → b 5 → c 5 → e 7 → f 6 → g 5 → h 4 e → b 9 → d 7 → f 3 f → d 6 → e 3 → g 2 g → d 5 → f 2 → h 6 3 已知图的邻接矩阵如图 6.34 所示。试分别画出自顶点 1 出发进行遍历所得的深度优先生成树和广度优先生成树。 有向网如图 6.35 所示试用迪杰斯特拉算法求出从顶点a 到其他各顶点间的最短路径 完成表 6.9。 图 6.28 邻接矩阵 图 6.34 邻接矩阵 图 6.35 有向网 表 6.9 D 终点 i1 i2 i3 i4 i5 i6 b 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) c 2 (a,c) d 12 (a,d) 12 (a,d) 11 (a,c,f,d) 11 (a,c,f,d) e ∞ 10 (a,c,e) 10 (a,c,e) f ∞ 6 (a,c,f) g ∞ ∞ 16 (a,c,f,g) 16 (a,c,f,g) 14 (a,c,f,d,g ) S 终 点集 {a,c} {a,c,f} {a,c,f,e} {a,c,f,e,d } {a,c,f,e,d ,g} {a,c,f,e,d ,g,b} 5 试对图 6.36 所示的 AOE-网 ① 求这个工程最早可能在什么时间结束 ② 求每个活动的最早开始时间和最迟开始时间 ③ 确定哪些活动是关键活动 图 6.36 AOE-网 答案按拓扑有序的顺序计算各个顶点的最早可能开始时间 Ve 和最迟允许开始时间 Vl。然后再计算各个活动的最早可能开始时间 e 和最迟允许开始时间 l根据 l - e 0? 来确定关键活动从而确定关键路径。 1 ¶ 2 ¸ 3 · 4 ¹ 5 º 6 » Ve 0 19 15 29 38 43 Vl 0 19 15 37 38 43 1, 2 1, 3 3, 2 2, 4 2, 5 3, 5 4, 6 5, 6 e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38 -e 17 0 0 8 0 12 8 0 此工程最早完成时间为 43。关键路径为1, 33, 22, 55, 6 3. 算法设计题 1 分别以邻接矩阵和邻接表作为存储结构实现以下图的基本操作 ① 增加一个新顶点 vInsertVex(G, v) ② 删除顶点 v 及其相关的边DeleteVex(G, v); ③ 增加一条边vw InsertArc(G, v, w); ④ 删除一条边vw DeleteArc(G, v, w)。 [算法描述] 假设图 G 为有向无权图以邻接矩阵作为存储结构四个算法分别如下 ① 增加一个新顶点 v Status Insert_Vex(MGraph G, char v)// 在邻接矩阵表示的图 G 上插入顶点 v { if(G.vexnum1)MAX_VERTEX_NUM return INFEASIBLE; G.vexs[G.vexnum]v; return OK; }//Insert_Vex ② 删除顶点 v 及其相关的边 Status Delete_Vex(MGraph G,char v)// 在邻接矩阵表示的图 G 上删除顶点 v { nG.vexnum; if((mLocateVex(G,v))0) return ERROR; G.vexs[m]-G.vexs[n]; //将待删除顶点交换到最后一个顶点 for(i0;in;i) { G.arcs[m]G.arcs[n]; G.arcs[m]G.arcs[n]; //将边的关系随之交换 } G.arcs[m][m].adj0; G.vexnum--; return OK; }//Delete_Vex 分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加。 ③ 增加一条边vw Status Insert_Arc(MGraph G,char v,char w)// 在邻接矩阵表示的图 G 上插入边(v,w) { if((iLocateVex(G,v))0) return ERROR; if((jLocateVex(G,w))0) return ERROR; if(ij) return ERROR; if(!G.arcs[j].adj) { G.arcs[j].adj1; G.arcnum; } return OK; }//Insert_Arc ④ 删除一条边vw Status Delete_Arc(MGraph G,char v,char w)// 在邻接矩阵表示的图 G 上删除边(v,w) { if((iLocateVex(G,v))0) return ERROR; if((jLocateVex(G,w))0) return ERROR; if(G.arcs[j].adj) { G.arcs[j].adj0; G.arcnum--; } return OK; }//Delete_Arc 以邻接表作为存储结构 本题只给出 Insert_Arc 算法.其余算法类似。 Status Insert_Arc(ALGraph G,char v,char w)// 在邻接表表示的图 G 上插入边(v,w) { if((iLocateVex(G,v))0) return ERROR; if((jLocateVex(G,w))0) return ERROR; pnew ArcNode; p- adjvexj;p-nextarcNULL; if(!G.vertices.firstarc) G.vertices.firstarcp; else { for(qG.vertices.firstarc;q-q-nextarc;qq-nextarc) if(q-adjvexj) return ERROR; //边已经存在 q- nextarcp; } G.arcnum; return OK; }//Insert_Arc 2 一个连通图采用邻接表作为存储结构设计一个算法实现从顶点 v 出发的深度优先遍历的非递归过程。 [算法描述] Void DFSn(Graph G,int v) { //从第 v 个顶点出发非递归实现深度优先遍历图 G Stack s; SetEmpty(s); Push(s,v); While(!StackEmpty(s)) { //栈空时第 v 个顶点所在的连通分量已遍历完 Pop(s,k); If(!visited[k]) { visited[k]TRUE; VisitFunc(k); //访问第 k 个顶点 //将第 k 个顶点的所有邻接点进栈 for(wFirstAdjVex(G,k);w;wNextAdjVex(G,k,w)) { if(!visited[w]w!GetTop(s)) Push(s,w); // 图中有环时 wGetTop(s) } } } 3 设计一个算法 求图 G 中距离顶点 v 的最短路径长度最大的一个顶点设 v 可达其余各个顶点。 [题目分析] 利用 Dijkstra 算法求 v0 到其它所有顶点的最短路径分别保存在数组 D[i]中然后求出 D[i]中值最大的数组下标 m 即可。 [算法描述] int ShortestPath_MAX(AMGraph G, int v0){ //用 Dijkstra 算法求距离顶点 v0 的最短路径长度最大的一个顶点 m nG.vexnum; //n 为 G 中顶点的个数 for(v 0; vn; v){ //n 个顶点依次初始化 S[v] false; //S 初始为空集 D[v] G.arcs[v0][v]; //将 v0 到各个终点的最短路径长度初始化 if(D[v] MaxInt) else Path [v]-1; Path [v]v0; //如果 v0 和 v 之间有弧则将 v 的前驱置为 v0 //如果 v0 和 v 之间无弧则将 v 的前驱置为-1 }//for S[v0]true; //将 v0 加入 S D[v0]0; //源点到源点的距离为 0 /*开始主循环每次求得 v0 到某个顶点 v 的最短路径将 v 加到 S 集*/ for(i1;in; i){ //对其余 n−1 个顶点依次进行计算 min MaxInt; for(w0;wn; w) if(!S[w]D[w]min) {vw; minD[w];} //选择一条当前的最短路径终点为 v S[v]true; //将 v 加入 S for(w0;wn; w) //更新从 v0 到 V−S 上所有顶点的最短路径长度 if(!S[w](D[v]G.arcs[v][w]D[w])){ D[w]D[v]G.arcs[v][w]; //更新 D[w] Path [w]v; //更改 w 的前驱为 v }//if }//for /*最短路径求解完毕设距离顶点 v0 的最短路径长度最大的一个顶点为 m */ MaxD[0]; m0; for(i1;in;i) if(MaxD[i]) mi; return m; } 4 试基于图的深度优先搜索策略写一算法判别以邻接表方式存储的有向图中是否存在由顶点 vi 到顶点 vj 的路径i≠j。 [题目分析] 引入一变量 level 来控制递归进行的层数 [算法描述] int visited[MAXSIZE]; //指示顶点是否在当前路径上 int level1;//递归进行的层数 int exist_path_DFS(ALGraph G,int i,int j)// 深度优先判断有向图 G 中顶点 i 到顶点 j 是否有路径,是则返回 1,否则返回 0 { if(ij) return 1; //i 就是 j else { visited[i]1; for(pG.vertices[i].firstarc;p;pp-nextarclevel--) { level; kp-adjvex; if(!visited[k]exist_path(k,j)) return 1;//i 下游的顶点到 j 有路径 }//for }//else if (level1) return 0; }//exist_path_DFS 5 采用邻接表存储结构编写一个算法判别无向图中任意给定的两个顶点之间是否存在一条长度为为 k 的简单路径。 [算法描述] int visited[MAXSIZE]; int exist_path_len(ALGraph G,int i,int j,int k) //判断邻接表方式存储的有向图 G 的顶点 i 到 j 是否存在长度为 k 的简单路径 {if(ijk0) return 1; //找到了一条路径,且长度符合要求 else if(k0) {visited[i]1; for(pG.vertices[i].firstarc;p;pp-nextarc) {lp-adjvex; if(!visited[l]) if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for visited[i]0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else return 0; //没找到 }//exist_path_len 第 7 章 查找 1. 选择题 1 对 n 个元素的表做顺序查找时 若查找每个元素的概率相同则平均查找长度为 。 A(n-1)/2 B n/2 C(n1)/2 D n 答案C 解释总查找次数 N123…nn(n1)/2则平均查找长度为 N/n(n1)/2。 2 适用于折半查找的表的存储方式及元素排列要求为 。 A链接方式存储元素无序 B链接方式存储元素有序 C顺序方式存储元素无序 D顺序方式存储元素有序答案D 解释折半查找要求线性表必须采用顺序存储结构而且表中元素按关键字有序排列。 如果要求一个线性表既能较快的查找又能适应动态变化的要求最好采用( ) 查找法。 A. 顺序查找 B折半查找 C分块查找 D哈希查找 答案C 解释分块查找的优点是在表中插入和删除数据元素时只要找到该元素对应的块就可以在该块内进行插入和删除运算。由于块内是无序的故插入和删除比较容易无需进行大量移动。如果线性表既要快速查找又经常动态变化则可采用分块查找。 4 折半查找有序表 4 61012 20 305070 88100。若查找表中元素 58则它将依次与表中 比较大小查找结果是失败。 A. 0703050 B30887050 C2050 D308850 答案A 解释表中共 10 个元素第一次取ë(110)/2û5与第五个元素 20 比较58 大于 20再取ë(610)/2û8与第八个元素70 比较依次类推再与 30、50 比较最终查找失败。 5 对 22 个记录的有序表作折半查找当查找失败时至少需要比较 次关键字。 A3 B4 C5 D6 答案B 解释22 个记录的有序表其折半查找的判定树深度为 ëlog222û 15且该判定树不是满二叉树即查找失败时至多比较 5 次至少比较 4 次。 6 折半搜索与二叉排序树的时间性能 。 A. 相同 B完全不同 C有时不相同 D数量级都是 O(log2n) 答案C 7 分别以下列序列构造二叉排序树与用其它三个序列所构造的结果不同的是 。 A10080 90 60 120110130 B10012011013080 60 90C10060 80 90 120110130 D(10080 60 90 120130110) 答案C 解释A、B、C、D 四个选项构造二叉排序树都以 100 为根易知 A、B、D 三个序列中第一个比 100 小的关键字为80即 100 的左孩子为 80而 C 选项中 100 的左孩子为 60故选 C。 8 在平衡二叉树中插入一个结点后造成了不平衡设最低的不平衡结点为 A并已知 A 的左孩子的平衡因子为 0 右孩子的平衡因子为 1则应作 型调整以使其平衡。 ALL BLR CRL DRR 答案C 9 下列关于 m 阶 B-树的说法错误的是 。 A根结点至多有 m 棵子树 B所有叶子都在同一层次上 C非叶结点至少有 m/2 (m 为偶数)或 m/21m 为奇数棵子树 D根结点中的数据是有序的答案D 10 下面关于 B-和 B树的叙述中不正确的是 。 AB-树和 B树都是平衡的多叉树 BB-树和 B树都可用于文件的索引结构 CB-树和 B树都能有效地支持顺序检索 DB-树和 B树都能有效地支持随机检索答案C 11m 阶 B-树是一棵 。 Am 叉排序树 Bm 叉平衡排序树 Cm-1 叉平衡排序树 Dm1 叉平衡排序树答案B 下面关于哈希查找的说法正确的是 。 哈希函数构造的越复杂越好因为这样随机性好冲突小除留余数法是所有哈希函数中最好的不存在特别好与坏的哈希函数要视情况而定 D哈希表的平均查找长度有时也和记录总数有关答案C下面关于哈希查找的说法不正确的是 。 A. 采用链地址法处理冲突时查找一个元素的时间是相同的 B. 采用链地址法处理冲突时若插入规定总是在链首则插入任一个元素的时间是相 同的 C. 用链地址法处理冲突不会引起二次聚集现象 D. 用链地址法处理冲突适合表长不确定的情况答案A 解释在同义词构成的单链表中查找该单链表表中不同元素所消耗的时间不同。 14 设哈希表长为 14哈希函数是 H(key)key%11表中已有数据的关键字为 1538 6184 共四个现要将关键字为 49 的元素加到表中用二次探测法解决冲突则放入的位置是 。 A8 B3 C5 D9 答案D 解释关键字 15 放入位置 4关键字 38 放入位置 5关键字 61 放入位置 6关键字 84放入位置 7再添加关键字 49计算得到地址为 5冲突用二次探测法解决冲突得到新地址为 6仍冲突再用用二次探测法解决冲突得到新地址为 4仍冲突再用用二次探测法解决冲突得到新地址为 9不冲突即将关键字 49 放入位置 9。 采用线性探测法处理冲突可能要探测多个位置在查找成功的情况下所探测的这些位置上的关键字 ( )。 A. 不一定都是同义词 B一定都是同义词 C一定都不是同义词 D都相同答案A 解释所探测的这些关键字可能是在处理其它关键字冲突过程中放入该位置的。 应用题 1假定对有序表 34572430425463728795 进行折半查找试回答下列问题 ① 画出描述折半查找过程的判定树 ② 若查找元素 54需依次与哪些元素比较 ③ 若查找元素 90需依次与哪些元素比较 ④ 假定每个元素的查找概率相等求查找成功时的平均查找长度。答案 ① 先画出判定树如下注midë(112)/2û6 30 5 63 3 7 42 87 4 24 54 72 95 ② 查找元素 54需依次与 30, 63, 42, 54 元素比较 ③ 查找元素 90需依次与 30, 63,87, 95 元素比较 ④ 求 ASL 之前需要统计每个元素的查找次数。判定树的前 3 层共查找 12×24× 317 次 但最后一层未满不能用 8×4只能用 5×420 次 所以 ASL1/12172037/12≈3.08 在一棵空的二叉排序树中依次插入关键字序列为 127 1711162139 214 请画出所得到的二叉排序树。 答案 12 7 17 2 11 16 21 4 9 13 验算方法 用中序遍历应得到排序结果2,4,7,9,11,12,13,16,17,21 已知如下所示长度为 12 的表 Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec ① 试按表中元素的顺序依次插入一棵初始为空的二叉排序树画出插入完成之后的二叉排序树并求其在等概率的情况下查找成功的平均查找长度。 ② 若对表中元素先进行排序构成有序表求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 ③ 按表中元素顺序构造一棵平衡二叉排序树并求其在等概率的情况下查找成功的平均查找长度。 答案 对图 7.31 所示的 3 阶 B-树依次执行下列操作画出各步操作的结果。 ① 插入 90 ② 插入 25 ③ 插入 45 ④ 删除 60 图 7.31 3 阶 B-树 设哈希表的地址范围为 017哈希函数为H keykey%16。用线性探测法处理冲突输入关键字序列 1024321731304647406349构造哈希表试回答下列问题 ① 画出哈希表的示意图 ② 若查找关键字 63需要依次与哪些关键字进行比较 ③ 若查找关键字 60需要依次与哪些关键字比较 ④ 假定每个关键字的查找概率相等求查找成功时的平均查找长度。答案 ① 画表如下 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 ② 查找 63,首先要与 H(63)63%1615 号单元内容比较即 63 与 31 比较 ,不匹配;然后顺移与 46,47,32,17,63 相比一共比较了 6 次 ③ 查找 60,首先要与 H(60)60%1612 号单元内容比较但因为 12 号单元为空应当有空标记所以应当只比较这一次即可。 ④ 对于黑色数据元素各比较 1 次共 6 次 对红色元素则各不相同要统计移位的位数。“63”需要 6 次“49”需要 3 次“40”需要 2 次“46”需要 3 次“47”需要 3 次 所以 ASL1/11623×3623/11 设有一组关键字 901231455208427采用哈希函数Hkeykey %7 表长为 10用开放地址法的二次探测法处理冲突。要求对该关键字序列构造哈希表并计算查找成功的平均查找长度。 答案 散列地址 0 1 2 3 4 5 6 7 8 9 关键字 14 1 9 23 84 27 55 20 比较次数 1 1 1 2 3 4 1 2 平均查找长度ASLsucc11123412/815/8 以关键字 27 为例H2727%76冲突 H161%107冲突 H2622 %100冲突H3633 %105 所以比较了 4 次。 设哈希函数 HK3 K mod 11哈希地址空间为 010对关键字序列3213 49243821412按下述两种解决冲突的方法构造哈希表并分别求出等概率下查找成功时和查找失败时的平均查找长度 ASLsucc 和 ASLunsucc。 ① 线性探测法 ② 链地址法。答案 ① 散列地址 0 1 2 3 4 5 6 7 8 9 10 关键字 4 12 49 38 13 24 32 21 比较次数 1 1 1 2 1 2 1 2 ASLsucc 11121212/811/8 ASLunsucc12187654321/1140/11 ② ASLsucc 1*52*3/811/8 ASLunsucc12123131311/1119/11 3. 算法设计题 1 试写出折半查找的递归算法。 [算法描述] int BinSrchrectype r[ ]int klowhigh //在长为 n 的有序表中查找关键字 k若查找成功返回 k 所在位置查找失败返回 0。 {iflow≤high //low 和 high 分别是有序表的下界和上界 {midlowhigh/2 ifr[mid].keykreturn mid else ifr[mid].keykreturn BinSrchr,kmid1high; else return BinSrchr,klowmid-1; } else return 0//查找失败。 }//算法结束 试写一个判别给定二叉树是否为二叉排序树的算法。 [题目分析] 根据二叉排序树中序遍历所得结点值为增序的性质在遍历中将当前遍历结点与其前驱结点值比较即可得出结论为此设全局指针变量 pre初值为 null和全局变量 flag初值为 true。若非二叉排序树则置 flag 为 false。 [算法描述] #define true 1 #define false 0 typedef struct node {datatype data; struct node *lchild,*rchild;} *BTree; void JudgeBSTBTree T,int flag // 判断二叉树是否是二叉排序树本算法结束后在调用程序中由 flag 得出结论。 { ifT!null flag { JudgebstT-lchild,flag// 中序遍历左子树 ifprenullpreT// 中序遍历的第一个结点不必判断 else ifpre-dataT-datapreT//前驱指针指向当前结点 else{flagflase} //不是完全二叉树 Judgebst T-rchild,flag// 中序遍历右子树 }//JudgeBST 算法结束 3 已知二叉排序树采用二叉链表存储结构 根结点的指针为 T 链结点的结构为 lchild,data,rchild其中 lchildrchild 分别指向该结点左、右孩子的指针data 域存放结点的数据信息。请写出递归算法从小到大输出二叉排序树中所有数据值x 的结点的数据。要求先找到第一个满足条件的结点后再依次输出其他满足条件的结点。 [题目分析]本题算法之一是如上题一样中序遍历二叉树在“访问根结点”处判断结点值是否≥x如是则输出并记住第一个≥x 值结点的指针。这里给出另一个算法利用二叉排序树的性质如果根结点的值x,则除左分枝中可能有x 的结点外都应输出。所以从根结点开始查找找到结点值x 的结点后将其与双亲断开输出整棵二叉排序树。如果根结点的值x,则沿右子树查找第一个≥x 的结点找到后与上面同样处理。 void PrintBSTree t // 中序输出以 t 为根的二叉排序树的结点 {ift{Printt-lchild Coutt-data Printt-rchild } } void PrintAllx(BSTree bstdatatype x //在二叉排序树 bst 中查找值≥x 的结点并输出 {pbst ifp {whilep p-dataxpp-rchild//沿右分枝找第一个值≥x 的结点 bstp; //bst 所指结点是值≥x 的结点的树的根 ifp {fp; pp-lchild //找第一个值x 的结点 whilep p-data≥x//沿左分枝向下找第一个值x 的结点 {fppp-lchild } //f 是 p 的双亲结点的指针 指向第一个值≥x 的结点 if(p) f-lchildnull; //双亲与找到的第一个值x 的结点断开 Print(bst)//输出以 bst 为根的子树 }//while }//内层 ifp }//第一层 ifp }//PrintAllx 已知二叉树 T 的结点形式为lling,data,count,rlink在树中查找值为 X 的结点若找到则记数count加 1否则作为一个新结点插入树中插入后仍为二叉排序树写出其非递归算法。 [算法描述] void SearchBST(BiTree T,int target){ BiTree s,q,f; //以数据值 target,新建结点 s snew BiTNode; s-data.xtarget; s-data.count0; s-lchilds-rchildNULL; if(!T){ Ts; return ; } //如果该树为空则跳出该函数 fNULL; qT; while (q){ if (q-data.xtarget){ q-data.count; return ; } //如果找到该值则计数加一 fq; if (q-data.xtarget) //如果查找值比目标值大则为该树左孩子 qq-lchild; else //否则为右孩子 qq-rchild; } //将新结点插入树中 if(f-data.xtarget) f-lchilds; else } f-rchilds; 5 假设一棵平衡二叉树的每个结点都表明了平衡因子 b试设计一个算法求平衡二叉树的高度。 [题目分析] 因为二叉树各结点已标明了平衡因子 b故从根结点开始记树的层次。根结 点的层次为 1每下一层层次加 1直到层数最大的叶子结点这就是平衡二叉树的高度。当结点的平衡因子 b 为 0 时任选左右一分枝向下查找若 b 不为 0则沿左当 b1 时或右当 b-1 时向下查找。 [算法描述] int HeightBSTree t // 求平衡二叉树 t 的高度 {level0pt whilep {level // 树的高度增 1 ifp-bf0pp-rchild//bf-1 沿右分枝向下 //bf 是平衡因子是二叉树 t 结点的一个域因篇幅所限没有写出其存储定义 else pp-lchild //bf0 沿左分枝向下 }//while return level//平衡二叉树的高度 } //算法结束 6 分别写出在散列表中插入和删除关键字为 K 的一个记录的算法设散列函数为 H解决冲突的方法为链地址法。 [算法描述] bool insert(){ int data; cindata; int anthash(data); LinkList pHT[ant]; //初始化散列表 while (p-next){ if(p-next-datadata) return false; pp-next; } //找到插入位置 LinkList s; snew LNode; s-datadata; s-nextp-next; p-nexts; //插入该结点 return true; } bool deletes(){ int data; cindata; int anthash(data); LinkList pHT[ant]; //初始化散列表 while (p-next){ if(p-next-datadata){ LinkList sp-next; p-nexts-next; delete s; //删除该结点 return true; } //找到删除位置 pp-next //遍历下一个结点 } return false; } 第 8 章 排序 1. 选择题 1 从未排序序列中依次取出元素与已排序序列中的元素进行比较将其放入已排序序列的正确位置上的方法这种排序方法称为 。 A. 归并排序 B冒泡排序 C插入排序 D选择排序答案C 2 从未排序序列中挑选元素并将其依次放入已排序序列初始时为空的一端的方法称为 。 A. 归并排序 B冒泡排序 C插入排序 D选择排序答案D 3 对 n 个不同的关键字由小到大进行冒泡排序在下列 情况下比较的次数最多。 A. 从小到大排列好的 B从大到小排列好的 C元素无序 D元素基本有序答案B 解释对关键字进行冒泡排序关键字逆序时比较次数最多。 4 对 n 个不同的排序码进行冒泡排序在元素无序的情况下比较的次数最多为 。 A. n1 Bn Cn-1 Dn(n-1)/2 答案D 解释比较次数最多时第一次比较 n-1 次第二次比较 n-2 次……最后一次比较 1 次即(n-1)(n-2)…1 n(n-1)/2。 5 快速排序在下列 情况下最易发挥其长处。 A被排序的数据中含有多个相同排序码 B被排序的数据已基本有序 C被排序的数据完全无序 D被排序的数据中的最大值和最小值相差悬殊 答案C 解释B 选项是快速排序的最坏情况。 对 n 个关键字作快速排序在最坏情况下算法的时间复杂度是 。 AO(n) BO(n2) CO(nlog2n)DO(n3)答案B 解释快速排序的平均时间复杂度为 O(nlog2n)但在最坏情况下即关键字基本排好序的情况下时间复杂度为O(n2)。 若一组记录的排序码为46, 7956384084则利用快速排序的方法以第一个记录为基准得到的一次划分结果为 。 A. 84046567984 B403846795684 C403846567984 D403846845679 答案C 8 下列关键字序列中 是堆。 A. 67231239453 B942331721653 C165323943172 D162353319472 答案D 解释D 选项为小根堆 9堆是一种 排序。 A插入 B选择 C交换 D归并 答案B 10堆的形状是一棵 。 A二叉排序树 B满二叉树 C完全二叉树 D平衡二叉树 答案C 11 若一组记录的排序码为467956384084则利用堆排序的方法建立的初始堆为 。 A. 94656384084 B847956384046 C847956464038 D845679404638 答案B 12 下述几种排序方法中要求内存最大的是 。 A. 希尔排序 B快速排序 C归并排序 D堆排序答案C 解释堆排序、希尔排序的空间复杂度为 O(1)快速排序的空间复杂度为 O(log2n)归并排序的空间复杂度为 O(n)。 13 下述几种排序方法中 是稳定的排序方法。 A. 希尔排序 B快速排序 C归并排序 D堆排序答案C 解释不稳定排序有希尔排序、简单选择排序、快速排序、堆排序稳定排序有直接插入排序、折半插入排序、冒泡排序、归并排序、基数排序。 14 数据表中有 10000 个元素如果仅要求求出其中最大的 10 个元素则采用( ) 算法最节省时间。 A. 冒泡排序 B快速排序 C简单选择排序 D堆排序答案D 15 下列排序算法中 不能保证每趟排序至少能将一个元素放到其最终的位置上。 A. 希尔排序 B快速排序 C冒泡排序 D堆排序答案A 解释快速排序的每趟排序能将作为枢轴的元素放到最终位置冒泡排序的每趟排序 能将最大或最小的元素放到最终位置堆排序的每趟排序能将最大或最小的元素放到最终位置。 2. 应用题 1设待排序的关键字序列为{1221630 281016*20618}试分别写出使用以下排序方法每趟排序结束后关键字序列的状态。 ① 直接插入排序 ② 折半插入排序 ③ 希尔排序增量选取 531 ④ 冒泡排序 ⑤ 快速排序 ⑥ 简单选择排序 ⑦ 堆排序 ⑧ 二路归并排序答案 ①直接插入排序 [2 12] 16 30 28 10 16* 20 6 18 [2 12 16] 30 28 10 16 * 20 6 18 [2 12 16 30] 28 10 16 * 20 6 18 [2 12 16 28 30] 10 16 * 20 6 18 [2 10 12 16 28 30] 16* 20 6 18 [2 10 12 16 16* 28 30] 20 6 18 [2 10 12 16 16* 20 28 30] 6 18 [2 6 10 12 16 16 * 20 28 30] 18 [2 6 10 12 16 16 * 18 20 28 30] ② 折半插入排序 排序过程同① ③ 希尔排序增量选取 531 10 2 16 6 18 12 16 * 20 30 28 增量选取 5 6 2 12 10 18 16 16 * 20 30 28 增量选取 3 2 6 10 12 16 16 * 18 20 28 30 增量选取 1 ④ 冒泡排序 2 12 16 28 10 16 * 20 6 18 [30] 2 12 16 10 16* 20 6 18 [28 30] 2 12 10 16 16* 6 18 [20 28 30] 2 10 12 16 6 16 * [18 20 28 30] 2 10 12 6 16 [16* 18 20 28 30] 2 10 6 12 [16 16 * 18 20 28 30] 2 6 10 [12 16 16 * 18 20 28 30] 2 6 10 12 16 16 * 18 20 28 30] ⑤ 快速排序 12 [6 2 10] 12 [28 30 16* 20 16 18] 6 [2] 6 [10] 12 [28 30 16* 20 16 18 ] 28 2 6 10 12 [18 16 16* 20 ] 28 [30 ] 18 2 6 10 12 [16* 16] 18 [20] 28 30 16* 2 6 10 12 16* [16] 18 20 28 30 左子序列递归深度为 1右子序列递归深度为 3 ⑥ 简单选择排序 2 [12 16 30 28 10 16 * 20 6 18] 2 6 [16 30 28 10 16 * 20 12 18] 2 6 10 [30 28 16 16 * 20 12 18] 2 6 10 12 [28 16 16 * 20 30 18] 2 6 10 12 16 [28 16 * 20 30 18] 2 6 10 12 16 16 * [28 20 30 18] 2 6 10 12 16 16 * 18 [20 30 28] 2 6 10 12 16 16* 18 20 [28 30] 2 6 10 12 16 16 * 18 20 28 [30] ⑧ 二路归并排序 2 12 16 30 10 28 16 * 20 6 18 2 12 16 30 10 16* 20 28 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 18 20 28 30 2给出如下关键字序列 3211565746287331333463试按链式基数排序方法列出每一趟分配和收集的过程。 答案 按最低位优先法 →321→156→57→46→28→7→331→33→34→63 分配 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 321 33 34 156 57 28 331 63 46 7 收集 →321→331→33→63→34→156→46→57→7→28 3对输入文件101511961371311719100552093050 690当 k6 时使用置换-选择算法写出建立的初始败者树及生成的初始归并段。 答案 初始败者树 初始归并段R1:3,19,31,51,61,71,100,101 R2:9,17,19,20,30,50,55,90 R3:6 3. 算法设计题 1 试以单链表为存储结构实现简单选择排序算法。 [算法描述] void LinkedListSelectSort(LinkedList head) //本算法一趟找出一个关键字最小的结点其数据和当前结点进行交换;若要交换指针则须记下 //当前结点和最小结点的前驱指针 phead-next; while(p!null) {qp-next; rp; //设 r 是指向关键字最小的结点的指针 while (q!null) {if(q-datar-data) rq; q:q-next; } if(r!p) r-data--p-data; pp-next; } 2 有 n 个记录存储在带头结点的双向链表中现用双向冒泡排序法对其按上升序进行排序请写出这种排序的算法。注双向冒泡排序即相邻两趟排序向相反方向冒泡。 [算法描述] typedef struct node { ElemType data; struct node *prior,*next; }node*DLinkedList; void TwoWayBubbleSort(DLinkedList la) //对存储在带头结点的双向链表 la 中的元素进行双向起泡排序。 {int exchange1; // 设标记 DLinkedList p,temp,tail; headla //双向链表头算法过程中是向下起泡的开始结点 tailnull; //双向链表尾算法过程中是向上起泡的开始结点 while (exchange) {phead-next; //p 是工作指针指向当前结点 exchange0; //假定本趟无交换 while (p-next!tail) // 向下右起泡一趟有一最大元素沉底 if (p-datap-next-data) //交换两结点指针涉及 6 条链 {tempp-next; exchange1;//有交换 p-nexttemp-next;temp-next-priorp //先将结点从链表上摘下 temp-nextp; p-prior-nexttemp; //将 temp 插到 p 结点前 temp-priorp-prior; p-priortemp; } else pp-next; //无交换指针后移 tailp; //准备向上起泡 ptail-prior; while (exchange p-prior!head) //向上左起泡一趟有一最小元素冒出 if (p-datap-prior-data) //交换两结点指针涉及 6 条链 {tempp-prior; exchange1; //有交换 p-priortemp-prior;temp-prior-nextp //先将 temp 结点从链表上摘下 temp-priorp; p-next-priortemp; //将 temp 插到 p 结点后右 temp-nextp-next; p-nexttemp; } else pp-prior; //无交换指针前移 headp; //准备向下起泡 }// while (exchange) } //算法结束 设有顺序放置的 n 个桶每个桶中装有一粒砾石每粒砾石的颜色是红白蓝之一。要求重新安排这些砾石使得所有红色砾石在前所有白色砾石居中所有蓝色砾石居后重新安排时对每粒砾石的颜色只能看一次并且只允许交换操作来调整砾石的位置。 [题目分析]利用快速排序思想解决。由于要求“ 对每粒砾石的颜色只能看一次” 设 3个指针 ij 和 k分别指向红色、白色砾石的后一位置和待处理的当前元素。从 kn 开始从右向左搜索若该元素是兰色则元素不动指针左移即 k-1若当前元素是红色砾石分 ij这时尚没有白色砾石和 ij 两种情况。前一情况执行第 i 个元素和第 k 个元素交换之后 i1后一情况i 所指的元素已处理过白色j 所指的元素尚未处理应先将 i和 j 所指元素交换再将 i 和 k 所指元素交换。对当前元素是白色砾石的情况也可类似处理。 为方便处理将三种砾石的颜色用整数 1、2 和 3 表示。 [算法描述] void QkSort(rectype r[],int n) { // r 为含有 n 个元素的线性表元素是具有红、白和兰色的砾石用顺序存储结构存 储 //本算法对其排序使所有红色砾石在前白色居中兰色在最后。 int i1,j1,kn,temp; while (k!j){ while (r[k].key3) k--;// 当前元素是兰色砾石指针左移 if (r[k].key1) // 当前元素是红色砾石 if (ij){tempr[k];r[k]r[i];r[i]temp; i;} //左侧只有红色砾石交换 r[k]和 r[i] else{tempr[j];r[j]r[i];r[i]temp; j; //左侧已有红色和白色砾石先交换白色砾石到位 tempr[k];r[k]r[i];r[i]temp; i; //白色砾石i 所指和待定砾石j 所指 } //再交换 r[k]和 r[i]使红色砾石入位。 if (r[k].key2) if (ij) { tempr[k];r[k]r[j];r[j]temp; j;} // 左侧已有白色砾石交换 r[k]和 r[j] else{ tempr[k];r[k]r[i];r[i]temp; ji1;} //i、j 分别指向红、白色砾石的后一位置 }//while if (r[k]2) j; /* 处理最后一粒砾石 else if (r[k]1) { tempr[j];r[j]r[i];r[i]temp; i; j; } //最后红、白、兰色砾石的个数分别为: i-1;j-i;n-j1 }//结束 QkSor 算法 [算法讨论]若将 j上面指向白色看作工作指针将 r[1..j-1]作为红色r[j..k-1]为白色r[k..n]为兰色。从 j1 开始查看若 r[j]为白色则 jj1若 r[j]为红色则交换 r[j]与 r[i]且 jj1ii1若 r[j]为兰色则交换 r[j]与 r[k];kk-1。算法进行到 jk 为止。 算法片段如下 int i1,j1,kn; while(jk) if (r[j]1) //当前元素是红色 {tempr[i]; r[i]r[j]; r[j]temp; i;j; } else if (r[j]2) j; //当前元素是白色 else //(r[j]3 当前元素是兰色 {tempr[j]; r[j]r[k]; r[k]temp; k--; } 对比两种算法可以看出正确选择变量指针的重要性。 4 编写算法对 n 个关键字取整数值的记录序列进行整理以使所有关键字为负值的记录排在关键字为非负值的记录之前要求 ① 采用顺序存储结构至多使用一个记录的辅助存储空间 ② 算法的时间复杂度为 O(n)。 [算法描述] void process (int A[n]){ low 0; high n-1; while ( lowhigh ){ while (lowhigh A[low]0) low; while (lowhigh A[high]0) high; if (lowhigh){ xA[low]; A[low]A[high]; A[high]x; low; high--; } } return; } 5 借助于快速排序的算法思想在一组无序的记录中查找给定关键字值等于 key 的记录。设此组记录存放于数组r[l..n]中。若查找成功则输出该记录在 r 数组中的位置及其值否则显示“not find”信息。请简要说明算法思想并编写算法。 [题目分析]把待查记录看作枢轴先由后向前依次比较若小于枢轴则从前向后直到查找成功返回其位置或失败返回 0 为止。 [算法描述] int index (RecType R[],int l,h,datatype key) {int il,jh; while (ij) { while (ij R[j].keykey) j--; if (R[j].keykey) return j; while (ij R[i].keykey) i; if (R[i].keykey) return i; } cout“Not find”; return 0; }//index 有一种简单的排序算法 叫做计数排序。这种排序算法对一个待排序的表进行排序并将排序结果存放到另一个新的表中。必须注意的是表中所有待排序的关键字互不相同计数排序算法针对表中的每个记录扫描待排序的表一趟统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录统计出的计数值为 c那么这个记录在新的有序表中的合适的存放位置即为 c。 ① 给出适用于计数排序的顺序表定义 ② 编写实现计数排序的算法 ③ 对于有 n 个记录的表关键字比较次数是多少 ④ 与简单选择排序相比较这种方法是否更好为什么 [算法描述] ① typedef struct {int key; datatype info }RecType ② void CountSort(RecType a[],b[],int n) //计数排序算法将 a 中记录排序放入 b 中 {for(i0;in;i) //对每一个元素 {for(j0,cnt0;jn;j) if(a[j].keya[i].key) cnt; //统计关键字比它小的元素个数 b[cnt]a[i]; }
}//Count_Sort
③ 对于有 n 个记录的表关键码比较 n2 次。
④ 简单选择排序算法比本算法好。简单选择排序比较次数是 n(n-1)/2,且只用一个交换记录的空间而这种方法比较次数是 n2 且需要另一数组空间。
[算法讨论]因题目要求“针对表中的每个记录扫描待排序的表一趟”所以比较次数是 n2 次。若限制“对任意两个记录之间应该只进行一次比较”则可把以上算法中的比较语句改为
for(i0;in;i) a[i].count0;//各元素再增加一个计数域初始化为 0 for(i0;in;i)
for(ji1;jn;j)
if(a[i].keya[j].key) a[j].count; else a[i].count;
