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

1、数据结构作业答案(大连理工大学)作业1. 线性表l 编程作业：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 -2typedef int Status;typedef int ElemType;typede

2、f struct ElemType *elem; int length; int listsize; SqList;立单链表 ");printf("2.取元素值 ");printf("3.查找 n");printf("4.插入 ");printf("5.删除 ");printf("6.显示n");printf("7.删除大于mink且小于maxk的元素值 ");printf("8.就地升序排序n");printf("9.就地逆置 &qu

3、ot;);printf("a.有序表插入 ");printf("q.退出n");printf("n请选择操作：");fflush(stdin);scanf("%c",&choice);switch(choice)case '1': printf("请输入单链表中结点个数："); scanf("%d",&n); Create_L2(L,n); break;case '2': printf("请输入元素位序：")

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

5、("%d",&i); printf("请输入要插入的元素："); scanf("%d",&e); if(ListInsert_L(L,i,e) printf("插入成功！单链表为："); else printf("插入失败。"); break;case '5': printf("请输入删除位置："); scanf("%d",&i); if(ListDelete_L(L,i,e) printf("删除成功！&

6、quot;); else printf("删除失败。n"); break;case '6': printf("n单链表为："); xsList(L); break;case '7': printf("请输入mink和maxk:"); scanf("%d,%d",&mink,&maxk); DelList(L,mink,maxk); break;case '8': sh_sort(L); break;case '9': nizhi(L);

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

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

9、i,jn）的地址计算公式为：存放下三角阵时，任一矩阵元素aij（1i,jn）的地址计算公式为：4 写出下面稀疏矩阵的三元组顺序表和十字链表表示。参考答案：l 编程作业栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。例如，输入表达式： a+b/c-(d*e+f)*g 输出其后缀表达式：abc/+de*f+g*- 参考答案：#include <>#include <>#include <>#define OVERFLOW -2#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100 #define

10、 STACKINCREMENT 10 typedef int Status;typedef char SElemType; typedef char string80; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; Status InitStack(SqStack &S) =(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType);if(! exit(OVERFLOW);=; =STACK_INIT_SIZE; return(OK);Sta

11、tus ClearStack(SqStack &S)=(SElemType*)realloc,STACK_INIT_SIZE *sizeof(SElemType); if(! exit(OVERFLOW); =; =STACK_INIT_SIZE; return(OK);void DestroyStack(SqStack &S)=0;iffree;=NULL;Status StackEmpty(SqStack S)if=return true;elsereturn false;SElemType GetTop(SqStack S) SElemType e;if> e=*;

12、 return e;Status Push(SqStack &S, SElemType e) if 树l 非编程作业：1 请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。参考答案：具有3个结点的树： 具有3个结点的二叉树： 2 已知二叉树的先序遍历序列是EABDCFHGIKJ，中序遍历序列是ABCDEFGHIJK，请构造二叉树，并写出其层次遍历序列和后序遍历序列。参考答案：EACBDIJHFGK 层次：E A F B H D G I C K J 后序-C D B A G J K I H F E3 将下图所示的森林转换成一棵二叉树。参考答案：BACDFGEHIJKL转换成的二

13、叉树为：4 将下图所示的二叉树还原成树或森林。参考答案：转换为森林：ACHBFDMEGNJIKL5 假设用于通信的电文由7个字母组成A,B,C,D,E,F,G，字母在电文中出现的频率分别为、。试为这7个字母设计哈夫曼编码，并计算其带权路径长度WPL。参考答案： 1AEGBDF哈夫曼树为：WPL=4*+3*+2*+=A:101 B:001 C:100 D:0001 E:11 F:0000 G:01l 编程作业：二叉树采用二叉链表存储，试设计算法实现：1 CreateBT(BiTree &T)：从键盘输入二叉树的先序遍历序列字符串（以”#”代表空结点），建立其二叉链表；如输入：AB#D#C

14、E#F# 则建立如下图所示二叉树的二叉链表2 ExchangeBT(BiTree T): 设计递归算法实现二叉树中所有结点的左右孩子交换；3 CountLeaf(BiTree T, TElemType x, int &count): 统计以值为x的结点为根的子树中叶子结点的数目；4 DispBiTree(BiTree T, int level) : 按树状打印二叉树。BCFAED 打印得到：#C#F#EA#D#B提示：对于根为T，层次为level的子树： 打印其下一层(level+1层)右子树； 打印根结点； 打印其下一层(level+1层)左子树； *结点左边的#个数为其层次数*参考

15、答案：#include <>#include <>typedef struct BiTNodechardata;struct BiTNode *lchild,*rchild;BiTNode, *BiTree;图l 非编程作业:1 已知带权有向图如图所示，画出该图的邻接矩阵存储结构。2aafbdgcheA69783251302421参考答案：2 无向图邻接表存储结构如图所示：(1) 画出该无向图；(2) 写出在该邻接表上，从顶点1出发所得到的深度优先遍历(DFS)和广度优先遍历(BFS)序列。参考答案：13247586DFS：1，3，4，7，8，6，5，2 BFS：1，3

16、，2，4，7，6，5，8 作业5. 查找、排序l 非编程作业：1 对下标为19的有序表进行折半查找，画出折半查找的判定树；并计算在等概率情况下查找成功的平均查找长度ASL。参考答案：2 设有关键字序列25，40，33，47，12，66，72，87，94，22，5，58，散列表长12，散列函数为h(key)=key%11，用线性探查再散列、链地址法处理冲突，请分别画出散列表，并计算。参考答案：线性探查再散列处理冲突：链地址法处理冲突：3 已知待排序序列为50，86，72，41，45，93，57，46，请写出按下列排序方法进行升序排序时的第一趟排序结果： 直接插入排序； 冒泡排序； 简单选择排序； 堆排序初建堆序列。参考答案：第一趟直接插入排序：50，86，72，41，45，93，57，46第一趟冒泡排序： 50，72，41，45，86，57，46，93第一趟简单选择排序：41，86，72，50，45，93，57，46堆排序初建堆序列 ：