数据结构与算法线性表复习习题【1】

数据结构与算法线性表复习习题【1】  

　　第 章  线性表

　　 描述以下三个概念的区别 头指针 头结点 首元结点（第一个元素结点）

　　解 头指针是指向链表中第一个结点的指针 首元结点是指链表中存储第一个数据元素的结点 头结点是在首元结点之前附设的一个结点 该结点不存储数据元素 其指针域指向首元结点 其作用主要是为了方便对链表的操作 它可以对空表 非空表以及首元结点的操作进行统一处理

　　 填空题

　　解 ( ) 在顺序表中插入或删除一个元素 需要平均移动表中一半元素 具体移动的元素个数与元素在表中的位置有关

　　( ) 顺序表中逻辑上相邻的元素的物理位置必定紧邻 单链表中逻辑上相邻的元素的物理位置不一定紧邻

　　( ) 在单链表中 除了首元结点外 任一结点的存储位置由其前驱结点的链域的值指示

　　( ) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理

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

　　解 当线性表的数据元素在物理位置上是连续存储的时候 用顺序表比用链表好 其特点是可以进行随机存取

　　 对以下单链表分别执行下列各程序段 并画出结果示意图

　　 画出执行下列各行语句后各指针及链表的示意图

　　L=(LinkList)malloc(sizeof(LNode));P=L;

　　for(i= ;i<= ;i++){

　　P >next=(LinkList)malloc(sizeof(LNode));

　　P=P >next;P >data=i* ;

　　}

　　P >next=NULL;

　　for(i= ;i>= ;i ) Ins_LinkList(L i+ i* );

　　for(i= ;i<= ;i++) Del_LinkList(L i);

　　解