当前位置：文档之家 › 算法设计与第三章2算法与数据结构

算法设计与第三章2算法与数据结构

  • 格式：ppt
  • 大小：286.50 KB
  • 文档页数：74

下载文档原格式

  / 74

合集下载

算法设计与分析知到章节答案智慧树2023年天津大学

算法设计与分析知到章节答案智慧树2023年天津大学

算法设计与分析知到章节测试答案智慧树2023年最新天津大学第一章测试1.下列关于效率的说法正确的是（）。

参考答案:提高程序效率的根本途径在于选择良好的设计方法，数据结构与算法;效率主要指处理机时间和存储器容量两个方面;效率是一个性能要求，其目标应该在需求分析时给出2.算法的时间复杂度取决于（）。

参考答案:问题的规模;待处理数据的初态3.计算机算法指的是（）。

参考答案:解决问题的有限运算序列4.归并排序法的时间复杂度和空间复杂度分别是（）。

参考答案:O(nlog2n);O(n)5.将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)。

（）参考答案:错6.用渐进表示法分析算法复杂度的增长趋势。

（）参考答案:对7.算法分析的两个主要方面是时间复杂度和空间复杂度的分析。

（）参考答案:对8.某算法所需时间由以下方程表示，求出该算法时间复杂度（）。

参考答案:O(nlog2n)9.下列代码的时间复杂度是（）。

参考答案:O(log2N)10.下列算法为在数组A[0,...,n-1]中找出最大值和最小值的元素，其平均比较次数为（）。

参考答案:3n/2-3/2第二章测试1.可用Master方法求解的递归方程的形式为（）。

参考答案:T(n)=aT(n/b)+f(n) , a≥1, b＞1, 为整数, f(n)＞0.2.参考答案:对3.假定，, 递归方程的解是. ( )参考答案:对4.假设数组A包含n个不同的元素，需要从数组A中找出n/2个元素，要求所找的n/2个元素的中点元素也是数组A的中点元素。

针对该问题的任何算法需要的时间复杂度的下限必为。

( )参考答案:错5.使用Master方法求解递归方程的解为（）.参考答案:6.考虑包含n个二维坐标点的集合S，其中n为偶数，且所有坐标点中的均不相同。

一条竖直的直线若能把S集合分成左右两部分坐标点个数相同的子集合，则称直线L为集合S的一条分界线。

若给定集合S，则可在时间内找到这条分界线L。

算法与数据结构

算法与数据结构

算法与数据结构1.引言本文档旨在介绍算法与数据结构的基本概念、常见算法和数据结构的实现方式，并提供相关的示例代码。

通过阅读本文档，读者将能够理解和应用算法与数据结构的基本原理，提高编程效率和代码质量。

2.算法基础2.1 算法定义●算法的概念和特性●算法复杂度分析方法2.2 常用算法设计策略●贪心算法●动态规划●分治法●回溯法3.数据结构3.1 线性数据结构3.1.1 数组3.1.2 链表3.1.3 栈3.1.4 队列3.2 非线性数据结构3.2.1 树●二叉树●平衡二叉树●堆●字典树3.2.2 图●图的表示方法●图的遍历算法●最短路径算法●最小树算法4.常见算法4.1 查找算法●顺序查找●二分查找●哈希查找4.2 排序算法●冒泡排序●插入排序●归并排序●快速排序4.3 字符串匹配算法●暴力匹配算法●KMP算法●Boyer-Moore算法5.示例代码5.1 示例1：________ 使用二分查找算法在有序数组中查找指定元素5.2 示例2：________ 使用快速排序算法对数组进行排序（更多示例代码详见附件）6.附件本文档附件中包含了相关的代码示例，可供读者参考并用于实践。

7.法律名词及注释在本文档中用到的法律名词及注释如下：________●算法：________根据一定的输入规则和运算规则，以明确的步骤得到输出结果的操作集合。

●数据结构：________是一种组织和管理数据的方式，使得数据可以高效地进行存储、检索和操作。

8.结束语本文档介绍了算法与数据结构的基本概念、常见算法和数据结构的实现方式，并提供了示例代码供读者参考。

通过学习本文档，读者将能够掌握算法与数据结构的基本原理，提高编程效率和代码质量。

算法与数据结构大纲

算法与数据结构大纲

算法与数据结构大纲一、课程简介算法与数据结构是计算机科学中的核心基础课程，旨在介绍算法设计和数据结构的基本概念、原理和方法，培养学生的算法思维和问题解决能力。

二、教学目标1. 了解算法与数据结构的基本概念和原理；2. 掌握常见的数据结构及其操作；3. 学习常见的算法设计策略和分析方法；4. 能够运用所学知识解决实际问题。

三、教学内容1. 算法基础- 算法的概念和特征- 算法的表示方法- 算法的分析：时间复杂度和空间复杂度2. 数据结构基础- 数据结构的概念和分类- 抽象数据类型- 数据结构的操作和实现3. 线性结构- 数组- 链表- 栈和队列4. 树状结构- 树的概念和基本操作- 二叉树- 二叉搜索树- 平衡二叉树5. 图状结构- 图的概念和基本操作- 图的存储和表示- 图的遍历6. 排序算法- 插入排序- 选择排序- 冒泡排序- 快速排序- 归并排序7. 查找算法- 顺序查找- 二分查找- 哈希查找8. 算法设计策略- 分治法- 动态规划法- 回溯法- 贪心算法四、教学方法1. 理论讲解：通过课堂讲解，介绍算法与数据结构的基本概念、原理和方法；2. 编程实践：通过编程练习，让学生掌握数据结构的实现和算法的应用；3. 案例分析：通过实际问题的解决，让学生学会运用所学知识解决实际问题；4. 小组讨论：通过小组讨论，培养学生的团队合作和问题解决能力。

五、考核方式1. 平时作业：包括课后作业、编程练习和课堂表现等；2. 期中考试：考核学生对前半部分教学内容的掌握程度；3. 期末考试：考核学生对整个课程内容的掌握程度。

六、教学资料1. 教材：《算法与数据结构》（教材名称），（作者）著，（出版社）出版；2. 参考资料：《数据结构与算法分析》（参考书名称），（作者）著，（出版社）出版。

七、教学设备1. 计算机实验室；2. 投影仪；3. 编程软件。

算法设计与分析智慧树知到答案章节测试2023年山东交通学院

算法设计与分析智慧树知到答案章节测试2023年山东交通学院

第一章测试1.解决一个问题通常有多种方法。

若说一个算法“有效”是指( )A:这个算法能在人的反应时间内将问题解决B:（这个算法能在一定的时间和空间资源限制内将问题解决）和（这个算法比其他已知算法都更快地将问题解决）C:这个算法能在一定的时间和空间资源限制内将问题解决D:这个算法比其他已知算法都更快地将问题解决答案:B2.农夫带着狼、羊、白菜从河的左岸到河的右岸，农夫每次只能带一样东西过河，而且，没有农夫看管，狼会吃羊，羊会吃白菜。

请问农夫能不能过去？（）A:不一定B:不能过去C:能过去答案:C3.下述（）不是是算法的描述方式。

A:自然语言B:程序设计语言C:E-R图D:伪代码答案:C4.有一个国家只有6元和7元两种纸币，如果你是央行行长，你会设置（）为自动取款机的取款最低限额。

A:40B:42C:29D:30答案:D5.算法是一系列解决问题的明确指令。

（）A:对B:错答案:A6.程序=数据结构+算法（）A:错B:对答案:B7.同一个问题可以用不同的算法解决，同一个算法也可以解决不同的问题。

（）A:错答案:B8.算法中的每一条指令不需有确切的含义，对于相同的输入不一定得到相同的输出。

( )A:错B:对答案:A9.可以用同样的方法证明算法的正确性与错误性 ( )A:对B:错答案:B10.求解2个数的最大公约数至少有3种方法。

( )A:错B:对答案:A11.没有好的算法，就编不出好的程序。

（）A:对B:错答案:A12.算法与程序没有关系。

( )A:错B:对答案:A13.我将来不进行软件开发，所以学习算法没什么用。

( )A:对B:错答案:B14.gcd(m,n)=gcd(n,m m od n)并不是对每一对正整数(m,n)都成立。

( )A:错B:对答案:A15.既然程序设计语言可以描述算法，所以算法就是程序。

( )A:错B:对答案:A第二章测试1.并不是所有的算法，规模更大的输入需要更长的运行时间。

( )A:对答案:B2.算法效率分析框架主要关心一个算法的基本操作次数的增长次数，并把它作为算法效率的主要指标。

数据结构和算法第三章2013.ppt

数据结构和算法第三章2013.ppt

//‘关系’算子，用于比较相等、大、小，例如 bool operator< (char *s）;//比较大小,本串小于标准串s则返回非0 bool operator< (String& s）;//比较大小，本串小于串s则返回非0 friend bool operator< (char *s1, String& s）； //友函数用于比较, // ,标准串s1小于串s,则返回非0 //‘输入输出’算子>>和<< 以及读子串等，例如友函数 friend istream& operator>> (isteream& istr,String& s）； friend ostream& operator<< (osteream& ostr,String& s）； // ‘子串函数’：插入子串、寻找子串、提取子串、删除子串等，例
‘实例串’
//在程序首,要#include <string.h>和#include <iostream.h>及 // 及#include <stdlib.h>，以及#include <assert.h>
{ //1.字符串的数据表示： //字符串S 通常用顺序存放，用数组S[]存储，元素的类型为
char //字符串为变长，使用变量size记录串的当前长度 // 2.使用变量访问字符串： //字符串变量能参与运算,例如S1 + S2表示两个字符串首尾
空串：长度为零的串，它不包含任 何字符内容。
3.1.1.1字符串常数和变量
字符串常数 例如： "\n"
字符串变量

算法设计与第三章2算法与数据结构

算法设计与第三章2算法与数据结构
3）考虑到算法的健壮性，要排除对 1——5之外的数据进行 统计。
算法如下：
vote( ) { int i,xp,a[6]; print(“input data until input -1 ”); input(xp ); while(xp!=-1)
{if (xp>=1 and xp<=5 )
a[xp]=a[xp]+1;
main( )
{int a[10],i,xh;
for(i =1;i<=21;i=i+1) {input(xh);
a[xh]=a[xh]+1;}
for(xh =1;xh<=9;xh=xh+1)
if(a[xh] =3 )
print(xh); }
【例4】统计找数字对的出现频率
算法说明： 输入N（2≤N≤100）个数字（在0与9之间），然后统计出这组数中相邻两 数字组成的链环数字对出现的次数。例如： 输入：N=20 {表示要输入数的数目}
算法如下：
main( )
{ int i,xp,a[8];
print(“input height data until input -1 ”);
input(sg );
while （sg<>-1）
{if (sg>179)
a[7]=a[7]+1
；
else
if (sg<150) a[0]=a[0]+1
；
else a[sg/5-29]=a[sg/5-29]+1
{input(k1); a[k0][k1]=a[k0][k1]+1; k0
for (i=0;i<=9;i=i+1) for (j=0;j<=9;j=j+1)

数据结构与算法设计

数据结构与算法设计数据结构与算法设计是计算机科学中非常重要的一门课程，它涵盖了数据的存储和组织方式以及解决实际问题的算法设计。

在本文中，将介绍数据结构与算法设计的基本概念、常见的数据结构和算法，并通过具体的例子来展示它们的应用。

一、基本概念数据结构是指数据元素之间的关系，通常包括逻辑结构和物理结构两个方面。

逻辑结构描述了数据元素之间的逻辑关系，如线性结构、树形结构、图形结构等；物理结构则是数据元素在计算机内存中的存储方式，如顺序存储、链式存储等。

算法是解决实际问题的步骤或方法，可以看做是对数据的操作。

一个好的算法应具备正确性、可读性、健壮性和高效性等特点。

常用的算法设计方法包括迭代法、递归法以及分治法等。

二、常见的数据结构1. 数组：数组是一种线性结构，其中的数据元素按照连续的方式存储。

它的一大优势是可以通过索引快速访问任意位置的元素，但插入和删除操作较为消耗时间。

2. 链表：链表也是一种线性结构，但数据元素通过指针进行连接而不是连续存储。

它的优势在于插入和删除操作的时间复杂度为O(1)，但访问元素需要遍历整个链表。

3. 栈：栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。

它可以用于表达式求值、函数调用和括号匹配等场景。

4. 队列：队列是一种先进先出（FIFO）的数据结构，只能在队尾插入元素，在队头删除元素。

它常用于任务调度、消息传递和缓冲区管理等。

5. 树：树是一种非线性结构，它由节点和边组成。

常见的树结构包括二叉树、平衡二叉树和二叉搜索树等。

三、常见的算法1. 排序算法：排序算法用于将一组数据按照特定的顺序排列。

常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序和归并排序等。

2. 查找算法：查找算法用于在一组数据中寻找特定的元素。

常见的查找算法包括线性查找、二分查找和哈希查找等。

3. 图算法：图算法主要用于解决图的遍历、最短路径和最小生成树等问题。

常见的图算法包括深度优先搜索（DFS）、广度优先搜索（BFS）和迪杰斯特拉算法等。

数据结构与算法设计

数据结构与算法设计1. 概述数据结构与算法是计算机科学中的重要基础知识，属于计算机程序设计的核心内容。

通过合理选择和设计数据结构，以及优化算法的实现，可以在计算机程序中高效地存储和处理数据，提高程序的性能。

2. 数据结构2.1 数组数组是一种简单的数据结构，它由一组有序的元素组成。

通过索引来访问和操作数组中的元素。

数组具有随机访问的特点，可以快速查找和修改元素。

但是插入和删除操作相对较慢，需要移动后续元素。

2.2 链表链表是一种非连续的存储结构，它由节点组成，每个节点包含数据和指向下一个节点的指针。

链表的插入和删除操作相对较快，不需要移动其他元素。

但是访问链表中的元素需要从头开始遍历，效率较低。

2.3 栈栈是一种后进先出（LIFO）的数据结构，可以通过压栈（入栈）和弹栈（出栈）操作来管理数据。

栈常用于递归函数的调用和表达式的计算等场景。

2.4 队列队列是一种先进先出（FIFO）的数据结构，可以通过入队（enqueue）和出队（dequeue）操作来管理数据。

队列常用于消息传递和任务调度等场景。

3. 算法设计3.1 排序算法排序算法是常见的算法设计问题，目的是将一组元素按照一定的规则进行排序。

常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。

3.2 查找算法查找算法用于在一组数据中查找指定的元素。

常见的查找算法有线性查找、二分查找、哈希查找等。

二分查找是一种高效的查找算法，但要求数据必须有序。

3.3 图算法图算法研究图结构的表示和处理。

常见的图算法包括图的遍历、最短路径算法、最小生成树算法、拓扑排序等。

图算法的设计和实现涉及到深度优先搜索（DFS）、广度优先搜索（BFS）等技术。

3.4 动态规划动态规划是一种用于解决复杂问题的算法设计思想，通过将大问题拆分成多个子问题进行求解，并利用子问题的解来构造大问题的解。

动态规划常用于求解最优化问题和最长公共子序列等。

4. 应用场景数据结构和算法广泛应用于各个领域的计算机程序设计中，主要包括以下几个方面：4.1 数据库管理系统：数据结构和算法用于高效的数据存储和检索。

算法与数据结构讲课课件

1．了解和研究需要解决的问题，提出适当的计 算模型并列出解决问题的方法和步骤
2．模型一旦建立起来，就要选择合适的算法， 并将解题步骤表述出来
3．用计算机语言将步骤转化为计算机可以“读 懂”的计算机程序，即所谓的“编程”
4．进行测试和修改
本章着重讨论解决问题的核心--算法以及 算法的处理对象--数据的结构
递推法
所谓递推法，它的数学公式也是递归的 （如：f(n)=n!=n*(n-1)!=n*f(n-1) ）。只是 在实现计算时迭代方向相反。从给定边界 出发逐步迭代到达指定计算参数。它不需 反复调用自己（节省了很多调用参数匹配 开销），效率较高
递推操作是提高递归函数执行效率最有效 的方法，科技计算中最常见
5x+3y+z/3=100
三层循环嵌套
迭代法
重复同样步骤，可以逐次求得更精确的值。这一 过程即为迭代过程
使用迭代法构造算法的基本方法是：首先确定一 个合适的迭代公式，选取一个初始近似值以及解 的误差，然后用循环处理实现迭代过程，终止循 环过程的条件是前后两次得到的近似值之差的绝 对值小于或等于预先给定的误差。并认为最后一 次迭代得到的近似值为问题的解。这种迭代方法 称为逼近迭代
常用流程图符号
开始
结束
(a) 起止框、连接框
A A
输入a,b
(b) 输入输出框
N>10 true
false
(c) 判断框
i+1→i
N为正整数
(d) 处理框
(e) 注释框
(f) 流向线
流程图简明直观、便于交流
N-S图
Nassi和Shneiderman提出了一种符合结构化程序设 计原则的图形描述工具，叫做盒图，也叫做N-S图

算法与数据结构基础知识

算法与数据结构基础知识一、引言算法与数据结构是计算机科学中最基础、最重要的两个概念。

算法是解决问题的一系列步骤或规则，数据结构是组织和存储数据的方法和技术。

掌握算法与数据结构基础知识，对于计算机科学的学习和实践具有重要意义。

二、算法基础知识1. 什么是算法算法是解决特定问题的一系列步骤或规则，它可以被描述为一个计算模型和一组操作规则。

一个好的算法应该具有正确性、可读性、效率和鲁棒性等特点。

2. 算法的分类常见的算法分类包括：递归算法、贪心算法、分治算法、动态规划算法、回溯算法和随机算法等。

不同的问题可能适用不同的算法，需要根据问题的特点选择最合适的算法。

3. 算法的复杂度算法的复杂度描述了算法的执行时间和空间资源消耗情况。

常见的复杂度包括时间复杂度和空间复杂度。

时间复杂度表示算法的执行时间与问题规模的增长关系，常见的时间复杂度有O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)等。

空间复杂度表示算法在执行过程中所需要的额外空间。

三、数据结构基础知识1. 什么是数据结构数据结构是组织和存储数据的方法和技术，它包括各种数据类型和数据之间的关系。

常见的数据结构包括数组、链表、栈、队列、树、图、堆等。

2. 数据结构的分类数据结构可以分为线性结构和非线性结构。

线性结构包括数组、链表、栈和队列等，数据元素之间存在一对一的关系。

非线性结构包括树、图和堆等，数据元素之间存在一对多或多对多的关系。

3. 数据结构的选择在实际问题中，根据问题的特点和需求选择合适的数据结构非常重要。

例如，对于需要快速查找的问题，可以选择哈希表或二叉搜索树作为数据结构；对于需要快速插入和删除的问题，可以选择链表或堆作为数据结构。

四、算法与数据结构的应用算法与数据结构广泛应用于计算机科学的各个领域，例如：1. 搜索引擎：通过使用合适的算法和数据结构，搜索引擎能够快速地从海量数据中找到用户需要的信息。

2. 图像处理：在图像处理中，算法和数据结构被用于图像的压缩、特征提取、目标识别等过程。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
for( i =0;i<=6;i=i+1) input(a[i]); for( i =0;i<=5;i=i+1) input(b[i]); for( i =0;i<=7;i=i+1) input(c[i]); for( i =0;i<=6;i=i+1) {v=a[i]; for( j =0;j<=5;j=j+1)
2）统计过程的一般方法为：先为五个候选人各自设置五个 “计数器”S1，S2，S3，S4，S5，然后根据录入数据通过 多分支语句或嵌套条件语句决定为某个“计数器”累加1, 这样做效率太低。
现在把五个“计数器”用数组代替，选票中候选人的编号xp 正好做下标，执行A(xp)=A(xp)+1就可方便地将选票内容 累加到相应的“计数器”中。也就是说数组结构是存储统 计结果的，而其下标正是原始信息。
if ( b[j]=v ) for(k =0;k<=7;k=k+1) if(c[k]=v)
{print(v); break;} } }
方法二 ：
用数组A的九个下标分量作为各号考生及格科目的计数器。将三科及格名单 共存一个数组，当扫描完毕总及格名单后，凡下标计数器的值为3的就是全及格 的，其余则至少有一科不及格的。
3.2.2数组使信息有序化
当题目中的数据缺乏规律时，很难把重复的工作 抽象成循环不变式来完成，但先用数组结构存储这些 地信息后，问题就迎刃而解了，
【例1】编程将编号“翻译”成英文。例35706“翻译”成 three-five-seven-zero-six。
算法设计1：
算法设计1： 1） 编号一般位数较多，可按长整型输入和存储。 2） 将英文的“zero——nine”存储在数组中，对应下标为
输入的身高可能在50——250之间，若用输入的身高数据 直接作为数组下标进行统计，即使是用PASCAL语言可设置上、 下标的下界，也要开辟200多个空间，而统计是分八个档次进行 的，这样是完全没有必要的。
由于多数统计区间的大小是都固定为5，这样用“身高/529”做下标，则只需开辟8个元素的数组，对应八个统计档次， 即可完成统计工作。
else print(xp, "input error!");
input(xp ); } for (i=1;i<=5;i++)
print(i,"number get", a[i], "votes"); }
【例2】编程统计身高（单位为厘米）。统计分150—— 154；155——159；160——164；165——169；170——174； 175——179及低于是150、高于是179共八档次进行。 算法设计：
2）六种面额不是等到差数列，为了能构造出循环不变 式，将六种币值存储在数组B。这样，六种币值就可表示为 B[i]，i=1，2，3，4，5，6。为了能达到先尽量多地找大面 额的币种，六种币值应该由大到小存储。
3）另外还要为统计六种面额的数量，同样为了能构造 出循环不变式，设置一个有六个元素的累加器数组S，这样操 作就可以通过循环顺利完成了。
每一个问题中的信息往往是多方面的，在算法中一般 有输入信息、输出信息和信息加工处理过程中的中间信息。 那么哪些信息需要用数组进行存储，数组元素下标与信息 怎么样对应等问题的确定，在很大程度上影响着算法的编 写效率和运行效率。
下面的例子恰当地选择了用数组存储的信息，并把题
目中的有关信息作为下标使用，使算法的实现过程大大简
该方法采用了枚举尝试的方法 A，B，C三组分别存放语文、代数、外语及格名单，尝 试范围为三重循环：
I循环， 初值0， 终值6， 步长1 J循环， 初值0， 终值5， 步长1 K循环， 初值0， 终值7， 步长1 定解条件：
A[I]=B[J]=C[K] 共尝试7*6*8=336次。
方法一算法如下：
main( ) {int a[7], b[6], c[8],i,j,k,v,flag;
算法如下：
main( ) {int i,a[10], ind; long num1,num2;
char eng[10][6]={“zero”,”one”,”two”,”three ”,” four”, ” five”,”six”,”seven”,“eight”,”nine”};
print(“Input a num”); input(num1); num2=num1; ind =0; while (num2<>0) {a[ind]=num2 mod 10; ind= ind +1; num2=num2/10; } print(num1, “English_exp:”, eng[a[ind-1]]); for( i=ind-2;i>=0;i=i-1)
0——9。这样无数值规律可循的单词，通过下标就可以方便存 取、访问了。
3） 通过求余、取整运算，可以取到编号的各个位数字。用 这个数字作下标，正好能找到对应的英文数字。 4）考虑输出翻译结果是从高位到低位进行的，而取各位数字， 比较简单的方法是从低位开始通过求余和整除运算逐步完成的。 所以还要开辟一个数组来存储从低位到高位翻译好的结果，并 记录编号的位数，最后倒着从高位到低位输出结果。
该方法同样也采用了枚举尝试的方法。
算法步骤为： 1）用下标计数器累加各学号学生及格科数， 2）尝试、输出部分。 累加部分为一重循环，初值1 ，终值为三科及格的总人 数，包括重复部分。计7+6+8=21，步长1。 尝试部分的尝试范围为一重循环，初值1 ，终值9，步 长1。 定解条件：A（i）=3
方法二算法如下：
3．2 算法与数据结构
3．2．1 3．2．2 3．2．3 3．2．4 3．2．5
原始信息与处理结果的对应存储 数组使信息有序化 数组记录状态信息 大整数存储及运算 构造趣味矩阵
1.常用的几种数据结构
数据的逻辑结构常分为四大类： （1）集合结构 （2）线性结构 （3）树形结构 （4）图结构（网结构）
01598722232787879659 输出：（7，8）=2 （8，7）=3 {指（7，8）、（8，7）数字对出现次数 分别为2次、3次
（7，2）=1 （2，7）=1 （2，2）=2 （2，3）=1 （3，2）=1
算法设计：
其实并不是只有一维数组这样的数据结构可以在算法设 计中有多采的应用，根据数据信息的特点，二维数组 的使用同样可以使算法易于实现，此题就正是如此。
化。
【例1】统计选票
【例2】统计身高
【例3】统计及格学生的名单
【例4】统计找数字对的出现频率
【例1】某次选举，要从五个候选人（编号分别为1、2、3、 4、5）中选一名厂长。请编程完成统计选票的工作。 算法设计：
1）虽然选票发放的数量一般是已知的，但收回的数量通常 是无法预知的，所以算法采用随机循环，设计停止标志为 “-1”。
input( sg );
}
for (i=0;i<=7;i=i+1)
print(i+1 ，“field the number of people： ”，a[i]);
}
【例3】一次考试共考了语文、代数和外语三科。某小组共有九
人，考后各科及格名单如下表，请编写算法找出三科全及格的 学生的名单（学号）。
科目 语文 代数 外语
print(“-”，eng[a[i]]); }
【例2】一个顾客买了价值x元的商品，并将y元的钱 交给售货员。售货员希望用张数最少的钱币找给顾 客。
问题分析：无论买商品的价值x是多大，找给他的钱最多需
要以下六种币值：50，20，10，5，2，1。
算法设计：
1）为了能达到找给顾客钱的张数最少，先尽量多地取 大面额的币种，由大面额到小面额币种逐渐进行。
{input(k1); a[k0][k1]=a[k0][k1]+1; k0=k1;} for (i=0;i<=9;i=i+1)
for (j=0;j<=9;j=j+1) if (a[i][j]<>0 and a[j][i]<>0); print(“(”,i,j,”)=“,a[i][j],”,(”,j,i,”)=”,a[j][i]) }
算法设计：
1） 用一个10 个元素的状态数组p，记录பைடு நூலகம்字0——9在X2中出 现的情况。数组元素都赋初值为1，表示数字0——9没有被使用 过。
2） 对尝试的每一个数x，求x*x,并取其各个位数字，数字作 为数组的下标，若对应元素为1，则该数字第一次出现，将对应 的元素赋为0，表示该数字已出现一次。否则，若对应元素为0， 则说明有重复数字，结束这次尝试。
(1) 在顺序表中做插入删除操作时，平均移动 大约表中一半的元素，因此对n较大的顺序表效 率低。
(2) 需要预先分配足够大的存储空间，估计过 大，可能会导致顺序表后部大量闲置；预先分配 过小，又会造成溢出。
温馨提示： 链表的优缺点恰好与顺序表相反。
3.在选取存储结构时权衡因素
１）基于存储的考虑
顺序表的存储空间是静态分配的，在程序 执行之前必须明确规定它的存储规模，也就是说 事先对“MAXSIZE”要有合适的设定，过大造成浪 费，过小造成溢出。可见对线性表的长度或存储 规模难以估计时，不宜采用顺序表；链表不用事 先估计存储规模，但链表的存储密度较低，
及格学生学号 1，9，6，8，4，3，7 5，2，9，1，3，7 8，1，6，7，3，5，4，9
方法一：
从语文及格名单中逐一抽出各及格学生学号，先在代数及格名单核对，若有 该学号（说明代数也及格了），再在外语及格名单中继续查找，看该学号是否也 在外语及格名单中。若仍在，说明该号属全及格学生的学号，否则就是至少有一 科不及格的。若语文及格名单中就没有某生的号，显然该生根本不在比较之列， 自然不属全及格学生 。