资源描述：
《最新数据结构作业题参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、东北农业大学网络教育学院数据结构作业题参考答案习题一答案一、选择题（每题2分，共20分）12345678910ABCCCDBBAB二、填空题（每题1分，共20分）1．n(n-1)/2；02．13．54．2i-15．2i；2i+1；i/26．顺序；链接；索引；散列7．10；4；38．n-19．一对一；一对多；多对多10．10三、运算题（每题5分，共10分）1．根据题意，矩阵A中当元素下标I与J满足I≥J时，任意元素A[I][J]在一维数组B中的存放位置为I*(I+1)/2+J，因此，A[8][5]在数组B中位置为8*(8+1)/2+5=41。2．判断结果元素值3456586394比较次数21
2、344四、应用题（每题10分，共50分）1．答：(1)直接插入排序第一趟(3)[8,3],2,5,9,1,6第二趟(2)[8,3,2],5,9,1,6第三趟(5)[8,5,3,2],9,1,6第四趟(9)[9,8,5,3,2],1,6第五趟(1)[9,8,5,3,2,1],6第六趟(6)[9,8,6,5,3,2,1](2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束）第一趟(9)[9],3,2,5,8,1,6第二趟(8)[9,8],2,5,3,1,6第三趟(6)[9,8,6],5,3,1,2第四趟(5)[9,8,6,5],3,1,2第五趟(3)[9,8,6,5,3],1,
3、2第六趟(2)[9,8,6,5,3,2],12．(1)是大堆；(2)是大堆；（4）是小堆；(3)不是堆，调成大堆100，98，66，85，80，60，40，77，82，10，203．答：先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下：（1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树（2）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树．（3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树．（4）若中序序列与层次遍历序列相同，则
4、或为空树，或为任一结点至多只有右子树的二叉树4．答：（1）T树的最大深度Kmax=6（除根外，每层均是两个结点）T树的最小深度Kmin=4（具有6个叶子的完全二叉树是其中的一种形态）（2）非叶子结点数是5。（n2=n0-1）（3）哈夫曼树见下图，其带权路径长度wpl=51Wpl=4*3+3*3+2*(4+5+6)=514561235．答：n（n>0）个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nd-(n-1)=n(d-1)+1个。习题二答案一、选择题（每题2分，共20分）12345678910BDACDDBBCA二、填空题（每空2分，共40分）1．n
5、-12．（15，02，21，24，26，57，43，66，81，48，73）3．O（n）4．HL->next==NULLHL->next==HL5．O(nlog2n)；O(n2)6．6；31；197．2；1；1；68．69．集合结构；线性结构；树型结构；图形结构10．n-i+1三、应用题（每题10分，共60分）1．答：可以做到。取a与b进行比较，c与d进行比较。设a>b,c>d(ad，则有序a>b>d；若bd>b，此时已进行了3次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需4次比较，从而共需7
6、次比较。2．该排序方法为快速排序。3．①快速排序②冒泡排序③直接插入排序4．答：（1）T树的最大深度Kmax=6（除根外，每层均是两个结点）T树的最小深度Kmin=4（具有6个叶子的完全二叉树是其中的一种形态）456123（2）非叶子结点数是5。（n2=n0-1）（3）哈夫曼树见下图，其带权路径长度wpl=51Wpl=4*3+3*3+2*(4+5+6)=515．答：n（n>0）个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nd-(n-1)=n(d-1)+1个。6．答：（1）176（2）76和108（3）28和116。习题三答案一、单选题（每题2分，共1
7、0分）1、A2、B3、D4、D5、D二、填空题（每空1分，共25分）1、1:11:NM:N（或者1对11对NM对N）2、p->nexta[p].next3、引用4、后进先出先进先出5、1626、31217、68、查找成功左子树右子树9、n210、nn-111、二叉搜索树理想平衡树（次序无先后）12、O(n)O(nlog2n)O(n)13、596三、运算题（每题6分，共24分）1、先根：a,b,e,c,f,h,i,j,g,
