2021年数据结构形成性考核答案(本)作业1-4.doc

数据构造（本）形成性考核作业答案作业1一、单项选取题1C 2D 3B 4C 5D 6C 7B 8C 9A 10B11C 12D 13C 14A 15B 16C 17C 18B 19B 20D二、填空题 1n-i+12n-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=p2（1）head=p（2）q=p（3）p-next=NULL（4）p-next=q-next（5）q-next=p3（1）p=q-next（2）q-next=p-next五、完毕：实验1线性表依照实验规定（见教材P201-202）认真完毕本实验，并提交实验报告。作业2答案一、单项选取题1C 2B 3A 4C 5B 6A 7B 8C 9A 10C 11B 12C 13B 14B 15A 16C 17B 18A 19C 20D 21B 22D 23C 24B 25D 26A 27C 28D 29D 30C 31A 32D 二、填空题 1后进先出2下一种3增1 增14假上溢5 栈与否满 s-top=MAXSIZE-1 栈顶指针 栈顶相应数组元素 栈与否空 s-top=-1 栈顶元素 修改栈顶指针6bceda7终结条件 递归某些8LU-front=LU-rear9运算符 操作数 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运用一种栈，则：（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，CABD5用S表达入栈操作，X表达出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应S和X操作串是什么？答：应是SXSSXSXX。各操作成果如下：S 1入栈X 1出栈 输出序列：1S 2入栈S 3入栈X 3出栈 输出序列：13S 4入栈 X 4出栈 输出序列：134X 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，CDEBA7写出如下运算式后缀算术运算式 3x2+x-1/x+5 (A+B)*C-D/(E+F)+G答；相应后缀算术运算式 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)/*初始化队列*/ 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) /*判断队列与否为空算法*/ 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答案一、单项选取题1B 2B 3D 4C 5B 6A 7A 8C 9A 10. D11. A 12C 13C 14B 15B 16C 17B 18C 19A 20B21D 22B 23. B 24. B 25. C 26. A 27A 28C二、填空题 1子树树木或后继结点数2树中所有结点度最大值3分支结点 非终端结点4叶子结点 终端结点5子树根 后继结点 孩子结点6祖先7树中结点最大层数8 9根结点 左子树 右子树10左子树 根结点 右子树11左子树 右子树 根结点12权13带权途径长度之和14最优二叉树 最小二叉树1569 162m-1 17多对多18所有顶点 一次19先序 20按层次21n222邻接矩阵 邻接表232(n-1)24n-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);/*CopyTree*/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答案一、单项选取题1D 2C 3B 4C 5D 6 7C 8D 9B 10D 11C 12C13A 14C 15D16B 17B 18D 19D20A21D22D23A 24A 25C 26C 27B 28A 29B 30C二、填空题 1哈希表查找法2数据项值 记录3主核心字4数学盼望值5顺序6二分查找 升序或降序排列 7顺序存储构造 8索引顺序查找 顺序查找9均不大于根结点值 均不不大于根结点值 二叉排序树10自变量 函数值119， 14， 16 ，17 12内部排序 外部排序 13互换排序 143154 816堆排序 迅速排序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已知序列（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，9085设一组记录核心字序列为（49，83，59，41，43，47），采用堆排序算法完毕如下操作：（规定小根堆，并画出中间过程）（1）以二叉树描述6个元素初始堆（2）以二叉树描述逐次取走堆顶元素后，经调节得到5个元素、4个元素堆答：（1）49598341434783474143594949834147435983594941434783495941594741498343434741598349594741438349474183594349474143834959（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次 15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 64715206416535(2)(3)平均查找长度=（1*1+2*2+3*3）/6=14/672461673185145（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)/* 在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）认真完毕本实验，并提交实验报告。