2021 数据结构与算法分析(常州大学) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2021-03-01到2021-06-30
本篇答案更新状态:已完结

【作业】第一讲 绪论 第一章作业

1、 问题:非线性结构是数据元素之间存在一种:A、 一对多关系 B、 一对多或者多对多关系 C、 多对多关系 D、 一对一关系
评分规则: 【 B
】

2、 问题:数据结构中,与所使用的计算机无关的是数据的_____ 结构。A、 存储 B、 物理 C、 逻辑 D、 物理和存储
评分规则: 【 C
】

3、 问题:算法分析的目的是:A、 找出数据结构的合理性 B、 研究算法中的输入和输出的关系 C、 分析算法的效率以求改进 D、 分析算法的易懂性和文档性
评分规则: 【 C
】

4、 问题:算法分析的两个主要方面是:A、 空间复杂性和时间复杂性 B、 正确性和简明性 C、 可读性和文档性 D、 数据复杂性和程序复杂性
评分规则: 【 A
】

5、 问题:计算机算法指的是:A、 计算方法 B、 排序方法 C、 解决问题的有限运算序列 D、 调度方法
评分规则: 【 C
】

6、 问题:计算机算法必须具备输入、输出和_____等5个特性。A、 可行性、可移植性和可扩充性 B、 可行性、确定性和有穷性 C、 确定性、有穷性和稳定性 D、 易读性、稳定性和安全性
评分规则: 【 B
】

7、 问题:链接存储的存储结构所占存储空间( )。 A、 分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针 B、 只有一部分,存放结点值 C、 只有一部分,存储表示结点间关系的指针 D、 分两部分,一部分存放结点值,另一部分存放结点所占单元数
评分规则: 【 A
】

8、 问题:线性表若采用链式存储结构时,要求内存中可用存储单元的地址( )。 A、 必须是连续的 B、 部分地址必须是连续的 C、 一定是不连续的 D、 连续或不连续都可以
评分规则: 【 D
】

【作业】第一讲 绪论 3-7课后作业

1、 问题:x=90; y=100;while(y>0)if(x>100) {x=x-10;y–;}else x++;求上述程序段的时间复杂度?
评分规则: 【 T(n)=O(1)
】

2、 问题:for (i=0; i T(n)=O(n*m)
】

3、 问题:s=0;for i=0; i T(n)=O(n^2)
】

4、 问题:i=1;while(i<=n) i=i*3;求上述程序段的时间复杂度？
评分规则: 【 O(log3n)
】

5、 问题:x=0;for(i=1; i T(n)=O(n^2)
】

6、 问题:x=n; //n>1y=0;while(x≥(y+1)*(y+1))y++;求上述程序段的时间复杂度？
评分规则: 【 T(n)=O(n^1/2)。
】

7、 问题:试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
评分规则: 【 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。即相同的逻辑结构，可以对应不同的存储结构。
】

8、 问题:简述逻辑结构的四种基本关系并画出它们的关系图。
评分规则: 【 （1）集合结构数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。（2）线性结构数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。（3）树结构数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树形结构。（4）图结构或网状结构数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图形结构或网状结构。其中树结构和图结构都属于非线性结构。
】

9、 问题:存储结构由哪两种基本的存储方法实现？
评分规则: 【 （1）顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。（2）链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。
】

10、 问题:简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
评分规则: 【 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，学生基本信息表也可是一个数据对象。数据结构：略逻辑结构：略存储结构：略抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
】

【作业】第二讲 线性表 第二章课后作业(3-19)

1、 问题:将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。
评分规则: 【 [题目分析]合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){//合并链表La和Lb，合并后的新表使用头指针Lc指向 pa=La->next; pb=Lb->next; //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa && pb) {if(pa->datadata){pc->next=pa;pc=pa;pa=pa->next;} //取较小者La中的元素，将pa链接在pc的后面，pa指针后移 else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} //取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移 else //相等时取La中的元素，删除Lb中的元素 {pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;pb =q; } } pc->next=pa?pa:pb; //插入剩余段 delete Lb; //释放Lb的头结点}
】

2、 问题:设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。
评分规则: 【 从首元结点开始，逐个地把链表L的当前结点p插入新的链表头部。[算法描述]void inverse(LinkList &L) {// 逆置带头结点的单链表 L p=L->next; L->next=NULL; while ( p) { q=p->next; // q指向p的后继 p->next=L->next; L->next=p; // p插入在头结点之后 p = q; }}
】

3、 问题:设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同 ）。
评分规则: 【 [题目分析]分别查找第一个值>mink的结点和第一个值 ≥maxk的结点，再修改指针，删除值大于mink且小于maxk的所有元素。[算法描述]void delete(LinkList &L, int mink, int maxk) { p=L->next; //首元结点 while (p && p->data<=mink) { pre=p; p=p->next; } //查找第一个值>mink的结点 if (p) {while (p && p->datanext; // 查找第一个值 ≥maxk的结点 q=pre->next; pre->next=p; // 修改指针 while (q!=p) { s=q->next; delete q; q=s; } // 释放结点空间 }//if}
】

4、 问题:已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。
评分规则: 【 [题目分析]知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点）六条链。[算法描述]void Exchange（LinkedList p）∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。{q=p->llink； q->llink->rlink=p； ∥p的前驱的前驱之后继为p p->llink=q->llink； ∥p的前驱指向其前驱的前驱。 q->rlink=p->rlink； ∥p的前驱的后继为p的后继。 q->llink=p； ∥p与其前驱交换 p->rlink->llink=q； ∥p的后继的前驱指向原p的前驱 p->rlink=q； ∥p的后继指向其原来的前驱}∥算法exchange结束。
】

第二讲 线性表 第二章课后测验(3-19)

1、 问题:在单链表中,要将s所指结点插入到p所指结点之后,其语句应为( )。
选项：
A: s->next=p+1; p->next=s;
B:(p).next=s; (s).next=(*p).next;
C:s->next=p->next; p->next=s->next;
D:s->next=p->next; p->next=s;
答案: 【s->next=p->next; p->next=s; 】

2、 问题:创建一个包括n个结点的有序单链表的时间复杂度是( )。
选项：
A:O(1)
B:O(n)
C:O()
D: O(nlog)
答案: 【O()】

3、 问题:在一个长度为n的顺序表中,在第i个元素(1≤i≤n+1)之前插入一个新元素时须向后移动( )个元素。
选项：
A:n-i
B: n-i+1
C: n-i-1
D:i
答案: 【 n-i+1 】

4、 问题:将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是( )。
选项：
A:n
B:2n-1
C:2n
D:n-1
答案: 【n 】

5、 问题:单链表的存储密度( )。
选项：
A:大于1
B:等于1
C:小于1
D:不能确定
答案: 【小于1】

6、 问题:线性表L在( )情况下适用于使用链式结构实现。
选项：
A:需经常修改L中的结点值
B:需不断对L进行删除、插入操作
C:L中含有大量的结点
D:L中结点结构复杂
答案: 【需不断对L进行删除、插入操作】

7、 问题:顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )。
选项：
A:110
B:108
C:100
D:120
答案: 【108】

8、 问题:向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动的元素个数为( )。
选项：
A:8
B:63.5
C:63
D:7
答案: 【63.5】

9、 问题: 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。
选项：
A:p->next->prior=p->prior; p->prior->next=p->next;
B:p->next=p->next->next; p->next->prior=p;
C:p->prior->next=p; p->prior=p->prior->prior;
D:p->prior=p->next->next; p->next=p->prior->prior;
答案: 【p->next->prior=p->prior; p->prior->next=p->next;】

10、 问题:在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。
选项：
A:p->next=q; q->prior=p; p->next->prior=q; q->next=q;
B:p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
C:q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;
D:q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;
答案: 【q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;】

【作业】第三讲 栈和队列 第三章 课后作业(3-30)

1、 问题:假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针) ，试编写：（1）置空队；（2）判队空；（3）入队；（4）出队。四个算法。（每小问5分，结构体定义5分，共45+5=25分）
评分规则: 【 //先定义链队结构:typedef struct queuenode{Datatype data;struct queuenode next;}QueueNode; //以上是结点类型的定义typedef struct{queuenode rear;}LinkQueue; //只设一个指向队尾元素的指针(1) 置空队void InitQueue( LinkQueue Q){ //置空队：就是使头结点成为队尾元素　QueueNode s;Q->rear = Q->rear->next;//将队尾指针指向头结点while (Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队{s=Q->rear->next;Q->rear->next=s->next;delete s;　}//回收结点空间}(2) 判队空 int EmptyQueue( LinkQueue Q){ //判队空。当头结点的next指针指向自己时为空队　return Q->rear->next->next==Q->rear->next;}(3) 入队void EnQueue( LinkQueue Q, Datatype x){ //入队。也就是在尾结点处插入元素QueueNode p=new QueueNode;//申请新结点p->data=x; p->next=Q->rear->next;//初始化新结点并链入Q-rear->next=p; Q->rear=p;//将尾指针移至新结点}(4) 出队Datatype DeQueue( LinkQueue Q){//出队,把头结点之后的元素摘下Datatype t;QueueNode p;if(EmptyQueue( Q ))Error(“Queue underflow”);p=Q->rear->next->next; //p指向将要摘下的结点x=p->data; //保存结点中数据if (p==Q->rear){//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点　Q->rear = Q->rear->next;Q->rear->next=p->next;}else Q->rear->next->next=p->next;//摘下结点pdelete p;//释放被删结点return x;}
】

2、 问题:已知循环队列Q的队头指针为front，队尾指针为rear，队列的最大长度为MaxSize，请分别写出队空、队满、入队、出队，以及求队中元素个数的语句。(每个各5分)
评分规则: 【 队空：Q.front==Q.rear队满：（Q.rear+1）%MAXQSIZE==Q.front入队：Q.base[Q.rear]=e //新元素插入队尾 Q.rear=(Q.rear+1)%MAXQSIZE //队尾指针加1出队：e=Q.base[Q.front] //保护队头元素 Q.front=(Q.front+1)%MAXQSIZE //队头指针加1求队中元素个数：Length=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE