《数据结构》第二章习题参考答案殷人昆版.doc

《《数据结构》第二章习题参考答案殷人昆版.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》第二章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。(×)2、链表中的头结点仅起到标识的作用。(×)3、所谓静态链表就是一直不发生变化的链表。(×)4、线性表的特点是每个元素都有一个前驱和一个后继。(×)5、在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（×）6、线性表就是顺序存储的表。（×）7、课本P842.4题（1）√（2）×（3）×（4）×（5）√（6）×（7）×（8）√（9）×（10）×（11）√（12）√二、单项选择题1、下面关于线性表的叙述中，错误的是哪一个？

2、（B）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。2、链表不具有的特点是（B）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比3、(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（B）A．（

3、1），（2）B．（1）C．（1），（2），(3)D.（2）4、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B）A．p->link=s;s->link=p->link;B．s->link=p->link;p->link=s;C．p->link=s;p->link=s->link;D．p->link=s->link;p->link=s;5、若某线性表最常用的操作是取任一指定序号的元素及其前驱，则利用（C）存储方式最节省时间。A．单链表B．双链表C．顺序表D．带头结点的双循环链表6、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C）。A．O(n)，O(n)B.O(n

4、)，O(1)C.O(1)，O(n)D.O(1)，O(1)7、在一个以h为头的单循环链中，p指针指向链尾的条件是（A）A.p->next=hB.p->next=NULLC.p->next->next=hD.p->data=-1三、填空题1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用___顺序____存储结构。2、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是__（n-1）/2______。3、在单链表中设置头结点的作用是___可以使链表的操作统一、编程简洁___。4、

5、一个头指针为head的带头结点的单链表为空表的条件是：_head->link==NULL。5．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动____n-i+1___个元素。6、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为__O(1)__,在给定值为x的结点后插入一个新结点的时间复杂度为__O(n)___。四、综合题1、线性表可用顺序表或链表存储。问：（1）两种存储表示各有哪些主要优缺点？（2）如果要求对n个表长动态变化的表进行处理，表的总数可能也发生改变，在此情况下，应选用哪种存储表示？为什么？参考解答：(1)顺序存储时，逻

6、辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高，可实现随机存取；缺点是插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活；缺点是存储密度小，存储空间利用率低，只能顺序存取。(2)宜选用链式存储结构，有利于高效进行动态内存开辟和插入、删除操作。2、试述头结点,首元结点,头指针这三个概念的区别。参考解答：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链

7、表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（也可存放链表的长度、用做监视哨等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。3、课本P832.3题参考解答：64，634、课本P852.10题参考解答：（1）//删除最小元素并返回其