问南广播电视大学现数中心 数据结构（本）形成性考核作业答案 数把结构（本）作业1 (本部分作业漫盖数材第1-2章的内容) 一、单灭选择思 (1)C (2)D (3) B (4) (5) D (6) (7) B (8) C (9) A (10)B (11)C (12)D (13)C (14A (15)B (16)C (17)B (18)B (19)D 二、就空题 (1)ni+1 (2》mi (3) 使合找性结构 树形结构 图状结构 (4) 物理结构存储结构 (5) 线性结构非线性结构 (6) 有穷性确定性 可行性 算法有零个或多个输入算法有零个或多个输出 (7) 图状结构 (8 树形结构 (9) 线性结构 (10)m10(n) (1l）乡2nel-p-2ne (12)head (13)g>next=p->next (14)p->next"head, (15)单蛙表 第1页共3页 版权所有河南电大规赖中心范霸，配箱5@单鱼m
河南广播电视大学现教中心 第1页 共3页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 数据结构（本）形成性考核作业答案 数据结构（本）作业 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） B （18） B （19） D 二、填空题 （1） n-i+1 （2） n-i （3） 集合 线性结构 树形结构 图状结构 （4） 物理结构 存储结构 （5） 线性结构 非线性结构 （6） 有穷性 确定性 可行性 算法有零个或多个输入 算法有零个或多个输出 （7） 图状结构 （8） 树形结构 （9） 线性结构 （10） n-1 O（n） （11） s->next=p->next; （12） head （13） q->next=p->next; （14） p->next=head; （15） 单链表
河南广播电视大学现教中心 (16)顺序存铅链式存储 (17)存储结构 (18)两个直接后整直接前聚尾结点头结点 (19)头结点的指针指向第一个结点的指针 (20)铣式随表 三、问答题 1、简述数据的逻细结构和存储结构的区别与联系，它门如何影响算法的设计与实现？ 容：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻惧结构， 数据在计算机中的存储表示称为数据的存储结构。可见，数据的逐辑结构是反晚数据之间的 固有关系，面数据的存销结构是数据在计算机中的存储表示。尽管因采用的存储结构不网： 逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部偏息，找到其相邻的结点， 从而保留了逻辑结构的特点，采用的存储结构不月。对数据的操作在灵活性，算法复柔度等 方面差别较大： 2、解释顺序存他结构和链式存储结构的特点，并比较顺序存储结构和睦式存储结构的优 缺点。 答：顺序结构存储时，相邻数据元素的存放地址也相忽，即逻细结构和存储结构是统一 的，要求内存中存储单元的地址必须是连续的。 优点：一般情况下，存储密度大，存储空间利用率高。 缺点：(1)在做插入和副除操作封，需移动大量元素：《2)由于走以估计，必须预先分 配较大的空阿。往往使存储空间不能得到充分利用：(3》表的容量难以扩充。 战式结构存销时，相邻数据元素可随意存放，所占空间分为两部分，一部分存成结点值， 另一部分存放表示结点间关系的指针， 优点：括入和别除元素时很方便，使用灵话。 缺点，存储密度小，存储空间利用率低。 3、什么情况下用顺序表比链表好？ 答：顺序表适于做查找这样的静态操作，链表适于做插入和制除这样的动古操作。如果 线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表：如果线性表的长度变化 较大，且其主要操作是插入，国除操作，则采用硅表。 4、解释头结点，第一个结点《或称首元结点)、头带针这三个概念的区别？ 答：头结点是在链表的开始结点之输附加的一个结点：第一个结点（或称首元结点）是 硅表中存储第一个数据元素的结点：头指针是番向链表中第一个结点（成为头结点成为首元 结点)的指针。 四、程序填空是 1.(1)pda= (2)p->next-NULL (3)q->next-p (4)p 2.(1)head->next-NUL (2)p->next=q->next (3)q->next-p 3、(1)p-9>w (2)q->next=p->next 第2项共3页 版权所有河南电大现教中心植额，都箱dpm恒cm
河南广播电视大学现教中心 第2页 共3页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn （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=p 2、 （1）head->next=NULL; （2）p->next=q->next （3）q->next=p 3、 （1）p=q->next （2）q->next=p->next
河南厂播电现大学现数中心 五、完成：实验1一一线性表 根据实验要求（见教材P细3》认真完成本实验，并提交实验报告。 第3风共3项 版权所有河南电大现教中心范额，邮箱5@m加m
河南广播电视大学现教中心 第3页 共3页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 五、完成：实验 1――线性表 根据实验要求（见教材 P201-202）认真完成本实验，并提交实验报告