第二章 线性表
一、填空题
1、数据逻辑结构包括 线性结构 、 树型结构 、 图型结构 这三种类型，树形结构和图形结构合称为 非线性结构 。
2、在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 个前驱结点，最后一个结点 没有 后续结点，其余每个结点有且只有 一 个后续结点。
3、在顺序表中插入或删除一个元素，需要平均移动 一半 元素，具体移动的元素个数与 插入或删除的位置 有关。
4、在顺序表中，逻辑上相邻的元素，其物理位置 一定 相邻。在单链表中，逻辑上相邻的元素，其物理位置 不一定 相邻。
5、在带头结点的非空单链表中，头结点的存储位置由 头指针 指示，首元素结点的存储位置由 头结点的next域 指示，除首元素结点外，其它任一元素结点的存储位置由 其直接前趋结点的next域 指示。
6、阅读下列算法，并补充所缺内容。
void purge_linkst( ListNode *& la )
{
// 从头指针为 la 的有序链表中删除所有值相同的多余元素，并释放被删结点空间
ListNode *p,*q;
if(la==NULL) return;
q=la; p = la->link;
while (p)
{
if (p && ___(1)p->data!=q->data___) {q=p; p = p->link;}
else
{
q->link= ___(2)p->link___;
delete(p);
p=___(3)q->link___;
}
}//while
}// purge_linkst
二、选择题
1、在数据结构中，从逻辑上可以把数据结构分成 C 。
A、动态结构和静态结构 B、紧凑结构和非紧凑结构
C、线性结构和非线性结构 D、内部结构和外部结构
2、线性表的逻辑顺序与存储顺序总是一致的，这种说法 B 。
A、正确 B、不正确
3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址 D 。
A、必须是连续的 B、部分地址必须是连续的
C、一定是不连续的 D、连续或不连续都可以
4、在以下的述叙中，正确的是 B 。
A、线性表的线性存储结构优于链表存储结构
B、二维数组是其数据元素为线性表的线性表
C、栈的操作是先进先出
D、队列的操作方式是先进后出
三、综合题
1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
A、在P结点后插入S结点的语句序列是（（4）、（1））；
B、在P结点前插入S结点的语句序列是（（7）、（11）、（8）、（4）、（1））；
C、在表首插入S结点的语句序列是（（5）、（12））；
D、在表尾插入S结点的语句序列是（（9）、（1）、（6）或（11）、（9）、（1）、（6））（其中6的位置可变）；
（1）P->next=S;
（2）P->next=S->next->next;
（3）P->next=S->next;
（4）S->next=P->next;
（5）S->next=L;
（6）S->next=NULL;
（7）Q=P;
（8）while(P->next!=Q) P=P->next;
（9）while(P->next!=NULL) P=P->next;
（10）P=Q;
（11）P=L;
（12）L=S;
（13）L=P;
2、已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
A、删除P结点的直接后继结点的语句序列是（11、3、14）；
B、删除P结点的直接前驱结点的语句序列是（10、12、8、11、3、14）；
C、删除P结点的语句序列是（10、12、7、3、14）；
D、删除首元结点的语句序列是（12、11、3、14）；
E、删除尾元结点的语句序列是（9、11、3、14）或（12、9、11、3、14）；
（1）P=P->next;
（2）P->next=P;
（3）P->next= P->next ->next;
（4）P = P->next ->next;
（5）while(P->next!=NULL) P=P->next;
（6）while(Q->next!=NULL) {P=Q;Q=Q->next};
（7）while(P->next!=Q) P=P->next;
（8）while(P->next->next!=Q) P=P->next;
（9）while(P->next->next!=NULL) P=P->next;
（10）Q=P;
（11）Q=P->next;
（12）P=L;
（13）L=L->next;
（14）free(Q);
3、 线性表定位操作ListFind(L, x)的功能是：在线性表L中查是否存在数据元素x，如果存在，返回线性表中和x值相等的第1个数据元素的序号（序号编号从0开始）；如果不存在，返回-1。要求编写顺序表的定位操作算法。
int ListFind(Sqlist L, ElemType x) {
ElemType *p;
int i=0;
p = L.elem;
while(i < L.length-1 && !Compare(*p++,x)){
return i;
++i;
}
return -1;
}
4、 在有些应用中，允许线性表中存在值相同的数据元素。线性表的另一个删除操作ListDeleteMore(L, x)的功能是：删除线性表L中所有等于x的数据元素。要求编写单链表的删除操作算法。
typedef struct Node
{
ElemType data;
struct Node *next;
} LNode;
int ListDeleteMore(LNode *L, ElemType x)
/*删除带头结点的单链表L的数据元素值为x结点*/
/*删除成功时返回1；失败返回0*/
{
LNode *p,*q *s;
int j，flag;
flag=0;
p = L; /*p指向首元结点*/
j = -1; /*j初始为-1*/
q=p->next;
while(q != NULL)
/*每次让指针p指向数据元素值为x的前一结点,q指向x*/
{ if(q->data= x)
{ flag=1
p->next = q->next; /*把数据元素ai结点从单链表中删除指*/
free(q); /*释放指针q所指结点的内存空间*/
q=p->next; /*只改q指针,p指针暂时不变*/
}
else
{ p = q; /*p,q指针同时后移*/
q = q->next
}
}
if(flag=1)
Return 1; /*有x*/
else
return 0;/*无x*/
}
5、 编写算法实现顺序表的逆置，即要求把顺序表A中的数据元素序列（a0,a1,…,an-1）逆置为（an-1,…,a1,a0），并把逆置后的数据元素存储到顺序表B中。
# define LIST_INIT_SIZE 100
sizeof 指针typedef struct {
ElemType *elem; // 存储空间基址
int length; // 当前长度
int listsize; // 当前分配的存储容量
// (以sizeof(ElemType)为单位)
} SqList;
void Reverse(Sqlist &LA，Sqlist &LB)//顺序表的就地逆置
{ ElemType t;
For(i=0,j=LA.length-1;i<j;i++,j--)
{ T=LA.elem[i];LA.elem[i]=LA.elem[j];LA.elem[j]=t;
LB.elem[i]=LA.elem[i];
}
}
6、编写循环双向链表的求数据元素个数操作算法和取数据元素操作算法。
//以下双向循环链表带头结点
struct DuLNode
{
ElemType data;
struct DuLNode *prior,*next;
}DuLNode;
typedef struct DuLNode *DuLinkList;
int ListLength(DuLinkList L)
{//初始条件：L存在。操作结果：返回L中数据元素的个数
int i=0;
DuLinkList p=L->next;//p指向第一个结点
while(p!=L) //没到表头
{
i++;
p=p->next;
}
return i;
}
Status GetElem(DuLinkList L,int i,ElemType *e)
{//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
int j=1;
DuLinkList p=L->next;//p指向第一个结点
while(p!=L&&j<i) //顺指针向后查知道p指向第i个元素或p指向头结点
{
p=p->next;
j++;
}
if(p==L||j>i) //第i个元素不存在
return ERROR;
*e=p->data; //取第i个元素
return OK;
}
7、设计单循环链表，要求：单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取数据元素操作和判非空操作。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论