数据结构形考作业答案

数据结构（本）形考作业1参考答案:一、单项选择题1C 2D 3C 4C 5D 6C 7C 8C 9A 10B二、填空题 1n-i+1 2n-i 3.集合、线性表、树、图 4. 存储结构、物理结构 5.线性表 图6. 有穷性、确定性、可行性、有输入、有输出 7. 图 8.树 9. 线性表 10 n-1 O(n)11s-next=p-next; 12head 13q-next=p-next; 14p-next=head; 15单链表 16顺序存储 链式存储 17存储结构 18.两个 后继结点 前驱结点 尾结点 头结点19指向头结点的指针 指向第一个结点的指针 20链式 链表三、问答题1简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。2解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。3什么情况下用顺序表比链表好？答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。如果线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 4解释头结点、第一个结点（或称首元结点）、头指针这三个概念的区别？答：头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。5解释带头结点的单链表和不带头结点的单链表的区别。答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点；在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。四、程序填空：1(1) p-data=i; (2) p-next=NULL; (3) q-next=p; (4)q=p;2. (1) head=p; (2) q=p; (3) p-next=NULL; (4) p-next=q-next (5) q-next=p;3. (1) p=(NODE *) malloc (sizeof(NODE); (2) p-data=x;五、完成：实验1线性表根据实验要求（见教材P201-202）认真完成本实验，并提交实验报告。数据结构（本）形考作业3参考答案:一、单项选择题1B2B3D4C5B6A7A8B9A10. D11.A12C13D14B15B16B17无18A19C20B21A22B23.B24.B25. C26.A27A28C二、填空题1出度和入度之和2.树中结点的度的最大值3.分支结点非终端结点4.叶子结点终端结点5. 逻辑后继直接后继结点孩子结点 6.祖先结点7.从根结点开始到叶结点的最大路径长度8. Log2n+1（上取整）9. 根结点 左子树 右子树 10. 左子树根结点 右子树11.左子树 右子树根结点 12.权13.带权路径长度之和 14.最优二叉树值最小的二叉树 15.6916.2m-1 17. 多对多m:m 18.每个结点1次19.先根20.后根21.n*n22.邻接矩阵邻接表23.n-124. n-125.栈三、综合题1写出如下图所示的二叉树的先序、中序和后序遍历序列。答：二叉树的定义是递归的，所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分.，这样划分一直进行到树叶结点。(1)先序为“根左右”，先序序列为：fdbacegihl(2)中序为“左根右”，中序序列为：abcdefghij(3)后序为“左右根”，后序序列为：acbedhjigf2已知某二叉树的先序遍历结果是：A，B，D，G，C，E，H，L，I，K，M，F和J，它的中序遍历结果是：G，D，B，A，L，H，E，K，I，M，C，F和J，请画出这棵二叉树，并写出该该二叉树后续遍历的结果。（1）二叉树图形表示如下：（2）该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C和A。3答 已知深度为k的二叉树最多有2k-1个结点(K1)，29-1892right,X)(3) (c2=1) return c2+12(1)for(j=0; jdata=p-data;t-lchild=CopyTree(p-lchild);t-rchild=CopyTree(p-rchild);return(t);elsereturn(NULL);2.int BTreeLeafCount(struct BTreeNode* BT)if(BT=NULL) return 0;else if(BT-left=NULL & BT-right=NULL) return 1;else return BTreeLeafCount(BT-left)+BTreeLeafCount(BT-right);六、完成：实验3栈、队列、递归程序设计，实验4图的存储方式和应用根据实验要求（见教材P203）认真完成本实验，并提交实验报告。数据结构（本）形考作业4参考答案 (2009-03-31 20:19:06)转载标签：教育分类：作业辅导作业4部分答案一、单项选择题1D 2C3C4C 5D6A7C8D9B10D11A12C 13A14C15D16B17B18D19D20D21D22D23A24A25C26D27B28A29B30C二、填空题1.散列2.特征项数据元素3.主键4.平均值5.顺序6.二分查找 升序有序7.顺序存储8.索引查找顺序查找9.小于根结点的值大于（或大于等于）根结点的值10.自变量地址值11.9， 14， 16 ，1712内部排序外部排序13交换排序143154816堆排序快速排序17主关键字18关键字相等的记录19n-1,n-j20堆尾堆顶向下三、综合题1已知序列（70,83,100,65,10,32,7,9），请写出对此序列采用插入排序法进行升序排序时各趟的结果。答：原始序列：（70），83，100，65，10，32，7，9第1趟： （70，83），100，65，10，32，7，9第2趟：（70，83，100），65，10，32，7，9第3趟：（65，70，83，100），10，32，7，9第4趟：（10，65，70，83，100），32，7，9第5趟：（10，32，65，70，83，100），7，9第6趟：（7，10，32，65，70，83，100），9第7趟：（7，9，10，32，65，70，83，100）2已知序列（10,18,4,3,6,12,1,9,15,8），请写出对此序列采用归并排序法进行升序排序时各趟的结果。答：原始序列：10，18，4，3，6，12，1，9，15，8第1趟：10，18 3，46，121，9 8，15第2趟：3，4，10，18， 1，6，9，12 8，15第3趟：3，4，10，18， 1，6，8，9，12，15第4趟：1，3，4，6，8，9，10，12，15，183已知序列（256，301，751，129，937，863，742，694，076，438）请给出采用冒泡排序法对该序列作升序排列时的每一趟结果。答：原始序列：256，301，751，129，937，863，742，694，076，438第1趟：256，301，129，751，863，742，694，076，438，937第2趟：256，129，301，751，742，694，076，438，863，937第3趟：129，256，301，742，694，076，438，751，863，937第4趟：129，256，301，694，076，438，742，751，863，937第5趟：129，256，301，076，438，694，742，751，863，937第6趟：129，256，076，301，438，694，742，751，863，937第7趟：129，076，256，301，438，694，742，751，863，937第8趟：076，129，256，301，438，694，742，751，863，937第9趟：076，129，256，301，438，694，742，751，863，9374已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用快速排序法对该序列作升序排列时的每一趟结果。原始序列：503，87，512，61，908，170，897，275，653，462第1趟：462，87，275，61，170503897，908，653，512第2趟：170，87，275，61 462，503897，908，653，512第3趟：87，61170275 462，503897，908，653，512第4趟：61 87170275 462，503897，908，653，512第5趟：61 ，87，170，275 462，503897，908，653，512第6趟：61 ，87，170，275，462，503897，908，653，512第7趟：61 ，87，170，275，462，503512，653897908第8趟：61 ，87，170，275，462，503，512，653 897908第9趟：61 ，87，170，275，462，503，653，897908第10趟： 61 ，87，170，275，462，503，653，897，9085设一组记录的关键字序列为（49，83，59，41，43，47），采用堆排序算法完成以下操作：（要求小根堆，并画出中间过程）（1）以二叉树描述6个元素的初始堆（2）以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆答：（1）（2）6(1)原序列1615205364715162053764n-1-j次151672053641571620536471516205364（2）（3）平均查找长度=（1*1+2*2+3*3）/6=14/67（1）(2)中序遍历：2，3，4，5，6，7，14，16，18四、程序填空题1.（1）j=0（2）aj（3）j-（4）temp2（1）j=n-1（2）i=n-j（3）ai=ai+1（4）ai+1=temp（5）当某趟冒泡中没有出现交换则已排好序结束循环。五、算法设计题1编写折半查找算法。折半查找算法如下；int Binary_Search(NODE a,int n, int k)int low,mid,high;low=0;high=n-1;while(low=high)mid=(low+high)/2;