2021 数据结构与程序设计（下）(中国人民解放军陆军工程大学) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2021-08-24到2022-01-24
本篇答案更新状态:已完结

第三周 链表（下）(总时长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; 】

第二周 指针(总时长57’49) 指针单元测试

1、 问题:指向结构体的指针p取某个域成员的值时，除了用(p)，还可以用？
选项：
A:p->
B:p<-
C:p.
D:p->
答案: 【p->】

2、 问题:对指针p的赋值方式，下面那种是错误的
选项：
A:int a[N], p;p=&a[0];
B:int a[N], p=&a[0];
C:int a[N], p=a;
D:int a[N], p;p=&a[0];
答案: 【int a[N], p;*p=&a[0];】

3、 问题:定义一个int类型的指针变量p，并使其指向数组a，下面哪个定义是正确的
选项：
A:int a[ ], p=a;
B:int a, p=a;
C:int a[M], p=a;
D:int a[M], p=a;
答案: 【int a[M], p=a;】

4、 问题:下列写法正确的是
选项：
A:char str[14];  str[]=″I love China!″;
B:char a;scanf("%s",a);
C:char b="House";b[2]=’r’;
D:char format="a=%d,b=%f";printf(format,a,b);
答案: 【char format="a=%d,b=%f";printf(format,a,b);】

5、 问题:当定义某函数时候，有一个形参被说明成int*类型，那么可以与之结合的实参类型可以是?
选项：
A:int型普通变量
B:int型指针
C:int型一维数组
D:int型值的地址
答案: 【int型指针;
int型一维数组;
int型值的地址】

6、 问题:指针p指向一维数组a后，下列说法正确的是
选项：
A:指针p可以指向自加操作，数组名a不可以。
B:p的初值只能指向数组的首元素
C:p+i表示的是&p[i]
D:p+i表示指向数组元素a[i].
E:a[i]和(a+i)的意义相同.
F:当p指向数组a后，p就和a一样，是地址常量。
答案: 【指针p可以指向自加操作，数组名a不可以。;
p+i表示的是&p[i];
a[i]和(a+i)的意义相同.】

7、 问题:有定义：int p；下面哪些说法正确：
选项：
A:p是一个 int 类型的变量
B:p指向的对象类型是int
C:p是一个野指针
D:在当前定义中，执行“p=3”是错误的
答案: 【p是一个 int 类型的变量;
p指向的对象类型是int;
p是一个野指针;
在当前定义中，执行“*p=3”是错误的】

8、 问题:可以把一个大于等于0的整数作为地址，赋给一个指针变量。
选项：
A:正确
B:错误
答案: 【错误】

9、 问题:指向一维数组的指针，是指指针变量存储的值为数组元素的地址。
选项：
A:正确
B:错误
答案: 【正确】