




免费预览已结束,剩余16页可下载查看
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第 1 章 绪 1 1 有下列几种二元组表示的数据结构 试画出它们分别对应的图形表示 并指出它们分别属于何种结构 1 A D R 其中 D a1 a2 a 3 a4 R 2 B D R 其中 D a b c d e R a b b c c d d e 3 C D R 其中 D a b c d e f g R d b d g b a b c g e e f 4 K D R 其中 D 1 2 3 4 5 6 R 1 集合 2 线性表 abcde 3 树 4 图 f g a b c d e 1 2 设 n 为正整数 求下列各程序段中的下划线语句的执行次数 1 i 1 k 0 while i n 1 k 10 i i 2 for int i 1 i n i for int j 1 j n j c i j 0 for int k 1 k n k c i j c i j a i k b k j 解 1 n 1 2 n i n j n k n 111 3 1 3 x 0 y 0 for int i 1 i n i for int j 1 j i j for int k 1 k j k x x y 3 6 2 1 nn n 2 1 2 1 6 12 1 2 1 2 1 2 1 2 1 1 11 2 111111 nnnnn ii ii j n i n i n i i j j k n i i j n i 1 3 指出下列个算法的功能 并求其时间复杂度 1 int sum1 int n int p 1 s 0 for int i 1 i n i p i s p return s 2 int sum2 int n int s 0 for int i 1 i n i int p 1 for int j 1 j i j p j s p return s 解 1 T n O n n 1i i 2 T n O n2 n 1i i 1 4 算法设计 有 3 枚硬币 其中有 1 枚是假的 伪币与真币重量略有不同 如何借用一 架天平 找出伪币 以流程图表示算法 上机练习题上机练习题 要求 给出问题分析 算法描述 源程序及运行截图 在线提交 1 设 a b c 为 3 个整数 求其中位于中间值的整数 开始 A B A C A是伪币 C是伪币 B是伪币 结束 是 是 否 否 第第 2 章章 线性表线性表 1 设计算法 在顺序表中删除值为 e 的元素 删除成功 返回 1 否则 返回 0 int Sqlist DeleteElem T e for i 1 i length i 按值顺序查找 i 可从 0 开始 if elem i 1 e 找到 进行删除操作 for j i j length j ai 至 an 依次前移 Elem j 1 elem j length 表长减一 return 1 删除成功 返回 1 return 0 未找到 删除不成功 返回 0 2 分析顺序表中元素定位算法 int SqList Locate T e 的时间复杂度 解 设表长为 n 等概率下 每个元素被定位的概率为 p 1 n 定位成功第 i 个元素 需比较 i 次 2 1 2 1 111 11 nnn n i n i n nf n i n i 3 对于有头结点的单链表 分别写出定位成功时 实现下列定位 语句序列 1 定位到第 i 个结点 ai p head j 0 while p j 2 定位到第 i 个结点的前驱 ai 1 p head j 0 while p j 3 定位到尾结点 p head while p next p p next 4 定位到尾结点的前驱 p head while p next next p p next 4 描述一下三个概念的区别 头指针 头结点 首元结点 并给 予图示 头指针 是一个指针变量 里面存储的是链表中首结点的地址 并以此来标识一个链表 头结点 附加在第一个元素结点之前的一个结点 头指针指向头结点 首元结点 指链表中的第一个元素结点 头头结结点点 a1a2 an a1a2 an 首首 元元 结结点点 尾尾 元元 结结点点 头头指指针针 5 对于无头结点单链表 给出删除第 i 个结点的算法描述 template T LinkList Delete int i template T LinkList Delete int i 在单链表上删除第 i 个数据元素 if head NULL throw 表空 空表 不能删 else if i 1 删除第 1 个元素 p Head x p data 保存被删元素值 Head p next delete p else 元素定位到第 ai 1 p Head j 1 定位查找起始位置 while p next j if p next j i 1 定位失败 throw 删除位置不合理 else 定位成功 进行结点删除 q p next x p data p next q next delete q retrun x 返回被删除元素值 6 用教材定义的顺序表的基本操作实现下列操作 template int DeleteElem SqList L T e include SqList h template int DeleteElem SqList L T e i L LocateElem e 按值查找 if i 未找到 return 0 else 找到 delete i 删除被找到的元素 7 已知 L 是有表头结点的单链表 且 P 结点既不是首元结点 也不是尾结点 试写出实现下列功能的语句序列 1 在 P 结点后插入 S 结点 2 在 P 结点前插入 S 结点 3 在表首插入 S 结点 4 在表尾插入 S 结点 解 1 s next p next p next s 2 q L while q next p q q next s next p 或 q next q next s 3 s next L next L next s 3 q L while q next NULL q q next s next q next q next s 上机练习题 要求 给出问题分析 算法描述 源程序及运行截图 在线提交 编程实现 删除单链表中值为 e 的元素 第第 3 章章 栈与队列栈与队列 1 铁路进行列车调度时 常把站台设计成栈 式结构的站台 如右图所示 试问 若进站 的六辆列车顺序如上所述 那么是否能够得到 325641 和 154623 的出站序列 如果不能 说 明为什么不能 如果能 说明如何得到 即写 出 进栈 或 出栈 的序列 解 325641 可以 154623 不可以 1 2 3 4 5 6 2 简述以下算法的功能 栈的元素类型为 int 1 status algo 1 SqStack S intint i n A 255 n 0 whilewhile S StackEmpty n A n S Pop forfor i 1 i n i S Push A i 2 status algo 2 SqStack S int e SqStack T int d whilewhile S tackEmpty d S Pop ifif d e T Push d whilewhile T StackEmpty d T Pop T Push d 解 1 借助一个数组 将栈中的元素逆置 2 借助栈 T 将栈 S 中所有值为 e 的数据元素删除之 3 编写一个算法 将一个非负的十进制整数 N 转换为 B 进制数 并输出转换后的结果 当 N 248D B 分别为 8 和 16 时 转换 后的结果为多少 include stack h int NumTrans int N int B 十进制整数 N 转换为 B 进制数 stack S 建立一个栈 while N 0 N 非零 i N B 从低到高 依次求得各位 N N B S push i 各位入栈 while S StackEmpty 栈不空 i S pop If i 9 i A 10 i cout S pop 依次出栈 得到从高到低的输出结果 4 借且栈 设计算法 假设一个算术表达式中包含 括号 对一个合法的数学表达式来说 括号 和 应是相互匹配的 若匹配 返回 1 否则 返回 0 解 以字符串存储表达式 也可以边输入边判断 顺序扫描表达式 左括号 入栈 右括号 如果此时栈空 表示多右括号 不 匹配 如果栈不空 出栈一个左括号 扫描结束 如果栈空 表示括号匹配 否则 括号不匹配 多左括号 int blank match char exp 用字符串存表达式 SqStack s 创建一个栈 char p exp 工作指针 p 指向表达式首 while p 不是表达式结束符 switch p case 左括号 入栈 s push ch break case 右括号 if s StackEmpty return 0 栈空 不匹配 多右括号 else s Pop break 左括号出栈 switch p 取表达式下一个字符 while if s StackEmpty 表达式结束 栈不空 return 0 不匹配 多左括号 else return 1 匹配 5 简述栈和队列的逻辑特点 各举一个应用实例 6 写出下列中缀表达式的后缀表达式 1 A B C D 2 A B D E F A D C 3 A while i 1 cout 1 cour x if x 0 sum 0 else test sum sum x cout x while x S push x cin x sum 0 cout sum while x S pop sum x cout sum 10 简述以下算法的功能 栈和队列的元素类型均为 int 解 利用栈 将队列中的元素逆置 voidvoid algo Queue 创建一个栈 intint d whilewhile Q QueueEmpty d DeQueue Q S Push d whilewhile S StackEmpty d S Pop Q EnQueue d 12 假设以数组 se m 存放循环队列的元素 同时设变量 rear 和 front 分别作为队首 队尾指针 且队首指针指向队首前一个位 置 队尾指针指向队尾元素处 初始时 rear fornt 1 写出 这样设计的循环队列入队 出队的算法 解 采用教材队空与队满判别方法 为了区分队空与队满条件 牺牲一个元素空间 即 rear front 为队空 rear front 1 m 为队满 template void EnQueue T Se T e int m 入队 if rear 1 m fornt 队满 不能插入 throw 队满 不能插入 else rear rear 1 m 队尾指针后移 se rear e 元素入队 return template T DnQueue T Se int m 出队 if rear fornt 队空 不能出队 throw 队空 不能出队 else front front 1 m 指针后移 指向队首元素 e se front 取队首元素 return e 上机练习题 要求 给出问题分析 算法描述 源程序及运行截图 在线提 交 1 借助栈 实现单链表上的逆置运算 第第 4 章章 串串 1 试问执行以下函数会产生怎样的输出结果 void demonstrate StrAssign s THIS IS A BOOK StrRep s StrSub s 3 7 ESE ARE StrAssign t StrConcat s S StrAssign u XYXYXYXYXYXY StrAssign v StrSub u 6 3 StrAssign w W cout t t endl cout v v cout u StrRep u v w demonstrate 解 t THESE ARE BOOKS v YXY w XWXWXW 2 设字符串 S aabaabaabaac P aabaac 1 给出 S 和 P 的 next 值和 nextval 值 2 若 S 作主串 P 作模式串 试给出 KMP 算法的匹配过程 1 S 的 next 与 nextval 值分别为 012123456789 和 002002002009 p 的 next 与 nextval 值分别为 012123 和 002003 2 利用 KMP 算法的匹配过程 第一趟匹配 aabaabaabaac aabaac i 6 j 6 第二趟匹配 aabaabaabaac aa baac 第三趟匹配 aabaabaabaac 成功 aa baac 3 算法设计 串结构定义如下 struct SString char data 串首址 int len 串长 int StrSize 存放数组的最大长度 1 编写一个函数 计算一个子串在一个字符串中出现的次数 如果不出现 则为 0 int str count SString S SString T 解 int str count SString S SString T int i j k count 0 for i 0 S data i i for j i k 0 S data j T data k j k if k T len 1 count return count 2 编写算法 从串 s 中删除所有和串 t 相同的子串 解 int SubString Delete SString i s len t len i for j 0 j t len 找到了与 t 匹配的子串 for k i k s len t len k s k s k t len 左移删除 s len t len n 被删除次数增 1 for return n Delete SubString 2 编写一个函数 求串 s 和串 t 的一个最长公共子串 void maxcomstr SString s SString t 解 void maxcomstr SString s SString t int index 0 len1 0 i j k len2 i 0 作为扫描 s 的指针 while i s len j 0 作为扫描 t 的指针 while j len1 将较大长度者给 index 和 len1 index i len1 len2 j len2 if else j while cout 最长公共子串 for i 0 i len1 i cout s data index 1 1 已知下列字符串 a THIS f A SAMPLE c GOOD d NE b s StrConcat a StrConcat StrSub f 2 7 StrConcat b StrSub a 3 2 t StrRep f StrSub f 3 6 c u StrConcat StrSub c 3 1 d g IS v StrConcat s StrConcat b StrConcat t StrConcat b u 试问 s t v StrLength s StrIndex v g StrIndex u g 各是什 么 已知 s XYZ t X Z Y 试利用下列运算 将 s 转化 为 t 联接 StrConcat 串长 int StrSize 存放数组的最大长度 求 串 S 所含不同字符的总数和每种字符的个数 不区分英文 字母的大小写 第第 5 章章 数组与压缩矩阵数组与压缩矩阵 1 假设有二维数组 A6 8 每个元素用相邻的 6 个字节存储 存储器按 字节编址 已知 A 的起始存储位置 基地址 为 1000 计算 1 数组 A 的体积 即存储量 2 数组 A 的最后一个元素 a57 的第一个字节的地址 3 按行存储时 元素 a14 的第一个字节的地址 4 按列存储时 元素 a47 的第一个字节的地址 解 1 6 8 6 288Byte 2 1000 288 6 1282 3 1000 1 8 4 6 1072 4 1000 7 6 4 6 1276 2 假设按低下标优先存储整数数组 A9 3 5 8时 第一个元素的字节地址 是 100 每个整数占四个字节 问下列元素的存储地址是什么 1 a0000 2 a8247 解 1 100 2 100 8 3 5 8 2 5 8 4 8 7 4500 3 一个稀疏矩阵如图所示 1 给出三元组存储示意图 2 给出带行指针向量的链式存储示意图 3 十字链表存储示意图 1 2 153 903 531 211 310 eji 153 903 531 211 310 ejiM data M mu4 M nu6 M tu5 0 1 2 3 4
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年多元文化教育研究生入学考试试卷及答案
- 2025年公共卫生政策与管理知识考试题及答案
- 2025年财务管理核心知识考试题及答案
- 标书文件-救护车、车载医疗设备公开招标文件
- 给排水工程施工方案及质量保证措施
- 中医病例首页填写
- 城市旧区改造拆迁补偿房产购买协议书
- 信息技术安全采购补充协议范本
- 茶馆及茶艺表演权转让协议范本
- 创优实施样板图例
- 《生物质热电联产工程设计规范》
- 康复设备一览表
- JJG 643-2024标准表法流量标准装置
- 小学生1-6年级成长档案模板(绝对原创)
- 22秋可编程控制器应用实训形考任务1-6答案
- 《中国人口老龄化》课件
- 半导体器件物理与工艺期末考试题
- TBM主要技术参数
- abb焊接机器人编程
- 吉林开放大学《集装箱班轮运输业务与法律》终结性考试复习题库(附答案)
- 曲阜师范大学基础乐理期末复习题
评论
0/150
提交评论