成人函授教育

成人函授教育 《数据结构》自学指导书 适用计算机专业、本(专)科 黑龙江科技学院成教院 目 录 „„„„„„„„„„„„„„„„„„„„„2 一、前 言 二、自学指导„„„„„„„„„„„„„„„„„„„„3 三、各章节自学参考„„„„„„„„„„„„„„„„„4 第一章 数据结构基本概念及简单的算法分析 „„„„4 第二章 线性表 „„„„„„„„„„„„„„„„„5 第三章 栈和队列„„„„„„„„„„„„„„„„10 第四章 串„„„„„„„„„„„„„„„„„„„11 第五章 数组和广义表„„„„„„„„„„„„„„12 第六章 树和二叉树„„„„„„„„„„„„„„„13 第七章 图„„„„„„„„„„„„„„„„„„„17 第八章 查找„„„„„„„„„„„„„„„„„„19 第九章 排序„„„„„„„„„„„„„„„„„„22 四、期末考试试类型说明„„„„„„„„„„„„„..34 1 一、前言 1、本课程的性质和任务 《数据结构》课程是计算机专业的一门专业基础课。它涉及在计算机中如何有效地表示数据，如何合理地组织数据和处理数据。内容包括:线性表、链表、栈和队列、串、数组和广义表，树和二叉树、图、查找、排序等。还涉及初步的算法和算法性能分析技术。学好数据结构课程，将为后续的专业课程，如数据库系统、操作系统、编译原理等，打下良好的知识基础，而且还为软件开发和程序设计提供了必要的技能训练。本课程学员对计算机的组成有基本的了解，对程序设计有一定基础，对c语言编程，有一定的了解。对涉及离散数学的知识，如表、树、图、集合等，有初步的了解。事实上，课程讲授中将会简单地补充这些方面的内容。 2、本课程的自学方法 (1) 考虑到函授学员的特点，对数据结构及算法设计的要求不能象本科生那样。因此，课程教学重点是介绍各种常用的数据结构及其实现。在每节授课过程中，首先提示本节应掌握的概念，再给出结构的类(抽象数据类型)定义和主要操作的实现。在讨论算法时主要给出算法实现的思路，以及算法实现的框架。在每一节最后，对讨论过的内容做一小结，提示本节的要点及容易出错的地方。使学员能够切实掌握每一种数据结构的特点和实现。 (2) 按照《数据结构》课程教学大纲的要求，课程的讲授将从面向过程的概念、数据结构的层次开始。从线性结构到非线性结构，从简单到复杂，循序渐进，逐步深入。 (3) 学好一门课程，教师的引导固然十分重要，但主要靠学员的自身努力。课堂教学可以起到画龙点睛的作用，但只有不断练习，才能巩固、掌握课程的内容。因此，本课程要求学员积极独立完成所布置的习题。 3、主要教学环节 考试说明: (1) 在教学大纲和考核说明所规定的知识范围内命题。在教学知识范围之内，需要灵活运用才能够解决问题的试题不属于超纲。 (2) 试题的考察要求覆盖面广、区分度高。 2 (3) 试题兼顾各个能力层次，理解占40%，简单运用占40%，综合运用占20%。 (4) 试题的难易程度和题量适当，按难易程度分为四个层次:容易占 ，较易占35%，较难占25%，难占15%。题量安排以平时能够独立完成25% 作业者，使他们能在规定的考试时间内做完并有一定时间检查为原则。 本课程使用的教材为《数据结构——C语言描述》，本教材充分起到了自学、助学和导学作用，系统地、完整地介绍各种数据结构的特点、实现及应用。教材为: 《数据结构——C语言描述》 耿国华等编著;西安电子科技大学出版社，2002年2月出版。 适用专业层次:本科。 二、自学进度表 自 学 进 度 要 求 面授 备注 周次 自学 时数 预习重点 自学各章节内容 日期 时数 第一章 绪论 作业 线性表 1 第二章 线性表 7 7 2.2、2.3、栈和队列 第三章 栈和队列 3.1、3.2 串 第四章 串 作业 2 4 4 数组和广义表 第五章 数组和广义表 4.4 3 树和二叉树 第六章 树和二叉树 4 4 6.9、6.11 4 图 第七章 图 7.1-7.4 3 3 7.1、7.3 图 第七章 图 7.5-7.6 7.6、 5 3 3 查找 第八章 查找8.1-8.2 8.2、8.4 6 查找 第八章 查找8.3-8.4 3 3 8.5、8.11 7 内部排序 第九章 内部排序 3 3 9.1、9.2 内部排序 第九章 内部排序 9.7、9.18 8 3 3 外部排序 第十章 外部排序 10.5 3 三、主要章节指导及说明 第一章 数据结构基本概念及简单的算法分析 1、教学内容: 什么是数据结构; 抽象数据类型及面向对象概念:数据类型;数据抽象与抽象数据类型;面向过程的概念;用于描述数据结构的语言; 数据结构的抽象层次; 算法定义; 性能分析与度量:算法的性能标准;空间复杂度度量;时间复杂度度量; 2、教学要求: 了解:什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系; 了解:什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。 了解:算法的定义、算法的特性、算法的时间代价、算法的空间代价 掌握:用C语言描述算法的方法; 3、习题与解答: (1)、什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为:数据结构 = { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容: ? 数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构， 简称为数据结构; ? 数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构; ? 施加于该数据结构上的操作。 (2)、什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。 4 【解答】 通常，定义算法为“为解决某一特定任务而规定的一个指令序列。”一个算法应当具有以下特性: 有输入。一个算法必须有0个或多个输入。它们是算法开始运算前 ? 给予算法的量。这些输入取自于特定的对象的集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法内给定。 ? 有输出。一个算法应有一个或多个输出，输出的量是算法计算的结果。 ? 确定性。算法的每一步都应确切地、无歧义地定义。对于每一种情况，需要执行的动作都应严格地、清晰地规定。 ? 有穷性。一个算法无论在什么情况下都应在执行有穷步后结束。 ? 有效性。算法中每一条运算都必须是足够基本的。就是说，它们原则上都能精确地执行，甚至人们仅用笔和纸做有限次运算就能完成。 算法和程序不同，程序可以不满足上述的特性(4)。例如，一个操作系统在用户未使用前一直处于“等待”的循环中，直到出现新的用户事件为止。这样的系统可以无休止地运行，直到系统停工。 (3)、设n为正整数, 分析下列各程序段中加下划线的语句的程序步数 (1) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { c[i][j] = 0.0; for (int k = 1; k <= n; k++) c[i][j] = c[i][j] + a[i][k] * b[k][j]; } 第二章 线性表 1、教学内容: 顺序表:顺序表的定义和特点;顺序表的类型定义;顺序表的查找、插入和删除; 单链表:单链表的结构;单链表的类型定义;单链表中的插入与删除;带表头结点的单链表;静态链表; 2、教学要求: 了解:线性表的逻辑结构特性，以及线性表的两种存储实现方式; 5 了解:链表与数组一样，是一种实现级结构。有动态链表和静态链表之分; 掌握:顺序表的定义与实现，包括搜索、插入、删除算法的实现及其平均比较次数的计算; 掌握:单链表的类定义、构造函数、单链表的插入与删除算法 掌握:双向链表的特点，双向链表的类定义及相关操作的实现，用双向链表解决问题的方法。 3、习题与解答: (1)、 将顺序表 (a，a，... ，a) 重新排列为以 a为界的两部12n1 分:a前面的值均比 a小，a后面的值都比 a大(这里假设数据元素的1 1 1 1 类型具有可比性, 不妨设为整型)，操作前后如图2.1所示。这一操作称为划分。a也称为基准。 1 划分的方法有多种，下面介绍的划分算法其思路简单，性能较差。 【解答】:从第二个元素开始到最后一个元素，逐一向后扫描: (1)当前数据元素 a比 a大时，表明它已经在 a的后面，不必改I 1 1 变它与 a之间的位置，继续比较下一个。 1 (2)当前结点若比 a小，说明它应该在 a的前面，此时将它上面的1 1 元素都依次向下移动一个位置，然后将它置入最上方。 25 15 30 10 20 20 60 25 10 30 35 60 15 35 . . . . . . 划分前 划分后 图2.1 顺序表的划分 6 算法如下: void part(SeqList *L) { int i,j; datatype x,y; x=L->data[0]; /* 将基准置入 x 中*/ for(i=1;i<=L->last;i++) if(L->data[i]data[i]; for(j=i-1;j>=0;j--) /*移动*/ L,>data[j+1]=L->data[j]; L->data[0]=y; } } 算法2.1 本算法中，有两重循环，外循环执行n,1次，内循环中移动元素的次数与当前数据的大小有关，当第,个元素小于 a时，要移动它上面的 i-11 个元素，再加上当前结点的保存及置入，所以移动 i-1+2次，在最坏情况下，a 后面的结点都小于 a，故总的移动次数为 : 11 nn*(3)nn，(12)(1)i,，,i，, ,,2,,22 ii, 即最坏情况下移动数据时间性能为,(,)。 这个算法简单但效率低，在第,章的快速排序中时我们将介绍另一种划分算法，它的性能为,(n)。 (2)、 已知单链表H，写一算法将其倒置。即实现如图2.2的操作。(a)为倒置前，(b)为倒置后。 (a) 2 H 2147 ? 9 5 8 56 7 (b) 22H 2174 ? 5 5 9 8 65 【解答】:依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。算法如下: void reverse (Linklist H) { LNode *p; p=H->next; /*p指向第一个数据结点*/ H->next=NULL; /*将原链表置为空表H*/ while (p) { q=p; p=p->next; q->next=H->next; /*将当前结点插到头结点的后面*/ H->next=q; } } 算法2.2 该算法只是对链表中顺序扫描一边即完成了倒置，所以时间性能为O(n)。 (3)、 已知单链表L，写一算法，删除其重复结点，即实现如图2.3的操作。(a)为删除前，(b)为删除后。 【解答】: 用指针p指向第一个数据结点，从它的后继结点开始到表的结束，找与其值相同的结点并删除之;p指向下一个;依此类推，p指向最后结点时算法结束。 (a) 1H 1111 ? 0 0 8 55 ? (b) 1H 1 1 ?2 0 5 8 ? 5 图2.3 删除重复结点 8 算法如下: void pur_LinkList(LinkList H) { LNode *p,*q,*r; p=H->next; /*p指向第一个结点*/ if(p==NULL) return; while (p->next) { q=p; while (q->next) /* 从*p的后继开始找重复结点*/ { if (q->next->data==p->data) { r=q->next; /*找到重复结点，用r指向，删除*r */ q->next=r->next; free(r); } /*if*/ else q=q->next; } /*while(q->next)*/ p=p->next; /*p指向下一个，继续*/ } /*while(p->next)*/ } 算法2.3 2该算法的时间性能为O(n)。 (4)、 设有两个单链表A、B，其中元素递增有序，编写算法将A、B 归并成一个按元素值递减(允许有相同值)有序的链表C，要求用A、B中的 原结点形成，不能重新申请结点。 算法思路:利用A、B两表有序的特点，依次进行比较，将当前值较小 者摘下，插入到C表的头部，得到的C表则为递减有序的。 【解答】: LinkList merge(LinkList A,LinkList B) /*设A、B均为带头结点的单链表*/ { LinkList C; LNode *p,*q; p=A->next;q=B->next; C=A; /*C表的头结点*/ 9 C->next=NULL; free(B); while (p&&q) { if (p->datadata) { s=p;p=p->next; } else {s=q;q=q从原AB表上摘下较小者*/ ->next;} /* s->next=C->next; /*插入到C表的头部*/ C->next=s; } /*while */ if (p==NULL) p=q; while (p) /* 将剩余的结点一个个摘下，插入到C表的头部*/ { s=p;p=p->next; s->next=C->next; C->next=s; } } 算法2.4 该算法的时间性能为O(m+n)。 第三章 栈和队列 1、教学内容: 栈:栈的抽象数据类型;栈的顺序存储表示;栈的链接存储表示 队列 :队列的抽象数据类型;队列的顺序存储表示;队列的链接存储表示;队列的应用举例; 2、教学要求: 熟练掌握:栈的定义、特性和栈的抽象数据类型，栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件 了解:在表达式计算时栈是如何使用的; 10 熟练掌握:队列的定义、特性和队列的抽象数据类型，队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针的变化情况; 、习题与解答: 3 1、 铁路进行列车调度时, 常把站台设计成栈 式结构的站台，如右图所示。试问: (1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序 开入栈式结构的站台, 则可能的出栈序列有多少种? (2) 若进站的六辆列车顺序如上所述, 那么是 否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出"进栈"或"出栈"的序列)。 【解答】 6，，1/(6，1),C,132(1) 可能的不同出栈序列有 种。 12 (2) 不能得到435612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。 3 5 6 2 2 4 4 4 4 1 1 1 1 1 1 1 1 5 3 4 4 1 2 2 2 2 6 第四章 串 1、教学内容: 字符串:字符串的抽象数据类型;字符串操作的实现; 2、教学要求: 熟练掌握:字符串的定义及实现 11 第五章 数组和广义表 1、教学内容: 作为抽象数据类型的数组:数组的定义和初始化;作为抽象数据类型的数组;数组的顺序存储方式; 2、教学要求: 了解:作为抽象数据类型的数组的定义，数组的按行顺序存储与按列顺序存储; 了解:稀疏矩阵的定义及其数组实现; 3、习题与解答: (1)、 画出下列广义表的图形表示和它们的存储表示: (1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1)) 【解答】: (1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1)) J1 D A B C J2 J3 c e a L a b c d A B ? ? 0 B ? J1 0 J1 2 2 0 A 1 e 1 c ? D 0 D 2 2 2 J2 0 J2 2 1 a 2 ? ? 0 C 1 a 2 C ? J3 0 J3 2 ? 0 L 1 b 1 c 1 d L 12 第六章 树和二叉树 1、教学内容: 树和森林的概念:树的定义;树的术语;树的抽象数据类型; 二叉树:二叉树的定义;二叉树的性质;二叉树的抽象数据类型 二叉树的表示:顺序表示;二叉链表表示 遍历二叉树:中序遍历;前序遍历;后序遍历;应用二叉树遍历的事 例;二叉树的计数 堆:堆的定义;堆的建立;堆的插入与删除;堆的调整算法 树与森林:树的存储表示;森林与二叉树的转换;遍历树;遍历森林 哈夫曼树:路径长度;哈夫曼树;霍夫曼编码 2、教学要求: 了解:树和森林的概念。包括树的定义、树的术语、树的抽象数据类型 掌握:二叉树的概念、性质及二叉树的表示 熟练掌握:二叉树的遍历方法 掌握:树与森林的实现，重点在用二叉树实现 掌握:森林与二叉树的转换;树的遍历算法 掌握:二叉树的计数方法及从二叉树遍历结果得到二叉树的方法 掌握:哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径长度的计算 3、习题与解答: (1)、列出右图所示二叉树的叶结点、分支结点和 每个 结点的层次。 【解答】 二叉树的叶结点有?、?、?。分支结点有?、?、 ?、?、?、?。 结点?的层次为0;结点?、?的层次为1;结点?、?、?的层次为2;结点?、?的层次为3;结点?的层次为4。 (2)、 使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出右图所示二叉树的存储表示。 13 【解答】 ? 0 1 2 3 4 5 6 7 8 9 ? ? ? ? ? ? ? ? ? ? 10 11 12 13 14 15 16 17 ? ? ? ? ? ? ? 18 ? ? ? ? ? ? ? 顺序表示 ? ? ? 二叉链表表示 (3)、在结点个数为n (n>1)的各棵树中，高度最小的树的高度是多少,它有多少个叶结点,多少个分支结点,高度最大的树的高度是多少,它有多少个叶结点,多少个分支结点, 【解答】 结点个数为n时，高度最小的树的高度为1，有2层;它有n-1个叶结点，1个分支结点;高度最大的树的高度为n-1，有n层;它有1个叶结点，n-1个分支结点。 (4)、试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 【解答】 具有3个结点的树 具有3个结点的二叉树 (5)、请画出右图所示的树所对应的二叉树。 【解答】 1 1 2 2 14 3 对应二叉树 4 3 4 5 5 6 7 6 8 7 8 6)、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果( 是EBCDAFHIGJ, 试画出这棵二叉树。 【解答】 当前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ时，逐步形成二叉树的过程如下图所示: A A A A B F B F B F FHIGJ EBCD E HIGJ E C G E C G CD D J D J HI H I (7)、 给定权值集合{15, 03, 14, 02, 06, 09, 16, 17}, 构造相应的霍夫曼树, 并计算它的带权外部路径长度。 【解答】 15 14 02 06 09 16 17 F: (?) 15 14 06 09 16 17 05 03 02 03 (?) 15 14 09 16 17 11 (?) 15 14 16 17 20 05 06 09 11 02 03 05 06 (?) (?) 16 17 20 29 20 29 33 02 03 09 11 14 15 09 11 14 15 16 17 05 06 05 06 15 02 03 02 03 82 (?) 33 49 (?) 33 49 16 17 20 29 16 17 20 29 09 11 14 15 09 11 14 15 05 06 05 06 02 03 02 03 此树的带权路径长度WPL = 229。 (8)、 假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不等长Huffman编码, 并给出该电文的总码数。 【解答】已知字母集 { c1, c2, c3, c4, c5, c6, c7, c8 }，频率 {5, 25, 3, 6, 10, 11, 36, 4 }，则Huffman编码为 c1 c2 c3 c4 c5 c6 c7 c8 0110 10 0000 0111 001 010 11 0001 电文总码数为 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4 = 257 100 1 0 39 61 1 0 0 1 17 22 25 36 0 1 0 1 C C7 10 11 11 2 7 0 1 0 1 CC 3 4 5 6 5 6 CCCC 3 8 1 4 16 第七章 图 1、教学内容: 图的基本概念:图的基本概念;图的抽象数据类型 图的存储表示:邻接矩阵;邻接表;邻接多重表 图的遍历与连通性:深度优先搜索;广度优先搜索;连通分量;关节 点与重连通分量 最小生成树:kruskul算法;prim算法 最短路径问题:dijkstra算法 活动网络:拓扑排序;关键路径; 2、教学要求: 理解:图的基本概念和图的抽象数据类型 掌握:图的3种存储表示:邻接矩阵、邻接表和邻接多重表。对于前两种，要求掌握典型操作，如构造、求根、找第一个邻接顶点、找下一个邻接顶点等操作的实现算法 熟练掌握:图的两种遍历算法与求解连通性问题的方法。包括深度优先搜索和广度优先搜索算法、求连通分量的方法(不要求算法); 理解:求解关节点及构造重连通图的方法(不要求算法); 掌握:构造最小生成树的Prim算法和Kruskal算法，要求理解算法 理解:;求解最短路径问题(不要求算法) 熟练掌握:拓扑排序算法 掌握:求解关键路径的方法 3、习题与解答: (1)、画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向完全图中，边的条数为n(n-1)/2。 【解答】 1个顶点的 2个顶点的 无向完全图 无向完全图 3个顶点的 4个顶点的 5个顶点的 无向完全图 无向完全图 无向完全图 17 【证明】 在有n个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有n-1条边与其他n-1个顶点相连，总计n个顶 条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同点有n(n-1) 一条边，所以总共有n(n-1)/2条边。 (2)、对于如右图所示的有向图，试写出: ? (1) 从顶点?出发进行深度优先搜索所得到的深度优先生成树; (2) 从顶点?出发进行广度优先搜索所得到的广度优先生成树; ? ? 【解答】 (1) 以顶点?为根的深度优先生成树(不唯一):? ? ? ? ? ? ? ? ? 或 ? ? ? ? ? ? ? ? (2) 以顶点?为根的广度优先生成树: ? ? ? ? ? (3)、 试对右图所示的AOE网络，解答下列问题。 (1) 这个

工程

路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理

最早可能在什么时间结束。 (2) 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[I]。 (3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。 (4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。 【解答】 按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时 18 间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, <1, <3, <2, <2, <3, <4, <5, 2> 3> 2> 4> 5> 5> 6> 6> e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38 l- 17 0 0 8 0 12 8 0 e 此工程最早完成时间为43。关键路径为<1, 3><3, 2><2, 5><5, 6> 第八章 查找 1、教学内容: 静态查找表:顺序查找和二分查找， 分块查找和索引查找; 动态查找: 二叉排序树， B树3.哈希表; 2、教学要求: 熟练掌握:静态查找表的查找算法及其实现; 熟练掌握:二叉排序树的插入和查找算法及其实现; 了解:B树、B+树的各种操作; 掌握哈希表的造表方法; 了解各种哈希函数和处理冲突的方法。 3、习题与解答: (1)、 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 【解答】 19 509 154 677 553 897 017 275 094 170 503 512 612 765 908 141145ASLC(12*23*44*7),,，，，,,succi141414,i1 151159'ASLC(3*14*14),,，,,unsucci151515,i0 (2)、假定用一个循环链表来实现一个有序表，并让指针head指向具有最小关键码的结点。指针current初始时等于head，每次搜索后指向当前检索的结点，但如果搜索不成功则current重置为head。试编写一个函数search(head, current, key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针0。请说明如何保持指针current以减少搜索时的平均搜索长度。 【解答】 curre nt 10 20 30 40 50 60 hea d 相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据成员。 template ListNode * Search ( ListNode * head, ListNode *& current, Type key ) { ListNode * p, * q; if ( key < current ) { p = head; q = current; } 20 //确定检测范围, 用p, q指示 else { p = current; q = head; } while ( p != q && p->data < key ) p = p->link; 循链搜索其值等于key的结点 // if ( p->data == key ) { current = p; return p; } //找到, 返回结点地址 else { current = head; return NULL; } //未 找到, 返回空指针 } (3)、设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 37, 70, 29 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。 【解答】 46 46 46 46 46 46 25 25 78 25 78 25 78 25 78 空树 加46 加25 加78 62 12 62 12 37 62 加62 46 46 加12 加37 25 78 25 78 12 37 62 12 37 62 70 29 70 加29 加70 第九章 排序 1、教学内容: 概述 插入排序:直接插入排序;折半插入排序;链表插入排序;希尔排序 21 交换排序:起泡排序;快速排序; 选择排序:直接选择排序;堆排序 ; 基数排序:多关键码排序;链式基数排序; 外排序:外排序的基本过程;最佳归并树; 2、教学要求: 掌握:排序的基本概念和性能分析方法 掌握:插入排序、交换排序、选择排序、归并排序等内排序的方法及 其性能分析方法 了解:基数排序方法及其性能分析方法 掌握:最佳归并树的建立方法 3、习题与解答: (1)、设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。 (1) 直接插入排序 (2) 希尔排序(增量为5,2,1) (3) 起泡排序 (4) 快速排序 (5) 直接选择排序 (6) 锦标赛排序 (7) 堆排序 (8) 二路归并排序 (9) 基数排序 【解答】 (1) 直接插入排序 初始排 0 1 2 3 4 5 6 7 8 9 排序码比较列 次数 * i = 1 [ 1 2 16 30 28 10 16 20 6 18 1 2 ] * i = 2 [ 1216 30 28 10 16 20 6 18 1 2 ] * i = 3 [ 12 1630 28 10 16 20 6 18 1 2 ] * i = 4 [ 12 16 3028 10 16 20 6 18 2 22 2 ] * i = 5 [ 12 16 28 3010 16 20 6 18 5 2 ] * i = 6 [ 10 12 16 28 3016 20 6 18 3 2 ] * i = 7 [ 10 12 16 16 28 3020 6 18 3 2 ] * i = 8 [ 10 12 16 16 20 28 30 6 18 3 2 ] * i = 9 [ 6 10 12 16 16 20 28 3018 8 2 ] * [ 6 10 12 16 16 18 20 28 30 2 ] (2) 希尔排序(增量为5,2,1) 初始排 0 1 2 3 4 5 6 7 8 9 排序码比较列 次数 * 12 2 16 30 28 10 16 20 6 18 1+1+1+1+1 = 5 d = 5 * 10 2 16 6 18 12 16 20 30 28 (1+1+2+1) + (1+1 d = 2 +1+1) = 9 * 10 2 16 6 16 12 18 20 30 28 1+1+3+1+3+1 +1 d = 1 +1+2 = 14 * 2 6 10 12 16 16 18 20 28 30 23 希尔(shell)本人采取的增量序列为 ，n/2，, ，，n/2，/2，, ，，n/2，/2，/2，, „,1。一般地，增量序列可采用，nα，, ，，nα，α，, ，，nα，α，α，, „, 1。大量实验表明，取α=0.45454的增量序列比取其他的增量 .45454n， 的一个简单方法是用整数算术计序列的优越性更显著。计算 ，0 算(5*n-1)/11。需要注意，当,< 1/2时，增量序列可能不以1结束，需要加以判断和调整。 (3) 起泡排序 初始排 0 1 2 3 4 5 6 7 8 9 排序码比较列 次数 * i = 0 [ 2 16 30 28 10 16 20 6 18 9 12 ] * i = 1 [ 6 16 30 28 10 16 20 18 8 2 12 ] * i = 2 6 [ 10 16 30 28 16 18 20 7 2 12 ] * i = 3 6 10 [ 16 16 30 28 18 20 6 2 12 ] * i = 4 6 10 [ 16 18 30 28 20 5 2 12 16 ] i = 5 6 10 16 [ 118 20 30 28 4 *2 12 6 ] * i = 6 6 10 16 16 [ 20 28 30 3 2 12 18 ] * 6 10 16 16 18 20 28 30 2 12 (4) 快速排序 PivPvtpo 0 1 2 3 4 5 6 7 8 9 排序码比较ot s 次数 * 12 0,1,2[ 16 30 28 10 16 20 6 18 ] 9 pos pos pos pos 24 ,3 12 2 * 6 0,1 [ 6 12 [ 16 16 20 30 18 ] 2 pos pos 2 10 28 ] * 28 4,5,6[ [ 112 [ 16 16 20 30 18 ] 5 pos pos pos pos pos ,7,8 2 ] 6 0 ] 28 * 18 4,5,6 2 10 12 [ 16 16 2028 [ 3 3 pos pos pos 6 18 ] 0 ] 4 2 10 12 [ 1618 [ 2230 1 pos **16 6 16 ] 0 ] 8 2 10 12 16[ 118 20 28 30 *6 6 ] 左子序列递归深度为1，右子序列递归深度为3。 (5) 直接选择排序 初始排 7 8 9 排序码比较列 0 1 2 3 4 5 6 次数 i = 0 [ 18 9 *12 2 16 30 28 10 16 20 6 ] i = 1 [ 18 8 *2 12 16 30 28 10 16 20 6 ] i = 2 [ 18 7 *2 6 16 30 28 10 16 20 12 ] 25 i = 3 [ 18 6 *2 6 10 30 28 16 16 20 12 ] i = 4 [ 18 5 *2 6 10 12 28 16 16 20 30 ] i = 5 [ 18 4 *2 6 10 12 16 28 16 20 30 ] i = 6 [ 18 3 *2 6 10 12 16 16 28 20 30 ] i = 7 [ 28 2 *2 6 10 12 16 16 18 20 30 ] i = 8 [ 28 1 *2 6 10 12 16 16 16 20 30 ] [ 3 *2 6 10 12 16 16 16 20 28 0 ] (6) 锦标赛排序 2 输出2，调整胜者 2 6 树 2 6 10 *2 16 10 6 16 *16 28 10 16 20 6 18 12 2 30 26 当参加排序的数据对象个数n不足2的某次幂时，将其补足到2的某 4次幂。本题的n = 10，将叶结点个数补足到2 = 16个。排序码比较次数 = 9。 6 输出6，调整胜者 10 6 树 6 12 10 *12 16 10 6 16 *12 2 16 30 28 10 16 20 6 18 10 输出10，调整胜者 10 排序码比18 树 10 18 12 较 *12 16 10 1618 次数 = *12 2 16 30 28 10 16 20 6 18 1。 当某结点的比较对手的参选标志为“不再参选”，该结点自动升入双亲结点，此动作不计入排序码比较次数。 12 输出12，调整胜者 12 18 排序码比 树 27 较 次数 = *18 12 16 *12 16 28 1618 *12 2 16 30 28 10 16 20 6 18 排序码比较次数=3。某对象输出后，对手自动升到双亲，不计入排序码比较次数。 16 输出16，调整胜者 16 18 排序码比树 *16 18 16 较 *12 16 28 1618 次数 = *12 2 16 30 28 10 16 20 6 18 2。 * 16* 输出16，调整胜 *16 18 排序码比者树 *30 16 18 较 *12 30 18 28 16 次数 = * 12 2 16 30 28 10 16 20 6 18 2。 18 输出18，调整胜者 20 18 排序码比树 30 20 18 28 较 次数 = 3。 12 30 18 28 20 *12 2 16 30 28 10 16 20 6 18 20 输出20，调整胜者20 18 排序码比 树 20 30 18 较 20 28 12 30 18 次数 = *12 2 16 30 28 10 16 20 6 18 0。 28 输出28，调整胜者 28 18 排序码比树 30 28 18 较 12 30 18 28 20 次数 = * 12 2 16 30 28 10 16 20 6 18 2。 30 输出30，排序完成 30 18 排序码比 30 28 18 较 12 30 28 20 18 次数 = *12 2 16 30 28 10 16 20 6 18 0。 29 (7) 堆排序 (略)，第二步，做堆排序。 第一步，形成初始的最大堆 12 30 12 2 16 28 16 28 16 ***30 28 10 16 20 18 10 16 20 18 10 16 6 20 6 18 2 6 12 2 30 # 初始排列，不是最大堆 形成初始最大堆 交换0 与# 9对象 20 28 6 18 16 20 16 20 16 *** 12 6 10 16 12 18 10 16 12 18 10 16 28 2 28 30 2 6 30 2 30 从0# 到8# 重新形成堆 交换0# 与8# 对象 从0# 到 7# 重新形成堆 * 162 18 12 16 18 16 12 16 **18 2 6 10 12 6 10 16 2 6 10 16 28 28 20 30 20 28 30 20 30 30 交换0# 与7# 对象 从0# 到6# 重新形成堆 交换0# 与6# 对象 * 10 1616 12 16 12 16 12 10 **18 2 6 16 18 2 6 16 18 2 6 10 20 28 30 20 28 30 20 28 30 从0# 到5# 重新形成堆 交换0# 与5# 对象 从0# 到4# 重新形成堆 2 6 12 6 10 12 10 6 10 * 18 12 16 16**2 16 16 18 2 16 16 18 20 28 30 20 28 30 20 28 30 交换0# 与4# 对象 从0# 到3# 重新形成堆 交换0# 与3# 对象 2 6 10 6 10 2 10 6 2 ***12 16 18 12 16 18 12 16 16 18 16 16 20 28 30 20 28 30 20 28 30 从0# 到2# 重新形成堆 交换0# 与2# 对象 从0# 到1# 重新形成堆 2 2 6 10 6 10 31 **12 16 18 12 16 18 16 16 20 28 30 20 28 30 交换0# 与1# 对象 从0# 到1# 重新形成堆，得到结果 (8) 二路归并排序 采用迭代的方法进行归并排序。设待排序的数据对象有n个。首先把每一个待排序的数据对象看作是长度为的初始归并项，然后进行两两归并，形成长度为2的归并项，再对它们两两归并，形成长度为4的归并项，如此一趟一趟做下去，最后得到长度为n的归并结果。 *12 2 16 30 28 10 16 20 6 18 排序码比较5* 2 12 16 30 10 28 6 18 16 20 12 次 排序码比较6* 2 12 16 30 10 16 20 28 6 18 次 排序码比较7*2 10 12 16 16 20 28 30 6 18 次 排序码比较9*2 6 10 12 16 16 18 20 28 30 次 (9) 基数排序 * 6 12 2 16 30 28 10 16 20 18 按最低位 分配 *6 20 r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9]2 18 16 10 12 16 28 30 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] *28 30 10 20 12 2 16 16 6 18 收集 32 按最高位分配 r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] 18 * 16 16 6 28 12 2 10 20 30 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] *2 6 10 12 16 18 20 30 28 16 收集 (2)、如果只想在一个有n个元素的任意序列中得到其中最小的第k (k<0)个数据的序列，选最小数据需进行n-1次数据比较，以后每选一个数据，进行数据比较的次数，均需 ，logn， -1次。例如，同样12个数据，第一次选最小的数据6，需进行112 次数据比较，以后选7、9、11时，都是 ，log12， -1 = 2次数据比较。 2 四、期末考试试题类型说明 单项选择题:给出有关数据结构概念、性质、特点或简单算法的不完整叙述，要求考生从题后给出的四种选择答案中选择合适的一种答案，补充完整。 填空题:给出一段有关数据结构概念、性质、特点或简单算法的叙述，其中在划有横线的地方缺少内容，要求考生填写完整。 判断题:给出一段有关数据结构概念、性质或特点叙述，要求考生判断正误(或对错)。 运算题:通过分析、计算或作图，对一些数据结构进行运算，得到运算结果。如得到树或图的遍历结果，得到图的最小生成树，得到数据散列存储的散列表，得到对数据进行某种排序的结果等。 算法分析题:给出一段算法或程序，通过阅读和分析回答一些问题。如根据给定输入数据写出程序运行结果;指出算法功能;按算法功能把算法中缺少的内容补充完整。 算法设计题:给出算法设计要求和相应数据结构表示，编写出满足要求的算法。 期末考核形式 采用期末考核平时考核相结合的方式。平时考核分为两种，一种视作业完成情况而定，占总成绩的10%;另一种为课堂出勤考核，占总成绩的20%。期末考核占总成绩的70%，时间为120分钟。总成绩满分为100分，合成成绩达60分及以上者可获得该课程规定的学分，否则不获得该课程学分。 期末考核试题样例及解答 34 (注:第五、六大题只是题的类型参考) 一、单选题 从供选择的答案中选出正确的答案，将其编号填入括号中。 1. 在数据结构的讨论中把数据结构从逻辑上分为( )。 A(内部结构与外部结构 B. 静态结构与动态结构 C. 线性结构与非线性结构 D. 紧凑结构与非紧凑结构 2. 采用线性链表表示一个向量时，要求占用的存储空间地址 ( )。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 可连续可不连续 3. 采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为( )。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 4. 在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行( )。 A. s?link = p?link; p?link = s; B. p?link = s; s?link = q; C. p?link = s?link; s?link = p; D. q?link = s; s?link = p; 5. 如果想在4092个数据中只需要选择其中最小的10个，采用( )方法最好。 A. 起泡排序 B. 堆排序 C. 直接选择排序 D. 快速排序 6. 设有两个串t和p，求p在t中首次出现的位置的运算叫做( )。 A. 求子串 B. 模式匹配 C. 串替换 D. 串连接 7. 在数组A中，每一个数组元素A[i, j] 占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是( )。 A. 80 B. 100 C. 240 D. 270 8. 将一个递归算法改为对应的非递归算法时，通常需要使用 35 ( )。 A. 栈 B. 队列 C. 循环队列 D. 优先队列 9. 一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为( )。 4, 3, 2, 1 B. 2, 4, 3, 1 A. C. 1, 2, 3, 4 D. 3, 2, 1, 4 10. 在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指 )。 针分别为front和rear，则当前队列中的元素个数是( A. (front - rear + 1) % m B. (rear - front + 1) % m C. (front - rear + m) % m D. (rear - front + m) % m 二、判断题 判断下列各个叙述的正误。对，在题号前的括号内填入",";错，在题号前的括号内填入"，"。 ( ) 1. 算法的运行时间涉及加、减、乘、除、转移、存、取等基本运算。要想准确地计算总运算时间是不可行的。 ( ) 2. 二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。 ( ) 3. 顺序表用一维数组作为存储结构，因此顺序表是一维数组。 ( ) 4. 通常使用两个类来协同表示单链表，即链表的结点类和链表类。 ( ) 5. 栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。 ( ) 6. 在使用后缀表示实现计算器类时用到一个栈类的实例，其作用是暂存运算对象。 ( ) 7. 具有n个结点的完全二叉树的高度为 ，log2 n， +1。(n , 0, 根在第0层) ( ) 8. 为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。 ( ) 9. 闭散列法通常比开散列法时间效率更高。 ( ) 10. 一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。 三、填空题 把合适的内容添到横线上。 36 1. 对于一个单链接存储的线性表，假定表头指针指向链表的第一个结点，则在表头插入结点的时间复杂度为________，在表尾插入结点的时间复杂度为________。 2. 假定一棵三叉树(即度为3的树)的结点个数为50，则它的最小 高度为________，假定树根结点为第0层。 3(一棵高度(假定树根结点为第0层)为4的完全二叉树中的结点数 ________个，最多为________个。 最少为 4. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。 5(从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时，其查找长度分别为________和________。 6(对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个________。 7. 在开散列表中，处理冲突的方法为________法，在闭散列表中，处理冲突的方法为____________法。 8(在堆排序的过程中，对任一分支结点进行筛运算(即调整为子堆的过程)的时间复杂度为________，整个堆排序过程的时间复杂度为________。 9. 快速排序在平均情况下的时间复杂度为________，在最坏情况下的时间复杂度为________。 10(在二路归并排序中，对n个记录进行归并的趟数为________。 四、运算题 1. 假定一棵普通树的广义表表示为a(b(e),c(f(h,i,j),g),d)， 分别写出先根、后根、按层遍历的结果。 先根: 后根: 按层: 2(若一个图的边集为 {(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)}，从顶点A开始分别对该图进行深度优先搜索和广度优先搜索，要求顶点值小的邻接点被优先访问， 37 则写出得到的深度优先搜索和广度优先搜索的顶点序列。 深度优先搜索得到的顶点序列: 广度优先搜索得到的顶点序列: 3(已知一个二叉搜索树的广义表表示为 38(25(16),52(,74(68(,72),90)))，在下表中填写出每个元素的比较次数。 1 2 3 4 5 6 7 8 38 25 52 16 74 68 90 72 4. 假定一个待散列存储的线性表为 (32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[13]，若采用除 留余数法构造散列函数和线性探测法处理冲突，试求出每一元素在闭散列 表中的初始散列地址和最终散列地址，画出最后得到的散列表，求出平均 查找长度。 1 2 3 4 5 6 7 8 9 10 元素 32 75 29 63 48 94 25 46 18 70 初始散列地址 最终散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12 散列表 平均查找长度: 5. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用快 速排序法进行排序时每一趟的排序结果。 五、算法分析题 1(给出下列每个递归过程的执行结果。 (1) void unknown(int w) { if(w){ unknown(w-1); 38 for(int i=1; i<=w; i++) cout< void DblList :: Locate ( Type & x ) { //查找x结点 DblNode *p = first->next; while ( p != first && ) p = p->next; if ( p != first ) { //链表中存 39 ? 在x ? ; //该结点的访问频度加1 DblNode *current = p; //从链表中摘下这个结点 current->prior->next = current->next; current->next->prior = current->prior; p = current->prior; //寻找重新插入的位 置 ? while ( p != first && ) p = p->prior; current->next = ; //插入在p之后 ? current->prior = p; p->next->prior = current; p->next = ; ? } else cout<<"Sorry. Not find!\n"; //没找到 } 缺失的语句为: ? ? ? ? ? 3. 假定btnode为二叉树中的结点类型，它含有数值域data、左指针域lchild和右指针域rchild，下面函数中的参数BT指向一棵二叉树的树根结点，X为给定元素，请给出该函数的功能。 btnode* AAA(btnode* BT, datatype X) { if(BT==NULL) return NULL; else { if(BT->data==X) return BT; //返回值为X结点的指针 40 else { btnode* mt; if(mt=AAA(BT->lchild,X)) return mt; else if(mt=AAA(BT->rchild,X)) return mt; else return NULL; } } } 六、算法设计题 1(设计一个算法，从树根指针为rbitreptr的二叉树中删除结点值为 x的子树，若删除成功则返回1，否则返回0。假定在算法中不要求回收被 删除子树中的所有街道，算法中的bitreptr为结点指针类型，所指结点类 型包含三个域，即值域data，左指针域lchild和右指针域rchild。 int deleteSubtree(bitreptr& r, datatype x); 2. 已知二叉搜索树中的结点类型用BtreeNode表示，被定义为: struct BtreeNode {ElemType data; BtreeNode *left, *right;}; 其中data为结点值域，left和right分别为指向左、右孩子结点的 指针域。假定具有BtreeNode*类型的指针参数BST指向一棵二叉搜索树的 根结点，试根据下面的函数声明编写一个非递归算法，向BST树中插入值 为item的结点，若树中不存在item结点则进行插入并返回1表示插入成 功，若树中已存在item结点则不插入并返回0表示插入失败。 int Insert(BTreeNode*& BST, const ElemType& item); 参考解答 一、单选题: 1. C 2. D 3. D 4. D 5. B 6. B 7. C 8. A 9. C 10. D 二、判断题 1. , 2. ， 3. ， 4. , 5. , 6. , 7. ， 8. , 9. ， 10. ， 三、填空题 1. O(1) O(n) 41 2. 4 3. 16 31 4. n-1 5. 1 3 6. 有序序列 7. 链接 开放定址 8(O(log2n) O(nlog2n) 9(O(nlog2n) O(n2) 10(，log2n， 四、运算题 1. 先根:a,b,e,c,f,h,i,j,g,d; 后根:e,b,h,i,j,f,g,c,d,a; 按层:a,b,c,d,e,f,g,h,i,j 2. 深度优先搜索得到的顶点序列:A,B,D,E,F,C 广度优先搜索得到的顶点序列:A,B,C,D,F,E 3(1 2 3 4 5 6 7 8 38 25 52 16 74 68 90 72 1 2 2 3 3 4 4 5 4(平均查找长度为14/10。 1 2 3 4 5 6 7 8 9 10 元素 32 75 29 63 48 94 25 46 18 70 初始散列地址 6 10 3 11 9 3 12 7 5 5 最终散列地址 6 10 3 11 9 4 12 7 5 8 0 1 2 3 4 5 6 7 8 9 10 11 12 散列表 29 94 18 32 46 70 48 75 63 25 42 5( 1 2 3 4 5 6 7 8 9 10 (0) [46 74 53 14 26 38 86 65 27 34] (1) [34 14 26 38 27] 46 [86 65 53 74] (2) [27 14 26] 34 38 46 [74 65 53] 86 (3) [26 14] 27 34 38 46 [53 65] 74 86 (4) [14 26] 27 34 38 46 53 65 74 86 五、算法分析题 1( (1) 1 22 333 4444 (2) 285 (3) 18 2. ? p->data != x ? p->freq++ ? current->freq > p->freq ? p->next ? current 3. 从BT为树根指针的二叉树上查找值为X的结点，若查找成功则返 回该结点指针，否则返回空。 六、算法设计题 1. //从二叉树中删除根结点值为x的子树，若删除成功则返回1，否 则返回0 int deleteSubtree(bitreptr& r, datatype x) { if(r==NULL) return 0; 43 else { if(r->data==x) { r=NULL; return 1;} else { if(deleteSubtree(r->lchild, x)) return 1; if(deleteSubtree(r->rchild, x)) return 1; } } } 2. //向二叉搜索树插入元素 int Insert(BTreeNode*& BST, const ElemType& item) { //查找插入位置 BTreeNode* t=BST, *parent=NULL; while(t!=NULL) { parent=t; if(item==t->data) return 0; else if(itemdata) t=t->left; else t=t->right; } //建立值为item，左、右指针域为空的新结点 BTreeNode* p=new BTreeNode; p->data=item; p->left=p->right=NULL; //将新结点插入到二叉搜索树中的确定位置上 if(parent==NULL) BST=p; else if(itemdata) parent->left=p; else parent->right=p; } 44 数据结构模拟试题 一、选择题(每小题,分，共,,分) 1. 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为 ( )。 2A. O ( n ) B .O ( 1 ) C. O ( n ) D. O ( logn ) 22. 设单链表中结点的结构为(data , link )。已知指针q所指结点是指 针p所指结点的直接前驱，若在*q 与 *p 之间插入结点*s ，则应 执行下列哪一个操作, ( ) A. s ? link = p ? link ; p ? link = s B. q ? link = s ; s ? link = p C. p ? link = s ? link ; s ? link = p D. p ? link = s; s ? link = q 3. 若让元素,，,，,依次进栈，则出栈次序不可能出现( )种 情况。 A.3,2,1 B.2,1,3 C.3,1,2 D.1,3,2 4. 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但 单从运行时间来看，通常递归过程比非递归过程( )。 A. 较快 B. 较慢 C. 相同 5. 树中所有结点的度等于所有结点数加( ) A. 0 B. 1 C. -1 D.2 6. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于( )。 A. n B. n-1 C. n+1 D. 2 * n 7. 对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索 到表中任一元素的平均搜索长度为( ) A.n/2 B.(n+1) / 2 C.(n-1) / 2 D. n / 4 45 8. 在无向图中定义顶点V与V 之间的路径为从V到V的一个( )。 ijij A.顶点有序 B. 边有序 C.权值有序 D.边的条数 9. 如果只想得到1024个元素组成的序列中的前5个最小元素，那么用 ( )方法最快。 A(起泡排序 B. 快速排序 C. 堆排序 D.直接选择 排序 10. 设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码 查询时找到一个表项的平均探查次数不超过1.5，则散列表应能够至少 容纳( )个表项。(设搜索成功的平均搜索长度为S={1+1/(1--a)} nl /2,其中a 为装填因子) A( 400 B(526 C( 624 D(676 二、填空题(每小题1分，共10分) 11. 在程序运行过程中不能扩充的数组是 分配的数组。 这种数组在声明它时必须指定它的大小。 12. 将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个 一维数组B中，A[0][0]存放于B[0]中。对于任意给定数组元素 A[I][J]，如果它能够在数组B中找到，则它应在 位置。 13. 链表适用于 查找。 14. 队列的插入操作在 进行，删除操作在 进行。 15. 设有一个顺序栈S，元素S ，S S , S , S S依次进栈，如果12,345, 6 6个元素的出栈顺序为S , S , S S , S S ，则顺序栈2,34, 65, 1 的容量至少应为 。 16. 通常程序在调试另一个程序时，都需要使用一个 来保持 被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 17. 广义表A(( a,b,c )，( d,e,f))的表尾为 。 18. 在一棵树中， 结点没有前驱结点。 19. 一棵树的广义表表示为a ( b ( c , d ( e , f ), g ( h ) ), i ( j , k ( x, y ) ) ), 结点k的所有祖先的结点数为 个。 46 20. 根据一组记录(56，42，50，64，48)依次插入结点生成一棵AVL树 (高度平衡的二叉搜索树)时，当插入到值为 的结 点时需要进行旋转调整。 三、判断题(每小题1分，共10分) 21. 二维数组可以视为数组元素为一维数组的一维数组。 ( ) 22. 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放， 通常存储器中还有空闲存储空间，就不会产生存储溢出的问题。 ( ) 23. 在用单链表表示的链式队列中，队头在链表的链尾位置。 ( ) 24. 凡是递归定义的数据结构都可以用递归算法来实现它的操作。 ( ) 25. 当向一个小根堆(最小堆)中插入一个具有最小值的元素时，该元素 需要逐层向上调整，直到被调整到堆顶位置为止。 ( ) 26. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。 ( ) 27. 进行折半搜索的表必须是顺序存储的有序表。 ( ) 28. 一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。 ( ) 29. 在散列法中采取开散列(链地址)法来解决冲突时，其装载因子的取 值一定在(0，1)之间。 ( ) 30. 一棵3阶B树是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3阶B树。( ) 四、运算题(每小题8分，共40分) 31.对于一个n * n 的矩阵A的任一矩阵元素a[ i ][ j ]，按行存储时和 按列存储时的地址之差是多少。(若设两种存储的开始存储地址LOC(0， 0)及元素所占存储单元数d相同) 32.设有一个求解汉诺塔(Hanoi)的递归算法 void HANOI( int n ,int peg, int peg2 ,int peg3 ) { 47 if ( n = = 1) cout << “ move ” << peg1 << “ to “ << peg3 << endl; else {HANOI( n – 1,peg1, peg3,peg2) ; move “ << peg1 << “ to “ << lpeg3 << endl; cout << “ HANOI ( n – 1,peg2,peg1,peg3); } } 假定采用HANOI(3，1，2，3)去调用上述算法，则写出整个输出结果的前四行内容。 33.已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。 中序序列:c , b, d, e, a, g, i , h, j, f 前序序列:a, b, c, d, e, f, g, h, i, j 后序序列: 34.假设一组数据对象为(40，28，16，56，50，32，30，63)，按次序插 入每个对象生成一棵AVL树(高度平衡的二叉搜索树)，根据插入过程 填写下表，在相应位置填写所需要的调整类型:“左单旋转”、“右单旋 转”、“先左后右双旋转”、“先右后左双旋转”，若不需要旋转则填写“无”。 数 40 28 16 56 50 32 30 63 调 据: 整: 35.设有150个表项要存储到散列表中，要求利用线性探查法解决冲突，同 时要求找到所需表项的平均比较次数不超过2次。试问散列表m至少需 要设计多大,设a是散列表的装载因子，则有ASL = 1/2(1 + 1/1-a ) SUCC m >= 五、算法分析题(每小题8分，共24分) 36.设顺序表SeqList 具有下列操作: int Length() const; //计算表长度 T Remove(); //删除当前表项，置下一表项为当前表项 48 T First(); //取表中第一表项的值，并把它置为当前表项 T Next(); //取当前表项的后继表项的值，并把该后继表项置为当前 表项 试针对下面所给算法，回答下列问题: (1)说明若顺序表中存放的数据为{29，38，47，16，95，64，73，83， 51，10，0，26}，表的长度为12，参数值s=10，t=30，写出执行算法 后得到的顺序。 (2)说明该算法的功能。 (3)若表长用n表示，说明它的渐进时间复杂度。 #include #include “SeqList.h” template void unknown (SeqList *L, T s, T t){ if (!L->Length()||s>=t) {cerr<<”List is empty or parameters are illegal!”<First(); while(iLength()) if (temp>=s && temp <=t) L->Remove(); else { temp=L->Next(); I++;} } i 37.将二项式(a + b)展开，其系数构成杨辉三角形。若想按行展开系 数的前n行打印出来，需要用到一个队列，存放各行展开式的系数。假 定n = 3，试根据下列算法写出输出结果。 # include “queue.h” void YANGVI(int n) Queue q(n+2); q.EnQueue(1); q.EnQueue(1); int i,j,t,s=0; for (i=1;i<=n;i++){ 49 cout<=0) ; int c2 = ; if (c2 >= 0) ; else return –1; //在树中不存在x结点返回—1 } } 50 六、算法设计题(6分) 39.已知二叉树中的结点类型用BinTreeNode 表示，被定义为: struct BinTreeNode {char data ;BinTreeNode * leftChild , * rightChild;};其中data 为结点值域，leftChild 和rightChild 分别为 指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树高 度的算法，该高度由函数返回。假定根结点的层次为0，参数BT初始指向 这棵二叉树的根结点。 int BTreeHeight (BinTreeNode * BT); 数据结构模拟试题答案 (供参考) 一、选择题(每小题1分，共10分) 1.B 2. B 3.C 4.B 5.C 6.C 7. B 8.A 9.D 10.A 二、填空题(每小题1分，共10分) 11. 静态 12. 2 * I + J 13. 顺序 14. 对尾 对头 15. 3 16. 栈 17. ((d,e,f)) 18. 根 19. 2 20. 50 三、判断题(每小题1分，共10分) 21.?22.?23.×24.?25.?26.?27.?28.×29.×30. × 四、运算题(每小题8分，共40分) 31.按行存储时与按列存储时，计算A[ i ][ j ]地址的公式分别为 LOC( i, j ) = LOC(0,0)+(i *n + j) * d 及 LOC ′( i, j ) = LOC(0,0)+( j *n + i) * d 两者相减，得 LOC( i, j ) – LOC ′( i, j ) = LOC(0,0)+( i *n + j) * d – LOC(0,0) 51 – ( j *n + i) * d =( i – j) * n * d + (j – i)*d 或 =(i – j)*(n – 1) *d 汉诺塔的递归处理过程如下表示: 32. move 1 to 3 (2分) move 1 to 2 (2分) ) move 3 to 2 (2分 move 1 to 3 (2分) 33.后序序列:c, e, d, b, i, j, h, g, f, a 34.插入结果和调整类型为 40 28 16 56 50 32 30 63 插入数 无 无 右单旋 无 先右后左 先左后无 左单旋 调整类据: 双旋转 右双旋 转 型: //每一个元素调整类型正确给1分。 35. 已知要存储的表项数为 n = 150，搜索成功的平均搜索长度为ASLSUCC ?2，则有ASL = 1/2(1+1/1-a)?2， 解得a ?2/3。 又有a = SUCC n/m = 150/m ? 2/3, 则 m ?225。 五、算法分析题(每小题8分，共24分) 36. (1) 算法执行后得到的顺序表为{38，47，94，64，73，83，51，0}， 表的长度减为8。(4分) (2)该算法的功能是在顺序表中删除其值在给定值s与t之间(要求s 小于t)的所有元素。(2分) (3)此算法的渐进时间复杂度为O(n)(2分) 37. 1 1 // 3分 1 2 1 // 3分 1 3 3 1 // 2分 52 38.(1) return c1 + 1 // 3分 (2) NodeLevel (BT ? rightChild , X) // 3分 (3) return c2 + 1 // 2 分 六、6分，请根据编程情况酌情给分。 39. 算法如下: int BTreeHeight (BinTreeNode * BT ) { if (BT = = NULL ) return – 1; // 对于空树，返回–1并结束递归，1分 else { int h1 = BTreeHeight(BT ? leftChild ); //计算左子树的高度，2分 int h2 = BTreeHeight(BT ? rightChild ); //计算右子树的高度，2分 if (h1>h2) return h1 + 1 ; else retrun h2 + 1; //返回树的高度，1分 } } 53