航空工业出版社《数据结构》课后题答案.pdf

第第 1 章章 数据结构导论数据结构导论 一、填空题一、填空题 1集合结构，线性结构，树形结构，图状结构 2顺序存储结构，链式存储结构 3有限性，确定性，可行性，输入，输出 4时间复杂度，空间复杂度 二、分析下面程序段的时间复杂度。二、分析下面程序段的时间复杂度。 1O(m*n) 2O(n2) 三、上机操作题三、上机操作题 1解答： #include void main () float a10; int i, n; float s = 0; printf (“输入数组中元素的个数 n：“); scanf (“%d“, for (i = 0; i void main () int x, y, z, t; printf (“请依次输入 x、y 和 z 的值：n“); scanf (“%d %d %d“, 数据结构 if (x next; /p为链表中第二个结点 r = *list; while (p != NULL) if (p - data q - data) q = p; /保存当前最大值结点 s = r; /保存当前最大值结点的前驱 r = p; /保存 p 所指结点位置 p = p - next; /p 指向下一结点 if (q = *list) /链表中第一个结点为最大值结点 *list = (*list) - next; /删除第一个结点 else /最大值结点不是链表的第一个结点 s - next = q - next; /删除 q 所指结点 3 数据结构 free (q); /释放 q 所指结点的空间 3解答： void DeleteItem (DLinkList *list, ElemType item) DNode *q; q = (*list) - next; /q 指向头结点的后继 while (q != *list) if (q - data = item) /q 所指结点的值为 item q - prior - next = q - next; /删除 q 所指结点 q - next - prior = q - prior; free (q); /释放 q 所指结点的空间 q = q - next; /q 指向下一结点 4解答： void InsertItem (DLinkList q, ElemType item) DLinkList p; p = (DLinkList) malloc (sizeof (DNode); /生成新结点 p - data = item; /新结点的数据域赋值 p - prior = q; /将新结点插入到 q 所指结点之后 p - next = q - next; /修改 p 所指结点的指针域 q - next = p; /修改 q 所指结点的后继 p - next - prior = p; /修改 p 的后继结点的前驱 第第 3 章章 栈和队列栈和队列 一、填空题一、填空题 1线性 2栈顶，队尾，队头 3后进先出，先进先出 4 课后习题答案 4数组，指示栈顶元素的位置 5将栈顶指针后移一个位置，将被插入元素放在修改后的栈顶指针所指出的位置 6链式 二、选择题二、选择题 1C 2D 3C 4C 5B 6A 7B 8D 9C 10D 三、上机操作题三、上机操作题 1解答： 表 3-1 算术表达式求值的过程 步骤步骤 OPTR 栈栈OPND 栈栈 当前读入字符步骤当前读入字符步骤OPTR 栈栈OPND 栈当前读入字符栈当前读入字符 1 # 35 8 # / 35 50 2 2 # 35 9 # / 35 50 2 3 # 35 5 10 # 35 25 4 # 35 5 * 11 # 10 5 # * 35 5 10 12 # 10 5 6 # * 35 5 10 / 13 # 10 5 # 7 # 35 50 / 14 # 15 # 2解答： char op7 = +, -, *, /, (, ), #; /算符数组 char cmp77 = , , , , , , , , , , , , , , , , , , , , , , , , , , , = 0 /栈顶元素出栈 str2k + = theta; /出栈元素复制到 str2 中 break; return OK; 3解答： int IsHuiwen (char *S) SeqStack T; int i , len; char t; InitStack ( len = StrLength (S); /求字符串长度 for ( i = 0; i 0 if ( m quelen = MAXSIZE; /进队 void EnQueue (SeqQueue *Q, ElemType e) if (FullQueue (Q) printf (“队已满，无法进队“); Q - elemQ - rear = e; /将 e 插入队尾 Q - rear = (Q - rear + 1) % MAXSIZE; /队尾指针在循环意义上的加 1 Q - quelen +; /队长增 1 /出队 void DeQueue (SeqQueue *Q, ElemType *e) int tmpfront; /设一个临时队头指针 if (Q - quelen = 0) Error(“队已空，无元素可出队“); if (Q - rear Q - quelen) /计算头指针位置 tmpfront = Q-rear - Q-quelen; else tmpfront = Q - rear + MAXSIZE Q - quelen; quelen -; *e = Q-elemtmpfront; /用 e 返回队头元素 第第 4 章章 串和数组串和数组 一、填空题一、填空题 1串中的元素为字符型数据 2两个串的长度相等，并且各个对应位置的字符都相等 3定长顺序存储，堆存储，块链存储，堆存储 41100 5行号，列号，元素值 6三元组，十字链表链式 7元素，表 10 课后习题答案 二、选择题二、选择题 1D 2C D 3A 4C 三、上机操作题三、上机操作题 1解答： /将串 S 的内容复制到串 T 中 void StrCopy (SString *T, SString S) int i; for (i = 0; i chi = S.chi; T - chi = 0; T - length = S.length; /在字符串 S 中查找串 T，并删除 void StrDelete (SString *S, SString T) SString temp; int i, j, flag, k = 0; if (StrLength (*S) = StrLength (T) /开始查找 for (i = 0; i chi + j != T.chj) flag = 0; /与串 T 不相等，则未查找成功 break; else flag = 0; if (flag = 1) /若查找成功，则跳过串 T for (j = 0; j chi; k +; i +; StrCopy (S, temp); /将 temp 复制到 S 中 2解答： /比较串 S 和串 T，若 S=T，则返回 1；否则返回 0 int StrCompare (BLString S, BLString T) Block *p, *q; int i = 0; p = S; q = T; while (p q = q - next; i +; if (i #include typedef char SeqString27; /定义串类型 #define Maxlen 100 /以下两句设置加密及解密映射表 12 课后习题答案 SeqString O riginal=“abcdefghijklmnopqrstuvwxyz“; SeqString Cipher =“ngzqtcobmuhelkpdawxfyivrsj“; /串匹配(子串只有一个字符) int StrMatch (SString S, char c) int i; for (i = 0; i = 0; i -) /将第 1 个至第 n-1 个元素依次后移一个位置 Ai + 1 = Ai; A0 = temp; /将temp中元素赋予数组的第1个元素 5解答： #define MaxN 100 ElemType Saddle (ElemType AMaxN, int m, int n) ElemType mina, maxa; int i, j, ii, jj; for (i = 0; i = Aiijj) ii +; if (ii m - 1) /找到鞍点 Aijj return Aijj; printf (“nThere is no saddle!n“); /不存在鞍点，给出提示信息 14 课后习题答案 6解答： #define MaxN 100 void TransForm (ElemType AMaxN, int m, int n, ElemType TA3) int i, j, t = 0; TA00 = m; /记录稀疏矩阵总行数 TA01 = n; /记录稀疏矩阵总列数 for (i = 0; i #define MaxSize 10 typedef int Datatype; /定义三元组 typedef struct int i,j; Datatype v; TriTupleNode; /定义三元组表 typedef struct TriTupleNode dataMaxSize; int m,n,t; /矩阵行，列及三元组表长度 TriTupleTable; 15 数据结构 /输出稀疏矩阵 void showMatrix(TriTupleTable *a) int p,q; int t=0; for(p=0;pm;p+) for(q=0;qn;q+) if(a-datat.i=p t+; else printf(“0 “); printf(“n“); /以下为矩阵加算法 / void AddTriTuple( TriTupleTable *A, TriTupleTable *B, TriTupleTable *C) /三元组表表示的矩阵 A,B 相加 int p,q,k,l; C-m=A-m;/矩阵行数 C-n=A-n;/矩阵列数 C-t=0; /三元组表长度 C-dataC-t.v=0; /三元组元素初值 k=0; l=0; for(p=0;pm;p+) /行 for(q=0;qn;q+) /列 if(A-datak.i=p/初始化三元组值 C-dataC-t.i=p; C-dataC-t.j=q; C-dataC-t.v+=A-datak.v; if(B-datal.i=p l+; /指向 B 表下一元素 k+; C-t+;/指向 A 表下一元素，C 表长增 1 else if(B-datal.i=p/初始化三元组值 C-dataC-t.i=p; C-dataC-t.j=q; C-dataC-t.v+=B-datal.v; l+; C-t+;/指向 B 表下一元素，C 表长增 1 /以下为测试程序 /主程序 void main() TriTupleTable A=1,3,4,2,2,4,2,4,3,3,3,9; TriTupleTable B=2,3,4,2,4,5; TriTupleTable C; A.m=5; A.n=5; A.t=4; B.m=5; B.n=5; B.t=2; printf(“The Matrix A:nn“); showMatrix( printf(“The Matrix B:nn“); showMatrix( AddTriTuple( printf(“The Matrix C:nn“); showMatrix( 17 数据结构 18 第第 5 章章 树与二叉树树与二叉树 一、填空题一、填空题 1根结点 231，8，16 3n01，n2n01 4，2i，2i1 2/ i 52n，n1，n1 6先序遍历，中序遍历，后序遍历，层次遍历 7HIDJEBFGCA 8前驱 9最优二叉树，带权路径长度WPL最短的二叉树，越近 10ABDCEGF，DBAEGCF，DBGEFCA 二、选择题二、选择题 1C 2B 3B 4C 5A 三、解答题三、解答题 1解答： 前序遍历序列为：ABCEGDFH，该二叉树如图5-1所示。 2解答： WPL346473112152202149 图 5-1 第 1 题 图 5-2 第 2 题 3哈夫曼树如图5-3所示。 A B D C EF G H 62 26 36 111516 20 97 63 课后习题答案 图 5-3 第 3 题 根据上图可得编码表： a:0010 b:10 c:00000 d:0001 e:01 f:00001 g:11 h:0011 四、上机操作题四、上机操作题 1解答： 要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵 子树的指针进行交换，最后一次访问是交换根结点的子树。 /交换子树 void ChangeBinTree(BinTree *T) if(*T) /这里以指针为参数使得交换在实参的结点上进行 /后序遍历 BinTree temp; ChangeBinTree( ChangeBinTree( temp=(*T)-lchild; 19 数据结构 (*T)-lchild=(*T)-rchild; (*T)-rchild=temp; /以前序序列打印结点数据 void PrintNode(BinTree T) if(T) printf(“%c“,T -data); PrintNode(T -lchild); PrintNode(T -rchild); /测试程序 void main() BinTree root; CreatBinTree(/建立二叉链表 PrintNode(root); /输出原表 printf(“n“); ChangeBinTree(/交换子树 PrintNode(root); /输出新表 printf(“n“); 2解答： 以向量为存储结构的完全二叉树，其存储在向量中的结点其实是按层次遍历的次序存放 的。 #include typedef char DataType;/设结点数据类型为char #define M 100/设结点数不超过100 typedef DataType BinTreeM; /以向量结构建立完全二叉树 void CreatBinTree(BinTree *T) int n; int i; printf(“输入结点个数及结点值:“); scanf(“%d “,/输入结点个数 20 课后习题答案 (*T)0=n; /下标为0的结点存储结点个数 for(i=1;i1 else if(j1 pi=Tj;/入队 printf(“%c“,pi);/打印结点值 void main() BinTree T; CreatBinTree( PrintTree(T); 21 数据结构 printf(“n“); Preorder(T);/前序遍历 3解答： #define NodeNum 100 void PreOrder (BTree T) BTree stackNodeNum, p = T; int top = -1; if (T != NULL) do while (p != NULL) visit (p); /访问当前p所指结点 stack+ top = p; /当前p所指结点进栈 p = p - lchild; /p指向其左孩子 p = stacktop -; /栈顶元素出栈 p = p - rchild; /p指向其右孩子 while (p != NULL | top != -1); 第第 6 章章 图图 一、填空题一、填空题 1邻接矩阵，邻接表，十字链表 2邻接矩阵，邻接表，邻接多重表 32m 4出度，入度 51 6无回路的有向图 7活动，活动之间的优先关系 二、选择题二、选择题 1B 2D 22 课后习题答案 23 3C 4B 5A 6A 三解答题三解答题 1解答： 邻接矩阵如图6-1（a）所示，邻接表如图6-1（b）所示。 010011 000001 110100 100010 001001 000000 （a） （b） 图 6-1 第 1 题 2解答： 深度优先遍历序列为：ABDFEGC 广度优先遍历序列为：ABCDEFG 3解答： 最小生成树如图6-2所示。 图 6-2 第 3 题 4解答： 线路图如图6-3所示。 图 6-3 第 4 题 D A B C 0 1 3 5 2 E F 4 5 0 0 1 4 v2v0v4 25 20 v1 v3 v5 25 25 10 数据结构 24 5解答： 表 6-1 第 5 题 a1a2a3a4 a5 a6 a7 a8 a9 a10a11a12a13a14 ee 0569 12 16 14131921 le 0969 12 17 14171921 e 0056 6 9 9 9 121216141319 l 4096 6 9 1313131219141719 存在两条关键路径，如图6-4所示。 图 6-4 第 5 题 完成该工程的最短时间为21个时间单位。 四上机操作题四上机操作题 1解答： #define MaxVNum 100 void ALGraphToMGraph (ALGraph GL, MGraph *GM, int n) int i, j; ArcNode *p; for (i = 0; i arcsij = 0; for (i = 0; i arcsip - adjvex = 1; p = p - next; 2解答： /广度优先判断有向图G中顶点vi到顶点vj是否有路径,是则返回1,否则返回0 int ExistPath (ALGraph G, int i, int j) a2 v9v6v8v0 v2 v4 a5 a10 a12a14 v9 v6v8 v0 v2 v4 a2 a10 a12a14 v3 a4 a6 课后习题答案 Queue Q; int visitedMAXSIZE; InitQueue( EnQueue( while(!QueueEmpty(Q) DeQueue( visitedu=1; for(p=G.vertexi.firstarc;p;p=p-next) k=p-adjvex; if(k=j) return 1; if(!visitedk) EnQueue( /for /while return 0; 第第 7 章章 查查 找找 一、填空题一、填空题 1顺序，数据元素按值有序排列 2关键字项，指针项 33 4中序 5哈希函数，处理冲突的方法，哈希表的装填因子 二、选择题二、选择题 1D 2B 3C 4D 5A 6A 三解答题三解答题 1解答： 25 数据结构 （1）生成的二叉排序树如图7-1所示，中序遍历序列为：15，20，30，37，45，56，69， 70。 （2）判定树如图7-2所示，ASL(122344)/82.6 15 20 56 37 30 70 45 69 15 20 70 45 37 30 56 69 图 7-1 第 1 题（1） 图 7-2 第 1 题（2） （3）平衡二叉树如图7-3所示。 2解答： 散列表如图7-4所示。 30 15 20 69 45 3756 70 0 1 2 3 4 5 6 TUETHUWEDFRISUN SAT MON 图 7-3 第 1 题（3） 图 7-4 第 2 题 四上机操作题四上机操作题 1解答： 先利用折半查找法找到被插入元素k的合适位置，然后将表的最后那个元素至该合适位 置之间的所有元素（包括最后那个元素与合适位置的那个元素）都依次后移一个位置，最后 将被插入元素k插入到该位置，同时修改表的长度加1。 void BinInsert (int A, int n, int k) int j, low = 1; high = n, mid; while (low = low; j -) /查找位置后的元素后移一个位置 Aj + 1 = Aj; Alow = k; /将k插入查找位置 n +; /表长加1 2解答： 提示：检验中序遍历序列是否递增有序？ 方法1：用非递归中序遍历算法，设双指针pre, p 一旦pre-data p-data 则返回假 方法2：用递归中序遍历算法，设全局指针pre， （参中序线索化算法） 一旦pre-data p-data 则返回假 方法3：用递归（中序或后序）算法 （1）空树是（2）单根树是（3）左递归真（4）右递归真 （5）左子树的右端小于根（6）右子树的左端大于根 /返回二叉排序树 T 中所有结点的最大值 TelemType Maxv(Bitree T) for (p=T; p-rchild; p=p-rchild); return p-data; /返回二叉排序树 T 中所有结点的最小值 TelemType Minv(Bitree T) for (p=T; p-lchild; p=p-lchild); return p-data; /判别 T 是否为二叉排序树 Status IsBST(Bitree T) if (!T) return OK; else if (!T-lchild)|(T-lchild) 3解答： typedef struct 27 数据结构 int maxkey; int firstloc; Index; typedef struct int *elem; int length; In