数据结构(工程大学) 中国大学MOOC答案2024版100分完整版

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