数据结构习题(有答案)

第 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