数据结构(工程大学) 中国大学mooc慕课答案2024版 m111529

第一周 数据结构概述（总时长19’23”） 概述单元测试

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、 计算机算法必须具备输入、输出和____等5个特性。

A:可行性、可移植性和可扩充性
B:可行性、确定性和有穷性
C:确定性、有穷性和稳定性
D:易读性、稳定性和安全性
答案: 可行性、确定性和有穷性 

9、 在决定选取何种存储结构时，一般不考虑_____。

A:各结点的值如何
B:结点个数的多少
C:对数据有哪些运算
D:所用编程语言实现这种结构是否方便
答案: 各结点的值如何

10、 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_____。

A:数据的处理方法
B:数据元素的类型
C:数据元素之间的关系
D:数据的存储方法
答案: 数据元素之间的关系 

11、 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着_____。

A:数据元素具有同一特点
B:不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致
C:每个数据元素都一样
D:数据元素所包含的数据项的个数要相等
答案: 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致

12、 以下说法正确的是_____。

A:数据元素是数据的最小单位
B:数据项是数据的基本单位
C:数据结构是带结构的各数据项的集合
D:一些表面上很不相同的数据可以有相同的逻辑结构
答案: 一些表面上很不相同的数据可以有相同的逻辑结构 

第二周 顺序表（总时长30’44”） 顺序表单元测验

1、 线性表的顺序存储最适合于实现 运算。

A:插入
B:删除
C:查找
D:由下标定位
答案: 由下标定位

2、 对有14个元素的有序表A[14]作二分查找，查找元素A[3]时，将会与 元素依次比较。

A:A[0]，A[1]，A[2]，A[3]
B: A[0]，A[13]，A[6]，A[3]
C:A[6]，A[2]，A[4]，A[3]
D:A[6]，A[4]，A[2]，A[3]
答案: A[6]，A[2]，A[4]，A[3]

3、 如果线性表最常用的操作是取第i个结点及其前驱，则采用_____存储方式最节省时间。

A:单向链表
B:双向链表
C:单向循环链表
D:顺序表
答案: 顺序表

4、 线性表是____。

A:一个有限序列，可以为空
B:一个有限序列，不可以为空
C:一个无限序列，可以为空
D:一个无限序列，不可以为空
答案: 一个有限序列，可以为空

5、 对于顺序存储的长度为n的线性表，在第i个位置插入一个元素需要移动____个元素。其中，0≤i＜n。

A:n-i
B:n-i+1
C:n-i-1
D:i
答案: n-i

6、 采用顺序查找法查找一个长度为n 的线性表，则查找每个元素的平均比较次数为_____。

A:n/2
B:n
C:(n+1)/2
D:(n-1)/2
答案: (n+1)/2 

7、 对线性表进行二分查找时，要求线性表必须采用 _____。

A:顺序存储
B:链式存储
C:顺序存储，且结点有序排序
D:链式存储，且结点有序排序
答案: 顺序存储，且结点有序排序

8、 有一个长度为12的有序表，按二分找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为_____。

A:35/12
B:37/12
C:39/12
D:43/12
答案: 37/12

9、 若数组M可存放10个元素，每个元素占4个字节，从首地址x开始按顺序连续存放，那么，元素M[8]的起始地址为_____。

A:x+8
B:x+28
C:x+32
D:x+64
答案: x+32

10、 有序数组a[18]进行二分查找时，查找到a[5]的查找路径（下标序列）为_____。

A:1，3，5
B:8，2，5
C:8，3，5
D:8，4，5
答案: 8，3，5

11、 用二分法对数组a[13]进行查找，若待查元素为x，且a[7]<x<a[8]，那么查找路径为______

A:6，9，7，8
B:6，9，7

C:7，9，8

D:6，9，8

答案: 6，9，7，8 

12、 对于顺序存储的长度为n的线性表，删除第i个元素需要移动____个元素。其中，0≤i＜n。

A:n-i
B:n-i+1
C:n-i-1
D:i
答案: n-i-1

13、 用二分法对数组a[13]进行查找，在等概率的情况下，查找不成功的平均查找长度为__。

A:27/7
B:54/13
C:49/14
D:49/13
答案: 27/7

14、 对a[12]进行二分查找，查找下标为_____的元素时，查找长度最大。

A:1，4，7，9，11
B:0，3，6，9，11
C:1，3，6，9，11
D:0，4，8，9，10
答案: 1，4，7，9，11

第三周 链表（上）(总时长22’57”） 链表（上）单元测验

1、 线性表采用链式存储时，其地址 。

A:必须是连续的
B:部分地址必须是连续的
C:一定是不连续的
D:连续与否均可以
答案: 连续与否均可以

2、 从一个具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，需要平均比较_ 个结点。

A:n/2
B:n
C:(n+1)/2
D:(n-1)/2
答案: (n+1)/2

3、 能够满足快速完成插入和删除运算的线性表存储结构是____。

A:顺序存储
B:链式存储
C:散列存储
D:有序存储
答案: 链式存储

4、 已知单向链表中指针p指向结点A， 表示删除A的后继结点（若存在）的链操作（不考虑回收）。

A:p—>next=p—>next—>next
B:p=p—>next
C:p=p—>next—>next
D:p—>next=p
答案: p—>next=p—>next—>next

5、 在一个单向链表中，已知结点q是p的前趋结点，若在q和p之间插入*s结点，则须执行_____。

A:s—>next= p—>next；p—>next=s；
B: q—>next=s； s—>next= p；
C: p—>next= s—>next；s—>next= p；
D:p—>next=s； s—>next=q；
答案:  q—>next=s； s—>next= p；

6、 已知last指向单向简单链表的尾结点，将s所指结点加在表尾，不正确的操作是____。

A:last->next=s,last=s,last->next=NULL;
B:last->next=s,s->next=NULL,last=s;
C:s->next=NULL, last->next=s, s=last;
D:s->next=NULL, last->next=s,last=s;
答案: s->next=NULL, last->next=s, s=last;

7、 已知last指向单向简单链表的尾结点，将s所指结点加在表尾，正确的操作是____。

A:s->next=s,last=s,last->next=NULL;
B:last->next=s,s->next=NULL,last=s;
C:s->next=NULL, last->next=s, s=last;
D:s->next=last, last->next=NULL,last=s;
答案: last->next=s,s->next=NULL,last=s;

8、 已知h是指向单向加头链表的头指针，p指向一个新结点，将p所指结点插在表头（p指向第一个实际结点）的操作是_____。

A:p->next=h,h->next=p;
B:p->next=h->next,h->next=p;
C:p->next=h,h=p;
D:h->next=p,p->next=h->next;
答案: p->next=h->next,h->next=p; 

9、 已知h是指向单向加头链表的头指针，删除首元结点（第1个实际元素）的操作是_____。

A:p=h,h=p->next;free(p);
B:p=h->next;free(p);h=h->next;
C:p=h->next,h->next=p->next;free(p);
D:free(h->next);h=h->next;
答案: p=h->next,h->next=p->next;free(p);

10、 就单一的____运算来说，线性表采用顺序存储比采用链式存储好（n是表长）。

A:存取任意第i（0≤i≤n-1）个结点
B:交换前两个结点的值
C:输出所有结点
D:查找结点x在表中的序号
答案: 存取任意第i（0≤i≤n-1）个结点

11、 就单一的____运算来说，线性表采用链式存储比采用顺序存储好。

A:删除指定元素
B:输出所有结点
C:查找结点x在表中的序号
D:在表尾处插入一个元素
答案: 删除指定元素

12、 判定以head为头指针的单向简单链表为空的条件是 。

A:head= =NULL
B:head->next= =NULL
C:head->next= =head
D:head!=NULL
答案: head= =NULL

13、 判定以head为头指针的单向加头链表为空的条件是 。

A:head= =NULL
B:head->next= =NULL
C:head->next= =head
D:head!=NULL
答案: head->next= =NULL

14、 链表不具备的特点是_____。

A:可随机访问任一结点
B:插入删除不需要移动元素
C:不必事先估计存储空间
D:所需空间与其长度成正比
答案: 可随机访问任一结点

15、 对一个具有n个元素的线性表，建立单向链表的时间复杂度至少为__ 。

A:O(n)
B:O(1)
C:O(logn)
D:O(n^2)
答案: O(n)

第三周 链表（下）(总时长18’38”） 链表（下）单元测验

1、 在长度为n的有序链表中插入一个结点并保持有序，最坏情况下和平均情况下，时间复杂性分别是_____。

A:O(n)和O(1)
B:O(n)和O(log n)
C:O(n)和O(n)
D:O(nlogn)和O(n)
答案: O(n)和O(n)

2、 将如图所示的向单向链表中A段和B段交换位置（将B段调到A段的前面，其余结点次序不变），正确的程序段为_。

A:p->next= q->next；q->next=r->next; r->next=p->next;
B:q->next=r->next; r->next=p->next; p->next=q->next；
C:t=q->next; q->next=r->next; r->next=p->next; p->next=t；
D:t=q->next; q->next=r->next; r->next=q; p->next=t；
答案: t=q->next; q->next=r->next; r->next=p->next; p->next=t；

3、 若某线性表中最常用的操作是在最后一个元素之后插入新元素，或删除第一个元素，则采用 存储方式最节省时间。

A:单链表
B:仅有头指针的单循环链表
C:双链表
D:仅有尾指针的单循环链表
答案: 仅有尾指针的单循环链表

4、 对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为_____。

A:O (n)
B:O (1)
C:O (logn)
D:O(n^2)
答案: O(n^2)

5、 以head为头指针的非空单向循环链表的尾结点（由p所指向）满足_____。

A:p—>next==NULL
B:p==NULL
C:p—>next==head
D:p==head
答案: p—>next==head

6、 一个长度为n（n>1）的单向链表设有头和尾两个指针，执行_____操作所用时间与表长有关。

A:删除单链表中的第一个元素
B:删除单链表中的最后一个元素
C:在单链表第一个元素前插入一个新元素
D:在单链表最后一个元素后插入一个新元素
答案: 删除单链表中的最后一个元素

7、 如果对非空线性表的运算只有如下4种：（1）删除第一个元素；（2）删除最后一个元素；（3）在第一个元素左边插入新元素；（4）在最后一个元素的右边插入新元素。那么，最合适的存储形式是_____。

A:仅有表头指针的单向链表
B:仅有表尾指针的单向链表
C:仅有表头指针的双向循环链表
D:仅有表尾指针的单向循环链表
答案: 仅有表头指针的双向循环链表

8、 设有两个长度都为n的单向链表，结点类型相同。若以h1为表头指针的链表是非循环的，以h2为表头指针的链表是循环的，则_____。

A:对于两个链表来说，删除第一个结点的操作，其时间复杂性都是O（1）
B:对于两个链表来说，删除最后一个结点的操作，其时间复杂性都是O（n）
C:循环链表要比非循环链表占用更多的内存空间
D:h1和h2是不同类型的变量
答案: 对于两个链表来说，删除最后一个结点的操作，其时间复杂性都是O（n）

9、 在长度为n的_____上，删除第一个元素，如果不允许移动结点的值，其算法的时间复杂性为O（n）。

A:只有表头指针的不带表头监督元结点的单向循环链表
B:只有表尾指针的不带表头监督元结点的单向循环链表
C:只有表尾指针的带表头监督元结点的单向循环链表
D:只有表头指针的带表头监督元结点的单向循环链表
答案: 只有表头指针的不带表头监督元结点的单向循环链表

10、 与单向链表相比，双向链表的优点之一是_____。

A:插入、删除操作更简单
B:顺序访问相邻结点更灵活
C:可以省略表头指针或表尾指针
D:可以进行随机访问
答案: 顺序访问相邻结点更灵活

11、 判定以head为头指针的单向加头循环链表为空的条件是 。

A:head->next= =NULL
B:head= =NULL
C:head->next= =head
D:head!=NULL
答案: head->next= =head

12、 双向循环链表中，在p所指结点的右侧插入指针s所指结点，其操作是____。

A:p->Rlink=s; s->Llink=p; (p->Rlink)->Llink=s; s->Rlink=p->Rlink;
B:s->Llink=p; s->Rlink=p->Rlink; p->Rlink=s; p->Rlink->Llink=s;
C:p->Rlink=s; p->Rlink->Llink=s; s->Llink=p; s->Rlink=p->Rlink;
D:s->Llink=p; s->Rlink=p->Rlink; p->Rlink->Llink=s; p->Rlink=s;
答案: s->Llink=p; s->Rlink=p->Rlink; p->Rlink->Llink=s; p->Rlink=s;

13、 在双向链表中，删除p所指结点（不考虑回收结点）不正确的操作是_____。

A:p->Llink->Rlink=p->Rlink, p->Rlink->Llink=p->Llink;
B:p->Llink= p->Rlink, p->Rlink=p->Llink;
C:p=p->Llink,p->Rlink= p->Rlink->Rlink, p->Rlink->Llink=p;
D:p=p->Rlink,p->Llink= p->Llink->Llink, p->Llink->Rlink=p;
答案: p->Llink= p->Rlink, p->Rlink=p->Llink; 

第四周 栈和队（总时长24’53”） 栈和队单元测验

1、 链栈与顺序栈相比有一个明显的优点，即 。

A:插入操作更方便
B:通常不会出现栈满的情况
C:不会出现栈空的情况
D:删除操作更加方便
答案: 通常不会出现栈满的情况

2、 设进栈序列是1，2，3，…，n，输出序列为p1，p2，p3，…，pn。若p1=3，则p2为_____。

A:可能是2
B:不可能是2
C:可能是1
D:必是1
答案: 可能是2

3、 已知hs为首指针的简单单向链表存储一个栈，使指针s所指结点进栈的操作是____。

A:hs->next=s;
B:s->next=hs;hs=s;
C:s->next=hs->next; hs->next=s;
D:s->next=hs;hs=hs->next;
答案: s->next=hs;hs=s;

4、 数组q[M]（M等于6）存储一个循环队，first和last分别是首尾指针。已知first和last的当前值分别等于2和5，且q[5]存放的是队尾元素。当从队列中删除两个元素，再插入一个元素后，first和last的值分别等于_____。

A:3和6
B:4和0
C:1和3
D:5和1
答案: 4和0

5、 对于链队，在进行删除操作时， 。

A:仅修改头指针
B:仅修改尾指针
C:头、尾指针都要修改
D:头、尾指针可能都要修改
答案: 头、尾指针可能都要修改

6、 设进栈次序为ABCDE，______是不可能得到的出栈序列。

A:ABCDE
B:BCDEA
C:EABCD
D:EDCBA
答案: EABCD

7、 设进栈序列是1，2，3，…，n，输出序列为p1，p2，p3，…，pn。若p3=1，则p1为_____。

A:必是2
B:可能是3
C:必定是3
D:不可能是3
答案: 可能是3

8、 数组S[M]存储一个栈，top为栈顶指针。如果条件top= =-1表示栈空，在栈不空的情况下，栈顶元素为_____。

A:S[top-1]
B:S[top]
C:S[top+1]
D:S[++top]
答案: S[top]

9、 数组S[M]存储一个栈，top为栈顶指针。如果条件top= =M表示栈满，那么条件_____表示栈空。

A:top= =1
B:top= =-1
C:top= =0
D:top!=0
答案: top= =0

10、 数组q[M]存储一个循环队，first和last分别是首尾指针，如果使元素x进队操作的语句为“q[last]=x,last=(last+1)%m;”那么判断队满的条件是_____。

A:last= =first
B:last= =M-1
C:(last+1)%m= =first
D:last+1= =first
答案: (last+1)%m= =first

11、 数组q[M]存储一个循环队，first和last分别是首尾指针。如果使元素x出队操作的语句为“first=(first+1)%m, x=q[first];”。那么元素x进队的语句是_____。

A:last=(last+1)%m,q[last]=x;
B:x=q[last], last =(last+1)%m;
C:q[last+1]=x;
D:q[(last+1)%m]=x;
答案: last=(last+1)%m,q[last]=x;

12、 一个单向简单链表存储的栈，其栈顶指针为top。执行操作______可将原栈顶元素退栈，并存放在变量x中（不考虑回收结点）。

A:x=top; top=top->next;
B:x=top->data;
C:top=top->next; x= top->data;
D:x=top->data; top=top->next;
答案: x=top->data; top=top->next;

13、 首尾指针分别是f和r的单向加头链表存储一个队，元素x出队的语句为“f=f->next, x=f->data;”，那么判断队空否的条件是_____。

A:f= =r
B:f= =NULL
C:f->next= =r
D:f->next=NULL
答案: f= =r

14、 设进栈序列是p1，p2，p3，…，pn，输出序列为1，2，3，…，n。若p3=1，则p1为_____。

A:可能是2
B:不可能是2
C:必是2
D:必定是3
答案: 不可能是2

15、 数组q[M]存储一个循环队，first和last分别是首尾指针。当前队中元素个数为_____。

A:(last- first+M)%M
B:last-first+1
C:last-first-1
D:last-first
答案: (last- first+M)%M

第四周 散列表(总时长30’11”) 散列表单元测试

1、 顺序查找法最适合用于（）的线性表。

A:散列存储
B:顺序存储或链式存储
C:压缩存储
D:分段存储
答案: 顺序存储或链式存储

2、 平均情况下，查找速度最快，而且又能适应插入、删除的数据结构是（）。

A:顺序存储的有序表
B:链式存储的有序表
C:散列表
D:链式存储的无序表
答案: 散列表

3、 数组a[m]存储的散列表，散列函数为：hash(x)=x mod p,一般情况下，p取（）时，散列结果可能比较平均。

A:小于m的最大奇数
B:小于m的最大素数
C:小于m的最大偶数
D:小于m的最大合数
答案: 小于m的最大素数

4、 以下说法错误的是_____。

A:散列存储的基本思想是由元素值决定其存储地址
B:散列表的结点中只包含数据元素自身的信息，不包含任何指针
C:装填因子是散列法的一个重要参数，它反映了散列表的装填程度
D:散列表的查找效率主要取决于的散列函数和处理冲突的方法
答案: 散列表的结点中只包含数据元素自身的信息，不包含任何指针

5、 设散列表长m=14，散列函数Hash(x)=x mod 11。表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空。若用平方探测法处理冲突，插入元素49时，其地址是_____。

A:8
B:3
C:5
D:9
答案: 9

下方是付费阅读内容：本平台商品均为虚拟商品，无法用作二次销售，不支持退换货，请在购买前确认您需要购买的资料准确无误后再购买，望知悉！

完整答案需点击上方按钮支付5元购买,所有答案均为章节测试答案，购买后上方矩形框将出现已付费的隐藏内容。

不知道怎么购买？点此查看购买教程！