数据结构形成性考核册第1次作业参考答案.doc

数据结构形成性考核册第1次作业参考答案第一章 绪论一、填空题161、 数据 操作2、 集合结构 线性结构 树型结构 图形结构3、 引用类型4、 1：1 1：n n：m5、 不对6、 多个7、 O（m*n）8、 时间复杂度空间复杂度9、 顺序 链接 索引 散列10、O（n2）11、O（n）12、O（n） O（m*n）二、选择题 18：DBABADDD三、应用题（1） 功能：判断n是否是一个素数，若是则返回数值1，否则返回0。时间复杂度：O（）。（2） 功能：计算S=1！+2！+n!的值。时间复杂度：O（n）。（3） 功能：计算S=1！+2！+n!的值。时间复杂度：O（n2）。（4） 求出满足不等式1+2+in的最小i值。O（）。第二章 线性表四、填空题1、 AP-12、 1083、 前驱 后继4、 最后一个 表头5、 p-next=q-next q-next=p6、 HL-next=NULL HL-next=HL7、 P-next8、 Q-next9、 P-next s10、从前向后 前移 n-i11、O（1） O（n）12、（n+1）/213、O（n） O（1）14、AP.next15、aj.next=ai.next ai.next=j16、数据值 指针五、选择题 15：BDDBC六、应用题1、（1）、（79，62，34，57，26，48）（2）、（26，34，48，57，62，79）（3）、（48，56，57，62，79，34）（4）、（56，57，79，34）（5）、（26，34，39，48，57，62）2、（1）将类型为List的线性表L中第i个元素移至表尾位置的算法，L中的元素类型为ElemType，假定不需要对i的值进行有效性检查。 void move (List& L, int i) ElemType x=L.list i-1; for(int j=i; jdata= =x)k+;P=P-next;return k;（3） 单链表的逆置算法；void inverse(LNode * & HL)LNode *q, * p=HL;HL=NULL;while (p!=NULL) q=p ; p=p-next ; q-next=HL; HL=q ;（4）删除一个有序的单链表中其值重复的元素，使链表中所有元素的值均不同的算法。void del(LNode * &HL)LNode *p=HL,q;if (HL!=NULL) While (p-next!=NULL) if (p-data!=p-next-data) p=p-next; else q=p-next ;p-next=q-next;delete q; （5）查找单链表中第i个元素的值的算法，如果给定的i值不合法或链表为空等异常情况返回空值NULL；ElemType GetANode ( Lnode *HL, int i ) if ( i 1 ) return NULL;int k = 1;while (HL != NULL & k next; k+; if (HL!=NULL) return HL-data;elsereturn NULL;数据结构形成性考核册第2次作业参考答案第三章 稀疏矩阵和广义表一、填空题1、 行号2、 行号 列号 元素值3、 3 34、 （a,(b,( ),c),(d),e)） ( )5、 单 表6、 （1，3，2），（2，1，3），（3，3，-1），（3，4，5）7、 行 列8、 4 59、 括号10、错误 二、选择题 16： BCDBCB三、应用题1、（1） 三元组线性表为：（1，2，4），（2，4，-3），（2，7，1），（3，1，8），（4，4，5），（5，2，-7），（5，6，2），（6，4，6）（2） 13234556247142644-3185-726（3） 转置矩阵的三元组线性表为：（1，3，8），（2，1，4），（2，5，-7），（4，2，-3），（4，4，5），（4，6，6），（6，5，2），（7，2，1） 转置矩阵的顺序存储表示为：122444673152465284-7-356212、广义表长度深度（1）12（2）31（3）23（4）22（5）33（6）14链接存储结构图略。第四章 栈和队列一、填空题1、 后进先出 先进先出2、 顺序 链接3、 （rear-front+N）%N4、 n-15、 front=rear (rear+1)%QueueMaxSize=front6、 top+7、 abc+*d-8、 HS=NULL9、 栈顶指针 top=010、1 二、选择题 15：CDACA三、应用题1、假定类型为Stack的栈S中元素为整型，编写一个算法，要求将栈S中所有偶数删除，奇数在栈中先后位置不变，假定栈中至少有一个奇数，并假定不需要检查存储空间是否用完。2、利用堆栈编写将十进制数转化为二进制数的算法； 1、void DelEven(Stack& S)int a S.top-1, temp,i=0; while (S.top!=-1) temp=Pop(S); if (temp%2=1) ai+=temp; for(int j=i-1; j-1; j- - ) Push(S,a j); 2、void Transform (long num) Stack a;InitStack(a);while (num!=0) int k=num%2;Push(a,k);num/=2;while (!StackEmpty(a) )coutPop (a);coutendl;3、如果一个循环队列Q中只设一个头指针front，不设队尾指针rear，而改置计数器count用以记录队列中元素的个数，试编写一个函数，完成元素item入队的运算。struct Queue ElemType queueQueueMaxSize; int front,count; void Qinsert（Queue &Q,const ElemType &item）int position;if (Q.count= =QueueMaxSize) cout”Queue is Full!”data=item ;if (rear=NULL) rear=newptr-next=newptr ;else newptr-next=rear-next ; rear-next=newptr ;rear=newptr ; 删除算法：ElemType Qdelete ( LNode *&rear)LNode * p=rear-next ;if (p= =rear) rear=NULL ;elserear-next=p-next;ElemType temp=p-data ;delete p ;return temp ;数据结构形成性考核册第3次作业参考答案第五章 树和二叉树一、填空题1、 N-12、 5 50或483、 (4h-1)/34、 65、 10 4 36、 2 1 1 67、 B I和J8、 8 159、 610、5 1811、a2i a2i+1 ai/212、2n n-1 n+113、514、第一个孩子 右兄弟15、9 二、选择题 15： BCCBB三、应用题1、 前序：ABCDE中序：BDCEA后序：DECBA层次：ABCDE2、先根：ABEFCGKLDHIJM后根：EFBKLGCHIMJDA层次：ABCDEFGHIJKLM3、已知一棵树的广义表表示为：A（B（E，F），C（G（K，L），D（H，I，J（M），请将其转换为对应的二叉树表示形式。解：其对应的二叉树表示为：ABEFCGKDIHLJM4、已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，nm个度为m的结点，问树中有多少个叶子结点。解：设叶子结点数为n0，则树中结点数和总度数分别为：结点数=n0+n1+n2+nm总度数=n1+2n2+mnm根据树的性质1可知，结点数等于总度数之和加1，所以得到第六章 二叉树的应用一、填空题1、 小于 大于2、 升序的有序序列3、 查找成功 左子树 右子树4、 2i+1 2i+25、 最小值 最大值6、 向上 根结点7、 向上 根结点8、 带权路径长度WPL9、 最后（堆尾）10、堆顶 堆尾 堆顶11、根 左子树 右子树二、应用题1、给定权值集合 3，7，8，2，6，10，14, 构造相应的Huffman树，并计算它的带权外部路径长度。解：根据Huffman树的构造规则构造的树为：235829107111614152150 WPL=(2+3)*4+(6+7+8)*3+(10+14)*2=20+63+48=1312、已知一组元素为：（26，18，79，62，12，50，70，22），画出按元素排列顺序输入生成的一棵二叉搜索树。解：其二叉搜索树的形式为：70791250226218263、从空堆开始依次向最小堆中插入线性表（28，12，49，16，34，72，30，25，13）中的每一个元素，要求以线性表的形式给出每插入一个元素后堆的状态。再从堆中依次删除元素二个元素后堆的线性表表示。解：每插入一个元素后堆的状态用线性表表示如下：（28）（12，28）（12，28，49）（12，16，49，28）（12，16，49，28，34）（12，16，49，28，34，72）（12，16，30，28，34，72，49）（12，16，30，25，34，72，49，28）（12，13，30，16，34，72，49，28，25）从堆中删除元素堆顶元素12后的线性表表示为：（13，16，30，25，34，72，49，28）再从堆中删除堆顶元素13后堆的线性表表示为：（16，25，30，28，34，72，49）数据结构形成性考核册第4次作业参考答案第七章 图一、填空题1、 22、 n(n+1)/2 n(n+1)3、 n-1 邻接矩阵 邻接表 边集数组4、 n*n5、 e 2e6、 出边邻接结点 入边邻接7、 e e8、 O(n) O(e/n) O(e)9、 O(n*n) O(n+e) O(e)10、O(n2) O(e)11、n n-112、链栈13、结点 结点间的关系14、i j15、任意多 任意多16、深度优先 广度优先17、有向无环 二、应用题1、按照教材上图的dfs1算法得到的从V0出发的深度优先遍历的顶点序列为：V0，V1，V2，V5，V3，V7，V8，V4，V6按照教材上图的bfs1算法得到的从V0出发的广度优先遍历的顶点序列为：V0，V1，V2，V3，V4，V5，V6，V7，V82、按照教材上图的dfs2算法得到的从V2出发的深度优先遍历的顶点序列为：V2，V6，V1，V5，V4，V0，V3按照教材上图的bfs2算法得到的从V2出发的广度优先遍历的顶点序列为：V2，V6，V0，V1，V3，V5，V43、解：（1）、按照普里姆算法从0开始依次得到的各条边：（0，4）4 ，（0，1）18，（1，2）5，（1，3）8，（1，5）12（2）、按照克鲁斯卡尔算法依次得到的各条边：（0，4）4 ，（1，2）5，（1，3）8，（1，5）12，（0，1）18 4、(1)按照普里姆算法从顶点V1出发得到的最小生成树各边如下表所示：123456边的顶点1161245边的顶点2642350边的权值141516122510(2)按照克鲁斯卡尔算法并入最小生成树中各边的次序如下表所示：123456边的顶点1021414边的顶点2536625边的权值1012141516255、先求得各顶点的入度数，再按书上给的算法，依次得到其拓扑序列为：V1，V4，V0，V2，V3，V6，V5，V8，V7，V9数据结构形成性考核册第5次作业参考答案第八章 查找一、填空题1、 （n+1）/2 O(n)2、 log2(n+1) O(log2n)3、 37/124、 顺序存储 有序5、 1 36、 二叉搜索树 理想平衡树7、 6 31 198、 索引值 子表开始9、 （12，63，36）（55，40，82）（23，74）10、稠密 稀疏11、下限值（low）12、11 O()13、500 2514、散列15、链接16、2 7/517、518、开放定址法 链接法19、 20、4 521、4 822、 m-1 m23、同一层 关键字24、关键码 哈希 25、索引二、应用题1、设有序顺序表中的元素依次为12，23，26，37，54，60，68，75，82，96。试画出对其折半查找时的判定树，并计算查找成功时的平均查找长度。 解：其判定树为：54237512266082376896ASLsucc=(1*1+2*2+4*3+3*4)/10=29/10 ；2、在序列 3，8，12，30，36，38，42，50，68 中，用折半查找法查找关键字32时，需要在哪个区间内和哪些元素进行比较，做多少次比较? 解：做4次关键字比较。第一次与36比较，查找区间缩小到3，8，12，30，第二次与8比较，查找区间缩小到12，30，第三次与12比较，查找区间缩小到30，第四次与30比较，查找失败。3、假定一个待散列存储的线性表为(32，75，29，63，48，94，25，46，18，70)，散列地址空间为HT13，若采用除留余数法构造散列函数，处理冲突采用线性探查法，试求出每个元素的散列地址，画出最后得到的散列表，求出平均查找长度。解：从题意可知散列函数可定义为：H(K)=K%13；H(32)=32%13=6H(75)=75%13=10H(29)=29%13=3H(63)=63%13=11H(48)=48%13=9H(94)=94%13=3，冲突，线性探查加1，得4，不冲突。H(25)=25%13=12H(46)=46%13=7 H(18)=18%13=5；H(70)=70%13=5，冲突；线性探查加1得6，冲突；线性探查加1得7，冲突；线性探查加1得8，不冲突。由上可知，其散列表表示应为：012345678910111229931832467048756325其平均查找长度为：（1+1+1+1+1+2+1+1+1+4）/10=14/10=1.4第9章 排序一、 填空题1、O(n2) O(n)2、稳定3、5 4 84、堆排序5、n-16、插入 选择7、插入/冒泡8、（84，79，56，38，40，46）9、O(n2)10、O（log2n） O（nlog2n）11、312、4 4二、应用题略（参见教材和复习资料解答！） 下面是赠送的中秋节演讲辞，不需要的朋友可以下载后编辑删除！谢谢中秋佳节演讲词推荐中秋,怀一颗感恩之心老师们，同学们：秋浓了，月圆了，又一个中秋要到了!本周日，农历的八月十五，我国的传统节日中秋节。中秋节，处在一年秋季的中期，所以称为“中秋”，它仅仅次于春节，是我国的第二大传统节日。中秋的月最圆，中秋的月最明，中秋的月最美，所以又被称为“团圆节”。金桂飘香，花好月圆，在这美好的节日里，人们赏月、吃月饼、走亲访友无论什么形式，都寄托着人们对生活的无限热爱和对美好生活的向往。中秋是中华瑰宝之一，有着深厚的文化底蕴。中国人特别讲究亲情，特别珍视团圆，中秋节尤为甚。中秋，是一个飘溢亲情的节日;中秋，是一个弥漫团圆的时节。这个时节，感受亲情、释放亲情、增进亲情;这个时节，盼望团圆、追求团圆、享受团圆这些，都已成为人们生活的主旋律。同学们，一定能背诵出许多关于中秋的千古佳句，比如“举头望明月，低头思故乡”、“但愿人长久，千里共婵娟”、“海上生明月，天涯共此时”这些佳句之所以能穿透历史的时空流传至今，不正是因为我们人类有着的共同信念吗。中秋最美是亲情。一家人团聚在一起，讲不完的话，叙不完的情，诉说着人们同一个心声：亲情是黑暗中的灯塔，是荒漠中的甘泉，是雨后的彩虹中秋最美是思念。月亮最美，美不过思念;月亮最高，高不过想念。中秋圆月会把我们的目光和思念传递给我们想念的人和我们牵挂的人，祝他们没有忧愁，永远幸福，没有烦恼，永远快乐! 一、活动主题：游名校、赏名花，促交流，增感情二、活动背景：又到了阳春三月，阳光明媚，微风吹拂，正是踏青春游的好时节。借春天万物复苏之际，我们全班聚集在一起，彼此多一点接触，多一点沟通，共话美好未来，与此同时，也可以缓解一下紧张的学习压力。 相信在这次春游活动中，我们也能更亲近的接触自然，感悟自然，同时吸收万物之灵气的同时感受名校的人文气息。三、活动目的：1. 丰富同学们的校园生活，陶冶情操。2. 领略优美自然风光，促进全班同学的交流，营造和谐融洽的集体氛围。 3. 为全体同学营造一种轻松自由的气氛，又可以加强同学们的团队意识。 4. 有效的利用活动的过程及其形式，让大家感受到我们班级的发展和进步。四、活动时间：XX年3月27日星期四五、活动参与对象：房产Q1141全体及“家属”六、活动地点：武汉市华中农业大学校内七、活动流程策划：1、27日8点在校训时集合，乘车2、9点前往华农油菜基地、果园，赏花摄影3、10点30，回农家乐开始做饭，进行“我是厨王”大比拼4、1点30，收拾食品残物，开始集体活动5、4点，乘车返校八、职能分工及责任定岗1、调研组：负责前期的选址、策划的撰写、实地考察、交通工具的联系和检验组长：金雄成员：吴开慧2、安全保卫组：负责登记参加春游的人数，乘车前的人数的登记，集体活动时同学的请假的审批，安全知识的培