2020 数据结构(西南科技大学) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-02-22到2020-05-20
本篇答案更新状态:已完结

第1周：绪论（时长：56分11秒） 第1周测验

1、 问题:计算机所处理的数据一般具备某种内在联系，这是指（ ）。
选项：
A:数据和数据之间存在某种关系
B:元素和元素之间存在某种关系
C:元素内部具有某种结构
D:数据项和数据项之间存在某种关系
答案: 【元素和元素之间存在某种关系】

2、 问题:在数据结构中，与所使用的计算机无关的是数据的（ ）结构。
选项：
A:逻辑
B:存储
C:逻辑和存储
D:物理
答案: 【逻辑】

3、 问题:在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。
选项：
A:数据的处理方法
B:数据元素的类型
C:数据元素之间的关系
D:数据的存储方法
答案: 【数据元素之间的关系】

4、 问题:数据结构在计算机内存中的表示是指（ ）。
选项：
A:数据的存储结构
B:数据结构
C:数据的逻辑结构
D:数据元素之间的关系
答案: 【数据的存储结构】

5、 问题:数据在计算机的存储器中表示时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称之为（ ）。
选项：
A:逻辑结构
B:顺序存储结构
C:链式存储结构
D:以上都对
答案: 【顺序存储结构】

6、 问题:数据采用链式存储结构时，要求（ ）。
选项：
A:每个节点占用一片连续的存储区域
B:所有节点占用一片连续的存储区域
C:节点的最后一个域必须是指针域
D:每个节点有多少后继节点，就必须设多少个指针域
答案: 【每个节点占用一片连续的存储区域】

7、 问题:可以用（ ）定义一个完整的数据结构。
选项：
A:数据元素
B:数据对象
C:数据关系
D:抽象数据类型
答案: 【抽象数据类型】

8、 问题:算法指的是（ ）。
选项：
A:计算机程序
B:解决问题的方法
C:查找或排序过程
D:求解特定问题的指令有限序列
答案: 【求解特定问题的指令有限序列】

9、 问题:在算法设计时，若实参和形参同步发生改变，则应把形参变量说明为（ ）型参数。
选项：
A:指针
B:引用
C:传值
D:常数
答案: 【引用】

10、 问题:某算法的时间复杂度为O()，表明该算法的（ ）。
选项：
A:问题规模是
B:执行时间等于
C:执行时间与成正比
D:问题规模与成正比
答案: 【执行时间与成正比】

【作业】第1周：绪论（时长：56分11秒） 第1周作业

1、 问题:有以下用C/C++语言描述的算法，说明其功能：void fun(double &y,double x,int n){ y=x; while (n>1) { y=y*x; n–; }}
评分规则: 【 参考答案：本算法的功能是计算y=。
】

2、 问题:一个算法的空间复杂度是O(1)，那么执行该算法时不需要任何空间，这个说法正确吗？为什么？
评分规则: 【 参考答案：这个说法是错误的。一个算法的空间复杂度是O(1)只是表明执行该算法时所需临时分配的空间大小是个常量，与问题规模无关，并不是不需要任何空间。回答是正确的，给0分。
】

3、 问题:一个算法的执行频度为，其时间复杂度多少？
评分规则: 【 参考答案：当n足够大时，T(n)®3n/10=0.3n，其时间复杂度为O(n)
】

4、 问题:设有算法如下：int Find(int a[], int n, int x){ int i; for (i=0;i 参考答案1：在最好情况下，a[0]=x，比较1次，所以最好时间复杂度为O(1)。
参考答案2：在最坏情况下，a[n-1]=x，比较n次，所以最坏时间复杂度为O(n)。
】

5、 问题:设有算法如下：int Find(ElemType a[ ],int s,int t,ElemType x){ int m=(s+t)/2; if (s<=t) { if (a[m]==x) return m; else if (x
】

【作业】第1周：线性表（上）（时长：1小时3分56秒） 第2周作业

1、 问题:设计一个算法，查找非空顺序表L中第一个最大的元素，并返回该元素的逻辑序号。
评分规则: 【 参考答案：采用顺序表指针方式：int MaxFirst(SqList *L){ int i,maxi=0; for (i=1;ilength;i++) if (L->data[i]>L->data[maxi]) maxi=i; return maxi+1;}或者直接采用顺序表方式：int MaxFirst(SqList L){ int i,maxi=0; for (i=1;iL.data[maxi]) maxi=i; return maxi+1;}
】

2、 问题:对于带头节点的单链表L1，其节点类型为LinkList，指出以下算法的功能。void fun(LinkList &L，ElemType x，ElemType y){ LinkList p=L->next; while (p!=NULL) { if (p->data==x) p->data=y; p=p->next; }}
评分规则: 【 参考答案：将单链表L中所有值为x的节点的值替换成y。
】

3、 问题:以下算法用于统计带头节点的单链表L中节点值等于给定值x的节点数的算法，其中存在错误，请指出错误的地方并修改为正确的算法。int count(LinkList L,ElemType x){ int n=0; while (L!=NULL) { L=L->next; if (L->data==x) n++; } return n;}
评分规则: 【 参考答案：当L指向尾节点时，while条件成立，再执行L=L->next，L=NULL，此时if语句出现错误。修改后的算法如下：int count(LinkList L,ElemType x){ LinkList *p=L->next; int n=0; while (p!=NULL) { if (p->data==x) n++; p=p->next; } return n;}
】

4、 问题:某非空单链表L中所有元素为整数，设计一个算法将所有小于零的节点移到所有大于等于零的节点的前面。
评分规则: 【 参考答案：算法如下：void Move(LinkList &L){ LinkList p=L->next,*pre=p; while (p!=NULL) { if (p->data<0) { pre->next=p->next; p->next=L->next; L->next=p; p=pre->next; } else { pre=p; p=p->next; } }}
】

5、 问题:有一个由整数元素构成的非空单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数节点，B单链表中含有所有的奇数节点，且保持原来的相对次序。
评分规则: 【
】

【作业】第3周：栈和队列（时长：1小时4分4秒） 第4周作业

1、 问题:设输入元素为1、2、3、P和A，进栈次序为123PA，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？
评分规则: 【 参考答案：AP321、P321A、P32A1、P3A21和PA321。
】

2、 问题:在以下几种存储结构中，哪个最适合用作链栈？并说明理由。（1）带头节点的单链表（2）不带头节点的循环单链表（3）带头节点的双链表
评分规则: 【 参考答案：栈中元素之间的逻辑关系属线性关系，可以采用单链表、循环单链表和双链表之一来存储，而栈的主要运算是进栈和出栈，当采用（1）时，前端作为栈顶，进栈和出栈运算的时间复杂度为O(1)。当采用（2）时，前端作为栈顶，当进栈和出栈时，首节点都发生变化，还需要找到尾节点，通过修改其next域使其变为循环单链表，算法的时间复杂度为O(n)。当采用（3）时，前端作为栈顶，进栈和出栈运算的时间复杂度为O(1)。但单链表和双链表相比，其存储密度更高，所以本题中最适合用作链栈的是带头节点的单链表。
】

3、 问题:简述以下算法的功能：void fun(int a[],int n){ int i=0,e; SqStack *st; InitStack(st); for (i=0;i 参考答案：本算法的功能是利用栈将数组a中所有元素逆置。
】

4、 问题:假设表达式中允许包含3种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈判断表达式中的括号是否正确配对。
评分规则: 【
】

5、 问题:假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。15（1）下面所示的序列中哪些是合法的？ A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO（2）通过对（1）的分析，写出一个算法判定所给的操作序列是否合法。若合法返回true；否则返回false（假设被判定的操作序列已存入一维数组中）。
评分规则: 【 参考答案1：（1）A、D均合法，而B、C不合法。
参考答案2：（2）对应的算法如下：bool judge(char A[],int n){ int i;　bool tag; ElemType x; LiStack *ls; InitStack(ls); for (i=0;i】

6、 问题:以1、2、3、…、n的顺序进队，可以产生的出队序列有多少种？
评分规则: 【 参考答案：可能的出队序列只有一种，即1、2、3、…、n。各元素的出队顺序与进队顺序相同。
】

7、 问题:什么是循环队列？采用什么方法实现循环队列？
评分规则: 【 参考答案：当用数组表示队列时，把数组看成是一个环形的，即令数组中第一个元素紧跟在最末一个单元之后，就形成一个循环队列。循环队列解决了非循环队列中出现的“假溢出”现象。通常采用逻辑上求余数的方法来实现循环队列，假设数组的大小为n，当元素下标i增1时，采用i=(i+1)%n来实现。
】

8、 问题:链队相对于顺序队而言，有何优势和不足？
评分规则: 【 参考答案：链队相对于顺序队而言，由于采用动态分配方式，基本上消除了队列上溢出现象。其不足之处有两点：一是使用了指针，存储密度不如顺序队；二是不像顺序队可以通过队头队尾指针求出队中元素个数。
】

9、 问题:对于循环队列，设计求其中元素个数的算法。
评分规则: 【 参考答案：int Count(SqQueue *qu){ return((qu->rear-qu->front+MaxSize)%MaxSize);}
】

10、 问题:对于顺序队来说，如果知道队尾元素的位置和队列中的元素个数，则队头元素所在位置显然是可以计算的。也就是说，可以用队列中的元素个数代替队头指针。设计出这种循环顺序队的初始化、入队、出队和判空算法。
评分规则: 【 队列类型定义如下：typedef struct{ ElemType data[MaxSize]; int rear; //队尾指针 int count; //队列中元素个数} QuType; //队列类型定义
void InitQu(QuType &qu) //队列初始化算法{ qu.rear=0; qu.count=0;}bool EnQu(QuType &qu,ElemType x) //进队算法{ if (qu.count==MaxSize) return false; else { qu.rear=(qu.rear+1)%MaxSize; qu.data[qu.rear]=x; qu.count++; return true; }}
bool DeQu(QuType &qu,ElemType &x) //出队算法{ int front; if (qu.count==0) return false; else { front=(qu.rear-qu.count+MaxSize)%MaxSize; front=(front+1)%MaxSize; x=qu.data[front]; qu.count–; return true; }}bool QuEmpty(QuType qu) //判队空算法{ return(qu.count==0);}
】

【作业】第3周：线性表（下）（时长：41分40秒） 第2周作业

1、 问题:以L为头节点指针，给出单链表、双链表、循环单链表和循环双链表中，p所指节点为尾节点的条件。
评分规则: 【 参考答案：在单链表中p所指节点为尾节点的条件是：p->next==NULL。（1分）在双链表中p所指节点为尾节点的条件是：p->next==NULL。（1分）在循环单链表中p所指节点为尾节点的条件是：p->next==L。（1分）在循环双链表中p所指节点为尾节点的条件是：p->next==L。（2分）
】