广工数据结构AV 答案最新版.docx

1、广工数据结构AV 答案最新版1-6/*【题目】试写一算法，如果三个整数a，b和c的值不是依次非递增的，则通过交换，令其为非递增。*/void Descend(int &a, int &b, int &c)/* 通过交换，令 a = b = c */ if(a b) a = a b; b = a b; a = a b; if(b c) b = b c; c = b c; b = b c; if(a b) a = a b; b = a b; a = a b; 1-8/*【题目】试编写算法求一元多项式 P(x) = a0 + a1x + a2x2 + . + anxn的值P(x0)，并确定算法中每一

2、语句的执行次数和整个算法的时间复杂度。*/float Polynomial(int n, int a, float x)/* 求一元多项式的值P(x)。 */* 数组a的元素ai为i次项的系数，i=0,.,n */ float p = a0; float temp = 1; for(int i = 0; i n; +i) temp *=x; p += ai+1 * temp; return p;1-11/*【题目】已知k阶裴波那契序列的定义为 f(0)=0, f(1)=0, ., f(k-2)=0, f(k-1)=1; f(n)=f(n-1)+f(n-2)+.+f(n-k), n=k,k+1,

3、.试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。*/Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */ int fibo100; int i; if(k 2 | m 0) return ERROR; if(m = k) if(m = k - 2) f = 0; else f = 1; else for(i = 0; i k - 2; i+) fiboi = 0; fibok - 1 = fibok = 1; for(i = k + 1; i MAXINT时，应按出错处理。注意选择你

4、认为较好的出错处理方法。*/Status Series(int a, int n) /* 求i!*2i序列的值并依次存入长度为n的数组a； */* 若所有值均不超过MAXINT，则返回OK，否则OVERFLOW */ int partOne = 1; int partTwo = 1; for(int i = 0; i MAXINT) return OVERFLOW; ai = temp; return OK;1-23/*【题目】假设有A、B、C、D、E五个高等院校进行田径对抗赛，各院校的单项成绩均以存入计算机并构成一张表，表中每一行的形式为： 项目名称 性别 校名 成绩 得分编写算法，处理上述

5、表格，以统计各院校的男、女总分和团体总分，并输出。*/void Scores(ResultType *result, ScoreType *score)/* 求各校的男、女总分和团体总分, 并依次存入数组score */* 假设比赛结果已经储存在result 数组中, */* 并以特殊记录 , male, , , 0 （域scorce=0）*/* 表示结束 */ for(int i = 0; resulti.score; +i) int index = 0; switch(resulti.schoolname) case A: index = 0; break; case B: index =

6、 1; break; case C: index = 2; break; case D: index = 3; break; case E: index = 4; break; default: break; switch(resulti.gender) case male: scoreindex.malescore += resulti.score; break; case female: scoreindex.femalescore += resulti.score; break; default: break; for(int j = 0; j = S.length) return ER

7、ROR; else S.elemi = e; return OK; 2-9/*【题目】试写一算法，由长度为n的一维数组a构建一个序列S。序列的类型定义为：typedef struct ElemType *elem; int length; Sequence;*/Status CreateSequence(Sequence &S, int n, ElemType *a) /* 由长度为n的一维数组a构建一个序列S，并返回OK。 */* 若构建失败，则返回ERROR */ if(n = 0) return ERROR; else S.length = n; for(int i = 0; i n;

8、+i, +a) S.elemi = *a; return OK; 2-21/*【题目】链表的结点和指针类型定义如下 typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;试写一函数，构建一个值为x的结点。*/LinkList MakeNode(ElemType x)/* 构建一个值为x的结点，并返回其指针。*/* 若构建失败，则返回NULL。 */ LNode temp = x, null ; LNode *node = &temp; return node;2-23/*【题目】链表的结点和指针类型定义

9、如下 typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;试写一函数，构建长度为2且两个结点的值依次为x和y的链表。*/LinkList CreateLinkList(ElemType x, ElemType y) /* 构建其两个结点的值依次为x和y的链表。*/* 若构建失败，则返回NULL。 */ LNode node2 = y, null , node1 = x, &node2 ; LinkList list = &node1; return list;2-25/*【题目】链表的结点和指针类型定

10、义如下 typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;试写一函数，构建长度为2的升序链表，两个结点的值分别为x和y，但应小的在前，大的在后。*/LinkList CreateOrdLList(ElemType x, ElemType y)/* 构建长度为2的升序链表。 */* 若构建失败，则返回NULL。 */ LNode node2 = x = y ? y : x, null ; LNode node1 = x = y ? x : y, &node2 ; LinkList list = &no

11、de1; return list;3-3/*【题目】试写一算法，实现顺序栈的判空操作StackEmpty_Sq(SqStack S)。顺序栈的类型定义为：typedef struct ElemType *elem; / 存储空间的基址 int top; / 栈顶元素的下一个位置，简称栈顶位标 int size; / 当前分配的存储容量 int increment; / 扩容时，增加的存储容量 SqStack; / 顺序栈*/Status StackEmpty_Sq(SqStack S)/* 对顺序栈S判空。 */ /* 若S是空栈，则返回TRUE；否则返回FALSE */ if(!*S.ele

12、m) return TRUE; else return FALSE;3-5/*【题目】试写一算法，实现顺序栈的取栈顶元素操作GetTop_Sq(SqStack S, ElemType &e)。顺序栈的类型定义为：typedef struct ElemType *elem; / 存储空间的基址 int top; / 栈顶元素的下一个位置，简称栈顶位标 int size; / 当前分配的存储容量 int increment; / 扩容时，增加的存储容量 SqStack; / 顺序栈*/Status GetTop_Sq(SqStack S, ElemType &e) /* 取顺序栈S的栈顶元素到e，

13、并返回OK； */ /* 若失败，则返回ERROR。 */ if(!*S.elem) return ERROR; else e = *(S.elem + S.top - 1); return OK; 3-7/*【题目】试写一算法，实现顺序栈的出栈操作Pop_Sq(SqStack &S, ElemType &e)。顺序栈的类型定义为：typedef struct ElemType *elem; / 存储空间的基址 int top; / 栈顶元素的下一个位置，简称栈顶位标 int size; / 当前分配的存储容量 int increment; / 扩容时，增加的存储容量 SqStack; / 顺

14、序栈*/Status Pop_Sq(SqStack &S, ElemType &e) /* 顺序栈S的栈顶元素出栈到e，并返回OK；*/ /* 若失败，则返回ERROR。 */ if(!*S.elem) return ERROR; else e = *(S.elem + S.top - 1); -S.top; return OK; 3-11/*【题目】若顺序栈的类型重新定义如下。试编写算法，构建初始容量和扩容增量分别为size和inc的空顺序栈S。typedef struct ElemType *elem; / 存储空间的基址 ElemType *top; / 栈顶元素的下一个位置 int s

15、ize; / 当前分配的存储容量 int increment; / 扩容时，增加的存储容量 SqStack2;*/Status InitStack_Sq2(SqStack2 &S, int size, int inc)/* 构建初始容量和扩容增量分别为size和inc的空顺序栈S。*/ /* 若成功，则返回OK；否则返回ERROR。 */ if(size = 0 | inc = S.size) S.size += S.increment; *S.top = e; +S.top; return OK;3-17/*【题目】若顺序栈的类型重新定义如下。试编写算法，实现顺序栈的出栈操作。typedef

16、 struct ElemType *elem; / 存储空间的基址 ElemType *top; / 栈顶元素的下一个位置 int size; / 当前分配的存储容量 int increment; / 扩容时，增加的存储容量 SqStack2;*/Status Pop_Sq2(SqStack2 &S, ElemType &e) /* 若顺序栈S是空的，则返回ERROR； */ /* 否则将S的栈顶元素出栈到e，返回OK。*/ if(!*(S.top - 1) return ERROR; else e = *(S.top - 1); -S.top; return OK; 3-22/*【题目】试写

17、一算法，借助辅助栈，复制顺序栈S1得到S2。顺序栈的类型定义为：typedef struct ElemType *elem; / 存储空间的基址 int top; / 栈顶元素的下一个位置，简称栈顶位标 int size; / 当前分配的存储容量 int increment; / 扩容时，增加的存储容量 SqStack; / 顺序栈可调用顺序栈接口中下列函数：Status InitStack_Sq(SqStack &S, int size, int inc); / 初始化顺序栈SStatus DestroyStack_Sq(SqStack &S); / 销毁顺序栈SStatus StackEm

18、pty_Sq(SqStack S); / 栈S判空，若空则返回TRUE，否则FALSEStatus Push_Sq(SqStack &S, ElemType e); / 将元素e压入栈SStatus Pop_Sq(SqStack &S, ElemType &e); / 栈S的栈顶元素出栈到e*/Status CopyStack_Sq(SqStack S1, SqStack &S2) /* 借助辅助栈，复制顺序栈S1得到S2。 */ /* 若复制成功，则返回TRUE；否则FALSE。 */ ElemType temp; SqStack S3; InitStack_Sq(S2, S1.size,

19、S1.increment); InitStack_Sq(S3, S1.size, S1.increment); while(!StackEmpty_Sq(S1) Pop_Sq(S1, temp); Push_Sq(S3, temp); while(!StackEmpty_Sq(S3) Pop_Sq(S3, temp); Push_Sq(S2, temp); DestroyStack_Sq(S3); return TRUE;3-33/*【题目】试写一算法，求循环队列的长度。循环队列的类型定义为：typedef struct ElemType *base; / 存储空间的基址 int front;

20、 / 队头位标 int rear; / 队尾位标，指示队尾元素的下一位置 int maxSize; / 最大长度 SqQueue;*/int QueueLength_Sq(SqQueue Q)/* 返回队列Q中元素个数，即队列的长度。 */ return (Q.rear - Q.front + Q.maxSize) % Q.maxSize;3-35/*【题目】如果希望循环队列中的元素都能得到利用，则可设置一个标志域tag，并以tag值为0或1来区分尾指针和头指针值相同时的队列状态是空还是满。试编写与此结构相应的入队列和出队列的算法。本题的循环队列CTagQueue的类型定义如下：typedef

21、 struct ElemType elemMAXQSIZE; int tag; int front; int rear; CTagQueue;*/Status EnCQueue(CTagQueue &Q, ElemType x)/* 将元素x加入队列Q，并返回OK；*/* 若失败，则返回ERROR。 */ if(Q.rear + MAXSIZE - Q.front) % MAXSIZE) Q.elemQ.rear+ % MAXSIZE = x; else if(Q.tag = 0) Q.elemQ.rear+ % MAXSIZE = x; else return ERROR; if(Q.rea

22、r + MAXSIZE - Q.front) % MAXSIZE = 0) Q.tag = 1; return OK;Status DeCQueue(CTagQueue &Q, ElemType &x)/* 将队列Q的队头元素退队到x，并返回OK；*/* 若失败，则返回ERROR。 */ if(Q.rear + MAXSIZE - Q.front) % MAXSIZE) x = Q.elemQ.front+ % MAXSIZE; else if(Q.tag = 1) x = Q.elemQ.front+ % MAXSIZE; else return ERROR; if(Q.rear + MAXSIZE - Q.front) % MAXSIZE = 0) Q.tag = 0; return OK;3-37/*【题目】假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。本题的循环队列CLenQueue的类型定义如下：typedef struct ElemType elemMAXQSIZE; int length; int rear; CLenQueue;*/Status