大学MOOC 数据结构(河南大学)1461627165 最新慕课完整章节测试答案

小测验：算法复杂度

1、单选题：
​下列函数中，哪个函数具有最快的增长速度：‌
选项：
A:
B:
C:
D:
答案: 【 】

2、单选题：
‍下面一段代码的时间复杂度是？if ( A > B ) {
    for ( i=0; i<N; i++ )
        for ( j=N*N; j>i; j-- )
            A += B;
}
else {
    for ( i=0; i<N*2; i++ )
        for ( j=N*2; j>i; j-- )
            A += B;
}​
选项：
A:
B:
C:
D:
答案: 【 】

测试1 数据结构概述

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

2、单选题：
‎与数据元素本身的形式、内容、相对位置、个数无关的是数据的（   ）。         ‎               ‎‎‎
选项：
A: 存储结构  
B: 存储实现
C: 逻辑结构
D: 运算实现
答案: 【 逻辑结构】

3、单选题：
下面说法错误的是（    ） ‏    (1）算法原地工作的含义是指不需要任何额外的辅助空间‏   （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法‏   （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界‏   （4）同一个算法，实现语言的级别越高，执行效率就越低‏‌‏
选项：
A: (1) 
B: (1),(2)
C: (1),(4)
D: (3)
答案: 【 (1),(4)】

4、单选题：
在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（     ）。‍‎‍
选项：
A: 数据的处理方法
B: 数据元素的类型
C: 数据元素之间的关系
D: 数据的存储方法
答案: 【 数据元素之间的关系】

5、单选题：
下面程序段的时间复杂度是     。​  for（ i ＝0； i＜n； i＋＋）​  for（j＝0；j＜m；j＋＋）​  {A[i][j] ＝ 0；​  Sum=sum+1；  }​‎​
选项：
A: O（n*m）
B: O（2n*m）
C: O（n+m）
D:  O（2n*2m）
答案: 【 O（n*m）】

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: 抽象数据类型的三个方面包括：数据对象、数据关系和基本操作。
答案: 【 数据元素是数据的基本单位。;
数据项是数据处理的最小单位。;
抽象数据类型的定义仅取决于它的一组逻辑特征，与其在计算机内部如何表示和实现无关。;
抽象数据类型的三个方面包括：数据对象、数据关系和基本操作。】

测试5 串、数组、广义表

1、单选题：
‎设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（   ）。‏
选项：
A: 求子串
B: 联接 
C: 匹配 
D: 求串长
答案: 【 匹配 】

2、单选题：
‎若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行‍‎concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))‍‎其结果为（    ）。‍
选项：
A: ABC###2345
B: ABC###G1234
C: ABCD###1234
D: ABC###01234
答案: 【 ABC###G1234】

3、单选题：
‎设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（   ）。​‎​
选项：
A: 13
B: 33
C: 18
D: 40
答案: 【 33】

4、单选题：
‏若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i<j）的位置k的关系为(     )。 ‏
选项：
A: j*(j-1)/2+I
B: i*(i-1)/2+j
C: i*(i+1)/2+j 
D:  j*(j+1)/2+i
答案: 【 j*(j-1)/2+I】

5、单选题：
‏有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（    ）。‌‏‌
选项：
A: 60
B: 33
C: 18000
D: 66
答案: 【 66】

6、单选题：
‏数组A[0..4,-1..-3,5..7]中含有元素的个数（   ）‌
选项：
A: 55
B: 45
C: 36
D: 16
答案: 【 45】

7、单选题：
‏7. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是(     )。‌
选项：
A: head(tail(LS))
B:  tail(head(LS))
C: head(tail(head(tail(LS)))
D: head(tail(tail(head(LS))))
答案: 【 head(tail(head(tail(LS)))】

8、多选题：
​下面说法正确的是(     )。​
选项：
A: 广义表的表头总是一个广义表
B: 广义表的表尾总是一个广义表
C: 广义表难以用顺序存储结构
D: 广义表可以是一个多层次的结构
答案: 【 广义表的表尾总是一个广义表;
广义表难以用顺序存储结构;
广义表可以是一个多层次的结构】

9、判断题：
‏ 串是一种数据对象和操作都特殊的线性表。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

10、判断题：
‎设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。​
选项：
A: 正确
B: 错误
答案: 【 正确】

11、判断题：
‍从逻辑结构上看，n维数组的每个元素均属于n个向量。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

12、判断题：
‍稀疏矩阵压缩存储后，必会失去随机存取功能。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

13、判断题：
​二维以上的数组其实是一种特殊的广义表。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

14、判断题：
‍广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

15、判断题：
‏广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

16、填空题：
‌组成串的数据元素只能是(    )。‏
答案: 【 字符】

17、填空题：
‎设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A[25,18]的存储地址为                    ‍
答案: 【 9572】

18、填空题：
‏当广义表中的每个元素都是原子时，广义表便成了              。‌
答案: 【 线性表】

19、填空题：
‍广义表的                 定义为广义表中括弧的重数。​
答案: 【 深度】

20、填空题：
‏广义表(a,(a,b),d,e,((i,j),k))的长度是 5 ，深度是 （       ） 。‎
答案: 【 3】

测试6 树和二叉树

1、单选题：
‌一个具有1025个结点的二叉树的高h为（  ）。​
选项：
A: 10
B: 11
C: 11至1025之间
D: 10至1024之间
答案: 【 11至1025之间】

2、单选题：
‏一棵完全二叉树上有1001个结点，其中叶子结点的个数是（   ）。‏‏‏
选项：
A: 250
B: 251
C: 254
D: 501
答案: 【 501】

3、单选题：
‌利用二叉链表存储树，则根结点的右指针是（    ）。‎‌‎
选项：
A: 指向最左孩子
B: 指向最右孩子
C: 空
D: 非空
答案: 【 空】

4、单选题：
​对于有n 个结点的二叉树, 其高度为（    ）。‍​‍
选项：
A: nlog2n
B:  log2n 
C:  ëlog2nû|+1  
D: 不确定
答案: 【 不确定】

5、单选题：
‍若对二叉树进行中序遍历，具有左、右子树的结点，其后继是该结点的（    ）。​‍​
选项：
A: 双亲结点
B: 其右子树中最左下角元素
C: 其右孩子
D: 其左子树中最右下角元素
答案: 【 其右子树中最左下角元素】

6、单选题：
‏已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为(     )。​‏​
选项：
A: -A+B*C/DE
B: -A+B*CD/E
C: -+*ABC/DE
D: -+A*BC/DE
答案: 【 -+A*BC/DE】

7、单选题：
​设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是(      )。‍​‍
选项：
A: m-n
B: m-n-1
C:  n+1
D: 条件不足，无法确定
答案: 【 m-n】

8、单选题：
‎在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（    ）。‏‎‏‎‏
选项：
A: 都不相同
B: 完全相同
C: 先序和中序相同，而与后序不同
D: 中序和后序相同，而与先序不同
答案: 【 完全相同】

9、多选题：
​有关二叉树下列说法不正确的是（       ）。‎​‎​‎
选项：
A: 二叉树的度为2
B: 一棵二叉树的度可以小于2
C: 二叉树中至少有一个结点的度为2 
D: 二叉树中任何一个结点的度都为2
答案: 【 二叉树的度为2;
二叉树中至少有一个结点的度为2 ;
二叉树中任何一个结点的度都为2】

10、多选题：
‎对一个二叉树的节点从1开始进行连续编号，要求每个节点的编号都要大于其左右孩子的编号，而且同一个节点的左孩子编号要小于右孩子编号，可采用那种遍历来进行编号是错误的。  （      ）‍‎‍‎‍
选项：
A: 先序
B: 中序
C: 后序
D: 层次
答案: 【 先序;
中序】

11、多选题：
​下面几个符号串编码集合中，哪些是前缀编码的是（      ）。‌​ ‌​‌
选项：
A: {0,10,110,1111}
B: {b,c,aa,ac,aba,abb,abc}
C: {00,010,0110,1000} 
D: {11,10,001,101,0001} 
答案: 【 {0,10,110,1111};
{b,c,aa,ac,aba,abb,abc};
{00,010,0110,1000} 】

12、判断题：
‎深度为K的二叉树中结点总数≤2k-1。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

13、判断题：
‎二叉树的遍历只是为了在应用中找到一种线性次序。​
选项：
A: 正确
B: 错误
答案: 【 正确】

14、判断题：
‏一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

15、判断题：
​哈夫曼树无左右子树之分。‎
选项：
A: 正确
B: 错误
答案: 【 错误】

16、填空题：
‍一个有2001个结点的完全二叉树的高度为         。‌
答案: 【 11】

17、填空题：
‍后序次序遍历树林正好等同于按           遍历对应的二叉树。‍‍‍
答案: 【 中序】

18、填空题：
​二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为                     。‍
答案: 【 E,A,C,B,D,G,F##%_YZPRLFH_%##EACBDGF】

19、填空题：
‍一个无序序列可以通过构造一棵                     树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。‌
答案: 【 二叉排序树】

20、填空题：
‌有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是6 ，带权路径长度WPL为           。​
答案: 【 261】

小测验：堆栈

1、单选题：
‏借助堆栈将中缀表达式A-(B-C/D)*E转换为后缀表达式，则该堆栈的大小至少为：‏‏‏
选项：
A: 2
B: 3
C: 4
D: 5
答案: 【 4】

2、单选题：
‌‍设1、2、…、n–1、n共n个数按顺序入栈，若第一个出栈的元素是n，则第三个出栈的元素是：‍‌‍
选项：
A: 3
B: n-2
C: n-3
D: 任何元素均可能
答案: 【 n-2】

3、单选题：
‏‌若用单向链表实现一个堆栈，当前链表状态为：1->2->3。当对该堆栈执行pop()、push(4)操作后，链表状态变成怎样？‌‏‌          （1）4->2->3    (2)  1->2->4‌‏‌
选项：
A: 只能是（1）
B: 只能是（2）
C: （1）和（2）都有可能
D: （1）和（2）都不可能
答案: 【 只能是（1）】

4、单选题：
‌如果一堆栈的输入序列是aAbBc，输出为 abcBA，那么该堆栈所进行的操作序列是什么？ 设P代表入栈，O代表出栈。‌‌‌
选项：
A: PPPOOPOPOO
B: POOPPPOPOO
C: POPPOPPOOO
D: PPOPPOOOPO
答案: 【 POPPOPPOOO】

小测验：线性表

1、单选题：
‌对于线性表，在顺序存储结构和链式存储结构中查找第k个元素，其时间复杂性分别是多少？‎
选项：
A: 都是O(1)
B: 都是O(k)
C: O(1)和O(k)
D: O(k)和O(1)
答案: 【 O(1)和O(k)】

2、单选题：
‌在顺序结构表示的线性表中，删除第i个元素（数组下标为i-1)，需要把后面的所有元素都往前挪一位，相应的语句是：‌‌‌for (___________ )‌‌            PtrL->Data[j-1]=PtrL->Data[j];  ‌‌‌其中空缺部分的内容应该是‌
选项：
A:  j = i; j< = PtrL->Last; j++
B:  j =PtrL->Last; j>= i;  j--
C:  j = i-1; j< = PtrL->Last; j++
D: j =PtrL->Last; j>= i-1;  j--
答案: 【  j = i; j< = PtrL->Last; j++】

3、判断题：
‎​下列函数试图求链式存储的线性表的表长，是否正确？&