下载文档原格式
算法与程序设计试题带答案1. 以下是一道经典的算法题，请编写代码实现求最大公约数（GCD）的算法。
```pythondef gcd(a, b):if b == 0:return areturn gcd(b, a % b)# 测试print(gcd(15, 25)) # 输出 5print(gcd(54, 72)) # 输出 18```解析：这是一个使用递归实现的辗转相除法算法，也叫欧几里得算法。
当两个数 a 和 b 求最大公约数时，如果 b 等于 0，则 a 就是最大公约数；否则，将 b 作为新的 a，将 a 除以 b 的余数作为新的 b 进行递归计算。
2. 请编写代码实现一个链表的反转。
```pythonclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverse_linked_list(head):prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev# 测试node1 = ListNode(1)node2 = ListNode(2)node3 = ListNode(3)node1.next = node2node2.next = node3reversed_head = reverse_linked_list(node1)while reversed_head:print(reversed_head.val)reversed_head = reversed_head.next```解析：这是一个经典的链表反转算法。
使用 prev、curr、next_node 三个指针来实现，其中 prev 用于保存上一个节点，curr 用于保存当前节点，next_node 用于保存下一个节点。
大学期末考试试卷B 卷（算法设计与分析）一、选择题（30分，每题2分）1、下面的算法段针对不同的自然数n 作不同的处理，其中函数odd (n) 当n 是奇数时返回true ，否则返回false ，while ( n > 1) if ( odd (n) ) n = 3 * n + 1;else n = n / 2;请问该算法所需计算时间的下界是 。
A ．Ω（2n ） B ．Ω（nlog n ） C ．Ω（n ！） D ．Ω（logn ）2、某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下同一时刻，该羽毛球场只能租借给一位客户，请问在这10位客户里面，体育馆最多能满足 位客户的需求。
P104 A ．3 B ．4 C ．5 D ．63、当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用 来消除或减少问题的好坏实例间的这种差别。
A ．数值概率算法 B ．舍伍德算法 C ．拉斯维加斯算法 D ．蒙特卡罗算法4、将一个正整数n 表示成一系列正整数之和， n = n 1 + n 2 + … +n k （其中，n 1≥n 2≥ … ≥n k ≥1，k ≥1）正整数n 的一个这种表示称为正整数n 的一个划分。
正整数n 的不同的划分个数总和称为正整数n 的划分数，记作p （n ）；另外，在正整数n 的所有不同划分中，将最大加数n1不大于m 的划分个数记作q （n ，m ）。
则当n=10时，p （n ）= 。
A ．q （8，8） B ．1 + q （9，9） P12 C ．2 + q （10，8） D ．A ，B ，C 都正确5、对于含有n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。
A ．n!B ．2nC ．2n+1-1D ．∑=ni i n 1!/! P1406、在棋盘覆盖问题中，对于2k ×2k 的特殊棋盘（有一个特殊方块），所需的L 型骨牌的个数是 A 。
Page190(13题)一、问题描述在一个n * m 的方格中，m为奇数，放置有n * m 个数，如图4-1所示。
方格中间的下方有一人，此人可按照5个方向前进但不能越出方格，如图4-2所示。
图4-1 方格图4-2 前进方向人每走过一个方格必取此方格中的数。
要求找到一条从底到顶的路径，使其数相加之和为最大。
输出最大和的值。
二、算法设计要求一条从底到顶的路径使其和最大，记顶为第1行，每个方格的数据存入数组a[][]中。
假使现在已经走到了第2行，并且已经求得了从底到第2行的任一列（可以到达的点）为终点的最大和，那么从底到顶（即为从第2行到第１行的最大和）的最大和。
假设以第1行第1列为可到达的终点，那么最大和为：a[1][1] + max3（a[2][1], a[2][2], a[2][3]）（三个数中的最大值），同理也可以求出以第1行任一列（可以到达的点）为终点的最大值，那么取第1行中最大的一个值即为所求的结果。
以上是假设已经走到了第2行，便可以求得第1行为终点的所有值，那么假设走到了第3行，便可得出第2行的值，以此类推，由起点可以得出最后一行的所有值，由最后1行，得出倒数第2行，由此便可得出状态转移方程：a[i][j] = a[i][j] + max5(a[i+1][(j-2) -> (j+2)]);即从第i+1行可以到达第i行第j列的所有值中的最大值加上a[i][j]，即为a[i][j]（以第i 行j列为终点）的最大值。
得出的状态转移方程，问题也基本上解决了，下N N 来就是一个细节的问题了，从底开始出发，只能到达5个方向其它的不能到的方格不能作为路径，只需控制好哪些方格可以作为可选的路径，哪些方格不可以作为路径即可（我是用两个变量控制的，具体见代码）！再用一个path[][]数组记录路径，最后打印出路径即可！三、流程图开 始输入行数n 和列数m 输入n 行m 列的矩阵a,并把矩阵a 赋值给数组dp t = 0 x = s - 4 y = s + 4 i = n - 1 j = x; if(j<= y) dp[i][j] += max5(i+1,j-2,j+2,t) if(i>0)i = i - 1; x -= 2, y += 2; j = j + 1;输出最大值和路径结 束四、程序实现和结果const int N = 1000, M = 1000;int xx, yy, dp[N][M], a[N][M], path[N][M], road[N];int max5(int i, int a, int b, int& t){int j, Max = 0x80000000; //Max先取整型的最小值for( j = a; j <= b; ++j )if( xx <= j && j <= yy && dp[i][j] > Max )Max = dp[i][j], t = j;return Max;}int main(){//freopen("191_13.txt", "r", stdin);int n, m, i, j;scanf("%d%d", &n, &m);for( i = 1; i <= n; ++i )for( j = 1; j <= m; ++j )scanf("%d", &a[i][j]), dp[i][j] = a[i][j];int s = m / 2 + 1;xx = s - 2; yy = s + 2;if( xx <= 0 ) xx = 1, yy = m;int x = s - 4, y = s + 4;if( x <= 0 ) x = 1, y = m;int t = 0;for( i = n - 1; i > 0; --i ){//第i行可以作为路径的点为[x, y]区间内的点for( j = x; j <= y; ++j ){dp[i][j] += max5(i + 1, j-2, j+2, t);path[i][j] = t;}xx = x, yy = y; x -= 2, y += 2;if( x <= 0 ) x = 1, y = m;}int Max = dp[1][x]; t = x;for( i = x + 1; i <= y; ++i )if( dp[1][i] > Max ) Max = dp[1][i], t = i;for( i = 1; i <= n; ++i )road[i] = a[i][t], t = path[i][t];printf("The max sum of the road is %d.\n", Max);printf("The path is: ");for( i = n; i > 0; --i ) printf("%d ", road[i]); puts("");return 0;}运行结果：图4-3 实验结果五、分析和总结能通过对本题的认真分析，更加的充分理解了动态规划的内涵，并更加熟练的掌握了动态规划。
算法分析与设计试题及答案一、选择题1. 下列哪个是属于分治算法的例子？A. 冒泡排序B. 归并排序C. 顺序查找D. 选择排序答案：B2. 在排序算法中，时间复杂度最优的是：A. 冒泡排序B. 插入排序C. 归并排序D. 快速排序答案：C3. 哪个不是动态规划的特点？A. 具有重叠子问题B. 通过递归求解C. 需要保存子问题的解D. 具有最优子结构答案：B4. 在图的广度优先搜索算法中，使用的数据结构是：A. 栈B. 队列C. 数组D. 堆栈答案：B5. 在最小生成树算法中，下列哪个不属于贪心策略？A. Kruskal算法B. Prim算法C. Dijkstra算法D. Prim-Kruskal混合算法答案：C二、简答题1. 请简述分治算法的思想和应用场景。
答案：分治算法的思想是将原问题分解成若干个规模较小且类似的子问题，然后解决子问题，最后将子问题的解合并得到原问题的解。
其应用场景包括排序算法（如归并排序、快速排序）、搜索算法（如二分查找）等。
2. 什么是动态规划算法？请给出一个动态规划算法的示例。
答案：动态规划算法是一种通过将问题分解成子问题并解决子问题来解决复杂问题的方法。
它的特点是具有重叠子问题和最优子结构性质。
以斐波那契数列为例，可以使用动态规划算法求解每一项的值，而不需要重复计算。
3. 图的深度优先搜索和广度优先搜索有什么区别？答案：图的深度优先搜索（Depth First Search，DFS）是一种先访问子节点再访问兄弟节点的遍历算法，通常使用递归或者栈实现。
而广度优先搜索（Breadth First Search，BFS）则是以层次遍历的方式展开搜索，使用队列来实现。
DFS更适合用于搜索路径，BFS则适用于寻找最短路径等。
4. 请简述贪心算法的特点及其应用场景。
答案：贪心算法的特点是每一步都采取当前状态下最优的选择，以期望得到全局最优解。
然而，贪心算法并不一定能求解所有问题的最优解，但对于一些特定问题，贪心算法往往能得到近似最优解。
一、选择题（20分）1．最长公共子序列算法利用的算法是（B ）。
A、分支界限法B、动态规划法C、贪心法D、回溯法2．实现棋盘覆盖算法利用的算法是（A ）。
A、分治法B、动态规划法C、贪心法D、回溯法3.下面是贪心算法的基本要素的是（C ）。
A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解4.回溯法的效率不依赖于下列哪些因素（ D ）A.满足显约束的值的个数B. 计算约束函数的时间C. 计算限界函数的时间D. 确定解空间的时间5.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ）A．递归函数 B.剪枝函数C。
随机数函数 D.搜索函数6．采用最大效益优先搜索方式的算法是（A ）。
A、分支界限法B、动态规划法C、贪心法D、回溯法7．贪心算法与动态规划算法的主要区别是（B ）。
A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解8. 实现最大子段和利用的算法是（B ）。
A、分治策略B、动态规划法C、贪心法D、回溯法9.优先队列式分支限界法选取扩展结点的原则是（C ）。
A、先进先出B、后进先出C、结点的优先级D、随机10.下列算法中通常以广度优先方式系统搜索问题解的是（A）。
A、分支限界法B、动态规划法C、贪心法D、回溯法二、填空题（22分每空2分）1.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。
2、大整数乘积算法是用分治法来设计的。
3、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。
4、舍伍德算法总能求得问题的一个解。
5、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
6.快速排序template<class Type>void QuickSort (Type a[], int p, int r){if (p<r) {int q=Partition(a,p,r);QuickSort (a,p,q-1); 哈密顿环问题的算法可由回溯法设计实现。
初级编程算法设计方法15种典型例题本文档介绍了初级编程算法设计的15种典型例题，以帮助读者提高编程技能和解决问题的能力。
1. 逆序输出题目要求：输入一个整数n，逆序输出其各个位上的数字。
示例：输入：1234输出：43212. 求和题目要求：输入一个整数n，计算从1到n的所有整数的和。
示例：输入：5输出：153. 阶乘计算题目要求：输入一个整数n，计算n的阶乘。
示例：输入：4输出：244. 素数判断题目要求：输入一个正整数n，判断n是否为素数。
示例：输入：7输出：是素数5. 最大公约数题目要求：输入两个正整数a和b，计算它们的最大公约数。
示例：输入：12, 18输出：66. 最小公倍数题目要求：输入两个正整数a和b，计算它们的最小公倍数。
示例：输入：4, 6输出：127. 数字反转题目要求：输入一个整数n，将其各个位上的数字反转。
示例：输入：输出：8. 数字平方根题目要求：输入一个正整数n，计算它的平方根。
示例：输入：9输出：39. 日期格式化题目要求：输入一个日期字符串，将其格式化为YYYY-MM-DD的格式。
示例：输入：""输出："2022-11-30"10. 列表合并题目要求：输入两个已排序的列表a和b，将它们合并成一个有序的列表。
示例：输入：[1, 3, 5], [2, 4, 6]输出：[1, 2, 3, 4, 5, 6]11. 找出重复元素题目要求：输入一个列表，找出其中重复的元素。
示例：输入：[1, 2, 3, 2, 4, 5, 3]输出：[2, 3]12. 字符串反转题目要求：输入一个字符串，将其反转。
示例：输入："Hello"输出："olleH"13. 矩阵转置题目要求：输入一个m ×n的矩阵，将其转置为n ×m的矩阵。
示例：输入：[[1, 2, 3], [4, 5, 6]]输出：[[1, 4], [2, 5], [3, 6]]14. 链表反转题目要求：输入一个链表，将其反转。
算法设计题打印部分假设有两个按元素值递增次序排列的线性表均以单链表形式存储。
请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表并要求利用原来两个单链表的结点存放归并后的单链表。
【北京大学1998 三、1 5分】类似本题的另外叙述有1设有两个无头结点的单链表头指针分别为hahb链中有数据域data链域next两链表的数据都按递增序存放现要求将hb表归到ha表中且归并后ha仍递增序归并中ha表中已有的数据若hb中也有则hb中的数据不归并到ha中hb的链表在算法中不允许破坏。
【南京理工大学1997 四、315分】PROCEDURE mergehahb 2已知头指针分别为la和lb 的带头结点的单链表中结点按元素值非递减有序排列。
写出将la 和lb两链表归并成一个结点按元素值非递减有序排列的单链表其头指针为lc并计算算法的时间复杂度。
【燕山大学1998 五20分】 2. 图编者略中带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。
两表中的元素皆为递增有序。
请写一算法求A和B的并集AUB。
要求该并集中的元素仍保持递增有序。
且要利用A和B的原有结点空间。
【北京邮电大学1992 二15分】类似本题的另外叙述有1 已知递增有序的两个单链表AB分别存储了一个集合。
设计算法实现求两个集合的并集的运算A:A∪B【合肥工业大学1999 五、18分】2已知两个链表A和B分别表示两个集合其元素递增排列。
编一函数求A与B的交集并存放于A链表中。
【南京航空航天大学2001 六10分】3设有两个从小到大排序的带头结点的有序链表。
试编写求这两个链表交运算的算法即L1∩L2。
要求结果链表仍是从小到大排序但无重复元素。
【南京航空航天大学1996 十一10分】4己知两个线性表A B均以带头结点的单链表作存储结构且表中元素按值递增有序排列。
设计算法求出A 与B的交集C要求C另开辟存储空间要求C同样以元素值的递增序的单链表形式存贮。
第2章1、大整数乘法的O(nm log(3/2))算法给定2个大整数u和v，它们分别有m位和n位数字，且mn。
用通常的乘法求uv的值需要O(mn)时间。
可以u和v均看作是有n位数字的大整数，用教材第2章介绍的分治法，在O(n log3)时间内计算uv的值。
当m比n小得多时，用这种方法就显得效率不够高。
试设计一个算法，在上述情况下用O(nm log(3/2))时间求出uv的值。
2、O(1)空间子数组换位算法设a[0:n-1]是一个有n个元素的数组，k(1kn-1)是一个非负整数。
试设计一个算法将子数组a[0:k-1]与a[k+1:n-1]换位。
要求算法在最坏情况下耗时O(n)，且只用到O(1)的辅助空间。
3、段合并排序算法如果在合并排序算法的分割步骤中，将数组a[0:n-1]划分为个子数组，每个子数组中有O()个元素。
然后递归地对分割后的子数组进行排序，最后将所得到的个排好序的子数组合并成所要的排好序的数组a[0:n-1]。
设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。
4、合并排序算法对拨给元素存储于数组和存储于链表中的2种情形，写出合并排序算法。
5、非增序快速排序算法如何修改QuickSort才能使其将输入元素按非增序排序？第三章1、整数线性规划问题考虑下面的整数线性规划问题试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。
2、Ackermann函数Ackermann函数A(m,n)可递归地定义如下：A（m，n）=试设计一个计算A(m,n)的动态规划算法，该算法只占用O(m)空间。
3、独立任务最优调试问题问题描述：用2台机A和B处理n个作业。
设第i个作业交给机器A 处理时需要时间a i，若由机器B来处理，则需要时间b i。
由于各作业的选战和机器的性能关系，很可能对于某些i，有ai≥bi，而对于某些j，j≠i，有a i<b j。
既不能将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。
Python 算法设计练习题及答案一、找出列表中的最大数题目描述：给定一个整数列表，编写一个函数来找出列表中的最大数。
解题思路：遍历列表，比较每个元素与当前最大值，更新最大值。
代码实现：```pythondef find_max(nums):max_num = float('-inf')for num in nums:if num > max_num:max_num = numreturn max_num```二、计算斐波那契数列题目描述：斐波那契数列是一个数列，其中每个数字都是前两个数字的和。
编写一个函数来计算斐波那契数列的第n个数字。
解题思路：使用递归或迭代方式计算斐波那契数列。
代码实现（递归）：```pythondef fibonacci_recursive(n):if n <= 1:return nreturn fibonacci_recursive(n-1) + fibonacci_recursive(n-2)```代码实现（迭代）：```pythondef fibonacci_iterative(n):if n <= 1:return na, b = 0, 1for _ in range(n-1):a, b = b, a+breturn b```三、判断字符串是否为回文题目描述：给定一个字符串，编写一个函数来判断它是否是回文。
回文是指正着读和反着读都一样的字符串。
解题思路：将字符串分别从头尾进行比较，如果对应字符不相等，则不是回文。
代码实现：```pythondef is_palindrome(s):left, right = 0, len(s) - 1while left < right:if s[left] != s[right]:return Falseleft += 1right -= 1return True```四、统计单词频率题目描述：给定一个字符串，编写一个函数来统计每个单词出现的频率。
苏州市职业大学20 ─20 学年第学期试卷标准答案及评分标准《》（集中/分散A/B卷开/闭卷笔试/上机）一、算法设计题1. 设二叉树bt采用二叉链表结构存储。
试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的个数。
【答案】int count=0;void algo2(BTNode *bt){if (bt){if(bt->lchild || bt->rchild){printf(bt->data);count++;}algo2(bt->lchild);algo2(bt->rchild);}}2. 阅读下列函数arrange()int arrange(int a[],int 1,int h,int x){//1和h分别为数据区的下界和上界int i,j,t；i=1；j=h；while(i<j){while(i<j && a[j]>=x)j--；while(i<j && a[j]>=x)i++；if(i<j){ t=a[j]；a[j]=a[i]；a[i]=t；}}if(a[i]<x) return i；else return i－1；}（1）写出该函数的功能；（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。
【答案】（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x 的元素均落在a[i＋1..h]上。
（2）int f(int b[],int n) 或int f(int b[],int n){ {int p,q；int p,q；p=arrange(b,0,n－1,0)；p=arrange(b,0,n－1,1)；q= arrange(b,p+1,n－1,1)；q= arrange(b,0,p,0)；return q－p；return p－q；} }3. 假设线性表以带表头结点的循环单链表表示。
试设计一个算法，在线性表的第k个元素前插入新元素y。
假如表长小于k，则插在表尾。
【答案】void algo1(LNode *h,int k,ElemType y){q=h; P=h->next; j=1;while( p!=h && j<k){q=p; p=p->next; j++;}s=(LNode *)malloc(sizeof(Lnode));s->data=y;q->next=s;s->next=q;}4. 二叉排序树的类型定义如下：typedef struct BSTNode {∥二叉排序树的结点结构int data; ∥数据域struct BSTNode *lchild, *rchild; ∥左、右孩子指针}BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。
【答案】int f34(BSTree root){int count;BSTNode *p;p=root;if ( p && p->data<a) count++;f34(p->lchild);return count;}5. 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。
（注：结点按从上往下，自左至右次序编号）【答案】BTNode * Firstleaf(BTNode *bt){ InitQueue(Q); //初始化队列Qif(bt){EnQueue(Q,bt);;while(!EmptyQueue(Q)){DeQueue(Q,p);if(!p->lchild && !p->rchild) return p;if(p->lchild) EnQueue(Q,p->lchild);if(p->rchild) EnQueue(Q,p->rchild);}}}6. 已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型,编写算法打印出编号为k的结点的双亲和孩子结点。
【答案】int algo2(char bt[],int n,int k){if (k<1||k>n) return 0;if( k==1) printf(“ %c is a root\n”, bt[1]);else printf(“ %c’s parent is %c\n”, bt[k], bt[k/2]);if(2*k<=n) printf(“ %c’s lchild is %c\n”, bt[k], bt[2*k]);else printf(“ %c is not lchild\n”, bt[k]));if(2*k+1<=n) printf(“ %c’s rchild is %c\n”, bt[k], bt[2*k+1]);else printf(“ %c is not rchild\n”, bt[k]));return 1;}7. 编写算法，将非空单链表hb插入到单链表ha的第i(0<i≤表长)个结点前。
【答案】int algo1(LNode *ha, LNode *hb,int i){for(p=hb;p->next; p=p->next);for(j=1,q=ha;j<i; j++) q=q->next;p->next=q->next;q->next=hb->next ；free(hb);}8. 设二叉树T已按完全二叉树的形式存储在顺序表T中，试设计算法根据顺序表T建立该二叉树的二叉链表结构。
顺序表T定义如下：struct tree{int no; /* 结点按完全二叉树的编号*/ElEMTP data; /* 数据域 */}T[N]; /* N为二叉树T的结点数*/【答案】BTNode *creat_tree(struct tree T[N]){ BTNode *p[MAX];t=NULL;for(i=0;i<N;i++){s=(BTNode *)malloc(sizeof(BTNode));s->data=T[i].data;s->lchild=s->rchild=NULL;m=T[i].no; p[m]=s;if(m==1) t=s;else { j=m/2;if(m%2==0) p[j]->lchild=s;else p[j]->rchild=s;}//slse}//forreturn t;}// creat_tree9. 编写算法判断带表头结点的单链表L是否是递增的。
若递增返回1，否则返回0。
【答案】int algo1 (LNode *L){if(!L->next) return 1;p=L->next;while(p->next){if(p->data < p->next->data) p=p->next;else return 0;}return 1;}10. 假设一线性表由Fibonacci数列的前n（n≥3）项构成，试以带表头结点的单链表作该线性表的存储结构，设计算法建立该单链表，且将项数n存储在表头结点中。
Fibonacci数列根据下式求得：1 (n=1)f(n)= 1 (n=2)f(n-2)+f(n-1) (n≥3)【答案】LNode * Creatlist(LNode *h,int n){h=(LNode *)malloc(sizeof(Lnode));h->data=n;h->next=p=(LNode *)malloc(sizeof(Lnode));p->next=q=(LNode *)malloc(sizeof(Lnode));p->data= q->data=1;for(i=3;i<=n;i++){q->next=s=(LNode *)malloc(sizeof(Lnode));s->data=p->data+q->data; s->next=NULL;p=q;q=s;}return h;}11. 设二叉树T采用二叉链表结构存储，数据元素为字符类型。
设计算法将二叉链表中所有data域为小写字母的结点改为大写字母。
【答案】void algo2(BTNode *bt){if (bt){if(bt->data>=’a’&& bt->data<=’z’)bt->data-=32;algo2(bt->lchild);algo2(bt->rchild);}}12. 假设线性表以带表头结点的循环单链表表示。
试设计一个算法，在线性表的第k个元素前插入新元素y。
假如表长小于k，则插在表尾。
【答案】void Insertlist(LNode *h,int k,ElemType y){q=h; P=h->next; j=1;while( p!=h && j<k){q=p; p=p->next; j++;}s=(LNode *)malloc(sizeof(Lnode));s->data=y;q->next=s;s->next=q;}13. 有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法在该链表中插入一个元素x，使得插入后的单链表仍有序。
【答案】void algo1 (LNode *H, ElemTp x){s=(LNode *) malloc (sizeof(LNode));s->data=x;q=H; p=H->next;while ( p && p->data<=x ){q=p; p=p->next;}s->next=p; q->next=s;}14. 二叉排序树的类型定义如下：typedef struct BSTNode {∥二叉排序树的结点结构int data; ∥数据域struct BSTNode *lchild, *rchild; ∥左、右孩子指针}BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。
【答案】int f34(BSTree root){int count;BSTNode *p;p=root;if ( p && p->data<a) count++;f34(p->lchild);return count;}15. 有一带表头结点的单链表，其结点的data域的类型为字符型，编写一个算法删除该链表中的数字字符。
