中科大汪增福模式识别第四次作业答案

中科大汪增福模式识别第三次作业答案

国科大数据库作业3详细过程以及完整答案，没有学过数据库的可以来看

编程作业 1.输入一个非零正整数，输出其各位数字。要求数字之间间隔至少一个空格。 例如：输入12085, 输出为1 2 0 8 5。 要求：采用递归和非递归(用堆栈)两种算法；输入的整数不允许按单个字符输入。 八皇后问题是一个古老而著名的问题。该问题要求在88格的国际象棋盘上摆放着8个皇后，使其不能互相攻击（如下图所示）。即任意两个皇后都不处于同一行、同一列或同一斜线上。问有多少种摆法。著名数学家高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的方案。后来有人用图论的方法解出有92种方案。现在用计算机递归程序，可以很方便地求出这92种方案。请设置堆栈，消除下面递归程序的递归。

作业内容： （C语言版）数据结构习题集(严蔚敏，吴伟明) 绪论 1.8，1.9，1.12，1.20 线性表 2.19, 2.20, 2.21 (电子教案例5) 2. 24 2.31, 2.32

一、数组与广义表 习题集 5.1 5.5 5.7 5.10 上机编程题 习题集5.19 二、二叉树（一） 1. 写算法 (1)已知二叉树（二叉链表）根结点指针为bt，求该二叉树中的叶子数目。 (2)已知某二叉树（三叉链表）的根结点地址root，该树中各结点的左、右儿子指针域已正确填充，写一个算法将所有结点的双亲指针域正确填充。 (3)已知某二叉树（二叉链表）的根结点指针bt。编写算法，将该二叉树中所有结点的左右子树互换。 (4)已知n个结点的完全二叉树结点数据域值按结点编号次序顺序存于一维数组（元素下标范围0..n-1）。编写算法，由该数组首地址以及数组长度n建立对应的二叉链表存储结构。 2. 上机题 (1)编写完整程序，用先序遍历法建立二叉树的二叉链表存储结构，要求结点data域值类型为int。输入的先序遍历整数序列用0表示NULL指针域，其它有效结点的data域值均不等0。定义三个算法函数，分别计算并输出二叉树中结点data域值的最大值、结点data域值之和以及data域值小于0的结点数。 (2)从键盘输入n个数据建立n元完全二叉树顺序存储结构。实现该完全二叉树的先、中、后序遍历。

一、二叉树（二） 1. 写算法 (1)二叉树的直径定义为从根结点至叶子的最大路径长度。编写算法，求二叉树(二叉链表)的直径。 (2)已知二叉树(二叉链表)根结点指针bt，树中两个结点的指针p、q。编写算法求距离结点*p和*q最近的公共祖先的地址。 (3)已知二叉树(二叉链表)根结点指针bt，利用二叉树叶子结点的rchild指针域将所有叶子结点从左向右连接成一个单向链表。算法返回单向链表头结点指针(即最左边第1个叶子结点的地址)。 2. 编程题 (1) 从键盘输入一个字符串（要求字符串中无重复字符），将串中字符当做完全二叉树的顺序存储结构，建立对应的完全二叉树的二叉链表存储结构，输出先、中、后序遍历结果。 (2) 用先序遍历法建立二叉树二叉链表存储结构(结点数据域类型为char，输入字符序列用字符'#'表示NULL)，实现中序线索化，并用非递归算法输出中序遍历结果的正序和逆序序列。 二、图 1. 已知某无向图如下图所示。画出该图的多重邻接表存储结构示意图。根据该存储结构，写出从顶点v0出发，深度和宽度优先遍历顶点访问次序。 2.写一个算法，判断无向图是否有环。算法提要：深度优先遍历过程中，访问某顶点后，该顶点的邻接点中有已访问的顶点且该已访问邻接点不是该顶点的上一级递归出发顶点(即存在回边)，则有环。 3.编程题: 建立无向图邻接表存储结构，输出深度和宽度优先遍历顶点访问次序。 4.编程题：建立AOE网络存储结构，计算并输出ve[]和vl[]。 5.选作题*：算法设计-已知AOE网络的邻接表存储结构G，ve[]和vl[]值已全部求取，写出算法，输出所有关键路径。要求每条关键路径用源点至汇点的顶点序列（拓扑有序）表示。

一、查找 1. 算法设计题 ：已知n元顺序表a0, a1, … , an-1按关键字递增有序存储。给定关键字值key，编写算法用对分查找求下标i，满足ai-1

2021-05-03 14:02:44 393KB 西南交通 数据结构作业