大连理工大学《数据结构》作业2016-参考答案

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

2、ElemType *elem; int length; int listsize; SqList; /创建空顺序表创建空顺序表 Status InitList_Sq( SqList if (!L.elem) exit(OVERFLOW); L.length = 0; 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.l

3、ength; return (OK); /顺序表显示顺序表显示 void xsList(SqList L) int i=L.length,k; for(k=0;ki;k+) printf(%d ,L.elemk); printf(n); /顺序表逆置顺序表逆置 void nizhi(SqList ElemType temp; for(;i10-20-30-40）; （3） InsertList()：在有序单链表中插入元素 x； （4） ReverseList()：单链表就地逆置； （5） DelList()：在有序单链表中删除所有值大于 mink 且小于 maxk 的 元素。 选作：使用文本菜

4、单完成功能选择及执行。 参考答案：参考答案： #include #include 数据结构作业参考答案 #include #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 node ElemType data; struct node *link; Lnode, *LinkList; /头插法建立单链表头插法建立单链表 void

5、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=

6、1;idata); 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 = (L

7、inkList) 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 个元素值个元素值

8、Status GetElem_L(LinkList L, int i, ElemType LinkList p=L-link; while(p j+; if(!p|ji) 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 数据结构作业参考答案

9、 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; q-link=L-link; L-link=q; q=u; 数据结构作业参考答案 /有序表插入有序表插入 void yxcharu(LinkList pre=L; p=

10、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); printf(4.插入插入 ); printf(5.删除删除 ); printf(6.显示显示n); printf(7.删

11、除大于删除大于 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(请输入元素位序请输入元素

12、位序：); scanf(%d, GetElem_L(L,i,e); printf(元素值为元素值为：%dn,e); break; case 3: printf(请输入要查找的元素请输入要查找的元素：); scanf(%d, if(dlbcz(L,e) printf(查找成功查找成功！); else printf(查找失败。查找失败。); break; case 4: printf(请输入插入位置请输入插入位置：); scanf(%d, printf(请输入要插入的元素请输入要插入的元素：); scanf(%d, if(ListInsert_L(L,i,e) printf(插入成功！单链表为：插

13、入成功！单链表为：); 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

14、; case 8: sh_sort(L); break; case 9: nizhi(L); break; case a: printf(请输入在有序表中插入的元素值请输入在有序表中插入的元素值:); scanf(%d, yxcharu(L,e); break; 作业作业 2. 栈、队列、数组栈、队列、数组 非编程作业： 1 若进栈序列为 ABCD，请写出全部可能的出栈序列和不可能的出栈序列。 参考答案参考答案： 可能的出栈序列：(14 种) dcba cdba bacd cbda adcb cbad bdca acdb bcda acbd bcad abdc badc abcd 不可能的出栈

15、序列：(10 种) dbca dbac dabc dacb dcab cabd cdab bdac cadb adbc 2 简要说明循环队列如何判断队满和队空？ 参考答案：参考答案： 当牺牲一个存储结点，约定以“队列头指针在队列尾指针的下一位置（指环 状的下一个位置） 上” 作为队列“满”状态的标志时， 循环队列判断队满的条件为： (rear+1) % MaxQsize=front；判断队空的条件为：front = rear。 3 设 A 为 n 阶对称矩阵， 采用压缩存储存放于一维数组 Fn(n+1)/2中 （从 F0 开始存放） ，请分别给出存放上三角阵时任一矩阵元素 aij（1i,jn）

16、的地址 计算公式和存放下三角阵时任一矩阵元素 aij（1i,jn）的地址计算公式。 参考答案：参考答案： 存放存放下下三角阵时三角阵时，任一矩阵元素 aij（1i,jn）的地址计算公式为： i j1 1 -1 Loc(a )=Loc(a )+1* 2 ii jl ij 数据结构作业参考答案 i j1 1 -1 Loc(a )=Loc(a )+1* 2 jj il 存放存放上上三角阵时三角阵时，任一矩阵元素 aij（1i,jn）的地址计算公式为： 4 写出下面稀疏矩阵的三元组顺序表和十字链表表示。 参考答案：参考答案： 编程作业 栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。 例

17、如，输入表达式： a+b/c-(d*e+f)*g 输出其后缀表达式：abc/+de*f+g*- 参考答案：参考答案： #include #include #include 400000 503008 000000 000700 200000 A ij ij11 -1 Loc(a )=Loc(a )+* 2 2n+2-ii jil ij ij11 -1 Loc(a )=Loc(a )+* 2 2n+2- jj ijl ij 数据结构作业参考答案 #define OVERFLOW -2 #define OK 1 #define ERROR 0 #define STACK_INIT_SIZE 100

18、 #define STACKINCREMENT 10 typedef int Status; typedef char SElemType; typedef char string80; 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

19、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) SElemType e; if(S.topS.base) e

20、=*(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; cas

21、e (: 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=; bre

22、ak; case *: order=; break; case /: order=; break; 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

23、 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)

24、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. 树树 非编程作业： 1 请分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态。 参考答案：参考答案： 具有 3 个结点的树： 具有 3

25、 个结点的二叉树： 数据结构作业参考答案 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 3 将下图所示的森林转换成一棵二叉树。 A BCD G HIJ K EF L 参考答案：参考答案： 转换成的二叉树为： E A C B D I J H F G K B A C D F G E H I J K L 数据结构作业参考答案 4 将下图所示的二叉树还原成树或森林。 A B C D

26、 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 个字 母设计哈夫曼编码，并计算其带权路径长度 WPL。 参考答案：参考答案： 哈夫曼树为： WPL=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:01 A C H B F D M E G N J I K

27、L 1 0.39 0.61 0.18 0.21 0.09 0.09 0.29 0.32 0.12 0.17 0.03 0.06 A E G B D F 数据结构作业参考答案 编程作业： 二叉树采用二叉链表存储，试设计算法实现： 1 CreateBT(BiTree struct BiTNode *lchild,*rchild; BiTNode, *BiTree; /输入先序序列，创建二叉树的二叉链表 void CreateBT(BiTree scanf(%c, if (ch = #) T = NULL; else B C F A E D 数据结构作业参考答案 T = (BiTNode *)mal

28、loc(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); PreOr

29、derTraverse(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

30、; if ( T ) if (T-lchild=NULL) else count=LeafCount1( T-lchild); count=LeafCount1( T-rchild); return count; void LeafCount2 (BiTree T, int LeafCount2( T-lchild, count); LeafCount2( T-rchild, count); /按树状打印输出二叉树的元素,level 表示结点的层次 void DispBiTree(BiTree T,int level) int i; if(T) DispBiTree(T-rchild, lev

31、el + 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); DispBi

32、Tree(T,0); printf(输入要统计叶子结点个数的子树的根：); fflush(stdin); scanf(%c, SubT=SearchTree(T,Subch); /countl=LeafCount1(SubT); LeafCount2(SubT, countl); printf(叶子结点数为：%dn,countl); 作业作业 4. 图图 非编程作业非编程作业: 1 已知带权有向图如图所示。 （1）画出该图的邻接矩阵存储结构； （2）求从顶点a到其余各顶点之间的最短路经 及最短路经长度，并给出计算过程。 参考答案：参考答案： （2）从顶点a到其余各顶点之间的最短路经及最短路经长

33、度 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 （1） 邻接矩阵为： 数据结构作业参考答案 2 无向图邻接表存储结构如图所示： (1) 画出该无向图； (2) 写出在该邻接表上， 从顶点 1 出发所得到的深度优先遍历(DFS)和广度优先 遍历(BFS)序列。 2 1 4 3 5 7 6 2 1 4 3 5

34、 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 1 3 2 4 7 5 8 6 数据结构作业参考答案 3. 已知带权无向图如图所示： （1）根据普里姆（Prim）算法，求它的从顶点 a 出发的最 小生成树(写出过程，即添加顶点、边次序)； （2）根据克鲁斯卡尔（Kruskal）算法，求该图的最小生 成树(写出过程，即添加边次序)。 参考答案：参考答案： 普里姆（普里姆（Prim）算法：）算法： a a d a e d 2 a c e d 2 3 a

35、cb e d 1 2 3 4 2 3 4 或添加顶点的顺序为：a, d, e, c, b 克鲁斯卡尔（克鲁斯卡尔（Kruskal）算法：）算法： a cb e d a cb e d 1 a cb e d 1 2 a cb e d 1 2 3 a cb e d 1 2 3 4 或添加边的顺序为：(b,c), (a,d), (d,e), (c,d) 作业作业 5. 查找、排序查找、排序 非编程作业：非编程作业： 1 对下标为 19 的有序表进行折半查找， 画出折半查找的判定树；并计算在等概率 情况下查找成功的平均查找长度 ASL。 参考答案：参考答案： 4 1 3 7 5 6 2 5 a b c e d 2 a