数据结构(本)形成性考核作业答案1

河南广播电视大学现教中心第1页共3页版权所有河南电大现教中心范颖，邮箱[e-mail]数据结构（本）形成性考核作业答案数据结构（本）作业1（本部分作业覆盖教材第1-2章的内容）一、单项选择题（1）C（2）D（3）B（4）C（5）D（6）C（7）B（8）C（9）A（10）B（11）C（12）D（13）C（14）A（15）B（16）C（17）C（18）B（19）B（20）D二、填空题（1）n-i+1（2）n-i（3）集合线性结构树形结构图状结构（4）物理结构存储结构（5）线性结构非线性结构（6）有穷性确定性可行性算法有零个或多个输入算法有零个或多个输出（7）图状结构（8）树形结构（9）线性结构（10）n-1O（n）（11）s-next=p-next;（12）head（13）q-next=p-next;（14）p-next=head;河南广播电视大学现教中心第2页共3页版权所有河南电大现教中心范颖，邮箱[e-mail]（15）单链表（16）顺序存储链式存储（17）存储结构（18）两个直接后继直接前驱尾结点头结点（19）头结点的指针指向第一个结点的指针（20）链式链表三、问答题1、简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。2、解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。3、什么情况下用顺序表比链表好？答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。如果线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。4、解释头结点、第一个结点（或称首元结点）、头指针这三个概念的区别？答：头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。四、程序填空题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=p河南广播电视大学现教中心第3页共3页版权所有河南电大现教中心范颖，邮箱[e-mail]3、（1）p=q-next（2）q-next=p-next五、完成：实验1――线性表根据实验要求（见教材P201-202）认真完成本实验，并提交实验报告。