电大数据结构形成性考核册答案(作业1-4)973.pdf

1 电大数据结构（本）考核作业答案 作业 1 一、单项选择题 1C 2D 3B 4C 5D 6C 7B 8C 9A 10B 11C 12D 13C 14A 15B 16C 17C 18B 19B 20D 二、填空题 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）由于难以估计，必须预先分配较大的空间，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=q-next（2）q-next=p-next 五、完成：实验 1线性表 根据实验要求（见教材P201-202）认真完成本实验，并提交实验报告。3 作业 2 答案（本部分作业覆盖教材第 3-5 章的内容）一、单项选择题 1C 2B 3A 4C 5B 6A 7B 8C 9A 10C 11B 12C 13B 14B 15A 16C 17B 18A 19C 20D 21 B 22 D 23 C 24 B 25 D 26 A 27 C 28 D 29 D 30 C 31 A 32 D 二、填空题 1后进先出 2下一个 3增 1 增 1 4假上溢 5 栈是否满 s-top=MAXSIZE-1 栈顶指针 栈顶对应的数组元素 栈是否空 s-top=-1 栈顶元素 修改栈顶指针 6bceda 7终止条件 递归部分 8LU-front=LU-rear 9运算符 操作数 ab+c/fde/-10s-next=h;11h=h-next;12r-next=s;13f=f-next;14字符 15顺序存储方式 链式存储方式 160 空格字符的个数 17特殊 稀疏 18（）（）2 19（d,e,f）20串长度相等且对应位置的字符相等 21i(i-1)/2+j 22行下标、列下标、非零元素值 三、问答题 1简述栈和一般线性表的区别。答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。2简述队列和一般线性表的区别。队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。3链栈中为何不设头结点？答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以 4 一般不设置头结点。4利用一个栈，则：（1）如果输入序列由 A，B，C 组成，试给出全部可能的输出序列和不可能的输出序列。（2）如果输入序列由 A，B，C，D 组成，试给出全部可能的输出序列和不可能的输出序列。答：（1）栈的操作特点是后进先出，因此输出序列有：A 入，A 出，B 入，B 出，C 入 C 出，输出序列为 ABC。A 入，A 出，B 入，C 入，C 出，B 出，输出序列为 ACB。A 入，B 入，B 出，A 出，C 入，C 出，输出序列为 BAC。A 入，B 入，B 出，C 入，C 出，A 出，输出序列为 BCA。A 入，B 入，C 入，C 出，B 出，A 出，输出序列为 CBA。由 A，B，C 组成的数据项，除上述五个不同的组合外，还有一个 C，A，B 组合。但不可能先把 C 出栈，再把 A 出栈，（A 不在栈顶位置），最后把 B 出栈，所以序列 CAB 不可能由输入序列 A，B，C 通过栈得到。（2）按照上述方法，可能的输出序列有：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。不可能的输出序列有：DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD 5用 S 表示入栈操作，X 表示出栈操作，若元素入栈顺序为 1234，为了得到 1342 出栈顺序，相应的S 和 X 操作串是什么？答：应是 SXSSXSXX。各操作结果如下：S 1 入栈 X 1 出栈 输出序列：1 S 2 入栈 S 3 入栈 X 3 出栈 输出序列：13 S 4 入栈 X 4 出栈 输出序列：134 X 2 出栈 输出序列：1342 6有 5 个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素 C、D 最先的次序有哪几个？答：从题中可知，要使 C 第一个且 D 第二个出栈，应是 A 入栈，B 入栈，C 入栈，C 出栈，D 入栈。之后可以有以下几种情况：（1）B 出栈，A 出栈，E 入栈，E 出栈，输出序列为：CDBAE。（2）B 出栈，E 入栈，E 出栈，A 出栈，输出序列为 CDBEA。（3）E 入栈，E 出栈，B 出栈，A 出栈，输出序列为 CDEBA 所以可能的次序有：CDBAE，CDBEA，CDEBA 7写出以下运算式的后缀算术运算式 3x2+x-1/x+5 (A+B)*C-D/(E+F)+G 答；对应的后缀算术运算式 5 3x2*x+1x/-5+AB+C*DEF+/-G+8 简述广义表和线性表的区别和联系。答：广义表是线性表的的推广，它也是 n(n0)个元素 a1,a2ai an的有限序列，其中 ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当 ai都是原子时，广义表退化成线性表。四、程序填空题 1（1）q-front-next=p-next;（2）free(p);（3）q-rear=q-front 五、综合题 1 答：出队序列是 e2,e4,e3,e6,e5,e1 的过程：e1 入栈（栈底到栈顶元素是 e1）e2 入栈（栈底到栈顶元素是 e1,e2）e2 出栈（栈底到栈顶元素是 e1）e3 入栈（栈底到栈顶元素是 e1,e3）e4 入栈（栈底到栈顶元素是 e1,e3,e4）e4 出栈（栈底到栈顶元素是 e1,e3）e3 出栈（栈底到栈顶元素是 e1）e5 入栈（栈底到栈顶元素是 e1,e5）e6 入栈（栈底到栈顶元素是 e1,e5,e6）e6 出栈（栈底到栈顶元素是 e1,e5）e5 出栈（栈底到栈顶元素是 e1）e1 出栈（栈底到栈顶元素是空）栈中最多时有 3 个元素，所以栈 S 的容量至少是 3。2 算法设计如下：/*只有一个指针 rear 的链式队的基本操作*/#include typedef char elemtype;struct node/*定义链队列结点*/elemtype data;struct node*next;typedef struct queue/*定义链队列数据类型*/struct node*rear;LinkQueue;void initqueue(LinkQueue*Q)/*初始化队列*/6 Q=(struct queue*)malloc(sizeof(struct queue);Q-rear=NULL;void enqueue(LinkQueue*Q,elemtype x)/*入队算法*/struct node*s,*p;s=(struct node*)malloc(sizeof(struct node);s-data=x;if(Q-rear=NULL)/*原为空队时*/Q-rear=s;s-next=s;else /*原队不为空时*/p=Q-rear-next;/*p 指向第一个结点*/Q-rear-next=s;/*将 s 链接到队尾*/Q-rear=s;/*Q-rear 指向队尾*/s-next=p;void delqueue(LinkQueue*Q)/*出队算法*/struct node*t;if(Q-rear=NULL)printf(队列为空!n);return(0);else if(Q-rear-next=Q-rear)/*只有一个结点时*/t=Q-rear;Q-rear=NULL;else /*有多个结点时*/t=Q-rear-next;/*t 指向第一个结点*/Q-rear-next=t-next;/*引成循环链*/free(t);elemtype gethead(LinkQueue*Q)/*取队首元素算法*/if(Q-rear=NULL)printf(队列为空!n);else return(Q-rear-next-data);int emptyqueue(LinkQueue*Q)/*判断队列是否为空算法*/7 if(Q-rear=NULL)return(1);/*为空,则返回 true*/else return(0);/*不为空,则返回 flase*/void dispqueue(LinkQueue*Q)/*显示队列中元素算法*/struct node*p=Q-rear-next;printf(队列元素:);while(p!=Q-rear)printf(%c,p-data);p=p-next;printf(%cn,p-data);六、完成：实验 2栈、队列、递归程序设计 根据实验要求（见教材P203）认真完成本实验，并提交实验报告。作业 3 答案（本部分作业覆盖教材第 6-7 章的内容）一、单项选择题 1B 2B 3D 4C 5B 6A 7A 8C 9A 10.D 11.A 12C 13C 14B 15B 16C 17B 18C 19A 20B 21D 22B 23.B 24.B 25.C 26.A 27A 28C 二、填空题 1子树树木或后继结点数 2树中所有结点的度的最大值 3分支结点 非终端结点 4叶子结点 终端结点 5子树的根 后继结点 孩子结点 6祖先 7树中结点的最大层数 81log2n 9根结点 左子树 右子树 10左子树 根结点 右子树 11左子树 右子树 根结点 12权 13带权路径长度之和 14最优二叉树 最小的二叉树 1569 8 162m-1 17多对多 18所有顶点 一次 19先序 20按层次 21n2 22邻接矩阵 邻接表 232(n-1)24n-1 25栈 三、综合题 1写出如下图所示的二叉树的先序、中序和后序遍历序列。答：二叉树的定义是递归的，所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分.，这样划分一直进行到树叶结点。(1)先序为“根左右”，先序序列为：fdbacegihl(2)中序为“左根右”，中序序列为：abcdefghij(3)后序为“左右根”，后序序列为：acbedhjigf 2已知某二叉树的先序遍历结果是：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）二叉树图形表示如下：HCABDIJFEKGML （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+1 2(1)for(j=0;jdata=p-data;t-lchild=CopyTree(p-lchild);t-rchild=CopyTree(p-rchild);return(t);else return(NULL);/*CopyTree*/2.int BTreeLeafCount(struct BTreeNode*BT)0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 v1v5v4v3v2 241 44551 2323 11 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 答案（本部分作业覆盖教材第 8-9 章的内容）一、单项选择题 1D 2C 3B 4C 5D 6 7C 8D 9B 10D 11C 12C 13A 14C 15D 16B 17B 18D 19D 20A 21D 22D 23A 24A 25C 26C 27B 28A 29B 30C 二、填空题 1哈希表查找法 2数据项的值 记录 3主关键字 4数学期望值 5顺序 6二分查找 升序或降序排列 7顺序存储结构 8索引顺序查找 顺序查找 9均小于根结点的值 均大于根结点的值 二叉排序树 10自变量 函数值 119，14，16，17 12内部排序 外部排序 13交换排序 143 154 8 16堆排序 快速排序 17主关键字 18关键字相等的记录 19n-1,n-j 20堆尾 堆顶 向下 三、综合题 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 12 第 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，18 3已知序列（17，18，60，40，7，32，73，65，85）采用冒泡排序法排序的各趟的结果如下：原始初始：17，18，60，40，7，32，73，65，85 第 1 趟：17，18，40，7，32，60，65，73，85 第 2 趟：17，18，7，32，40，60，65，73，85 第 3 趟：17，7，18，32，40，60，65，73，85 第 4 趟：7，17，18，32，40，60，65，73，85 第 5 趟：7，17，18，32，40，60，65，73，85 4已知序列（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，908 5设一组记录的关键字序列为（49，83，59，41，43，47），采用堆排序算法完成以下操作：（要求小根堆，并画出中间过程）（1）以二叉树描述 6 个元素的初始堆（2）以二叉树描述逐次取走堆顶元素后，经调整得到的 5 个元素、4 个元素的堆 答：13（1）（2）6(1)原序列 16 15 20 53 64 7 15 16 20 53 7 64 n-1 趟 15 16 20 7 53 64 n-j 次 49 59 83 41 43 47 83 47 41 43 59 49 49 83 41 47 43 59 83 59 49 41 43 47 83 49 59 41 59 47 41 49 83 43 43 47 41 59 83 49 59 47 41 43 83 49 47 41 83 59 43 49 47 41 43 83 49 59 14 15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 64(2)(3)平均查找长度=（1*1+2*2+3*3）/6=14/6 7（1）(2)中序遍历：2，3，4，5，6，7，14，16，18 四、程序填空题 1.（1）j=0（2）aj（3）j-（4）temp 2（1）j=n-1（2）i=n-j（3）ai=ai+1（4）ai+1=temp（5）当某趟冒泡中没有出现交换则已排好序结束循环。五、算法设计题 7 15 20 64 16 532 4 6 16 7 3 18 5 14 15 1编写折半查找算法。折半查找算法如下；int Binary_Search(NODE a,int n,int k)/*在a0到an-1中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1*/int low,mid,high;low=0;high=n-1;while(low=high)mid=(low+high)/2;if(amid.key=k)return mid;/*查找成功，返回查找到的记录的下标*/else if(amid.keyk)low=mid+1;/*取后半查找区间*/else high=mid-1;/*取前半查找区间*/return-1;/*查找失败*/2.编写顺序查找算法。顺序查找算法如下：int search(NODE a,int n,int k)/*在a0an-1中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时返回-1*/int i=0;while(in&ai.key!=k)/*没有查到同时查找过程没有结束，则继续查找*/i+;if(ai.key=k)/*查找成功*/return i;else return-1;/*查找失败*/六、完成：实验 3栈、队列、递归程序设计 实验 4图的存储方式和应用 根据实验要求（见教材P203）认真完成本实验，并提交实验报告。