2015广工数据结构答案.pdf

题目 试写一算法 如果三个整数 a b 和 c 的值 不是依次非递增的 则通过交换 令其为非递增 void Descend int if a b t a a b b t if b c t b b c c t if a b t a a b b t 题目 试编写算法求一元多项式 P x a0 a1x a2x 2 anx n 的值 P x0 并确定算法中每一语句的执行次数和整个算法 的时间复杂度 float Polynomial int n int a float x 求一元多项式的值 P x 数组 a 的元素 a i 为 i 次项的系数 i 0 n int i j float p 0 t 1 for i 0 i n i p a i t p t t x return p 题目 已知 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 试编写求 k 阶裴波那契序列的第 m 项值的函数算法 k 和 m 均以值调用的形式在函数参数表中出现 Status Fibonacci int k int m int if k 2 m 0 return ERROR if m k 1 f 0 else if m k 1 f 1 else for i 0 i k 2 i t i 0 t k 1 1 for i k i m i sum 0 for j i k jMAXINT 时 应按出错处理 注意 选择你认为较好的出错处理方法 Status Series int a int n 求 i 2 i 序列的值并依次存入长度为 n 的数组 a 若所有值均不超过 MAXINT 则返回 OK 否则 OVERFLOW int last 1 int i for i 1 iMAXINT return OVERFLOW last a i 1 return OK 题目 假设有 A B C D E 五个高等院校进行田径对抗赛 各院校的单项成绩均以存入计算机并构成一张表 表中每一行 的形式为 项目名称 性别 校名 成绩 得分 编写算法 处理上述表格 以统计各院校的男 女总分和团体 总分 并输出 void Scores ResultType result ScoreType score 求各校的男 女总分和团体总分 并依次存入数组 score 假设比赛结果已经储存在 result 数组中 并以特殊记录 male 0 域 scorce 0 表示结束 int i 0 while result i sport NULL switch result i schoolname 使用 switch 语句记录各院校的成绩 case A score 0 totalscore result i score if result i gender male score 0 malescore result i score else score 0 femalescore result i score break case B score 1 totalscore result i score if result i gender male score 1 malescore result i score else score 1 femalescore result i score break case C score 2 totalscore result i score if result i gender male score 2 malescore result i score else score 2 femalescore result i score break case D score 3 totalscore result i score if result i gender male score 3 malescore result i score else score 3 femalescore result i score break case E score 4 totalscore result i score if result i gender male score 4 malescore result i score else score 4 femalescore result i score break i 题目 试写一算法 对序列 S 的第 i 个元素赋以值 e 序列的类型定义为 typedef struct ElemType elem int length Sequence Status Assign Sequence if S length i S elem NULL return ERROR S elem i e return OK 题目 试写一算法 由长度为 n 的一维数组 a 构建一个序列 S 序列的类型定义为 typedef struct ElemType elem int length Sequence Status CreateSequence Sequence S elem ElemType malloc n sizeof ElemType if S elem NULL return ERROR S length n if n 0 return ERROR for i 0 i n i S elem i a i return OK 题目 链表的结点和指针类型定义如下 typedef struct LNode ElemType data struct LNode next LNode LinkList 试写一函数 构建一个值为 x 的结点 LinkList MakeNode ElemType x 构建一个值为 x 的结点 并返回其指针 若构建失败 则返回 NULL LNode a LNode p if p NULL return NULL a data x return p 题目 链表的结点和指针类型定义如下 typedef struct LNode ElemType data struct LNode next LNode LinkList 试写一函数 构建长度为 2 且两个结点的值依次为 x 和 y 的链表 LinkList CreateLinkList ElemType x ElemType y 构建其两个结点的值依次为 x 和 y 的链表 若构建失败 则返回 NULL LNode a b LNode p1 LNode p2 if p1 NULL p2 NULL return NULL a data x b data y a next p2 return p1 题目 链表的结点和指针类型定义如下 typedef struct LNode ElemType data struct LNode next LNode LinkList 试写一函数 构建长度为 2 的升序链表 两个结点的值 分别为 x 和 y 但应小的在前 大的在后 LinkList CreateOrdLList ElemType x ElemType y 构建长度为 2 的升序链表 若构建失败 则返回 NULL LNode a b LNode p1 LNode p2 if p1 NULL p2 NULL return NULL if x y a data x b data y else a data y b data x a next p2 return p1 题目 试写一算法 实现顺序栈的判空操作 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 top 0 return TRUE return FALSE 题目 试写一算法 实现顺序栈的取栈顶元素操作 GetTop Sq SqStack S ElemType 存储空间的基址 int top 栈顶元素的下一个位置 简称栈顶位标 int size 当前分配的存储容量 int increment 扩容时 增加的存储容量 SqStack 顺序栈 Status GetTop Sq SqStack S ElemType e S elem S top 1 return OK 题目 试写一算法 实现顺序栈的出栈操作 Pop Sq SqStack 存储空间的基址 int top 栈顶元素的下一个位置 简称栈顶位标 int size 当前分配的存储容量 int increment 扩容时 增加的存储容量 SqStack 顺序栈 Status Pop Sq SqStack e S elem S top return OK 题目 若顺序栈的类型重新定义如下 试编写算法 构建初始容量和扩容增量分别为 size 和 inc 的空顺序栈 S typedef struct ElemType elem 存储空间的基址 ElemType top 栈顶元素的下一个位置 int size 当前分配的存储容量 int increment 扩容时 增加的存储容量 SqStack2 Status InitStack Sq2 SqStack2 if NULL S elem size 0 incS size newbase ElemType realloc S elem S size S increment sizeof ElemType if NULL newbase return ERROR S elem newbase S size S size S increment S top e return OK 题目 若顺序栈的类型重新定义如下 试编写算法 实现顺序栈的出栈操作 typedef struct ElemType elem 存储空间的基址 ElemType top 栈顶元素的下一个位置 int size 当前分配的存储容量 int increment 扩容时 增加的存储容量 SqStack2 Status Pop Sq2 SqStack2 e S top return OK 题目 试写一算法 借助辅助栈 复制顺序栈 S1 得到 S2 顺序栈的类型定义为 typedef struct ElemType elem 存储空间的基址 int top 栈顶元素的下一个位置 简称栈顶位标 int size 当前分配的存储容量 int increment 扩容时 增加的存储容量 SqStack 顺序栈 可调用顺序栈接口中下列函数 Status InitStack Sq SqStack 初始化顺序栈 S Status DestroyStack Sq SqStack 销毁顺序栈 S Status StackEmpty Sq SqStack S 栈 S 判空 若空则返回 TRUE 否则 FALSE Status Push Sq SqStack 将元素 e 压入栈 S Status Pop Sq SqStack 栈 S 的栈顶元素出栈到 e Status CopyStack Sq SqStack S1 SqStack return TRUE S2 elem S1 elem S2 top S1 top return TRUE 题目 试写一算法 求循环队列的长度 循环队列的类型定义为 typedef struct ElemType base 存储空间的基址 int front 队头位标 int rear 队尾位标 指示队尾元素的下一位置 int maxSize 最大长度 SqQueue int QueueLength Sq SqQueue Q 返回队列 Q 中元素个数 即队列的长度 int s s Q rear Q front if s 0 s Q maxSize Q front Q rear return s 题目 如果希望循环队列中的元素都能得到利用 则可设置一个标志域 tag 并以 tag 值为 0 或 1 来区分尾 指针和头指针值相同时的队列状态是 空 还是 满 试编写与此结构相应的入队列和出队列的算法 本题的循环队列 CTagQueue 的类型定义如下 typedef struct ElemType elem MAXQSIZE int tag int front int rear CTagQueue Status EnCQueue CTagQueue if Q rear 0 Q elem 0 x Q rear 1 else Q elem Q rear x Q rear Q rear 1 MAXQSIZE Q tag 1 return OK Status DeCQueue CTagQueue x Q elem Q front Q front Q front 1 MAXQSIZE Q tag 0 return OK 题目 假设将循环队列定义为 以域变量 rear 和 length 分别指示循环队列中队尾元素的位置和内 含元素的个数 试给出此循环队列的队满条件 并 写出相应的入队列和出队列的算法 在出队列的算 法中要返回队头元素 本题的循环队列 CLenQueue 的类型定义如下 typedef struct ElemType elem MAXQSIZE int length int rear CLenQueue Status EnCQueue CLenQueue Q rear Q rear 1 MAXQSIZE Q elem Q rear x Q length return OK Status DeCQueue CLenQueue x Q elem Q rear MAXQSIZE Q length 1 MAXQSIZE Q length return OK 题目 已知 k 阶斐波那契序列的定义为 f0 0 f1 0 fk 2 0 fk 1 1 fn fn 1 fn 2 fn k n k k 1 试利用循环队列编写求 k 阶斐波那契序列中第 n 1 项 fn 的算法 本题的循环队列的类型定义如下 typedef struct ElemType base 存储空间的基址 int front 队头位标 int rear 队尾位标 指示队尾元素的下一位置 int maxSize 最大长度 SqQueue long Fib int k int n 求 k 阶斐波那契序列的第 n 1 项 fn SqQueue Q int i j long fn 0 Q base ElemType malloc sizeof ElemType Q front 0 Q rear 0 Q maxSize k for i 0 i k 1 i Q base Q rear 0 Q rear Q rear 1 Q maxSize Q base Q rear 1 Q rear Q rear 1 Q maxSize if n k 1 return 1 else if n k 1 return 0 for i k i n i fn 0 for j 0 j k j fn fn Q base j Q base Q rear fn Q rear Q rear 1 Q maxSize return fn 题目 设 A a1 am 和 B b1 bn 均为有序顺序表 A 和 B 分别为 A 和 B 中除去最大共同前缀后的子表 例如 A x y y z x z B x y y z y x x z 则两者中最大 的共同前缀为 x y y z 在两表中除去最大共同前缀后 的子表分别为 A x z 和 B y x x z 若 A B 空表 则 A B 若 A 空表 而 B 空表 或者两者均不为空表 且 A 的首元小于 B 的首元 则 AB 试写一个比 较 A 和 B 大小的算法 注意 在算法中 不要破坏原表 A 和 B 也不一定先求得 A 和 B 才进行比较 顺序表类型定义如下 typedef struct ElemType elem int length int size int increment SqList char Compare SqList A SqList B 比较顺序表 A 和 B 返回 若 A 若 A B int i 0 while i A length i if i A length if i A length 题目 试写一算法 实现顺序表的就地逆置 即利用原表的存储空间将线性表 a1 a2 an 逆置为 an an 1 a1 顺序表类型定义如下 typedef struct ElemType elem int length int size int increment SqList void Inverse SqList ElemType t for i 0 i L length 2 i t L elem i L elem i L elem L length i 1 L elem L length i 1 t 题目 试对一元稀疏多项式 Pn x 采用存储量同多项式 项数 m 成正比的顺序存储结构 编写求 Pn x0 的算法 x0 为给定值 一元稀疏多项式的顺序存储结构 typedef struct int coef 系数 int exp 指数 Term typedef struct Term elem 存储空间基址 int length 长度 项数 Poly float Evaluate Poly P float x P elem i coef 存放 ai P elem i exp 存放 ei i 1 2 m 本算法计算并返回多项式的值 不判别溢出 入口时要求 0 e1 e2 em 算法内不对此再作验证 int i j float a 1 f 0 for i 0 i P length i a 1 for j 0 j P elem i exp j a a x f f P elem i coef a return f 题目 假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示 即 线性表中的数据元素即为集合中的成员 试写一算法 求并集 A A B 顺序表类型定义如下 typedef struct ElemType elem 存储空间的基址 int length 当前长度 int size 存储容量 int increment 空间不够增加空间大小 SqList 顺序表 可调用顺序表的以下接口函数 Status InitList Sq SqList 初始化顺序表 L int ListLength Sq SqList L 返回顺序表 L 中元素个数 Status GetElem Sq SqList L int i ElemType 用 e 返回顺序表 L 中第 i 个元素的值 int Search Sq SqList L ElemType e 在顺序表 L 顺序查找元素 e 成功时返回该元素在表中第一次出现的位置 否则返回 1 Status Append Sq SqList 在顺序表 L 表尾添加元素 e void Union SqList for i 0 idata return OK 题目 试写一算法 实现链队列的判空操作 链队列的类型定义为 typedef struct LQNode ElemType data struct LQNode next LQNode QueuePtr 结点和结点指针类型 typedef struct QueuePtr front 队头指针 QueuePtr rear 队尾指针 LQueue 链队列类型 Status QueueEmpty LQ LQueue Q 判定链队列 Q 是否为空队列 若 Q 是空队列 则返回 TRUE 否则 FALSE if Q front NULL return TRUE else return FALSE 题目 试写一算法 实现链队列的求队列长度操作 链队列的类型定义为 typedef struct LQNode ElemType data struct LQNode next LQNode QueuePtr 结点和结点指针类型 typedef struct QueuePtr front 队头指针 QueuePtr rear 队尾指针 LQueue 链队列类型 int QueueLength LQ LQueue Q 求链队列 Q 的长度并返回其值 if Q front NULL return 0 int i 1 QueuePtr p p Q front while p Q rear p p next i return i 题目 假设以带头结点的循环链表表示队列 并且 只设一个指针指向队尾元素结点 注意不设头指针 试编写相应的队列初始化 入队列和出队列的算法 带头结点循环链队列 CLQueue 的类型定义为 typedef struct LQNode ElemType data struct LQNode next LQNode CLQueue Status InitCLQueue CLQueue if rear NULL return ERROR rear next rear return OK Status EnCLQueue CLQueue p LQNode malloc sizeof LQNode if p NULL return ERROR p data x p next rear next rear next p rear p return OK Status DeCLQueue CLQueue t rear next if t rear return ERROR p t next x p data t next p next free p return OK 题目 试写一算法 实现带头结点单链表的判空操作 单链表的类型定义为 typedef struct LNode ElemType data struct LNode next LNode LinkList 结点和结点指针类型 Status ListEmpty L LinkList L 判定带头结点单链表 L 是否为空链表 若 L 是空链表 则返回 TRUE 否则 FALSE if L next NULL return TRUE else return FALSE 题目 试写一算法 实现带头结点单链表的销毁操作 单链表的类型定义为 typedef struct LNode ElemType data struct LNode next LNode LinkList 结点和结点指针类型 Status DestroyList L LinkList p L next while p NULL L next p next free p p L next free L return OK 题目 试写一算法 实现带头结点单链表的清空操作 单链表的类型定义为 typedef struct LNode ElemType data struct LNode next LNode LinkList 结点和结点指针类型 Status ClearList L LinkList LinkList p p L next while p NULL L next p next free p p L next return OK 题目 试写一算法 实现带头结点单链表的求表长度操作 单链表的类型定义为 typedef struct LNode ElemType data struct LNode next LNode LinkList 结点和结点指针类型 int ListLength L LinkList L 求带头结点单链表 L 的长度 并返回长度值 若 L 不是带头结点单链表 则返回 1 int i 0 LinkList p if L NULL return 1 p L next while p NULL p p next i return i 题目 试写一算法 在带头结点单链表 L 插入第 i 元素 e 带头结点单链表的类型定义为 typedef struct LNode ElemType data struct LNode next LNode LinkList Status Insert L LinkList L int i ElemType e 在带头结点单链表 L 插入第 i 元素 e 并返回 OK 若参数不合理 则返回 ERROR int j LinkList p t L if i 0 return ERROR if L NULL return ERROR p LNode malloc sizeof LNode if p NULL return ERROR for j 1 jnext if t NULL return ERROR p data e p next t next t next p return OK 题目 试写一算法 在带头结点单链表删除第 i 元素到 e 带头结点单链表的类型定义为 typedef struct LNode ElemType data struct LNode next LNode LinkList Status Delete L LinkList L int i ElemType LinkList p t L if inext NULL L NULL return ERROR for j 1 jnext if t next NULL return ERROR p t next e p data t next p next free p return OK 题目 试写一算法 在带头结点单链表的第 i 元素起的 所有元素从链表移除 并构成一个带头结点的新链表 带头结点单链表的类型定义为 typedef struct LNode ElemType data struct LNode next LNode LinkList Status Split L LinkList L LinkList LinkList p t L Li LNode malloc sizeof LNode if Li NULL return ERROR if inext NULL Li NULL return ERROR for j 1 jnext if t next NULL Li NULL return ERROR p t next t next NULL Li next p return OK 题目 试写一算法 在带头结点单链表删除第 i 元素 起的所有元素 带头结点单链表的类型定义为 typedef struct LNode ElemType data struct LNode next LNode LinkList Status Cut L LinkList L int i 在带头结点单链表 L 删除第 i 元素起的所有元素 并返回 OK 若参数不合理 则返回 ERROR int j LinkList p1 p2 t L if inext NULL L NULL return ERROR for j 1 jnext if t next NULL return ERROR p1 t next t next NULL while p1 NULL p2 p1 next free p1 p1 p2 return OK 题目 试写一算法 删除带头结点单链表中所有值 为 x 的元素 并释放被删结点空间 单链表类型定义如下 typedef struct LNode ElemType data struct LNode next LNode LinkList Status DeleteX L LinkList L ElemType x 删除带头结点单链表 L 中所有值为 x 的元素 并释放被删结点空间 返回实际删除的元素个数 if L NULL L next NULL return ERROR int i 0 LinkList p1 L p2 while p1 next NULL if p1 next data x p2 p1 next p1 next p2 next free p2 i else p1 p1 next return i 题目 试写一算法 删除带头结点单链表中所有值 小于 x 的元素 并释放被删结点空间 单链表类型定义如下 typedef struct LNode ElemType data struct LNode next LNode LinkList Status DeleteSome L LinkList L ElemType x 删除带头结点单链表 L 中所有值小于 x 的元素 并释放被删结点空间 返回实际删除的元素个数 int i 0 LinkList p1 L p2 while p1 next NULL if p1 next datanext p1 next p2 next free p2 i else p1 p1 next return i 题目 试以顺序表 L 的 L rcd L length 1 作为监视哨 改写教材 5 2 节中给出的升序直接插入排序算法 顺序表的类型 RcdSqList 定义如下 typedef struct KeyType key RcdType typedef struct RcdType rcd MAXSIZE 1 r 0 闲置 int length RcdSqList void InsertSort RcdSqList for i L length i 1 i if L rcd i 1 key L rcd i key L rcd L length 1 L rcd i 1 j i 1 do j L rcd j 1 L rcd j while L rcd L length 1 key L rcd j 1 key L rcd j L rcd L length 1 题目 如下所述 改写教材 1 5 节的冒泡排序算法 将算法中用以起控制作用的布尔变量 change 改为一个整型 变量 指示每一趟排序中进行交换的最后一个记录的位置 并以它作为下一趟起泡排序循环终止的控制值 顺序表的类型 RcdSqList 定义如下 typedef struct KeyType key RcdType typedef struct RcdType rcd MAXSIZE 1 r 0 闲置 int length RcdSqList void BubbleSort RcdSqList 比较 void Swap RedType 交换 int change t i j for i L length change L length i 1i t change change 1 for j 1 j t j if GT L rcd j L rcd j 1 Swap L rcd j L rcd j 1 change j 题目 已知记录序列 L rcd 1 L length 中的关键 字各不相同 可按如下所述实现计数排序 另设数组 c 1 n 对每个记录 a i 统计序列中关键字比它 小的记录个数存于 c i 则 c i 0 的记录必为关键字 最小的记录 然后依 c i 值的大小对序列中记录进行 重新排列 试编写算法实现上述排序方法 顺序表的类型 RcdSqList 定义如下 typedef struct KeyType key RcdType typedef struct RcdType r MAXSIZE 1 r 0 闲置 int length RcdSqList void CountSort RcdSqList for i 1 i L length 1 i for j 1 j L length 1 j if L rcd j key L rcd i key c i RcdType L1 if L length 0 L1 RcdType malloc L length sizeof RcdType for i 1 i L length 1 i L1 c i L rcd i for i 1 i L length 1 i L rcd i L1 i 1 free L1 题目 已知某哈希表的装载因子小于 1 哈希函数 H key 为关键字 标识符 的第一个字母在字母表中的序号 处理 冲突的方法为线性探测开放定址法 试编写一个按第一个 字母的顺序输出哈希表中所有关键字的算法 哈希表的类型 HashTable 定义如下 define SUCCESS 1 define UNSUCCESS 0 define DUPLICATE 1 typedef char StrKeyType 4 typedef struct StrKeyType key 关键字项 int