mooc数据结构_50课后答案(mooc2023课后作业答案)
第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周作业
1、有以下用C/C++语言描述的算法，说明其功能： void fun(double &y,double x,int n) { y=x; while (n>1) { y=y*x; n--; } }
2、一个算法的空间复杂度是O(1)，那么执行该算法时不需要任何空间，这个说法正确吗？为什么？
3、设有算法如下： int Find(int a[], int n, int x) { int i; for (i=0;i<n;i++ ) if (a[i]==x) return i; return –1; } 成功找到x的最好和最坏时间复杂度是多少？
第2周：线性表（上）（时长:1小时3分56秒）
第2周测验
1、线性表是（ ）。
A、一个有限序列，可以为空
B、一个有限序列，不可以为空
C、一个无限序列，可以为空
D、一个无限序列，不可以为空
2、线性表的基本运算ListInsert(&L,i,e)表示在线性表L中第i个位置上插入一个元素e，若L的长度为n，则i的合法取值是（ ）。
A、1≤i≤n
B、1≤i≤n+1
C、0≤i≤n-1
D、0≤i≤n
3、顺序表具有随机存取特性，指的是（ ）。
A、查找值为x的元素与顺序表中元素个数n无关
B、查找值为x的元素与顺序表中元素个数n有关
C、查找序号为i的元素与顺序表中元素个数n无关
D、查找序号为i的元素与顺序表中元素个数n有关
4、在顺序表中删除一个元素所需要的时间（ ）。
A、与删除元素的位置及顺序表的长度都有关
B、只与删除元素的位置有关
C、与删除任何其他元素所需要的时间相等
D、只与顺序表的长度有关
5、在n（n>1）个运算的顺序表中，算法时间复杂度为O(1)的运算是（ ）。
A、访问第i个元素（2≤i≤n）并求其前驱元素
B、在第i个元素之后插入一个新元素
C、删除第i个元素
D、将这n个元素递增排序
6、关于线性表的顺序存储结构和链式存储结构的描述中，正确的是（ ）。 Ⅰ.线性表的顺序存储结构优于链式存储结构 Ⅱ.顺序存储结构比链式存储结构的存储密度高 Ⅲ.如需要频繁插入和删除元素，最好采用顺序存储结构 Ⅳ.如需要频繁插入和删除元素，最好采用链式存储结构
A、Ⅰ、Ⅱ、Ⅲ
B、Ⅱ、Ⅳ
C、Ⅱ、Ⅲ
D、Ⅲ、Ⅳ
7、在单链表中，增加一个头节点的目的是为了（ ）。
A、使单链表至少有一个节点
B、标识链表中某个重要节点的位置
C、方便插入和删除运算的实现
D、表示单链表是线性表的链式存储结构
8、通过含有n（n≥1）个元素的数组a，采用头插法建立一个单链表L，则L中节点值的次序（ ）。
A、与数组a的元素次序相同
B、与数组a的元素次序相反
C、与数组a的元素次序无关
D、以上都不对
9、某算法在含有n（n≥1）个节点的单链表中查找值为x节点，其时间复杂度是（ ）。
A、
B、O(1)
C、
D、O(n)
10、在长度为n（n≥1）的单链表中删除尾节点的时间复杂度为（ ）。
A、O(1)
B、
C、O(n)
D、
11、关于线性表的正确说法是（ ）。
A、每个元素都有一个前驱和一个后继元素
B、线性表中至少有一个元素
C、表中元素的排序顺序必须是由小到大或由大到小
D、除第一个元素和最后一个元素外，其余每个元素有且仅有一个前驱和一个后继元素
12、以下关于顺序表的叙述中，正确的是（ ）。
A、顺序表可以利用一维数组表示，因此顺序表与一维数组在结构上是一致的，它们可以通用
B、在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻
C、顺序表和一维数组一样，都可以进行随机存取
D、在顺序表中每一个元素的类型不必相同
13、以下属于顺序表的优点是（ ）。
A、插入元素方便
B、删除元素方便
C、存储密度大
D、以上都不对
14、设线性表中有n个元素，以下运算中，（ ）在单链表上实现要比在顺序表上实现效率更高。
A、删除指定位置元素的后一个元素
B、在尾元素的后面插入一个新元素
C、顺序输出前k个元素
D、交换第i个元素和第n-i+1个元素的值（i=1，2，…，n）
15、以下关于单链表的叙述中正确的是（ ）。 Ⅰ.节点除自身信息外还包括指针域，存储密度小于顺序表 Ⅱ.找第i个节点的时间为O(1) Ⅲ.在插入、删除运算时不必移动节点
A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ
C、仅Ⅰ、Ⅲ
D、Ⅰ、Ⅱ、Ⅲ
第2周作业
1、设计一个算法，查找非空顺序表L中第一个最大的元素，并返回该元素的逻辑序号。
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; } }
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; }
4、某非空单链表L中所有元素为整数，设计一个算法将所有小于零的节点移到所有大于等于零的节点的前面。
5、有一个由整数元素构成的非空单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数节点，B单链表中含有所有的奇数节点，且保持原来的相对次序。
第3周：线性表（下）（时长：41分40秒）
第3周测验
1、与单链表相比，双链表的优点之一是（ ）。
A、插入、删除操作更简单
B、可以进行随机访问
C、可以省略表头指针或表尾指针
D、访问前后相邻节点更方便
2、带头节点的双链表L为空表时应满足（ ）。
A、L==NULL
B、L->prior==L->next
C、L->prior==NULL
D、L->next==NULL
3、在长度为n（n≥1）的双链表中插入一个节点（非尾节点）要修改（ ）个指针域。
A、1
B、2
C、3
D、4
4、对于长度为n（n≥1）的双链表L，在p所指节点之前插入一个新节点的算法的时间复杂度为（ ）。
A、O(1)
B、O(n)
C、
D、
5、在长度为n（n≥1）的双链表中删除一个节点（非尾节点）要修改（ ）个指针域。
A、1
B、2
C、3
D、4
6、与非循环单链表相比，循环单链表的主要优点是（ ）。
A、不再需要头指针
B、已知某个节点的位置后，能够容易找到它的前驱节点
C、在进行插入、删除操作时，能更好地保证链表不断开
D、从表中任意节点出发都能扫描到整个链表
7、设有带头节点的循环单链表L，当这种链表成为空链表时，有（ ）。
A、表头节点指针域next为空
B、L的值为NULL
C、表头节点的指针域next与L的值相等
D、表头节点的指针域next与L的地址相等
8、在长度为n（n≥1）的循环双链表L中，删除尾节点的时间复杂度为（ ）。
A、O(1)
B、O(n)
C、
D、
9、将两个分别含有m、n个节点的有序单链表归并成一个有序单链表，要求不破坏原有的单链表，对应算法的空间复杂度是（ ）（MIN表示取最小值）。
A、O(n)
B、O(m)
C、O(m+n)
D、O(MIN(m,n))
10、已知两个长度分别为m 和n 的升序单链表，若将它们合并为一个长度为m+n 的降序单链表，则时间复杂度是（ ）。
A、O(n)
B、O(m×n)
C、O(m)
D、O(m+n)
11、在长度为n（n≥1）的双链表L中，删除p所指节点的时间复杂度为（ ）。
A、O(1)
B、O(n)
C、
D、
12、在长度为n（n≥1）的循环单链表L中，删除尾节点的时间复杂度为（ ）。
A、O(1)
B、O(n)
C、
D、
13、在只有尾节点指针rear没有头节点的非空循环单链表中，删除尾节点的时间复杂度为（ ）。
A、O(1)
B、O(n)
C、
D、
14、在只有尾节点指针rear没有头节点的非空循环单链表中，删除开始节点的时间复杂度为（ ）。
A、O(1)
B、O(n)
C、
D、
15、两个长度为n的双链表，节点类型相同，若以h1为头指针的双链表是非循环的，以h2为头指针指针的双链表是循环的，则（ ）。
A、对于非循环双链表来说，删除首节点的操作，其时间复杂度都是O(n)
B、对于循环双链表来说，删除首节点的操作，其时间复杂度都是O(n)
C、对于非循环双链表来说，删除尾节点的操作，其时间复杂度都是O(1)
D、对于循环双链表来说，删除尾节点的操作，其时间复杂度都是O(1)
第3周作业
1、以L为头节点指针，给出单链表、双链表、循环单链表和循环双链表中，p所指节点为尾节点的条件。
2、有一个双链表L，设计一个算法计算其中值为x的节点个数。
3、有一个非空双链表L，设计一个算法删除第一个值为x的节点。
4、设计一个算法，求一个非空循环单链表L中最后一个最大节点的逻辑序号。
5、对于有n（n≥1）个节点的循环单链表L，假设所有节点值是递增有序的，设计一个算法就地删除所有值重复的节点。
6、用带头节点单链表表示集合，假设该单链表中的元素递增有序，设计一个高效算法求两个集合的交集，并分析该算法的时间和空间复杂度。
第4周：栈和队列（时长：1小时4分4秒）
第4周测验
1、栈的“先进后出”特性是指（ ）。
A、最后进栈的元素总是最先出栈
B、同时进行进栈和出栈操作时，总是进栈优先
C、每当有出栈操作时，总要先进行一次进栈操作
D、每次出栈的元素总是最先进栈的元素
2、给定一个足够大的空栈，有4个元素的进栈次序为A、B、C、D，则以C、D开头的出栈序列的个数为（ ）。
A、1
B、2
C、3
D、4
3、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是（ ）。
A、dcebfa
B、cbdaef
C、bcaefd
D、afedcb
4、一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（ ）。
A、edcba
B、decba
C、dceab
D、abcde
5、当用一个数组data[0..n-1]存放栈中元素时，栈底最好（ ）。
A、设置在data[0]处
B、设置在data[n-1]处
C、设置在data[0]或data[n-1]处
D、设置在data数组的任何位置
6、若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1，则以下元素x进栈的正确操作是（ ）。
A、top++; data[top]=x;
B、data[top]=x; top++;
C、top--; data[top]=x;
D、data[top]=x; top--;
7、若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进栈的正确操作是（ ）。
A、top++; data[top]=x;
B、data[top]=x; top++;
C、top--; data[top]=x;
D、data[top]=x; top--;
8、在设计链栈时，通常采用单链表作为链栈，而不采用双链表作为链栈，其准确的原因是（ ）。
A、栈中元素是顺序存取的，用单链表就足够了
B、栈中元素是随机存取的，用单链表就足够了
C、双链表运算较单链表更复杂
D、双链表存储密度较单链表低
9、栈和队列的不同点是（ ）。
A、都是线性表
B、都不是线性表
C、栈只能在同一端进行插入删除操作，而队列在不同端进行插入删除操作
D、没有不同点
10、设循环队列qu中数组data的下标是0～N-1，其队头、队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），元素x进队的操作是（ ）;qu.data[qu.rear]=x。
A、qu.rear++
B、qu.rear=(qu.rear+1)%N
C、qu.front++;
D、qu.front=(qu.front+1)%N
11、设循环队列qu中数组data的下标是0～N-1，其队头、队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），元素x出队的操作是（ ）;x=qu.data[qu.front]。
A、qu.rear++
B、qu.rear=(qu.rear+1)%N
C、qu.front++;
D、qu.front=(qu.front+1)%N
12、若某循环队列有队首指针front和队尾指针rear，在队不空时出队操作仅会改变（ ）。
A、front
B、rear
C、front和rear
D、以上都不对
13、通常设置循环队列qu的队空条件（front队首指针指向队首元素的前一位置，rear队尾指针指向队尾元素）是（ ）。
A、(qu.rear+1)%MaxSize==(qu.front+1)%MaxSize
B、(qu.rear+1)%MaxSize==qu.front+1
C、(qu.rear+1)%MaxSize==qu.front
D、qu.rear==qu.front
14、设循环队列的存储空间为a[0..20]，且当前队头指针（f指向队首元素的前一位置）和队尾指针（r指向队尾元素）的值分别为8和3，则该队列中元素个数为（ ）。
A、5
B、6
C、16
D、17
15、假设用一个不带头节点的单链表表示队列，队头在链表的（ ）位置。
A、链头
B、链尾
C、链中
D、以上都可以
16、与顺序队相比，链队（ ）。
A、优点是可以实现无限长队列
B、优点是进队和出队时间性能更好
C、缺点是不能进行顺序访问
D、缺点是不能根据队首和队尾指针计算队的长度
17、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。
A、1和5
B、2和4
C、4和2
D、5和1
18、一个循环队列中用data[0..n-1]数组保存队中元素，另设置一个队尾指针rear和一个记录队中实际元素个数的变量count，则该队中最多可以存放的元素个数是（ ）。
A、n-1
B、n
C、(rear+n) % n
D、(n-rear) % n
19、已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（ ）。
A、0，0
B、0，n-1
C、n-1，0
D、n-1，n-1
20、在循环队列中，元素的排列顺序（ ）。
A、由元素进队的先后顺序确定
B、与元素值的大小有关
C、与队头和队尾指针的取值有关
D、与队中数组大小有关
第4周作业
1、设输入元素为1、2、3、P和A，进栈次序为123PA，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？
2、在以下几种存储结构中，哪个最适合用作链栈？并说明理由。 （1）带头节点的单链表 （2）不带头节点的循环单链表 （3）带头节点的双链表
3、简述以下算法的功能： void fun(int a[],int n) { int i=0,e; SqStack *st; InitStack(st); for (i=0;i<n;i++) Push(st,a[i]); i=0; while (!StackEmpty(st)) { Pop(st,e); a[i++]=e; } DestroyStack(st); }
4、假设表达式中允许包含3种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈判断表达式中的括号是否正确配对。
5、假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。15 （1）下面所示的序列中哪些是合法的？ A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO （2）通过对（1）的分析，写出一个算法判定所给的操作序列是否合法。若合法返回true；否则返回false（假设被判定的操作序列已存入一维数组中）。
6、以1、2、3、…、n的顺序进队，可以产生的出队序列有多少种？
7、什么是循环队列？采用什么方法实现循环队列？
8、链队相对于顺序队而言，有何优势和不足？
9、对于循环队列，设计求其中元素个数的算法。
10、对于顺序队来说，如果知道队尾元素的位置和队列中的元素个数，则队头元素所在位置显然是可以计算的。也就是说，可以用队列中的元素个数代替队头指针。设计出这种循环顺序队的初始化、入队、出队和判空算法。
第6周：递归（时长：31分29秒）
第6周测验
1、一个正确的递归算法通常包含（ ）。
A、递归出口
B、递归体
C、递归出口和递归体
D、以上都不包含
2、递归函数f(x，y)定义如下： f(x，y)=f(x-1，y)+f(x，y-1) 当x>0且y>0 f(x，y)=x+y 否则 则f(2，1)的值是（ ）。
A、1
B、2
C、3
D、4
3、某递归算法的执行时间的递推关系如下： T(n)=1 当n=1时 T(n)=T(n/2)+1 当n>1时 则该算法的时间复杂度为（ ）。
A、O(1)
B、
C、O(n)
D、
4、某递归算法的执行时间的递推关系如下： T(n)=1 当n=1时 T(n)=2T(n/2)+1 当n>1时 则该算法的时间复杂度为（ ）。
A、O(1)
B、
C、O(n)
D、
5、将递归算法转换成非递归算法时，通常要借助的数据结构是（ ）。
A、线性表
B、栈
C、队列
D、树
第6周作业
1、两个非负整数a和b相加时，若b为0，则结果为a，利用C/C++语言中“++”和“--”运算符其递归定义。
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)调用）？
3、设计一个递归算法求一个实型数组a[0..n-1]的平均值。
4、有一个不带表头节点的单链表，其节点类型为LinkList。设计一个递归算法，删除以h为首指针的单链表中第一个值为x的节点。
5、有一个不带表头节点的单链表，其节点类型为LinkList。设计一个递归算法，删除以h为首指针的单链表中值为x的所有节点。
第5周：串（时长：31分9秒）
第5周测验
1、下面关于串的叙述中，正确的是（ ）。
A、串是一种特殊的线性表
B、串中元素只能是字母
C、空串就是空白串
D、串的长度必须大于零
2、两个字符串相等的条件是（ ）。
A、串的长度相等
B、含有相同的字符集
C、都是非空串
D、两个串的长度相等且对应位置的字符相同
3、若串str=“Software”，其子串的个数是（ ）。
A、8
B、9
C、36
D、37
4、一个链串的节点类型定义为 #define NodeSize 6 typedef struct node { char data[NodeSize]; struct node *next; } LinkStrNode; 如果每个字符占1个字节，指针占2个字节，该链串的存储密度为（ ）。
A、1/3
B、1/2
C、2/3
D、3/4
5、串采用节点大小为1的链表作为其存储结构，是指（ ）。
A、链表的长度为1
B、链表中只存放一个字符
C、链表中每个节点的数据域中只存放一个字符
D、以上都不对
6、对于一个链串s，查找第一个字符值为x的算法的时间复杂度为（ ）。
A、O(1)
B、O(n)
C、
D、以上都不对
7、设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（ ）。
A、求子串
B、串联接
C、模式匹配
D、求串长
8、在串的简单模式匹配中，当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是（ ）。
A、i++
B、i=j+1
C、i=i-j+1
D、i=j-i+1
9、在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是（ ）。
A、i=next[j]
B、i不变
C、.j不变
D、j=next[j]
10、在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位j与目标串位i比较时，两字符不相等，则j的位移方式是（ ）。
A、i=next[j]
B、i不变
C、j不变
D、j=next[j]
第5周作业
1、设s为一个长度为n的串，其中的字符各不相同，则s中的互异非平凡子串（非空且不同于s本身）的个数是多少？
2、在KMP算法中，计算模式串的next时，当j=0时，为什么要取next[0]=-1？
3、给出以下模式串的next值和nextval值： （1）ababaa （2）abaabaab
4、设有一个顺序串s，其字符仅由数字和小写字母组成。设计一个算法将s中所有数字字符放在前半部分，所有小写字母字符放在后半部分。并给出你所设计的算法的时间和空间复杂度。
5、用带头节点的单链表表示链串，每个节点存放一个字符。设计一个算法求s中最长平台的长度，所谓平台是指连续相同字符。
中国大学数据结构_50
数据结构是计算机科学的核心课程之一，也是计算机科学专业的重要基础课程。本文将介绍中国大学数据结构课程的相关内容。
课程简介
中国大学数据结构_50课程是一门包括课堂教学和实验的课程，主要介绍数据结构的概念、基本操作、算法和应用，帮助学生掌握各种常用数据结构的算法思想和实现方法。
课程内容
本课程的主要内容包括：
- 线性表
- 栈和队列
- 串
- 树
- 图
- 排序
- 查找
- 算法分析
教材
中国大学数据结构_50课程采用的教材有：
- 《数据结构》（严蔚敏、吴伟民）
- 《算法导论》（Thomas H. Cormen等）
此外，还有一些相关的参考书籍供学生参考，例如《数据结构与算法分析》（Mark Allen Weiss）。教师将会根据具体情况推荐使用哪些参考书籍。
实验
中国大学数据结构_50课程的实验有以下几个方面：
- 线性表的实现
- 栈和队列的实现
- 二叉树的实现
- 图的实现
- 排序算法的实现
- 查找算法的实现
- 算法分析的实现
实验课程将会让学生在课堂上进行实践，帮助学生更好地理解课堂上的理论知识。
考核方式
中国大学数据结构_50课程的考核方式主要有以下几种：
- 平时成绩（包括课堂出勤、作业、实验等）
- 期中考试
- 期末考试
教师将会根据具体情况制定考核方案，并在课程开始时向学生详细介绍。
总结
中国大学数据结构_50课程是计算机科学专业中非常重要的一门课程，它不仅是计算机科学专业的主干课程之一，而且是其他专业加入计算机科学领域的必修课程。学习此课程可以帮助学生掌握数据结构的基础概念和操作，为日后的计算机科学研究和实践打下坚实的基础。
