数据结构（本）形考作业1参考答案：.pdfVIP

数据结构（本）形考作业1参考答案：--第1页

数据结构（本）形考作业1参考答案:

一、单项选择题

1．C2．D3．C4．C5．D6．C7．C8．C9．A10．B

二、填空题

1．n-i+12．n-i3.集合、线性表、树、图4.存储结构、物理结构5.线性表图

6.有穷性、确定性、可行性、有输入、有输出7.图8.树9.线性表10．n-1O(n)

11．s-next=p-next;12．head13．q-next=p-next;14．p-next=head;15．单链

表16．顺序存储链式存储17．存储结构18.两个后继结点前驱结点尾结点头

结点

19．指向头结点的指针指向第一个结点的指针20．链式链表

三、问答题

1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？

答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结

构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之

间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不

同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结

点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂

度等方面差别较大。

2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的

优缺点。

数据结构（本）形考作业1参考答案：--第1页

数据结构（本）形考作业1参考答案：--第2页

答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统

一的，，要求内存中存储单元的地址必须是连续的。

优点：一般情况下，存储密度大，存储空间利用率高。

缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预

先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。

链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点

值，另一部分存放表示结点间关系的指针。

优点：插入和删除元素时很方便，使用灵活。

缺点：存储密度小，存储空间利用率低。

3．什么情况下用顺序表比链表好？

答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。如

果线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；如果线性表的长度变

化较大，且其主要操作是插入、删除操作，则采用链表。

4．解释头结点、第一个结点（或称首元结点）、头指针这三个概念的区别？

答：头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）

是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首

元结点）的指针。

5．解释带头结点的单链表和不带头结点的单链表的区别。

答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作

上。

在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点

的单链表不含头结点；在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入

数据结构（本）形考作业1参考答案：--第2页

数据结构（本）形考作业1参考答案：--第3页

或删除的位置是地第一个结点还