数据结构(本)形考作业1参

作业1参

一、单项选择题

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-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．解释头结点、第一个结点（或称首元结点）、头指针这三个概念的区别？

答：

头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。

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

    答：

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

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

在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。

四、程序填空题

1．

（1）p->data=i

（2）p->next=NULL

（3）q->next=p

（4）q=p

2．

（1）head=p

（2）q=p

（3）p->next=NULL

（4）p->next=q->next

（5）q->next=p

3．

（1）p=q->next

（2）q->next=p->next

五、完成：实验1――线性表

根据实验要求（见教材P201-202）认真完成本实验，并提交实验报告。