《算法与数据结构设计课题.doc》由会员分享，可在线阅读，更多相关《算法与数据结构设计课题.doc（2页珍藏版）》请在三一文库上搜索。
1、图的基本运算算法设计与飞机换乘次数最少问题研究(1) 分别采用邻接矩阵和邻接表两种不同存储结构上设计图的基本运算的算法；(2) 在邻接矩阵和邻接表存储结构上实现图的深度和宽度优先遍历算法；(3) 设有n个城市，编号为0n-1，m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案；说明：可以使用有向图表示城市间的航线；只要两城市间有航班，则图中这两点间存在一条权值为1的边；可以使用Dijkstra算法实现。 (4) 基于Dijkstra算法解决城市公交换乘最少问题。各种内排序算法设计与性能比较设计数据结构课程中学过的各种内排序算法，分析各种排序算法的时间复杂度。使用随机数产生器产生
2、大数据集合(如：100个、1000个和10000个等)，运行上述各种排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。二叉树基本操作与哈夫曼编码译码系统的设计创建一棵二叉树，分别实现先序、中序和后序遍历一棵二叉树，计算二叉树结点个数等操作。设计哈夫曼编码/译码系统。能成功演示二叉树的有关运算，运算完毕后能成功释放二叉树所有结点占用的系统内存。线性表的基本运算与多项式的算术运算设计实现顺序表和单链表的基本运算，多项式的加法和乘法算术运算。能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。欧几里德算法与递归算法设计分别采用欧几里德递归算法、欧几里德迭代算法和连续整
3、数检测算法，求两正整数m和n的最大公约数和最小公倍数。回顾递归程序设计方法，并用递归算法实现Hanoi塔问题。RSA密码算法设计构造一个简单的RSA公开密钥系统，完成RSA密钥系统的具体实现，使之能够生成正确的公有密钥和私有密钥，并能用公有密钥对明文进行加密、用私有密钥对密文进行解密。熟悉非对称密钥系统的工作流程，理解加、解密算法的基本原理，能够编程实现生成正确的公有/私有密钥对、用公有密钥对明文进行加密并用私有密钥对密文进行解密的功能。1、RSA密钥产生过程： 随机选择两个大素数 p与q，且p q = n； 计算n的欧拉函数值：(n) = (p-1) (q-1)。 随机选择一个大的正整数e，
4、e满足小于n且与(n)互素的条件，即e与(n)的最大公因子是1； 根据e，(n)，计算另外一个值d，d是e的乘法逆元，且(n)是它们的模，由模运算的及乘法逆元的性质，d e 1 mod (n)； 则两个二元组(e,n)、(d,n) 构成RSA的密钥对，选择其中任意一个二元组作为公钥，则另外一个就为私钥，在此，我们定义(e,n)为公钥，(d,n)为私钥。2、加密过程：先指数运算，然后再取模。已知明文M，公钥(e，n)，私钥(d，n)，则加密过程如下：对M的e次方幂指数运算结果再做模n运算，所得结果即为密文C，即由M计算C用公式表示为：C = Me mod n 3、解密过程：先指数运算，然后再取模。RSA算法加密和解密过程是等价的，解密过程如下：对C的d次方幂运算结果再做模n运算，所得结果即为明文M，即由C推导M可用公式表示为：M = Cd mod n