《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源习题答案-修改标红》由会员分享，可在线阅读，更多相关《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源习题答案-修改标红（15页珍藏版）》请在金锄头文库上搜索。
1、习题答案第1章 绪论1填空题(1) 线性结构、树型结构和图型结构(2) 一对一、一对多和多对多(3) 效率，人对算法阅读理解的难易程度，对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果(4) 时间复杂度2选择题(1) C (2) C 3简答题程序1 答案：n-1，O（n） 程序2答案： n-1 O（n）程序3答案： 11* n+1, O（n）（n为初始值100）程序4答案： , O（） 第2章1填空题(1)顺序存储和链式存储(2) addr+m*i(3)n-i+1(4) 1=in ； 0=in-12选择题(1) B (2) A C(3) B第3章1填空题(1) 1,2,4(2
2、)push,pop,push,push,pop,push,pop,pop(3) 栈空；栈满。(4) s.top - ； s.top + 。(5) 队尾 ， 队头 。(6) q.front=q.rear ， q.front=(q.rear+1)%MaxSize 。(7) 21 。2选择题D C A B A D C C 3. （1）算法设计题基本操作如下：进队void AddQueue(CirQueue* q, int r, int f, int x) Push(q,f,r,x,2)出队Void RemoveQueue(CirQueue* q, int r, int f) Pop(q,f,r,1)
3、将x下推进栈i(i=1,2)Void Push(stack * s, int t1, int t2,int x,int i) if (t2+1) mod n = t1printf(“栈满”) else if (i=1) at1=x; t1=(t1-1)mod n; else t2=(t2+1)mod n; at2=x; 将栈i(i=1,2)的栈顶元素上托出栈Void Pop (stack * s, int t1, int t2,int i) if (t1=t2)printf(“栈空”) else if (i=1) t1=(t1+1)mod n; else t2=(t211)mod n; （2）
4、约瑟夫环/约瑟夫环public void YueSeFu(int n,int k,int m) int i;for(i=1;i=n;i+)AddQueue(q,i);/q为定义的顺序队列 /前k个元素先出队再入队for(i=1;ik;i+)Object x=DelQueue(q);/出队AddQueue(q,x);/入队printf(出队序列：n);while(!notEmpty()for(i=1;i=0 。(3) 不含任何字符的串 。(4) 仅含空格字符的字符串 。(5) 固定长度 ， 设置长度指针 。2. 选择题（BBD）3. 简答题(1)解答：不含任何字符的串称为空串，其串长度为零；仅含
5、有空格字符的串称为空格串，它的长度为串中空格符的个数。空格符在字符串中可用来分隔一般的字符，便于阅读和识别，但空格符会占用有效串长。空串在处理过程中可用于作为任意字符串的子串。(2) 解答：StrLength(s)=14，StrLength(t)=4，SubString(s,7,7)= STUDENT, SubString(t,2,1)= O，Index(s,A)=3，Index(s,t)=04.算法设计题（1）#include stdafx.h#include #include bool isdigit(char ch)if (ch 9)return false;elsereturn tru
6、e;int countint()int i = 0;int a100;int num = 0;char ch = #;scanf(%c, &ch);while(ch != #)if (isdigit(ch)num = 0;while (isdigit(ch) & ch != #)num = num * 10 + (ch - 0);scanf(%c, &ch);ai = num;i+; / ifif (ch != #)scanf(%c, &ch); / whileprintf(int count:%d:n, i);for (int j = 0; j i; j+)printf(%6dn, aj);
7、return i;int main(int argc, char* argv)countint();return 0;第5章1填空题(1) 线性结构 ， 顺序结构 ， 以行为主序 和 以列为主序 。(2) Loc（aij）=Loc(a00)+（jm+i） k 。(3) (0,2,2),(1,0,3),(2,2,-1),(2,3,5) 。(4) n(n+1)/2。(5) 41 。2选择题（C C B）3. 简答题解答：1）288字节 6*8*6(字节)=2882）1282 Loc()=1288-6=12823）1072 Loc()=1000+(18+4) 6=10724）1276 Loc()=1
8、000+(76+4)6=12764. 算法题/ chap05_xt01.cpp : Defines the entry point for the console application./#include stdafx.h#include #include int main() int n, i, j, count = 0; /n is The length of the Array scanf(%d, &n);int *a = (int *)malloc(sizeof(int) * n); for (i = 0; i n; i+) scanf(%d, &ai); for (i = 0; i
9、 n; i+) count = 0; for (j = 0; j n; j+) if (i = aj) count+; if (count = 0) printf(%d does not appear in the array!n, i); else printf(%d appear in the array for %d timesn, i, count); free(a);return 0; 第6章 1填空题(1) 16(2) 34(3) 2h-1(4) EFCGHDBA(5) 2h-12选择题(1) C (2) A(3) D 3简答题(1)【解答】二叉树的叶结点有、。分支结点有、。结点的
10、层次为0；结点、的层次为1；结点、的层次为2；结点、的层次为3；结点的层次为4。（2）【解答】结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。（3）【解答】（4）【解答】总结点数 n = n0 + n1 + n2 + + nm总分支数 e = n-1 = n0 + n1 + n2 + + nm-1 = m*nm + (m-1)*nm-1 + + 2*n2 + n1则有 （5） 【解答】(1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；(2) 二叉树的中序序列与后序序列相同：空树
11、或缺右子树的单支树；(3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。（6） 【解答】哈夫曼树的带权路径长度WPL = 229。(7)【解答】已知字母集 c1, c2, c3, c4, c5, c6, c7, c8 ，频率 5, 25, 3, 6, 10, 11, 36, 4 ，则Huffman编码为 c1 c2 c3 c4 c5 c6 c7 c8 0110 10 0000 0111 001 010 11 0001 电文总码数为 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4= 2574、算法设计题(1) 非递归先根遍历树/定义堆栈，做非递归遍历算法typedef structSElemtype dataMaxsize;int top;SqStack;
