1. Toy模板网首页
  2. > Toy博客

数据结构第1~2章练习答案（PTA）

7月前 作者：Yhan涵涵 分类：Toy博客 阅读(32) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构第1~2章练习答案（PTA）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

单选题

2-1下面代码段的时间复杂度是（B）

x=0;
for( i=1; i<n; i++ )
    for ( j=1; j<=n-i; j++ )
        x++;

A.O(n)                B.O(n²)                C.O(n³)                D.O(2ⁿ)

2-2下列函数的时间复杂度是（B）

int func ( int n )
{   int i = 0, sum = 0;
    while ( sum < n )  sum += ++i;
    return i;
}

A.O(logn)           B.O()                C.O(n)                 D.O(nlogn) 

2-3顺序表是线性表的(B)

A.链式存储结构  B.顺序存储结构   C.索引存储结构   D.散列存储结构

2-4对于顺序表，以下说法错误的是（A）

A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址​

B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列

C.顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻

D.顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中

2-5以下说法错误的是 (C)

A.对于线性表来说，定位运算LocateElem在顺序表和单链表上的时间复杂度均为O（n）

B.插入、删除操作在顺序表上的实现，平均时间复杂度为O（n）

C.在链表上实现读表元运算的平均时间复杂度为O（1）

D.插入、删除操作在链表上的实现可在O（1）时间内完成

2-6若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（A）存储方式最节省时间（A）

A.顺序表        B.单链表        C.双链表        D.单循环链表

2-7哪个选项不是线性表的链式存储结构（B）

A.单链表        B.顺序表        C.循环链表     D.双向链表

2-8在N个结点的顺序表中，算法的时间复杂度为O(1)的操作是（A）

A.访问第i个结点（1≤i≤N）和求第i个结点的直接前驱（2≤i≤N）

B.在第i个结点后插入一个新结点（1≤i≤N）

C.删除第i个结点（1≤i≤N）

D.将N个结点从小到大排序

2-9线性表L=（a1, a2 ,……，an ）用一维数组表示，假定删除线性表中任一元素的概率相同（都为1/n），则删除一个元素平均需要移动元素的个数是（C）。

A.n/2                B.(n+1)/2        C.(n-1)/2        D.n

2-10顺序存储表示中数据元素之间的逻辑关系是由（C）表示的。

A.指针              B.逻辑顺序      C.存储位置    D.问题上下文

2-11对于顺序表的优缺点，以下说法错误的是(C)。

A.无需为表示结点间的逻辑关系而增加额外的存储空间

B.可以方便地随机存取表中的任一结点

C.插入和删除运算较方便

D.容易造成一部分空间长期闲置而得不到充分利用

2-12在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B）

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

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

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

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

2-13对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B）

A.head==NULL

B.head→next==NULL

C.head→next==head

D.head!=NULL

2-14设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（D）最节省时间。

A.单链表

B.单循环链表

C.带尾指针的单循环链表

D.带头结点的双循环链表

2-15链表不具有的特点是（B）

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

B.方便随机访问任一元素

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

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

2-16在单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行（C）

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

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

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

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

2-17带头结点的单链表h为空的判定条件是（B）

A.h == NULL;

B.h->next == NULL;

C.h->next == h;

D.h != NULL;

2-18将两个结点数都为N且都从小到大有序的单向链表合并成一个从小到大有序的单向链表，那么可能的最少比较次数是（B）

A.1        B.N        C.2N        D.NlogN

2-19对于一非空的循环单链表，h和p分别指向链表的头、尾结点，则有（A）

A.p->next == h

B.p->next == NULL

C.p == NULL

D.p == h

2-20在双向链表存储结构中，删除p所指的结点，相应语句为（C）

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

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

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

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

函数题

6-1 单链表按姓名插入删除

本题要求实现按姓名音序有序插入函数与按姓名删除函数。

函数接口定义：

Status ListInsert(LinkList &L,ElemType e);  //在单链表L中按姓名有序插入新联系人e
Status ListDelete(LinkList &L,char name[]);  //在单链表L中删除姓名为name的联系人信息

裁判测试程序样例：

#include<string.h>
#include<stdio.h>
#include<stdlib.h>

#define  OK     1
#define  ERROR 0
#define  OVERFLOW  -2

typedef int Status;
typedef  struct  Telephone{
          char name[10];
          char Tel[12];
}ElemType;
typedef struct LNode  /* 定义链式存储结构 */
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

Status ListInsert(LinkList &L,ElemType e);
Status ListDelete(LinkList &L,char name[]);

Status InitList(LinkList &L) {
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    return OK;
}

void Print_LinkList( LinkList H)     /* 输出链表中每个数据元素值 */
{
    LNode *p;
    p=H->next; //p指向首元结点
    if(p==NULL) printf("链表为空\n");
    while(p!=NULL)
    {
        printf("姓名：%s,电话：%s\n",p->data.name,p->data.Tel);
        p=p->next;
   }
  }/* Print_LinkList */

int  main()
  {
    LinkList L; 
    ElemType e;
    char name[10];
    int n;
    InitList(L);
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%s",e.name);
        scanf("%s",e.Tel);
        ListInsert(L,e);
    }
    Print_LinkList(L);   //输出单链表
    scanf("%s",name);  //输入删除人姓名
    if(ListDelete(L,name)){
        printf("删除后：\n");
        Print_LinkList(L);   //输出单链表
    }
    else{
        printf("查无此人！");
    }
    return 0;
}
/* 请在这里填写答案 */

参考答案：

Status ListInsert(LinkList &L,ElemType e)  //在单链表L中按姓名有序插入新联系人e
{
   LNode *p;
   p=(LNode *)malloc(sizeof(LNode));
   p=L;
   while(p->next!=NULL&&strcmp(e.name,p->next->data.name)>0)
   {
   	p=p->next;
   }
   LNode *s;
   s=(LNode *)malloc(sizeof(LNode));
   s->next=NULL;
   s->data=e;
   
   if(p==NULL) p=s;
   else
   {
   	s->next=p->next;
   	p->next=s;
   }
   return OK;
}
Status ListDelete(LinkList &L,char name[])  //在单链表L中删除姓名为name的联系人信息
{
   LNode *p,*q;
   p=(LNode *)malloc(sizeof(LNode));;
   q=(LNode *)malloc(sizeof(LNode));;
   p=L;
   if(p->next==NULL) return ERROR;
   while(p->next!=NULL&&strcmp(name,p->next->data.name)!=0)
   {
   	p=p->next;
   }
   if(p->next==NULL) return ERROR;
   q=p->next;
   p->next=p->next->next;
   free(q);
   return OK;
}

 6-2 顺序表的插入操作

本题要求实现一个函数，在顺序表的第i个位置插入一个新的数据元素e，插入成功后顺序表的长度加1，函数返回值为1；插入失败函数返回值为0；

函数接口定义：

int ListInsert(SqList &L,int i,ElemType e);

其中SqList结构定义如下：

typedef struct{
    ElemType *elem;
    int length;
 }SqList;

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
typedef int ElemType;
typedef struct{
    ElemType *elem;
    int length;
 }SqList;
void InitList(SqList &L);/*细节在此不表*/
int ListInsert(SqList &L,int i,ElemType e);
int main()
{
    SqList L;
    InitList(L);
    ElemType e;
    int i;
    scanf("%d%d",&i,&e);
    int result=ListInsert(L,i,e);
    if(result==0){
        printf("Insertion Error.The value of i is unlawful or the storage space is full!");    
    }else if(result==1){
        printf("Insertion Success.The elements of the SequenceList L are:");    
        for(int j=0;j<L.length;j++){
            printf(" %d",L.elem[j]);
        }
    }
    return 0;
}
/* 请在这里填写答案 */

输入格式：

输入数据有1行，首先给出以-1结束的顺序表元素值（不超过100个，-1不属于顺序表元素），然后是插入位置和被插入元素值。所有数据之间用空格分隔。

输入样例：

2 6 4 -1 2 100

输出样例：

Insertion Success.The elements of the SequenceList L are: 2 100 6 4

参考答案：

int ListInsert(SqList &L,int i,ElemType e)
{
    if(i>L.length+1 or L.length>=100 or i<1) return 0;
	L.length++;
	int temp;
    int j=L.length;
	while(j>=i)
	{
		L.elem[j]=L.elem[j-1];
        j--;
	}
    L.elem[i-1]=e;
	return 1;
}

 6-3 顺序表的删除操作

本题要求实现一个函数，要求将顺序表的第i个元素删掉，成功删除返回1，否则返回0；

函数接口定义：

int ListDelete(SqList &L,int i);

其中SqList结构定义如下：

typedef struct{
    ElemType *elem;
    int length;
 }SqList;

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
typedef int ElemType;
typedef struct{
    ElemType *elem;
    int length;
 }SqList;
void InitList(SqList &L);/*细节在此不表*/
int ListDelete(SqList &L,int i);
int main()
{
    SqList L;
    InitList(L);
    int i;
    scanf("%d",&i);
    int result=ListDelete(L,i);
    if(result==0){
        printf("Delete Error.The value of i is illegal!");    
    }else if(result==1){
        printf("Delete Success.The elements of the SequenceList L are:");    
        for(int j=0;j<L.length;j++){
            printf(" %d",L.elem[j]);
        }
    }
    return 0;
}
/* 请在这里填写答案 */

输入格式：

输入数据有1行，首先给出以-1结束的顺序表元素值（不超过100个，-1不属于顺序表元素），然后是删除位置。所有数据之间用空格分隔。

输入样例：

2 6 4 -1 1

输出样例：

Delete Success.The elements of the SequenceList L are: 6 4

参考答案：

int ListDelete(SqList &L,int i)
{
    if(i>L.length or i<1) return 0;
    L.length--;
    i--;
	while(i<L.length)
    {
        L.elem[i]=L.elem[i+1];
        i++;
    }
	return 1;
}

 6-4 单链表的查询插入删除

编写3个函数，分别实现单链表（带头结点）的查询、插入、删除。文章来源地址https://www.toymoban.com/news/detail-723733.html

函数接口定义：

int Get_LinkList(LinkList H, ElemType key)；//H为单链表的头指针，key为待查找的值；
Status ListInsert(LinkList &H,int i,ElemType e)；//H为单链表的头指针，i为插入位置，e为新插入的值；
Status ListDelete(LinkList &H,int i)；//H为单链表的头指针，i为删除位置

裁判测试程序样例：

#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 30
#define  TRUE   1
#define  FALSE  0
#define  OK     1
#define  ERROR 0
#define  OVERFLOW  -1
typedef int Status;
typedef   int ElemType;
typedef struct LNode  /* 定义链式存储结构 */
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
int  Get_LinkList(LinkList H, ElemType key) ;//按值查询，找到则返回其位置，未找到则返回0
Status ListInsert(LinkList &H,int i,ElemType e);
Status ListDelete(LinkList &H,int i);
Status Creat_LinkList(LinkList &L)               /* 创建链式表 */
  {
    LinkList head,r,s;
    int k;
    head=(LinkList)malloc(sizeof(LNode));
    head->next=NULL;
    r=head;
    scanf("%d",&k);
    while(k>0)
    {
      s=(LNode *)malloc(sizeof(LNode));
      s->data=k;
      s->next=NULL;
      r->next=s;
      r=s;
      scanf("%d",&k);
    }
    L=head;
    return OK;
  }/* Creat_LinkList */
void Print_LinkList( LinkList H)     /* 输出链式表 */
{
    LNode *p;
    p=H->next;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
   }
   printf("\n");
  }/* Print_LinkList */


int  main()
  {
    ElemType key;
    LinkList L;
    int p,loc;
    Creat_LinkList(L);  //创建单链表
    Print_LinkList(L);   //输出单链表
    scanf("%d",&key);  //读入待查找的值
    p=Get_LinkList(L,key);  //
    printf("key在第%d位\n",p);
    scanf("%d%d",&key,&loc);  //输入要插入的值key以及位置loc
    ListInsert(L,loc,key);
    Print_LinkList(L);
    scanf("%d",&loc);//输入要删除元素的位置
    ListDelete(L,loc);
    Print_LinkList(L);
    return 0;
}

/* 请在这里填写答案 */

输入样例：

1 2 3 4 5 6 0
3
10 2
5

输出样例：

1 2 3 4 5 6 
key在第3位
1 10 2 3 4 5 6 
1 10 2 3 5 6

参考答案：

Status Get_LinkList(LinkList H, ElemType key)
{
    int index;
    LNode *p;
    p=(LNode *)malloc(sizeof(LNode));
    p=H->next;
    index=1;
    while(p->next!=NULL and p->data!=key)
    {
        p=p->next;
        index++;
    }
    if(p->next==NULL) return 0;
    else return index;
}
Status ListInsert(LinkList &H,int i,ElemType e)
{
    if(i<1) return ERROR;
    LNode *p,*q;
    p=(LNode *)malloc(sizeof(LNode));
    q=(LNode *)malloc(sizeof(LNode));
    int j=1;
    p=H;
    while(j!=i)
    {
        if(p==NULL) return ERROR;
        j++;
        p=p->next;
    }
    q->data=e;
    q->next=p->next;
    p->next=q;
    return OK;
}
Status ListDelete(LinkList &H,int i)
{
    if(i<1) return ERROR;
    LNode *p,*q;
    p=(LNode *)malloc(sizeof(LNode));
    q=(LNode *)malloc(sizeof(LNode));
    int j=1;
    p=H;
    while(j<i)
    {
        p=p->next;
        j++;
    }
    q=p->next;
    p->next=p->next->next;
    free(q);
    return OK;
}

到了这里，关于数据结构第1~2章练习答案（PTA）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 《数据结构》_PTA_数据结构作业6：图

    《数据结构》_PTA_数据结构作业6：图

    1-1 无向连通图所有顶点的度之和为偶数。 T 1-2 无向连通图边数一定大于顶点个数减1 F 1-3 无向连通图至少有一个顶点的度为1。 F 1-4 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关. F 1-5 用邻接矩阵法存储图，占用的存储空间数只与图中结点个数

    2024年02月04日
    浏览(45)
  • 7-1 天梯地图 (PTA-数据结构)

    7-1 天梯地图 (PTA-数据结构)

    本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。 输入格式： 输入在第一行给出两个正整数 N （2 ≤

    2024年02月02日
    浏览(28)
  • 7-1 抢红包(PTA - 数据结构)

    7-1 抢红包(PTA - 数据结构)

    没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。 输入格式： 输入第一行给出一个正整数N（≤104），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：

    2024年01月23日
    浏览(31)

  • 数据结构Pta训练题-编程2

    感谢你这么帅（漂亮）​还支持我 一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。 输入

    2024年02月16日
    浏览(38)
  • 数据结构Pta训练题函数题详解

    数据结构Pta训练题函数题详解

    感谢你这么帅（漂亮）​还支持我 pta网站：PTA | 程序设计类实验辅助教学平台 (pintia.cn) 文章内容较长，建议搭配目录使用 给定一个顺序存储的线性表，请设计一个函数删除所有值大于min而且小于max的元素。删除后表中剩余元素保持顺序存储，并且相对位置不能改变。 函数接

    2024年02月12日
    浏览(35)

  • 数据结构pta训练题-编程题1

    感谢你这么帅（漂亮）​还支持我 训练网站：PTA训练平台 设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

    2024年02月10日
    浏览(32)

  • C/C++数据结构---单链表逆转（PTA）

    个人主页： 仍有未知等待探索_数据结构,C语言疑难,小项目-CSDN博客 专题分栏： 数据结构_仍有未知等待探索的博客-CSDN博客 目录 一、前言 二、题目 函数接口定义： 裁判测试程序样例： 输出样例： 三、理解+代码 1.理解 2.分析  3.代码          对于初次学习数据结构，

    2024年02月07日
    浏览(30)

  • 7-1 回文判断（数据结构） PTA C语言

    回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。编写一个程序，使用栈判定给定的字符序列是否为回文。 若用C++，可借助STL的容器实现。 输入格式: 输入待判断的字符序列，按回车键结束，字符序列长度20。 输出格式: 若字符序列是

    2024年02月02日
    浏览(34)

  • 排序7-2 奥运排行榜 PTA 数据结构

    7-2 奥运排行榜 分数 25 全屏浏览题目 切换布局 作者 陈越 单位 浙江大学 每年奥运会各大媒体都会公布一个排行榜，但是细心的读者发现，不同国家的排行榜略有不同。比如中国金牌总数列第一的时候，中国媒体就公布“金牌榜”；而美国的奖牌总数第一，于是美国媒体就

    2024年02月02日
    浏览(34)
  • C/C++数据结构---在一个数组中实现两个堆栈（PTA）

    C/C++数据结构---在一个数组中实现两个堆栈（PTA）

    个人主页 仍有未知等待探索_数据结构,C语言疑难,小项目-CSDN博客 专题分栏---数据结构 数据结构_仍有未知等待探索的博客-CSDN博客 目录 一、前言         二、题目 要求 函数接口定义 裁判测试程序样例 输入样例  输出样例  三、分析  1.栈的特点 2.题目分析  3.栈的创建

    2024年02月08日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包