资源描述：
《数据结构(本科)期末综合练习(算法设计题).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构（本科）期末综合练习（算法设计题）1.设有一个线性表(e0,e1,…,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个元素内容置换为(en-1,en-2,…,e1,e0)。函数的原型为：templatevoidinverse(TypeA[],intn);2.试编写一个函数，在一个顺序表A中找出具有最大值和最小值的整数。函数的原型如下所示，原型的参数表中给出顺序表对象为A，通过算法执行，从参数表中的引用参数Max中得到表中的最
2、大整数，Min中得到表中的最小整数。注意，函数中可使用顺序表的两个公有函数：Length()求表的长度；getData(intk)提取第k个元素的值。#include“SeqList.h”templatevoidFindMaxMin(SeqList&A,int&Max,int&Min);3.设有两个整数类型的顺序表A（有m个元素）和B（有n个元素），其元素均以升序排列。试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也以升序排列（表中允许元素重复）。函数的原型如下所示。原型中的参数表给出参加运算的三个顺
3、序表A、B与C。从C中得到执行结果。函数中用到顺序表的4个公有函数：Length()求表的当前长度；maxLength()求表的最大允许长度；getData(intk)提取第k个元素的值；setData(intk,intval)修改第k个元素的值为val。templatevoidmerge(SeqList&A,SeqList&B,SeqList&C);4.编写一个函数frequency，统计在一个输入字符串中各个不同字符出现的频度。函数返回两个数组：A[]记录字符串中有多少种不同的字符，C[]记录
4、每一种字符的出现次数。此外，还要通过整数k返回不同字符数。函数的原型如下所示：#include#include17voidfrequency(char*s,charA[],intC[],int&k);5.根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。要求新生成的链表中不允许有重复元素，并要求返回新表的表头指针。填写程序中缺少的部分。ListNode*Merge(ListNode*L1,ListNode*L2){//根据两个有序单链表L1和L2,生成一个新的有序单链表ListNode*
5、p1=L1->link,*p2=L2->link;ListNode*first=newListNode;ListNode*p=first;while(p1!=NULL&&p2!=NULL){//当两个链表都未检测完时}while(p1!=NULL){//继续处理p1链表中剩余的结点。p=p->link=newListNode;p->data=p1->data;p1=p1->link;}while(p2!=NULL){//继续处理p2链表中剩余的结点。p=p->link=newListNode;p->data=p2->data;p2=p2->l
6、ink;}p->link=NULL;returnfirst->link;}6.假定在一个带表头结点的单链表L中所有结点的值按递增顺序排列，试补充下面函数，功能是删除表L中所有其值大于等于min，同时小于等于max的结点。voidrangeDelete(ListNode*L,ElemTypemin,ElemTypemax){ListNode*q=L,*p=L->link;17}7.已知一个带表头附加结点的单链表LA中包含有三类字符：数字字符；字母字符；其他字符。试编写一个while循环补充下面Separate函数，其功能是构造三个新的单链表，使
7、LA,LB,LC单链表各自指向同一类字符。要求使用原表的结点空间。Separate函数将调用如下两个函数：boolisdigit(charch);//判断字符是否为数字，若是则返回“真”，否则返回“假”boolisalpha(charch);//判断字符是否为字母，若是则返回“真”，否则返回“假”voidSeparate(ListNode*&LA,ListNode*&LB,ListNode*&LC){//原来的单链表是LA,新的三个单链表是LA,LB,LC，它们均需要带表头附加结点ListNode*pa=LA;ListNode*pb=newL
8、istNode,*pc=newListNode;LB=pb;LC=pc;ListNode*p=LA->link;//p指向待处理的结点//添加的while循环位置p
