数据结构（本科）期末综合练习（算法设计题）.DOC

数据结构（本科）期末综合练习（算法设计题）

1. 设有一个线性表 (e0, e1, ?, en-2, en-1) 存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个元素内容置换为 (en-1, en-2, ?, e1, e0)。 函数的原型为：

template

void inverse ( Type A[ ], int n );

2. 试编写一个函数，在一个顺序表A中找出具有最大值和最小值的整数。

函数的原型如下所示，原型的参数表中给出顺序表对象为A，通过算法执行，从参数表中的引用参数Max中得到表中的最大整数，Min中得到表中的最小整数。

注意，函数中可使用顺序表的两个公有函数： Length( ) 求表的长度；

getData(int k) 提取第k个元素的值。

#include “SeqList.h”

template void FindMaxMin ( SeqList& A, int& Max, int& Min );

3. 设有两个整数类型的顺序表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

void merge(SeqList& A, SeqList& B, SeqList& C);

4. 编写一个函数frequency，统计在一个输入字符串中各个不同字符出现的频度。函数返回两个数组：A[ ]记录字符串中有多少种不同的字符，C[ ]记录每一种字符的出现次数。此外，还要通过整数k返回不同字符数。 函数的原型如下所示： #include #include

1

void frequency( char* s, char A[ ], int C[ ], int &k );

5. 根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。要求新生成的链表中不允许有重复元素，并要求返回新表的表头指针。填写程序中缺少的部分。

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 ) { //当两个链表都未检测完时

}

while ( p1 != NULL ) { //继续处理p1链表中剩余的结点。

p=p->link = new ListNode; p->data = p1->data; p1 = p1->link;

}

while ( p2 != NULL ) { //继续处理p2链表中剩余的结点。

p=p->link = new ListNode; p->data = p2->data; p2 = p2->link; }

p->link = NULL; return first->link;

}

6. 假定在一个带表头结点的单链表L中所有结点的值按递增顺序排列，试补充下面函数，功能是删除表L中所有其值大于等于min，同时小于等于max的结点。

void rangeDelete ( ListNode * L, ElemType min, ElemType max ) {

ListNode *q = L, *p = L->link;

2

}

7. 已知一个带表头附加结点的单链表LA中包含有三类字符：数字字符；字母字符；其他字符。试编写一个while循环补充下面Separate函数，其功能是构造三个新的单链表，使LA,LB,LC单链表各自指向同一类字符。要求使用原表的结点空间。Separate函数将调用如下两个函数： bool isdigit(char ch); //判断字符是否为数字，若是则返回“真”，否则返回“假” bool isalpha(char ch); //判断字符是否为字母，若是则返回“真”，否则返回“假”

void Separate ( ListNode *& LA, ListNode *& LB, ListNode *& LC )

{ //原来的单链表是LA, 新的三个单链表是LA,LB,LC，它们均需要带表头附加结点 ListNode *pa=LA;

ListNode *pb=new ListNode, *pc=new ListNode; LB=pb; LC=pc;

ListNode *p=LA->link; //p指向待处理的结点

//添加的while循环位置

pa->link = NULL; pb->link = NULL; pc->link = NULL; }

//请把while循环内容写在此行下面

8. 已知first为单链表的表头指针, 结点结构为(data,link），试根据下列每个函数声明和算法功能写出递归算法。

int Max(LinkNode *f); //递归算法: 求链表中的最大值，若链表为空则返回0

int Num(LinkNode *f); //递归算法: 求链表中结点个数

3

9. 请分别写出在循环队列上进行插入和删除操作的算法。 循环队列定义如下： struct CyclicQueue {

ElemType elem[M]; //M为已定义过的整型常量，表示队列长度

int rear,front ; // rear指向队尾元素后一个位置，front 指向队头元素 int tag ;

// 当 front=rear且tag=0时，队列空，当front=rear且tag=1时，队列满 };

bool EnCQueue( CyclicQueue& Q, ElemType x ) {

// Q 是一个循环队列，最多可存储M个元素，若队列不满， //将x插入至队尾并返回 true；否则返回 false。

}

bool DelCQueue( CyclicQueue& Q, ElemType& x ) {

// Q 是一个循环队列，若队列不空，则删除队头元素并由 x 带回， //且返回 true，否则返回 false

}

10. Q 是一个由其尾指针和队列长度标识的循环队列，请写出插入和删除一个元素的算法。 struct CyclicQueue // 循环队列定义 {

ElemType elem[M]; //M为已定义过的整型常量

4

int rear; // rear指向队尾元素的后一个位置 int length; // length 指示队列中元素个数 };

bool EnCQueue( CyclicQueue& Q, ElemType x ) {

//Q是一个循环队列，若队列不满，则将x插入并返回true；否则返回false

}

bool DelCQueue( CyclicQueue& Q, ElemType& x ) {

//Q 是一个循环队列，若队列不空，则删除队头元素并由x带回， //且返回true；否则返回false

}

nn-1n-2

11. 计算多项式 Pn (x) = a0 x + a1 x + a2 x + ?? + an-1 x + an 通常使用的方法是一种递推的方法。它可以描述为如下的递推形式： pn (x) = x * pn-1 (x) + an (n>0) 此处

n-1n-2

Pn-1 (x) = a0 x + a1 x + ?? + an-2 x + an-1 P0=an

这也是问题的递归形式。多项式的递归求解形式为： poly(x, 0) = A[0] poly(x, n) = x * poly(x, n-1) + A[n], n > 0

试编写一个递归函数，计算这样的多项式的值。 float poly ( float x, float A[], int n ) {

5

本文来源：https://www.bwwdw.com/article/ep5t.html