数据结构本科形成性考核册复习资料

1、作业 1一、单项选择题1C2 D3B4C5D6C7B8C9A10B11C 12D 13C 14A 15B 16C 17C 18B 19B 20D二、填空题1n-i+12n-i3集合 线性结构树形结构 图状结构4物理结构 存储结构5线性结构非线性结构6有穷性 确定性 可形性 有零个或多个输入 有零个或多个输出7图状结构8树形结构9线性结构10 n-1 O（n）11 s->next=p->next;12 head13 q->next=p->next;14 p->next=head;15单链表16顺序存储 链式存储17存储结构18两个 直接后继 直接前驱 尾结点 头结点

2、19头结点的指针指向第一个结点的指针20链式 链表 三、问答题1简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？ 答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中 的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构 是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同， 但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数 据的操作在灵活性，算法复杂度等方面差别较大。2解释顺序存储结构和链式存储结构的特点，并

3、比较顺序存储结构和链式存储结构的优缺点。 答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的， ，要求内存中存储 单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（ 1）在做插入和删除操作时，需移动大量元素； （ 2）由于难以估计，必须预先分配较大的空间，往 往使存储空间不能得到充分利用； （ 3）表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表 示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。 缺点：存储密度小，存储空间利用率低。3什么情况下用顺序表比链表好？答

4、：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。如果线性表的变化长度 变化不大，且其主要操作是查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是插入、删 除操作，则采用链表。4 解释头结点、第一个结点（或称首元结点）、头指针这三个概念的区别？答：头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据 元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。5 .解释带头结点的单链表和不带头结点的单链表的区别。答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。在结构上，带头结点的单

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

6、.(1) p=q_>next(2) q_>next=p->next作业2一、单选CBAAC AACCC BCBBC CBAAD BAABD ACDCA D二、填空1、堆栈2、加13、rear 值+1 fear 值+14、假上溢5、队列是否已满sq->=MaxSize 尾指针的值 尾指针指向的数据单元队列是否为空 sq->=sq->front 队头指针加 1 返回 front 所指位置的元素。6、bceda7、终止条件 递归条件8、LU->rear=Lu-front9、？ab+c/fdc/-10、s-next=h;11、h=h->next;12、r

7、->next=s;13、f=f->next;14、字符15、顺序存储 链接存储16、0 117、特殊 稀疏18、() () 219、( d,e,f)20、两串的长度相等，且对应位置上的字符相同。21、i(i-1)/2+j22、行号 列号 元素值三、简答1、一般线性表使用数组来表示的，线性表一般有插入、删除、读取等对于任意元素的操作而栈只是一种特殊的线性表，栈只能在线性表的一端插入(称为入栈，push)或者读取栈顶元素或者称为“弹出、出栈” (pop)。 栈在数组的基础上可以用一个指向栈顶的标识符来表 示，如 a 表示栈，则 atop 就表示栈顶元素 。2、 队列是一种运算受限的线性

8、表，它的运算限制与栈不同 ，是两头都有限制 ，插入只能在表的一端进行 (只进不出 )，而删除只能在表的另一端进行(只出不进 )。而一般线性表是用数组来表示的，线性表一般有插入、删除、读取等对于任意元素的操作。3、 如果你的栈有头结点且头结点不存储有效数据，且sq 指向栈顶的有效数据，那么 sq->next = NULL 表示栈空。如果你的栈有头结点且头结点存储有效数据，且sq指向栈顶的有效数据，那么sq=NULL 表示栈空。4、 (1)CBA，ABC，BAC，BCA，ACB可根据栈的特点 "后进先出 "来的出结果 ，不可能的是： CAB (2)可能的输出序列： ABC

9、D， ABDC， ACBD， ACDB ，ADCB ，BACD ，BADC ，BCAD ，BCDA ，BDCA CBAD， CBDA， CDBA， DCBA ，共 14 种共 10 种。CEDBA不可能的输出序列： ADBC，BDAC，CDAB， CABD， CADB，DCAB， DABC， DACB ，DBCA ，DBAC5、SXSSXSXX6、以元素 C 开头的有： CBADE CBAED CBDAE CBDEA CDBAE CDBEA CDEBA 以元素 D 开头的有： DCBAE DCEBA DCBEA DECBA7、 第一个有问题3x2x+1x/-5+AB+C*DEF+/-G+8、一

10、般线性表使用数组来表示的，线性表一般有插入、删除、读取等对于任意元素的操作 广义表是线性表的推广 ，也称为列表 ，也是一种线性结构 ;任何一个非空表 ，表头可能是原子 ，也可能是列表 ;但表尾一定是列表 . 广义表中元素既可以是原子类型 ，也可以是列表 ;当每个元素都为原子且类型相同时 ，就是线性表 .四、1、这个题目拿不准( 1) q->front=p->next;(2) free(p);(3) else fron t=rear=p五、1栈的特点是先进后出，而出队的序列e2首，即el肯定在栈中，然后是 e4,这样，e1,e3,e4必须同时在栈中，才能保证e4出栈，然后是e3出栈，

11、此时只有el在栈中，然后是 e6出栈，这样，必须保证e1,e5,e6同时在栈中。因此，此栈容量最小为3。2、不会。作业3一、单选BBBCB ABCAD ACCBB C1CAB BBBBD DAC17 题答案，好像是 1 倍。二、填空1、非空子树2、树中所有结点的度的最大值3、 分支结点非终端结点4、 叶子结点分支结点5、后继孩子结点6、祖先7、树中结点的最大层数。8、( n+1)/29、根结点 左子树右子树10、左子树根结点右子树11、第一个空不填左子树右子树根结点12、权13、带权路径长度之和14、最优二叉树 最小的二叉树15、7616、2n-1 个17、多对多18、所有的顶点一次19、先序

12、20、按层21、n22、邻接矩阵邻接表23、2(n-1)24、n-125、一维数组三、综合1、(1)先序：fdbacegihj(2) 中序：abcdefghij(3) 后序：acbedhjigf2、 此树如下：*表示分隔，-表示靠左边的距离只要斜线 /,其它不要画。*y/*B C/*/*、DG*H*/*八*L*k*m其后序遍历：GDBLHKMIEJFCA3、(1)树高为 X，则 2Ax>892>2Ax-1(2) 叶子结点数为结点数一半：即(3) 因为这是一棵完全二叉树，有(4) 最后一个非终端结点的序号为4、( 1)-ABC-ABC(A表示乘方)，则X应为10，即树高为10。892

13、/2=446 个892个结点，892-1=891，为单数，故单支结点数为892/2=446。1个。A5、不会6、不会7、(1) V1V2*V5本题目有错误，多了个(V3，V4)，划去一个。*V4-V3只画线，不要*(2)邻接矩阵为大括号要画到最后一行。v1 v2 v3 v4 v5a1=01010 v110011v200011v311100v401100v5<-最后行。邻接表：(参照课本P130)v1至v5分别由0-4来编号。024A1145A245A3123A423A(3 )每个顶点的度： D(v1)=2D(v2)=3 D(V3)=2D(v4)=3D(V5)=2四、1、( 1) retu

14、rn c1+;( 2) NodeLevel(BT->right,x ) ; ( 3) (c2>=1) return c2+;(2)dfstree(GA,j, n);2、(1)for(j=0;j<=n;j+)五、还没做出来。作业4一、单选DCABA ABDBD DDACD BBDDD CDCAA DBAxC二、填空1、哈希查找2、数据项的值记录3、主关键字4、数学期望值5、顺序6、二分查找 升序或降序排列7、顺序存储结构8、索引顺序查找顺序查找9、都小于它的根结点的值都大于它的根结点的值 一棵二叉排序树10、自变量 函数值11、8， 13，15，1612、内部排序 外部排序13

15、、交换排序14、16 15、4 816、快速排序 堆排序17、主关键字18、其中关键字相等的记录19、（n-1） （n-j ）20、堆中最后一个 堆顶元素 交换三、综合1、解：取第一个元素：第二趟第三趟第四趟第五趟第六趟7070 8370 83 10070 83 100 10510 70 83 100 1057 10 70 83 100 1053、解：初始状态：第一趟冒泡第二趟冒泡第三趟冒泡第四趟冒泡第五趟冒泡四、1、（ 1） j>0（ 2）aj; (3)j-; (4)temp2、解：初始 10， 18，4， 3，6，12，1，9，15，8( 1， 1)归并后： 10 18 3 4 6 12 1 9 8 15( 2， 2)归并后： 3 4 10 18 1 6 9 128 15(4,4) 归并后： 1 3 4 6 9 10 12 18 8 15(8,2) 归并后： 1 3 4 6 8 9 10 12 15 18 17，18，60，40，7，32， 73，65，8517 18 40 7 32 60 73 65 8517 18 7 32 40 60 73 65 8517 7 18 32 40 60 73 65 857 17 18 32 40 60 73 65 857 17