第二章线性表【数据结构与算法】3-阿里云开发者社区

习题2

题目

1.单项选择题

(1)链表不具有的特点是 ____。

A. 插入、删除不需要移动元素

B. 可随机访问任一元素

C. 不必事先估计存储空间

D. 所需空间与线性长度成正比

(2) 设单链表中结点的结构为(data.next)。若在指针p所指结点后插入由指针s指向的结点,则应执行____操作。

A.p->next=s; s->next=p;

B. s->next=p->next;p->next=s;

C.s->next=p;s=p

D. p->next=s;s->next=p->next;

(3)在双向链表指针p的指针前插入一个指针q的结点,操作是 ____。

注:双向链表的结点结构为(prior,data,next)。

A. p->prior=q;q->next=p;p->prior->next=q;q->prior=q;

B. p->prior=g;p->prior->next=q;q->next=p;q->prior=p->prior;

C. q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;

D.q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;

(4)对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度，和在给定值为x的结点后插入一个新结点的时间复杂度分别为 ____。

A. O(n),O(n)

B.O(1),0(n)

C.O(1),O(1)

D.O(n),O(1)

(5)以下错误的是 ____。

① 静态链表既有顺序存储的优点,又有动态链表的优点。所以,它存取表中第i个元素的时间与i无关。

② 静态链表中能容纳的元素个数在表定义时就确定了,以后不能增加。

③ 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。

A. ①②

B. ①

C. ①②③

D. ②

2.综合题

(1) 设有一线性表e=(e1,e2,…,e[n-1],en,其逆线性表定义为e’=(en,e[n-1],…,e2,e1)。请设计一个算法,将线性逆置,要求逆线性表仍占用原线性表的空间,并且用顺序表和单链表两种方法来表示,写出不同的处理函数。
(3) 已知线性表A的长度为n,并且采用顺序存储结构。请编写算法，删除线性表中所有值为x的元素。

(5) 假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表中某结点的指针，试编写算法,在链表中删除指针s所指结点的前驱结点。
(8)设指针la和lb分别指向两个无头结点单链表中的首元结点,试设计算法,从表la中删除自第i个元素起共len个元素,并将它们插入表lb的第j个元素之后。
(9)设带头结点的线性单链表A=(a1,a2,…,am),B=(b1,b2,…bn)。试编写算法按下列规则合并A、B为线性单链表C,使得

C=(a1,b1,…,am,bm,b_(m+1),…,bn),m<=n

或者

C=(b1,a1,…,bn,an,a_(n+1),…,am),m>n

参考

1.单项选择题

(1) B

(2) B

(3) C

(4) B

(5) A

2.综合题

(1)

顺序表

相关代码请看配套资源

(1)_1.c

/*
（1）设有一线性表e=(e1,e2,...,e[n-1],en,其逆线性表定义为e'=(en,e[n-1],...,e2,e1)。
请设计一个算法,将线性逆置,
要求逆线性表仍占用原线性表的空间,
并且用顺序表和单链表两种方法来表示,写出不同的处理函数。
*/
void Reverse(SeqList* L){
  int len=L->length+1;//数组实际长度因为有索引【0】 
  int i=1;
  for(i=1;i<=len/2;i++){
    int t=L->elem[i];
    L->elem[i]=L->elem[len-i];
    L->elem[len-i]=t;
  }
} 
int main(){
  SeqList _L;
  SeqList *L=&_L;
  //初始化 
  Init(&_L);
  //创建 
  int n=0;
  printf("输入线性表的长度："); 
  scanf("%d",&n);
  CreateList(L,n);
  Output(L);
  //倒置
  Reverse(L);
  printf("倒置\n");
  Output(L);
}

运行结果如下

单链表

相关代码请看配套资源

(1)_2.c

/*
（1）设有一线性表e=(e1,e2,...,e[n-1],en,其逆线性表定义为e'=(en,e[n-1],...,e2,e1)。
请设计一个算法,将线性逆置,
要求逆线性表仍占用原线性表的空间,
并且用顺序表和单链表两种方法来表示,写出不同的处理函数。
*/
// 单链表的逆置
void Reverse(LinkList H){  
  LNode * p,*q;
  p=H->next;    //p指向第一个数据结点
  H->next= NULL;    //将原链表置为空表H
  while(p){
    q=p;
    p=p->next;
    q->next=H->next;  //将当前结点插到头结点的后面(头插)
    H->next=q;
  }
} 
void main(){
  //建立 
  LinkList h=CreatByBear();
  OutPut(h);
  //逆置 
  Reverse(h);
  printf("逆置\n");
  OutPut(h);
}

运行结果如下

(3)

相关代码请看配套资源

(3).c

/*
3）已知线性表A的长度为n,并且采用顺序存储结构。
请编写算法，删除线性表中所有值为x的元素。
*/
int Delete(SeqList* L, ElemType e){
  int i=1;//存储索引 
  int find=0;//找到表值 
  for(i;i<=L->length;i++){
    if(L->elem[i]==e){
      find=1;
      break;    
    }
  }
  if(find==0){
    return 0;//删除失败 
  }
  int j;
  for (j=i;j<=L->length-1;j++){
    L->elem[j]=L->elem[j+1];//向上移动 
  }
  L->length--;
  return 1;//删除成功   
}
void DeleteValue(SeqList* L, ElemType e){
  int r=Delete(L,e);
  if(r==1){
    DeleteValue(L,e);
  }
}
int main(){
  SeqList _L;
  SeqList *L=&_L;
  //初始化 
  Init(&_L);
  //创建 
  int n=0;
  printf("输入线性表的长度："); 
  scanf("%d",&n);
  CreateList(L,n);
  Output(L);
  //删出所有的给定值
  int x;
  printf("输入删除的值：");
  scanf("%d",&x); 
  DeleteValue(L,x); 
  Output(L);
}

运行结果如下

(5)

/*
（5）假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。
已知s为指向链表中某结点的指针，
试编写算法,在链表中删除指针s所指结点的前驱结点。
*/
#include <stdio.h>
typedef struct node{
  int data;
  struct node * next; 
}Dlist;
void delete(Dlist *s){
  Dlist *p=s->next,*temp;  
  while(p->next!=s){
    temp=p;
    p=p->next;
  }
  temp->next=s; 
  free(p);
}

(8)

相关代码请看配套资源

8.c

//算法 
int Fun(LinkList la,LinkList lb,int i,int len,int j,LinkList *an){
  LNode *b=Get(lb,j);  //查找第j个结点
  if(b==NULL){
    printf("插入位置j错") ;
    return ERROR; 
  }
  LNode *b_=b->next;  //保存原来b后面的结点 
  if(i==1){
    if(len>Length(la)){
      printf("删除长度len错") ;
      return ERROR; 
    }
    LinkList tem=la;
    la=NULL; 
    LNode *a=Get(tem,len);
    *an=a->next;
    a->next=NULL;
    b->next=tem;
    a->next=b_;
    la=*an;
    return TRUE;
  }
  LNode *a=Get(la,i-1);  //查找第i-1个结点
  if(a->next==NULL) {   //第i个结点不存在，不能删除 
    printf("删除位置i错") ;
    return ERROR; 
  } 
  if(i-1+len>Length(la)){
    printf("删除长度len错") ;
    return ERROR; 
  } 
  int count=0;
  for(count=0;count<len;count++){
    LNode *s=a->next;//第i个结点 
    a->next=s->next;//删除 
    b->next=s;//新结点插入 第j结点 后 
    b=s;  //尾插 
  }
  b->next=b_; 
  return TRUE;
}
void main(){
  printf("输入la:\n");
  //建立 
  LinkList la=CreatByBear();
  OutPut(la);
  //建立 
  printf("\n输入lb:\n");
  LinkList lb=CreatByBear();
  OutPut(lb);
  int i;
  int len;
  int j;
  printf("输入i:");
  scanf("%d",&i); 
  while(i<=0){
    printf("重新输入i:");
    scanf("%d",&i);
  }
  printf("输入len:");
  scanf("%d",&len);
  while(len<=0){
    printf("重新输入len:");
    scanf("%d",&len);
  }
  printf("输入j:");
  scanf("%d",&j);
  while(j<=0){
    printf("重新输入j:");
    scanf("%d",&j);
  }
  printf("\n"); 
  LinkList *an=(LinkList*)malloc(sizeof(LinkList)); 
  int result=Fun(la,lb,i,len,j,an);
  if(result==1){
    printf("输出la:\n");
    if(i==1){
      la=*an;     
    }
    OutPut(la);
    printf("\n输出lb:\n");
    OutPut(lb);
  }
}

运行结果如下

(9)

相关代码请看配套资源

9.c

function1和function2都可以用

//function 和function2都可以实现
LinkList function(LinkList A,LinkList B){
  LinkList C = (LinkList)malloc(sizeof(LNode));
    C->next = NULL;
  LinkList pa, pb, qa, qb;
    pa = A->next;  // pa 指向 A 的首元结点
    pb = B->next;
    C = A;        // 因为 C 中第一个元素是 A 中的元素，所以只需要 C 指向 A就行了
    while(pa && pb)
    {
        qa = pa;
        qb = pb;
        pa = pa->next;
        pb = pb->next;
        qb->next = qa->next;
        qa->next = qb;
    }
    if(!pa)  // 如果 A 链表的长度小于 B 链表的长度//默认小于等于 
        qb->next = pb; // 将 B 的后续节点连接到新链表的尾端
    pb = B;  // 准备删除 B 链表
    free(pb);
    return C;
}
LinkList function2(LinkList l,LinkList sh){
  LinkList H=(LinkList)malloc(sizeof(LNode)); //生成头结点 
  H->next=NULL;   //空表 
  LNode *s, *r=H;
  LNode *ls=l->next;
  LNode *ss=sh->next;
  int i;
  int n=Length(sh);
  for(i=0;i<2*n;i++){
    if(i%2==0){//插sh 
      s=ss;
      r->next=s;
      r=s;
      ss=ss->next;
    }else{
      s=ls;
      r->next=s;
      r=s;
      ls=ls->next;
    }
  }
  r->next=ls;
  return H;
}
void main(){
  //建立 
  printf("a\n");
  LinkList a=CreatByBear();
  OutPut(a);
  printf("\nb\n");
  LinkList b=CreatByBear();
  OutPut(b);
  LinkList c;
  printf("\n");
//  if(Length(a)<=Length(b)){
//    c=function(a,b);
//  }else{
//    c=function(b,a);
//
//  }   
  if(Length(a)>Length(b)){
    c=function2(a,b);
  }else{
    c=function2(b,a);
  }
  printf("c\n");
  OutPut(c);
} 
}

运行结果如下

第二章线性表【数据结构与算法】3

习题2

题目

1.单项选择题

(1)链表不具有的特点是 ____。

(2) 设单链表中结点的结构为(data.next)。若在指针p所指结点后插入由指针s指向的结点,则应执行____操作。

(3)在双向链表指针p的指针前插入一个指针q的结点,操作是 ____。

(4)对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度，和在给定值为x的结点后插入一个新结点的时间复杂度分别为 ____。

(5)以下错误的是 ____。

2.综合题

参考

1.单项选择题

(1) B

(2) B

(3) C

(4) B

(5) A

2.综合题

(1)

(3)

(5)

(8)

(9)

热门文章

最新文章

相关电子书

第二章 线性表【数据结构与算法】3

习题2

题目

1.单项选择题

(1)链表不具有的特点是 ____。

(2) 设单链表中结点的结构为(data.next)。若在指针p所指结点后插入由指针s指向的结点,则应执行____操作。

(3)在双向链表指针p的指针前插入一个指针q的结点,操作是 ____。

(4)对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度，和在给定值为x的结点后插入一个新结点的时间复杂度分别为 ____。

(5)以下错误的是 ____。

2.综合题

参考

1.单项选择题

(1) B

(2) B

(3) C

(4) B

(5) A

2.综合题

(1)

(3)

(5)

(8)

(9)

热门文章

最新文章

相关电子书

第二章线性表【数据结构与算法】3