数据结构作业答案(大连理工大学).pdf

数据结构作业 2013 作业作业 1 1 线性表线性表 编程作业 1 将顺序表逆置 要求用最少的附加空间 参考答案参考答案 include include include define LIST INIT SIZE 100 define LISTINCREMENT 10 define TRUE 1 define FALSE 0 define OK 1 define ERROR 0 define INFEASIBLE 1 define OVERFLOW 2 typedef int Status typedef int ElemType typedef struct ElemType elem int length int listsize SqList 创建空顺序表创建空顺序表 Status InitList Sq SqList if L elem exit OVERFLOW L length 0 数据结构作业 2013 L listsize LIST INIT SIZE return OK 顺序表在第顺序表在第 i 个元素之前插入个元素之前插入 e Status sxbcr SqList if iL length 1 return ERROR else q for p p q p p 1 p q e L length return OK 顺序表显示顺序表显示 void xsList SqList L int i L length k for k 0 k i k printf d L elem k printf n 顺序表逆置顺序表逆置 void nizhi SqList ElemType temp for i10 20 30 40 3 InsertList 在有序单链表中插入元素 x 4 ReverseList 单链表就地逆置 5 DelList 在有序单链表中删除所有值大于 mink 且小于 maxk 的 元素 选作 使用文本菜单完成功能选择及执行 参考答案 参考答案 include include include define TRUE 1 define FALSE 0 define OK 1 define ERROR 0 define INFEASIBLE 1 define OVERFLOW 2 数据结构作业 2013 typedef int Status typedef int ElemType typedef struct node ElemType data struct node link Lnode LinkList 头插法建立单链表头插法建立单链表 void Create L1 LinkList int i L LinkList malloc sizeof Lnode L link NULL for i n i 0 i p LinkList malloc sizeof Lnode scanf d p link L link L link p 尾插法建立单链表尾插法建立单链表 void Create L2 LinkList int i L LinkList malloc sizeof Lnode L data 0 L link NULL p L for i 1 idata 数据结构作业 2013 s link NULL p link s p s 查找是否存在结点查找是否存在结点 e LinkList dlbcz LinkList L ElemType e LinkList p L link while p NULL return p 在第在第 i 个元素之前插入结点个元素之前插入结点 e Status ListInsert L LinkList L int i ElemType e LinkList p L s int j 0 while p j if p j i 1 return ERROR s LinkList malloc sizeof Lnode s data e s link p link p link s return OK 删除第删除第 i 个结点个结点 Status ListDelete L LinkList L int i ElemType int j 0 while p link j if p link j i 1 return ERROR q p link p link q link e q data free q return OK 求第求第 i 个元素值个元素值 Status GetElem L LinkList L int i ElemType LinkList p L link while p j if p j i return ERROR e p data return OK 显示单链表中元素显示单链表中元素 void xsList LinkList L LinkList p L link while p printf d p data p p link 删除大于删除大于 mink 且小于且小于 maxk 的元素的元素 void DelList LinkList while p link q p while q p link q 就地升序排序就地升序排序 void sh sort LinkList p link NULL while q p L link pre L while p p p link u q link pre link q q link p q u 就地逆置就地逆置 void nizhi LinkList p link NULL while q u q link 数据结构作业 2013 q link L link L link q q u 有序表插入有序表插入 void yxcharu LinkList pre L p L link while p s LinkList malloc sizeof Lnode s data e s link p pre link s main LinkList L int n i mink maxk ElemType e char choice 0 while choice q printf n n printf 1 建立单链表建立单链表 printf 2 取元素值取元素值 printf 3 查找查找 n 数据结构作业 2013 printf 4 插入插入 printf 5 删除删除 printf 6 显示显示 n printf 7 删除大于删除大于 mink 且小于且小于 maxk 的元素值的元素值 printf 8 就地升序排序就地升序排序 n printf 9 就地逆置就地逆置 printf a 有序表插入有序表插入 printf q 退出退出 n printf n 请选择操作 请选择操作 fflush stdin scanf c switch choice case 1 printf 请输入单链表中结点个数 请输入单链表中结点个数 scanf d Create L2 L n break case 2 printf 请输入元素位序请输入元素位序 scanf d GetElem L L i e printf 元素值为元素值为 d n e break case 3 printf 请输入要查找的元素请输入要查找的元素 scanf d if dlbcz L e 数据结构作业 2013 printf 查找成功查找成功 else printf 查找失败查找失败 break case 4 printf 请输入插入位置请输入插入位置 scanf d printf 请输入要插入的元素请输入要插入的元素 scanf d if ListInsert L L i e printf 插入成功 单链表为 插入成功 单链表为 else printf 插入失败插入失败 break case 5 printf 请输入删除请输入删除位置 位置 scanf d if ListDelete L L i e printf 删除成功 删除成功 else printf 删除失败删除失败 n break case 6 printf n 单链表为 单链表为 xsList L break case 7 printf 请输入请输入 mink 和和 maxk scanf d d DelList L mink maxk break case 8 sh sort L 数据结构作业 2013 break case 9 nizhi L break case a printf 请输入在有序表中插入的元素值请输入在有序表中插入的元素值 scanf d yxcharu L e break 作业作业 2 2 栈栈 队列队列 数组数组 非编程作业 1 若进栈序列为 ABCD 请写出全部可能的出栈序列和不可能的出栈序列 参考答案参考答案 可能的出栈序列 14 种 dcba cdba bacd cbda adcb cbad bdca acdb bcda acbd bcad abdc badc abcd 不可能的出栈序列 10 种 dbca dbac dabc dacb dcab cabd cdab bdac cadb adbc 2 简要说明循环队列如何判断队满和队空 参考答案参考答案 数据结构作业 2013 当牺牲一个存储结点 约定以 队列头指针在队列尾指针的下一位置 指 环状的下一个位置 上 作为队列 满 状态的标志时 循环队列判断队满的条件 为 rear 1 MaxQsize front 判断队空的条件为 front rear 3 设A为n阶对称矩阵 采用压缩存储存放于一维数组F n n 1 2 中 从F 0 开始存放 请分别给出存放上三角阵时任一矩阵元素 aij 1 i j n 的 地址计算公式和存放下三角阵时任一矩阵元素 aij 1 i j n 的地址计算 公式 参考答案参考答案 存放上三角阵时 任一矩阵元素 aij 1 i j n 的地址计算公式为 i j11 1 Loc a Loc a 1 2 ii jl 存放下三角阵时 任一矩阵元素 aij 1 i j n 的地址计算公式为 ij11 1 Loc a Loc a 1 2 jj il 4 写出下面稀疏矩阵的三元组顺序表和十字链表表示 400000 503008 000000 000700 200000 A 数据结构作业 2013 参考答案参考答案 编程作业 栈采用顺序栈存储 试设计算法实现将表达式转换成后缀表达式输出 例如 输入表达式 a b c d e f g 输出其后缀表达式 abc de f g 参考答案参考答案 include include include define OVERFLOW 2 define OK 1 define ERROR 0 数据结构作业 2013 define STACK INIT SIZE 100 define STACKINCREMENT 10 typedef int Status typedef char SElemType typedef char string 80 typedef struct SElemType base SElemType top int stacksize SqStack Status InitStack SqStack if S base exit OVERFLOW S top S base S stacksize STACK INIT SIZE return OK Status ClearStack SqStack if S base exit OVERFLOW S top S base S stacksize STACK INIT SIZE return OK void DestroyStack SqStack if S base free S base S base S top NULL Status StackEmpty SqStack S if S top S base return true else return false SElemType GetTop SqStack S 数据结构作业 2013 SElemType e if S top S base e S top 1 return e Status Push SqStack if S base exit OVERFLOW S top S base S stacksize S stacksize STACKINCREMENT S top e return OK Status Pop SqStack e S top return OK Status InOP SElemType c char Operators 0 int len strlen Operators for int i 0 i break case case order break break case case switch curtop case case case case order break break case switch curtop case order break case order break case order break case order break case order break case order break case order break case order break case order break 数据结构作业 2013 case order break case order break break case switch curtop case order break case order break case order break case order break case order break case order break break return order void Pass string Suffix SElemType ch Suffix ch void Transform string Infix string Suffix SqStack S SElemType ch e int flag 0 len InitStack S Push S len strlen Infix Infix len ch Infix while StackEmpty S if InOP ch Pass Suffix ch else switch Precede GetTop S ch case Pop S e Pass Suffix e flag 1 break if flag if ch ch Infix Pass Suffix 0 DestroyStack S void main string Infix Suffix gets Infix Transform Infix Suffix puts Suffix 作业作业 3 3 树树 非编程作业 1 请分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态 参考答案参考答案 具有 3 个结点的树 数据结构作业 2013 具有 3 个结点的二叉树 2 已知二叉树的先序遍历序列是 EABDCFHGIKJ 中序遍历序列是 ABCDEFGHIJK 请构造二叉树 并写出其层次遍历序列和后序遍历序 列 参考答案参考答案 层次 E A F B H D G I C K J 后序 C D B A G J K I H F E E A C B D I J H F G K 数据结构作业 2013 3 将下图所示的森林转换成一棵二叉树 A BCD G HIJ K EF L 参考答案参考答案 转换成的二叉树为 B A C D F G E H I J K L 数据结构作业 2013 4 将下图所示的二叉树还原成树或森林 A B C D G H I J K E F L M N 参考答案参考答案 转换为森林 5 假设用于通信的电文由 7 个字母组成 A B C D E F G 字母在电文中出现 的频率分别为 0 17 0 09 0 12 0 06 0 32 0 03 0 21 试为这 7 个 A C H B F D M E G N J I K L 数据结构作业 2013 字母设计哈夫曼编码 并计算其带权路径长度 WPL 参考答案参考答案 哈夫曼树为 WPL 4 0 03 0 06 3 0 12 0 17 0 09 2 0 32 0 21 2 56WPL 4 0 03 0 06 3 0 12 0 17 0 09 2 0 32 0 21 2 56 A 101 B 001 C 100 D 0001 E 11 F 0000 G 01A 101 B 001 C 100 D 0001 E 11 F 0000 G 01 编程作业 二叉树采用二叉链表存储 试设计算法实现 1 CreateBT BiTree struct BiTNode lchild rchild BiTNode BiTree 输入先序序列 创建二叉树的二叉链表 void CreateBT BiTree scanf c if ch T NULL else T BiTNode malloc sizeof BiTNode T data ch CreateBT T lchild CreateBT T rchild 交换二叉树中结点的左右孩子 void ExchangeBT BiTree T BiTree temp if T temp T lchild T lchild T rchild T rchild temp ExchangeBT T lchild ExchangeBT T rchild 先序遍历二叉树 void PreOrderTraverse BiTree T if T printf c T data 数据结构作业 2013 PreOrderTraverse T lchild PreOrderTraverse T rchild 查找值为 x 的结点 BiTree SearchTree BiTree T char X BiTree bt if T if T data X return T bt SearchTree T lchild X if bt NULL bt SearchTree T rchild X return bt return NULL 统计以 T 为根的子树中叶子结点数 int LeafCount1 BiTree T static int count if T if T lchild NULL else count LeafCount1 T lchild count LeafCount1 T rchild return count void LeafCount2 BiTree T int 数据结构作业 2013 LeafCount2 T lchild count LeafCount2 T rchild count 按树状打印输出二叉树的元素 level 表示结点的层次 void DispBiTree BiTree T int level int i if T DispBiTree T rchild level 1 for i 0 i data DispBiTree T lchild level 1 void main BiTree T SubT char Subch int countl 0 printf 输入先序序列建立二叉树 n CreateBT T printf n 二叉树的先序序列 PreOrderTraverse T printf n 二叉树为 n DispBiTree T 0 printf 交换结点的左右孩子 n ExchangeBT T printf n 此时二叉树为 n DispBiTree T 0 数据结构作业 2013 printf 输入要统计叶子结点个数的子树的根 fflush stdin scanf c SubT SearchTree T Subch countl LeafCount1 SubT LeafCount2 SubT countl printf 叶子结点数为 d n countl 作业作业 4 4 图图 非编程作业非编程作业 1 已知带权有向图如图所示 画出该图的邻接矩阵存储结构 参考答案 参考答案 2 a f b d g c h e 6 9 7 8 3 2 5 1 30 24 21 0269 0301 05 02 807 3024 021 0 a b c d e f g h a b c d e f g h 0269 0301 05 02 807 3024 021 0 a b c d e f g h a b c d e f g h 数据结构作业 2013 2 无向图邻接表存储结构如图所示 1 画出该无向图 2 写出在该邻接表上 从顶点1出发所得到的深度优先遍历 DFS 和广度优先 遍历 BFS 序列 2 1 4 3 5 7 6 2 1 4 3 5 7 6 88 3 2 4 4 6 57 8 8 8 1 1 3 2 4 4 4 76 5 参考答案 参考答案 DFS 1 3 4 7 8 6 5 2 BFS 1 3 2 4 7 6 5 8 作业作业 5 5 查找查找 排序排序 非编程作业 非编程作业 1 3 2 4 7 5 8 6 数据结构作业 2013 1 对下标为 1 9 的有序表进行折半查找 画出折半查找的判定树 并计算在等 概率情况下查找成功的平均查找长度 ASL 参考答案 参考答案 2 设有关键字序列 25 40 33 47 12 66 72 87 94 22 5 58 散 列表长 12 散列函数为 h key key 11 用线性探查再散列 链地址法处理冲 突 请分别画出散列表 并计