大学MOOC 数据结构(南昌航空大学)1450771167 最新慕课完整章节测试答案

1.1什么是数据结构

1、多选题：
‏数据结构的研究对象主要包括：‌
选项：
A: 数据集合中元素之间的关系
B: 数据集合的存储实现方式
C: 对数据集合进行的操作
D: 操作算法优劣的评价
答案: 【 数据集合中元素之间的关系;
数据集合的存储实现方式;
对数据集合进行的操作;
操作算法优劣的评价】

2、判断题：
‏数据结构主要研究非数值计算的问题。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

3、判断题：
‎数据结构的研究与计算机硬件无关。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

1.2数据结构的基本概念一——逻辑结构

1、单选题：
​数据的逻辑结构是指 （        ）关系的整体。‏
选项：
A: 数据存储结构之间
B: 数据类型之间
C: 数据元素之间逻辑
D: 数据项之间逻辑
答案: 【 数据元素之间逻辑】

2、多选题：
‎以下说法不正确的是（        ）。‍
选项：
A: 数据可由若干个数据元素构成。
B: 数据项是不可分割的最小可标识单位。
C: 数据项可由若干个数据元素构成。
D: 数据元素是数据的最小单位。
答案: 【 数据项可由若干个数据元素构成。;
数据元素是数据的最小单位。】

3、多选题：
‌数据的逻辑结构可以分为（        ）。‍
选项：
A: 动态结构和静态结构
B: 线性结构和非线性结构
C: 内部结构和外部结构
D: 集合、线性结构、树形结构、图状结构
答案: 【 线性结构和非线性结构;
集合、线性结构、树形结构、图状结构】

1.2数据结构的基本概念二——物理结构

1、单选题：
‎下面关于数据的逻辑结构与存储结构说法正确的是（        ）。‍
选项：
A: 逻辑结构要体现出存储结构。
B: 存储结构要体现出逻辑结构。
C: 两者是一一对应的。
D: 二者毫无关系。
答案: 【 存储结构要体现出逻辑结构。】

2、单选题：
‍在数据的存储中，一个结点通常存储一个（        ）。‌
选项：
A: 数据结构
B: 数据类型
C: 数据元素
D: 数据项
答案: 【 数据元素】

3、单选题：
‌在决定选取任何类型的存储结构时，一般不多考虑（        ）。‏
选项：
A: 对数据有哪些运算
B: 结点个数的多少
C: 各结点的具体取何值
D: 所用编程语言实现这种结构是否方便
答案: 【 各结点的具体取何值】

1.3抽象数据类型

1、多选题：
‏下列关于抽象数据类型（ADT）定义的说法，正确的有（        ）。​
选项：
A: ADT的定义只取决于它的一组逻辑特性。
B: ADT的定义与计算机内部如何表示和实现无关。
C: 不论ADT的内部结构如何变化，只要它的数学特性不变，都不影响它的外部使用。
D: ADT定义了一个完整的（狭义）数据结构。
答案: 【 ADT的定义只取决于它的一组逻辑特性。;
ADT的定义与计算机内部如何表示和实现无关。;
不论ADT的内部结构如何变化，只要它的数学特性不变，都不影响它的外部使用。;
ADT定义了一个完整的（狭义）数据结构。】

2、多选题：
‍调用下列test( )函数，能够在屏幕上输出“hello world”的是（        ）。​
选项：
A: void GetMemory(char *p){    p = (char *)malloc(100);}void Test(void){    char *str = NULL;    GetMemory(str);    strcpy(str, "hello world");    printf(str);}
B: char *GetMemory(void){    char p[ ] = "hello world";    return p;}void Test(void){    char *str = NULL;    str = GetMemory();    printf(str);}
C: void Test(void){    char *str = (char *) malloc(100);    strcpy(str, "No!");    free(str);    if (str != NULL)    {        strcpy(str, "hello world");        printf(str);    }}
D: void GetMemory(char **p, int num){    *p = (char *)malloc(num);}void Test(void){    char *str = NULL;    GetMemory(&str, 100);    strcpy(str, "hello world");    printf(str);}
答案: 【 void Test(void){    char *str = (char *) malloc(100);    strcpy(str, "No!");    free(str);    if (str != NULL)    {        strcpy(str, "hello world");        printf(str);    }};
void GetMemory(char **p, int num){    *p = (char *)malloc(num);}void Test(void){    char *str = NULL;    GetMemory(&str, 100);    strcpy(str, "hello world");    printf(str);}】

1.4什么是算法

1、单选题：
‏计算机中算法是解决某一问题的有限运算序列，必须具备输入、输出、（        ）等5个特性。‎
选项：
A: 确定性、有穷性和健壮性
B: 可读性、正确性和健壮性
C: 可行性、正确性和可读性
D: 可行性、确定性和有穷性
答案: 【 可行性、确定性和有穷性】

2、单选题：
​数据的运算（即操作） （        ）。‍
选项：
A: 在不同计算机上的实现方法都是相同的。
B: 必须用程序设计语言来描述
C: 与采用何种存储结构有关
D: 有算术运算和关系运算两大类
答案: 【 与采用何种存储结构有关】

3、多选题：
‏算法的设计目标有（        ）等等。‌
选项：
A: 可行性
B: 健壮性
C: 有穷性
D: 正确性
答案: 【 健壮性;
正确性】

1.5算法的分析与度量

1、单选题：
‏算法分析的主要任务之一是分析（        ）。​
选项：
A: 算法中是否存在语法错误
B: 算法的执行时间与问题规模之间的关系
C: 算法中输入和输出之间的关系
D: 算法是否具有较好的可读性
答案: 【 算法的执行时间与问题规模之间的关系】

2、单选题：
​给出算法的时间复杂度是属于一种（        ）。‎
选项：
A: 事前统计的方法
B: 事前分析估算的方法
C: 事后统计的方法
D: 事后分析估算的方法
答案: 【 事前分析估算的方法】

3、单选题：
‏下述函数中时间复杂度最小的是（        ） 。‎
选项：
A:
B:
C:
D:
答案: 【 】

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

2.1线性表的定义一——概念和ADT

1、单选题：
​下列有关线性表的叙述中，正确的是（      ）。‏
选项：
A: 线性表中元素之间的关系是线性关系。
B: 线性表中至少有一个元素。
C: 线性表中的任一元素有且仅有一个直接前趋。
D: 线性表中的任一元素有且仅有一个直接后继。
答案: 【 线性表中元素之间的关系是线性关系。】

2、判断题：
‍插入和删除操作是线性表的基本操作，这两种操作在数组中也经常使用。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

2.1线性表的定义二——合并与归并

1、单选题：
‏将两个长度均为n的有序线性表归并成一个有序线性表，最少需要（    ）次比较。​
选项：
A: n-1
B: n
C: 2n-1
D: 2n
答案: 【 n】

2、单选题：
‌假设两个集合分别存储在两个线性表中，长度分别为m和n，将它们合并到一个新的线性表中，则该线性表的最小长度是（    ）。​
选项：
A: m+n
B: min(m,n)
C: max(m,n)
D: 无法确定
答案: 【 max(m,n)】

2.2顺序表

1、单选题：
‏顺序表具有随机存取特性，指的是（    ）。‏
选项：
A: 查找值为 x 的元素与顺序表中元素个数 n 无关
B: 查找值为 x 的元素与顺序表中元素个数 n 有关
C: 查找序号为 i 的元素与顺序表中元素个数 n 无关
D: 查找序号为 i 的元素与顺序表中元素个数 n 有关
答案: 【 查找序号为 i 的元素与顺序表中元素个数 n 无关】

2、单选题：
‏顺序表中，删除一个元素所需要的时间（    ）。‎
选项：
A: 与删除元素的位置及顺序表的长度都有关
B: 只与删除元素的位置有关
C: 只与顺序表的长度有关
D: 与删除元素的位置及顺序表的长度都无关
答案: 【 与删除元素的位置及顺序表的长度都有关】

3、单选题：
‌假设某顺序表中第一个元素的存储地址是1010H，每个元素占8个存储单元，则第5个元素的存储地址是（    ）。‏
选项：
A: 1042H
B: 1050H
C: 1030H
D: 1038H
答案: 【 1030H】

4、判断题：
‌顺序表中元素的逻辑顺序与存储顺序总是一致的。​
选项：
A: 正确
B: 错误
答案: 【 正确】

2.3线性链表一——单链表

1、单选题：
‍已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（    ）。‍
选项：
A: O(n)
B: O(m*n)
C: O(min(m,n))
D: O(max(m,n))
答案: 【 O(max(m,n))】

2、单选题：
‌下列关于单链表的说法，错误的是（    ）。‌
选项：
A: 数据域用于存储线性表的一个数据元素。
B: 指针域用于存储一个指向本结点对应元素的直接后继所在结点的指针。
C: 单链表中各结点的地址不可以连续。
D: 单链表无法随机存取。
答案: 【 单链表中各结点的地址不可以连续。】

3、多选题：
​单链表具备的特点有（    ）。 ‍
选项：
A: 插入和删除不需要移动元素。
B: 不必事先估计整个线性表所需的存储空间。
C: 所需存储空间与线性表长度成正比。
D: 只能顺序访问。
答案: 【 插入和删除不需要移动元素。;
不必事先估计整个线性表所需的存储空间。;
所需存储空间与线性表长度成正比。;
只能顺序访问。】

4、多选题：
​在一个单链表中，已知 q 是 p 的前趋结点，若在 q 和 p 之间插入结点 s ，则应当执行语句序列（    ）。‏
选项：
A: s -> next = p -> next;     p -> next = s;
B: s -> next = q -> next;     p -> next = s;
C: s -> next = q -> next;     q -> next = s;
D: q -> next = s;     s -> next = p;
答案: 【 s -> next = q -> next;     q -> next = s;;
q -> next = s;     s -> next = p;】

2.3线性链表二——静态链表

1、单选题：
‍静态链表中的指针域存放的是（    ）。​
选项：
A: 下一个元素的地址
B: 内存地址
C: 下一个元素在数组中的位置
D: 以上都不对
答案: 【 下一个元素在数组中的位置】

2、判断题：
‌静态链表不需要一开始就分配所有的存储空间，可以等到要插入数据元素时再申请‍
选项：
A: 正确
B: 错误
答案: 【 错误】

2.4循环链表和双向链表

1、单选题：
‍对于双向链表，在两个结点之间插入一个新结点需修改的指针共（    ）个。‌
选项：
A: 1
B: 2
C: 3
D: 4
答案: 【 4】

2、单选题：
‍非空的循环单链表 head 的尾结点 p 满足 （    ）。‏
选项：
A: p -> next == head
B: p -> next == NULL
C: p == NULL
D: p == head
答案: 【 p -> next == head】

3、单选题：
‌对于长度为 n（n≥1）的双向链表 L ，在 p 所指结点之前插入一个新结点，其时间复杂度为（    ）。​
选项：
A: O(1)
B: O(n)
C: O(nlogn)
D:
答案: 【 O(1)】

4、多选题：
‏对于一个头指针为 head 的带头结点的双向循环链表，可以作为判定该表为空表的条件是（    ）。‍
选项：
A: head == NULL
B: head == NULL
C: head -> prior == head
D: head -> next == head
答案: 【 head -> prior == head;
head -> next == head】

2.5顺序表与线性链表的比较一——顺序表与链表

1、单选题：
‌静态链表与顺序表相比，优点在于（    ）。‎
选项：
A: 所有操作的算法实现更简单
B: 便于随机存取
C: 便于插入和删除
D: 便于利用零散的存储空间
答案: 【 便于插入和删除】

2、单选题：
​若某线性表最常用的操作是存取任意指定序号的元素和在表尾元素之后进行插入和删除操作，则采用（        ）存储方式最节省时间。​
选项：
A: 带头结点的单链表
B: 不带头结点的单链表
C: 带头结点的双向循环链表
D: 顺序表
答案: 【 顺序表】

3、单选题：
‏设线性表中有 2n 个元素，以下操作中，（    ）在单链表上实现要比在顺序表上实现效率更高。‏
选项：
A: 删除指定位置元素的下一个元素
B: 在最后一个元素的后面插入一个新元素
C: 顺序输出前 k 个元素
D: 交换第 i 个元素和第 n-i+1 个元素的值 （i=1, 2, …, n）
答案: 【 删除指定位置元素的下一个元素】

2.5顺序表与线性链表的比较二——各种链表的对比

1、单选题：
‏与非循环单链表相比，循环单链表的主要优点是（    ）。‎
选项：
A: 不再需要头指针
B: 已知某个节点的位置后，能够容易找到它的前驱节点
C: 在进行插入、删除操作时，能更好地保证链表不断开
D: 从表中任意节点出发都能扫描到整个链表
答案: 【 从表中任意节点出发都能扫描到整个链表】

2、单选题：
‏若某线性表最常用的操作是在表尾结点插入新结点和删除表尾结点，则采用（        ）存储方式最节省时间。‌
选项：
A: 带头结点的双向循环链表
B: 不带头结点的单链表
C: 仅有尾指针的循环单链表
D: 仅有头指针的循环单链表
答案: 【 带头结点的双向循环链表】

3、单选题：
‍若某线性表最常用的操作是在表尾结点之后插入新结点和删除表头结点，则采用（        ）存储方式最节省时间。‌
选项：
A: 仅有头指针的循环单链表
B: 仅有尾指针的循环单链表
C: 带头结点的单链表
D: 带头结点的双向循环链表
答案: 【 仅有尾指针的循环单链表】

4、单选题：
‍下列关于链表的描述，错误的是（    ）。‏
选项：
A: 在循环单链表中，从表中任一结点出发都可以通过前后移动操作来遍历整个循环链表。
B: 在双向链表中，可以从任一结点开始沿同一方向查找到任何其他结点。
C: 单链表不具有随机存取特性，而双向链表具有随机存取特性。
D: 为了方便插入和删除，可以使用双向链表存放数据。
答案: 【 为了方便插入和删除，可以使用双向链表存放数据。】

3.1栈的定义与实现

1、单选题：

‌一个栈的入栈序列为1,2,3,…,n，其出栈序列是。若，则为（        ）。

​选项：
A: i
B: n-i
C: n-i+1
D: 不确定
答案: 【 n-i+1】

2、单选题：
‏设栈最大长度为3，入栈序列为1、2、3、4、5、6，则不可能的出栈序列是（    ）。‎
选项：
A: 1、2、3、4、5、6
B: 2、1、3、4、5、6
C: 3、4、2、1、5、6
D: 4、3、2、1、5、6
答案: 【 4、3、2、1、5、6】

3、单选题：
‍在 n 个单元的顺序栈中，假设以地址高端（下标为 n-1 的单元）作为栈底，以 top 作为栈顶指针，则向栈中压入一个元素时，top的变化是（    ）。​
选项：
A: top 不变
B: top=top->next
C: top=top-1
D: top=top+1
答案: 【 top=top-1】

3.2栈的应用举例一——数制转换、括号匹配、行编辑器

1、单选题：
‏利用栈将十进制数 N（N<100）转换为二进制数时，为了确保栈在处理过程中不会发生上溢，则该栈至少要有（    ）个存储单元。‏
选项：
A: 6
B: 7
C: 8
D: 9
答案: 【 7】

2、单选题：
‍利用栈对表达式 { ( a - b ) / [ c * ( d + e ) ] * ( f - g ) } 进行括号匹配的检验时，该栈至少要有（    ）个存储单元才能确保不发生上溢。‏
选项：
A: 3
B: 5
C: 7
D: 9
答案: 【 3】

3.2栈的应用举例三—表达式求值

1、单选题：
‌利用栈求表达式的值时，假设操作符栈 OPND 只有2个存储单元。在处理下列表达式的过程中，不会发生上溢的是（    ）。‍
选项：
A: A-B*(C-D)
B: (A-B)*C-D
C: (A-B*C)-D
D: (A-B)*(C-D)
答案: 【 (A-B)*C-D】

2、单选题：
‍表达式 (a+b)*(c+d)-e 的后缀表达式是（    ）。​
选项：
A: abcde++*-
B: ab+cde+*-
C: ab+cd+e*-
D: ab+cd+*e-
答案: 【 ab+cd+*e-】

3.3栈与递归的实现二——递归的实现

1、单选题：
递归函数如下：‎void f ( int n ) {‎    printf( "%d", n%10 );‎    if ( n/10 != 0)  f( n/10 );‎}‎执行语句 f( 857 ) 的输出结果是（    ）。‎
选项：
A: 857
B: 758
C: 75
D: 7
答案: 【 758】

2、单选题：
‏递归函数如下：​‏void print( int w ) {​‏    int i;​‏    if ( w != 0 ) {​‏        print( w-1 );​‏        for ( i=1; i<=w; i++ )​‏            printf( "%3d", i );​‏        printf( "n" );​‏    }​‏} ​‏执行语句 print( 3 ) 的输出结果是（    ）。​
选项：
A:   1  1  2  1  2  3
B:   1  2  3  1  2  1
C:   1  2  2  3  3  3
D:   3  3  3  2  2  1
答案: 【   1  1  2  1  2  3】

3.4队列的定义与实现一——定义和链队列

1、单选题：
‍若用单链表来表示队列，则应该选用（    ）。‌
选项：
A: 带尾指针的非循环队列
B: 带尾指针的循环链表
C: 带头指针的非循环链表
D: 带头指针的循环链表
答案: 【 带尾指针的循环链表】

2、单选题：
‏栈和队列的共同点是（    ）。​
选项：
A: 都是先进后出
B: 都是后进先出
C: 只允许在端点处插入和删除元素
D: 没有共同点
答案: 【 只允许在端点处插入和删除元素】

3、单选题：
‌在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓冲区应是一个（    ）结构。‎
选项：
A: 数组
B: 线性表
C: 堆栈
D: 队列
答案: 【 队列】

3.4队列的定义与实现二——循环队列和双端队列

1、单选题：
​循环队列存储在数组A[0..7]中，假设当前队尾指针Rear和队头Front的值分别为0和5，则当从队列中加入2个元素，删除3个元素后，Rear和Front的值分别为多少（        ）。‌
选项：
A: 7和3
B: 0和2
C: 2和0
D: 3和7
答案: 【 2和0】

2、单选题：
‏某队列允许在两端进行入队操作，但仅允许在一端进行出队操作，则入队序列abcde不可能得到的出队序列是（    ）。‍
选项：
A: bacde
B: dbace
C: dbcae
D: ecbad
答案: 【 dbcae】

4.1串的定义

1、单选题：
‏若串 s = "progress"，其子串的个数是（    ）。‏
选项：
A: 8
B: 36
C: 37
D: 256
答案: 【 37】

2、单选题：
​串是一种特殊的线性表，其特殊性体现在（    ）。‎
选项：
A: 可以顺序存储
B: 数据元素是一个字符
C: 可以链接存储
D: 数据元素可以是多个字符
答案: 【 数据元素是一个字符】

3、单选题：
‌若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘TTT’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（    ）。‍
选项：
A: ABCTTTG0123
B: ABCDTTT2345
C: ABCTTTG1234
D: ABCDTTT1234
答案: 【 ABCTTTG1234】

4.2串的表示和实现

1、单选题：
‎对于一个链串s，查找第i个元素的算法时间复杂度为（    ）。‌
选项：
A: O(1)
B: O(n)
C: