1、将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。
2、将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
4、已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B 的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。
5、设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B 表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。
6、设计一个算法，通过一趟遍历在单链表中确定值最大的结点。
7、设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。
8、设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。
9、已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change(p)，交换p所指向的结点和它的前缀结点的顺序。
知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点）六条链。
10、已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。
11、回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)
12、设从键盘输入一整数的序列：a1, a2, a3，…，a n，试编写算法实现：用栈结构存储输入的整数，当a i≠-1时，将a i进栈；当a i=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。
13、从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一
行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、-、*、/四种运算。例如：234 34+2*$。
14、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
①下面所示的序列中哪些是合法的？
A. IOIIOIOO
B. IOOIOIIO
C. IIIOIOIO
D. IIIOOIOO
②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
15、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空、入队和出队等算法。
16、假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag== 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。
17、如果允许在循环队列的两端都可以进行插入和删除操作。要求：
①写出循环队列的类型定义；
②写出“从队尾删除”和“从队头插入”的算法。
18、已知Ackermann函数定义如下:
①写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程。
②写出计算Ack(m,n)的非递归算法。
19、已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法：
①求链表中的最大整数；
②求链表的结点个数；
③求所有整数的平均值。
20、写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。
21、写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。
22、编写算法，实现下面函数的功能。函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。假设分配给字符串s的空间足够让字符串t 插入。（说明：不得使用任何库函数）
23、已知字符串S1中存放一段英文，写出算法format(s1,s2,s3,n)，将其按给定的长
度n格式化成两端对齐的字符串S2, 其多余的字符送S3。
24、设二维数组, 1..n] 含有m*n 个整数。
①写一个算法判断a中所有元素是否互不相同?输出相关信息(yes/no)；
②试分析算法的时间复杂度。
25、设任意n个整数存放于数组A(1:n)中，试编写算法，将所有正数排在所有负数前面（要求算法复杂性为0(n)）。
26、以二叉链表作为二叉树的存储结构，编写以下算法：
（1）统计二叉树的叶结点个数。
（2）判别两棵树是否相等。
（3）交换二叉树每个结点的左孩子和右孩子。
27、设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。
28、计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。
29、用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目。
30、求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。
31、输出二叉树中从每个叶子结点到根结点的路径。
32、分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：
①增添一个新顶点v，InsertV ex(G, v)；
②删除顶点v及其相关的边，DeleteV ex(G, v);排序题
③增加一条边<v，w>，InsertArc(G, v, w);
④删除一条边<v，w>，DeleteArc(G, v, w)。
33、一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。
34、设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。
35、试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点v i到顶点v j的路径（i≠j）。
36、采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否
存在一条长度为为k的简单路径。
37、试以单链表为存储结构，实现简单选择排序算法。
38、有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。
39、设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜是红，白，蓝之一。要求重新安排这些砾石，使得所有红砾石在前，所有白砾石居中，所有蓝砾石居后，重新安排时对每粒砾石的颜只能看一次，并且只允许交换操作来调整砾石的位置。
40、编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：
①采用顺序存储结构，至多使用一个记录的辅助存储空间；
②算法的时间复杂度为O(n)。
50、借助于快速排序的算法思想，在一组无序的记录中查给定关键字值等于key的记录。设此组记录存放于数组]中。若查成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请简要说明算法思想并编写算法。
51、有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。
①给出适用于计数排序的顺序表定义；
②编写实现计数排序的算法；
③对于有n个记录的表，关键字比较次数是多少？
④与简单选择排序相比较，这种方法是否更好？为什么？
52、设有一个线性表(e0, e1, …, en-2, en-1) 存放在一个一维数组A[arraySize]中的前n 个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个元素内容置换为(en-1, en-2, …, e1, e0)。
函数的原型为：
template<class Type>
void inverse ( Type A[ ], int n );
53、试编写一个函数，在一个顺序表A中出具有最大值和最小值的整数。
函数的原型如下所示，原型的参数表中给出顺序表对象为A，通过算法执行，从参数表中的引用参数Max中得到表中的最大整数，Min中得到表中的最小整数。
注意，函数中可使用顺序表的两个公有函数：
Length( ) 求表的长度；
getData(int k) 提取第k个元素的值。
#include “SeqList.h”
template <class T> void FindMaxMin ( SeqList<int>& A, int& Max, int& Min );
54、设有两个整数类型的顺序表A（有m个元素）和B（有n个元素），其元素均以升序排列。试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也以升序排列（表中允许元素重复）。
函数的原型如下所示。原型中的参数表给出参加运算的三个顺序表A、B与C。从C中得到执行结果。函
数中用到顺序表的4个公有函数：
Length( ) 求表的当前长度；
maxLength( ) 求表的最大允许长度；
getData(int k) 提取第k个元素的值；
setData(int k, int val) 修改第k个元素的值为val。
template<class T>
void merge(SeqList<int>& A, SeqList<int>& B, SeqList<int>& C);
55、编写一个函数frequency，统计在一个输入字符串中各个不同字符出现的频度。函数返回两个数组：A[ ]记录字符串中有多少种不同的字符，C[ ]记录每一种字符的出现次数。此外，还要通过整数k返回不同字符数。
函数的原型如下所示：
#include <iostream.h>
#include <string.h>
void frequency( char* s, char A[ ], int C[ ], int &k );
56、根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。要求新生成的链表中不允许有重复元素，并要求返回新表的表头指针。填写程序中缺少的部分。
ListNode * Merge ( ListNode *L1, ListNode *L2 ) {
//根据两个有序单链表L1和L2, 生成一个新的有序单链表
ListNode *p1 = L1->link, *p2 = L2->link;
ListNode *first=new ListNode;
ListNode *p=first;
while ( p1 != NULL && p2 != NULL ) { //当两个链表都未检测完时
发布评论