MOOC 数据结构-计算机学院刘遵仁(青岛大学)1464773161 最新慕课完整章节测试答案

【Test】单元测试 - 绪论

1、单选题：
‎在Data_Structure=(D，S)中，D是（）的有限集合。‌
选项：
A: 数据元素
B: 算法
C: 数据操作
D: 数据对象
答案: 【 数据元素】

2、单选题：
‎被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为（ ）。​
选项：
A: 规则
B: 结构
C: 集合
D: 运算
答案: 【 结构】

3、单选题：
​以下关于数据结构的说法正确的是（ ）。‍
选项：
A: 数据结构的逻辑结构独立于其存储结构
B: 数据结构的存储结构独立于该数据结构的逻辑结构
C: 数据结构的逻辑结构唯一地决定了该数据结构的存储结构
D: 数据结构仅由其逻辑结构和存储结构决定
答案: 【 数据结构的逻辑结构独立于其存储结构】

4、单选题：
‎在数据结构中，从逻辑上可以把数据结构分成（   ）。‎
选项：
A: 动态结构和静态结构
B: 紧凑结构和非紧凑结构
C: 线性结构和非线性结构
D: 内部结构和外部结构
答案: 【 线性结构和非线性结构】

5、单选题：
​以下关于数据结构的说法中错误的是（ ）。‏
选项：
A: 数据结构相同，对应的存储结构也相同
B: 数据结构涉及数据的逻辑结构、存储结构和施加其上的操作3个方面
C: 数据结构操作的实现与存储结构有关
D: 定义逻辑结构时可不考虑存储结构
答案: 【 数据结构相同，对应的存储结构也相同】

6、单选题：
‍算法指的是（ ）。‎
选项：
A: 计算机程序
B: 解决问题的计算方法
C: 搜索和排序方法
D: 解决问题的有限运算序列
答案: 【 解决问题的有限运算序列】

7、单选题：
‍算法的时间复杂度与（   ）有关。​
选项：
A: 问题规模
B: 计算机硬件的运行速度
C: 源程序的长度
D: 编译后执行程序的质量
答案: 【 问题规模】

8、单选题：

‏某算法的时间复杂度是O()，表明该算法（ ）。

‌选项：
A: 问题规模是
B: 问题规模与成正比
C: 执行时间等于 
D: 执行时间与成正比
答案: 【 执行时间与成正比】

9、单选题：
‍以下函数中时间复杂度最小的是（  ）。‎
选项：
A: T(n)=+5000n
B: T(n)=-10000n
C: T(n)=-6000n
D: T(n)=20000
答案: 【 T(n)=20000】

10、单选题：
‏下面程序段的时间复杂度为（  ）。‏‏x = 90;‏‏y = 100;‏‏while(y > 0)‏‏    if(x > 100)‏‏    {‏‏        x = x - 10;‏‏        y--;‏‏    }‏‏    else x++;‏‏‏
选项：
A: O(1)
B: O()
C: O()
D: O()
答案: 【 O(1)】

11、单选题：
‌下面程序段的时间复杂度为（ ）。‏‌i = 1;‏‌while(i <= n)‏‌    i = i * 3;‏
选项：
A: O()
B: O(3n)
C: O()
D: O()
答案: 【 O()】

12、单选题：
‍下面程序段的时间复杂度为（ ）。‌‍x = 0;‌‍for(i = 1; i < n; i++)‌‍    for (j = 1; j <= n - i; j++)‌‍        x++;‌
选项：
A: O(n)
B: O()
C: O()
D: O()
答案: 【 O()】

13、判断题：
‏数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

14、判断题：
‍数据的物理结构是指数据结构在计算机内的实际存储形式。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

15、判断题：
‎数据的逻辑结构与各数据元素在计算机中如何存储有关。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

16、判断题：
‍算法的时间效率和空间效率往往相互冲突，有时很难两全其美。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

【Test】单元测试 - 链式存储结构

1、单选题：
‌单链表的结点所占存储空间（   ）。​
选项：
A: 分两部分，一部分存放数据值，另一部分存放表示逻辑关系的指针
B: 只有一部分，存放结点值
C: 只有一部分，存储逻辑关系的指针
D: 分两部分，一部分存放结点值，另一部分存放结点所占单元数
答案: 【 分两部分，一部分存放数据值，另一部分存放表示逻辑关系的指针】

2、单选题：
‏线性表若采用链式存储结构时，要求内存中可用存储单元的地址（   ）。​
选项：
A: 必须是连续的
B: 部分地址必须是连续的
C: 一定是不连续的
D: 连续或不连续都可以
答案: 【 连续或不连续都可以】

3、单选题：
‌线性表L在（   ）情况下适用于使用链式结构实现。‎
选项：
A: 需经常修改L中的结点值
B: 需不断对L进行删除插入
C: L中含有大量的结点
D: L中结点结构复杂
答案: 【 需不断对L进行删除插入】

4、单选题：
‎单链表的存储密度（   ）。‎
选项：
A: 大于1
B: 等于1
C: 小于1
D: 不能确定
答案: 【 小于1】

5、单选题：
‌创建一个包括n个结点的有序单链表的时间复杂度是（    ）。‌
选项：
A: O(1)
B: O(n)
C: O()
D: O()

答案: 【 O()】

6、单选题：
‏以下说法错误的是（   ）。‎
选项：
A: 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B: 顺序存储的线性表可以随机存取
C: 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D: 线性表的链式存储结构优于顺序存储结构
答案: 【 线性表的链式存储结构优于顺序存储结构】

7、单选题：
‏在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（   ）。‏
选项：
A: s->next=p+1; p->next=s;
B: (*p).next=s; (*s).next=(*p).next;
C: s->next=p->next; p->next=s->next;
D: s->next=p->next; p->next=s;  
答案: 【 s->next=p->next; p->next=s;  】

8、单选题：
​在双向链表存储结构中，删除p所指的结点时须修改指针（   ）。​
选项：
A: p->next->prior=p->prior; p->prior->next=p->next;
B: p->next=p->next->next; p->next->prior=p;
C: p->prior->next=p; p->prior=p->prior->prior;
D: p->prior=p->next->next; p->next=p->prior->prior;
答案: 【 p->next->prior=p->prior; p->prior->next=p->next;】

9、单选题：
​在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（   ）。‍
选项：
A: p->next=q; q->prior=p; p->next->prior=q; q->next=q;
B: p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
C: q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;
D: q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;
答案: 【 q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;】

10、单选题：
‍在单链表中查找指定值的结点的时间复杂度是（  ）。‌
选项：
A: O(1)
B: O(n)
C: O()
D: O()
答案: 【 O(n)】

11、单选题：
‍以下关于单链表的叙述中，不正确的是（  ）。‏
选项：
A: 结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B: 逻辑上相邻的元素物理上不必相邻
C: 可以通过头结点直接计算第i个结点的存储地址
D: 插入、删除运算操作方便，不必移动结点
答案: 【 可以通过头结点直接计算第i个结点的存储地址】

12、单选题：
‎在单链表中，增加一个头结点的目的是为了（  ）。​
选项：
A: 使单链表至少有一个结点
B: 方便运算的实现
C: 标识链表中重要结点的位置
D: 说明单链表是线性表的链式存储结构
答案: 【 方便运算的实现】

13、单选题：
‏在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（  ）。‌
选项：
A: O(1)
B: O(n)
C: O()
D: O()
答案: 【 O(n)】

14、单选题：
‌将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度是（  ）。‍
选项：
A: O(1)
B: O(m)
C: O(n)
D: O(m+n)
答案: 【 O(m)】

15、单选题：
​已知一个长度为n的单链表中所有结点是递增有序的，以下叙述中正确的是（  ）。‎
选项：
A: 插入一个结点使之有序的算法的时间复杂度为O(1)
B: 删除最大值结点使之有序的算法的时间复杂度为O(1)
C: 找最小值结点的算法的时间复杂度为O(1)
D: 以上都不对
答案: 【 找最小值结点的算法的时间复杂度为O(1)】

16、单选题：
‏在一个长度为n(n>l)的带头结点的单链表L上，另设有尾指针r(指向尾结点)，执行(   )操作与链表的长度有关。‌
选项：
A: 删除单链表中的第一个元素
B: 删除单链表中的尾结点
C: 在单链表第一个元素前插入一个新结点
D: 在单链表最后一个元素后插入一个新结点
答案: 【 删除单链表中的尾结点】

17、单选题：
下列算法的功能是：删除单链表L（含两个或两个以上的数据结点）中第一个值为x的结点的前驱结点。请在空白处选择正确的语句。
int deleteFirstX(LinkList &L, ElemType x)
{
    LinkList prepre = L, pre = prepre->next, p;
    if (pre->data == x) return 0;
    p = pre->next;
    while (p != NULL && p->data != x) {
        prepre = pre;
        ____________________;
        p = p->next;
    }
    if (p != NULL) {
        prepre->next = p;
        free(pre);
        return 1;
    }
    else return 0;
}‌‏‌‏
选项：
A: pre = p
B: prepre->next = p
C: p = pre->next
D: p = prepre->next
答案: 【 pre = p】

18、单选题：
下列算法的功能是：设List={a1,b1,a2,b2，......，an,bn}为一线性表，采用带头结点的单链表head存放，设计一个就地算法，将其拆分为两个线性表，每个线性表均采用带头结点的单链表存储，使得：A={a1,a2,......,an}，B={bn,bn-1,......，b2,b1}。
请在空白处选择正确的语句。
void splitList(LinkList head, LinkList &headA, LinkList &headB)
{
    LinkList p = head->next, q, r;
    headA = head;
    r = headA;
    headB = (LNode *)malloc(sizeof(LNode));
    headB->next = NULL;
    while (p != NULL) {
        r->next = p;
        r = p;
        p = p->next;
        q = p->next;
        ________________________;
        headB->next = p;
        p = q;
    }
    r->next = NULL;
}‍‌‍‌
选项：
A: headB->next = p->next
B: p = headA->next
C: p->next = headA->next
D: p->next = headB->next
答案: 【 p->next = headB->next】

19、判断题：
‌链式存储表示的存储空间