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

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

【作业】第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
】

【作业】第4周：栈和队列（时长：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);}
】

【作业】第6周：递归（时长：31分29秒） 第6周作业

1、 问题:两个非负整数a和b相加时，若b为0，则结果为a，利用C/C++语言中“++”和“–”运算符其递归定义。
评分规则: 【 参考答案：两个非负整数a和b相加的递归定义如下：add(a，b)=a 当b=0时add(a，b)=add(++a，–b) 当b>0时
】

2、 问题:有如下递归函数：double pow(double x，int n){ if (n==1) return x; return x*pow(x，n-1);}（1）pow(x，n)的功能是什么？（2）执行pow(2，5)的结果是什么？其执行过程中发生了几次递归调用（含pow(2，5)调用）？‍（3）执行pow(x，n)最多发生了几次递归调用（含pow(x,n)调用）？
评分规则: 【 （1）其功能是求x的n次幂。
（2）执行pow(2，5)的结果是32。其执行过程中发生了5次递归调用，pow(2，5)→pow(2，4) →pow(2，3) →pow(2，2)→pow(2，1)。
（3）执行pow(x，n)最多发生了n次递归调用。
】

3、 问题:设计一个递归算法求一个实型数组a[0..n-1]的平均值。
评分规则: 【 参考答案：double Avg(double a[]，int i){ double avg; if (i==0) return a[0]; else { avg=Avg(a，i-1); return (avg*i+a[i])/(i+1); }}
】

4、 问题:有一个不带表头节点的单链表，其节点类型为LinkList。设计一个递归算法，删除以h为首指针的单链表中第一个值为x的节点。
评分规则: 【 参考答案：void delnode(LinkList &h，ElemType x) { LinkList p; if (h!=NULL) { if (h->data==x) //若首节点值为x { p=h; h=h->next; free(p); } else //若首节点值不为x delnode(h->next，x); }}
】

5、 问题:有一个不带表头节点的单链表，其节点类型为LinkList。设计一个递归算法，删除以h为首指针的单链表中值为x的所有节点。
评分规则: 【 参考答案：void delall(LinkList &h，ElemType x){ LinkList p; if (h!=NULL) { if (h->data==x) //若首节点值为x { p=h; h=h->next; free(p); delall(h，x); //在后继节点递归删除 } else //若首节点值不为x delall(h->next，x); //在后继节点递归删除 }}
】

【作业】第8周：树和二叉树（上）（时长：57分37秒） 第8周作业

1、 问题:若一棵度为4的树中度为1、2、3、4的节点个数分别为4、3、2、2，则该树的总节点个数是多少？
评分规则: 【 参考答案：节点总数n=n0+n1+n2+n3+n4，又由于除根节点外，每个节点都对应一个分支，所以总的分支数等于n-1。而度为i（0≤i≤4）的节点的分支数为i，所以有：总分支数=n-1=0×n0+1×n1+2×n2+3×n3+4×n4。综合两式得：n0=n2+2n3+3n4+1=3+2×2+3×2=14，则n=n0+n1+n2+n3+n4=14+4+3+2+2=25，所以该树的总节点个数是25。
】

2、 问题:对于度为m的树T，其高度为h，则最少的节点个数和最多的节点个数分别是多少？
评分规则: 【 参考答案：第i层最多有个节点，所以最多节点个数=最少节点的情况是：某一层有m个节点，其他每层只有一个节点，此时节点个数=m+(h-1)=m+h-1。
】

3、 问题:对于含有n个节点的m次树，采用孩子链存储结构时，其中空指针域的个数有多少？
评分规则: 【 参考答案：该m次树中有n个节点，采用孩子链存储结构时，每个节点有m个指针，总指针域个数=m×n。又由于分支数=n-1，而每个分支是由一个非空指针域引出的，所以总的非空指针域个数=n-1，因此，空指针域的个数=总指针域个数-空指针域的个数=m×n-(n-1)=n(m-1)+1。
】

4、 问题:任意一个有n个节点的二叉树，已知它有m个叶子节点，试证明有(n-2m+1)个度数为1的节点。
评分规则: 【 参考答案：证明：设n1为二叉树中度为1的节点数，n2为度2的节点数，则总的节点数为：n=n1+n2+m根据二叉树的性质1可知n0=n2+1，即n2=n0-1=m-1，所以有n=n1+n2+m=n1+2m-1，则n1=n-2m+1。
】

5、 问题:为什么说一棵非空完全二叉树，一旦节点个数n确定了，其树形也就确定了。
评分规则: 【 参考答案：按层序编号时，完全二叉树的节点编号为1～n，如果已知各类节点个数，该完全二叉树的形态一定是确定的。若n已知，则可以根据其奇偶性确定n1：当n为偶数，n1=1，当n为奇数，n1=0，而n0=n2+1，n=n0+n1+n2=2n0-1+n1，n0=(n-n1+1)/2，从而n0和n2也确定了，所以这样的完全二叉树的形态就确定了。
】

6、 问题:已知一棵完全二叉树的第6层（设根为第1层）有8个叶子节点，则该完全二叉树的节点个数最多是多少？
评分规则: 【 参考答案：完全二叉树的叶子节点只能在最下两层，对于本题，节点最多的情况是第6层为倒数第二层，即1～6层构成一个满二叉树，其节点总数为-1=63。其中第6层有=32个节点，含8个叶子节点，则另外有32-8=24个非叶子节点，它们中每个节点有两个孩子节点（均为第7层的叶子节点），计48个叶子节点。这样最多的节点个数=63+48=111。
】

7、 问题:假设非空二叉树采用顺序存储结构，每个节点值为单个字符。设计一个算法求编号为i的节点的层次。
评分规则: 【 参考答案：int log2(int x) //求以2为底的x的对数{ int i=0; while (x!=1) { i++; x=x/2; } return i;}int Level(SqBTree t，int n，int i) //输出编号为i的节点的层次{ if (i<1 || i>n) return 0; else return log2(i)+1;}
】

8、 问题:假设非空二叉树采用顺序存储结构，每个节点值为单个字符。设计一个算法输出编号为i的节点的所有祖先节点值。
评分规则: 【 参考答案：void Ancestor(SqBTree t，int n，int i) //输出编号为i的节点的所有祖先节点值{ int j; if (i<=1 || i>n) return; else { j=i/2; while (j!=0) { printf(“%c “，t[j]); j=j/2; } } printf(“”);}
】

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

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

2、 问题:有一个双链表L，设计一个算法计算其中值为x的节点个数。
评分规则: 【 参考答案：算法如下int Count(DLinkList L,ElemType x){ int n=0; DLinkList p=L->next; while (p!=NULL) { if (p->data==x) n++; p=p->next; } return n;}
】

3、 问题:有一个非空双链表L，设计一个算法删除第一个值为x的节点。
评分规则: 【
】

4、 问题:设计一个算法，求一个非空循环单链表L中最后一个最大节点的逻辑序号。
评分规则: 【 参考答案：int Findlastmax(LinkList L){ LinkList p=L->next,*maxp=p; int i=1,lasti=i; while (p!=L) { if (p->data>=maxp->data) { lasti=i; maxp=p; } i++; p=p->next; } return lasti;}
】

5、 问题:对于有n（n≥1）个节点的循环单链表L，假设所有节点值是递增有序的，设计一个算法就地删除所有值重复的节点。