一、二叉树（二）
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[]值已全部求取，写出算法，输出所有关键路径。要求每条关键路径用源点至汇点的顶点序列（拓扑有序）表示。
2021-05-03 14:02:44
40KB
一、查找
1. 算法设计题 ：已知n元顺序表a0, a1, … , an-1按关键字递增有序存储。给定关键字值key，编写算法用对分查找求下标i，满足ai-1
2021-05-03 14:02:44
393KB
实验内容及要求：
用字符文件提供数据建立AOE网络邻接表存储结构，编写程序，输出一条关键路径以及工程的最短完成时间。输出的关键路径用该路径上全部顶点的拓序有序序列表示。
实验目的：掌握图的邻接表存储结构；掌握基于拓扑排序算法的关键活动求取算法；自拟输出出一条关键路径的算法。
2021-05-03 14:02:44
48KB
实验内容及要求：
输入n个整数，分别用希尔排序、快速排序、堆排序和归并排序实现由小到大排序并输出排序结果。要求n=10，15，20进行三组排序实验。
实验目的：掌握希尔排序、快速排序、堆排序、归并排序算法。
2021-05-03 14:02:43
187KB
实验内容及要求：
从键盘输入中缀表达式，建立操作数与运算符堆栈，计算并输出表达式的求值结果。
基本要求：实现 +, -, *, /四个二元运算符以及（）；
操作数范围为0至9。
提高要求：实现+, -, *, /四个二元运算符以及（）；
实现+, -两个一元运算符（即正、负号）；
操作数可为任意整型值（程序假定整数及运算范围不超过int型表示范围）。
若两个整数相除，结果只保留整数商（余数丢弃）；每位同学可选择实现基本要求或者提高要求；程序可不处理表达式语法错误。
实验目的：掌握堆栈在表达式求值中的应用。
2021-05-03 09:03:01
51KB
实验内容及要求：
编程建立循环队列存储结构，对排队买票过程进行模拟。要求程序在控制台屏幕上显示字符菜单：
1. 排队——输入新到达的买票人姓名，加入买票队列中；
2. 售票——排队队列中最前面的人购票成功，显示信息并将其从队列中删除；
3. 查看队列——从队首到队尾依次列出所有正在排队买票人的姓名；
4. 结束——退出系统。
“排队”时，若队满，应提示等待（排队不成功）；
“售票”时，若队空，应提示无人排队（售票失败）。
实验目的：掌握循环队列的基本操作。
2021-05-03 09:03:01
95KB
实验内容及要求：
从字符文件输入两个多项式的非零系数及对应的指数，建立多项式的链式存储结构，计算这两个多项式的乘积，输出乘积多项式的全部非零系数及对应的指数到另一字符文件中。
要求输入输出字符文件中的数据格式自拟；编程语言采用C/C++。
实验目的：掌握单向链表的基本操作以及基于链表的多项式加法与乘法。
2021-05-03 09:03:01
46KB
实验内容及要求：
用字符文件提供数据建立连通无向图邻接表存储结构。编写程序，实现DFS与BFS算法，输出DFS与BFS生成树的每条边。（边用顶点序号组成的无序偶表示）
实验目的：掌握图的邻接表存储结构；掌握图的遍历算法与生成树。
2021-05-03 09:03:00
61KB
实验内容及要求：
已知两个n阶下半三角矩阵的乘积仍为n阶下半三角矩阵。编程输入两个n阶下半三角矩阵，输出这两个矩阵的乘积。要求n阶下半三角矩阵采用一维数组压缩存储（即只存储下半三角）。
程序先从键盘(或字符文件)输入n值，建立三个矩阵的一维数组动态存储结构，然后从键盘(或字符文件)输入两个半三角矩阵，最后输出计算结果到屏幕上(或另一个字符文件中)。
例如：键盘输入为：
3
1
2 3
4 5 6
-1
-2 -3
-4 -5 -6
则输出为：
-1
-8 -9
-38 -45 -36
实验目的：掌握半三角矩阵的顺序存储结构。
2021-05-03 09:03:00
39KB
实验内容及要求：
设二叉树采用二叉链表存储结构，结点数据域为字符类型。编写程序，用先序递归遍历法建立二叉树的二叉链表存储结构，然后输出先、中、后序三种递归遍历结果。最后输入一个字符，输出该字符在先、中、后序遍历中的访问次序（访问次序从1开始）。若输入的字符不在二叉树中，输出相应提示信息。要求程序可以反复输入字符并输出访问次序，直到输入某个特殊字符时结束程序。
注意：输入单个字符时需对其后的换行符进行处理。
实验目的：掌握二叉树的基本算法、提前中止递归的方法，递归函数的形参与返回值设置。
2021-05-03 09:03:00
71KB