大学MOOC 数据结构(新疆天山职业技术学院（本科）)1455559164 最新慕课完整章节测试答案

3月16日预习检测

1、单选题：
‎下列说法正确的是(    )。‌
选项：
A: A.数据是数据元素的基本单位
B: B.数据元素是数据项中不可分割的最小单位
C: C.数据可由若干个数据元素构成
D: D.数据项可由若千个数据元素构成
答案: 【 C.数据可由若干个数据元素构成】

2、单选题：
​数据元素是数据的基本单位，其内(   )数据项。‍
选项：
A: A.只能包括一个
B: B.不包含
C: C.可以包含多个
D: D.可以包含也可以不包含
答案: 【 C.可以包含多个】

3、单选题：
‏数据结构本质上是由(    )构成。‌
选项：
A: A、一个有限的数据元素集合及其上关系的有限集:
B: B、一个特定的数据元素集合及其上关系的有限集:
C: C、一个数据元素集合以及定义在该集合之上的一个关系的有限集:
D: D.个数据元素集合及其上关系的集合。
答案: 【 A、一个有限的数据元素集合及其上关系的有限集:】

4、单选题：
‌逻辑结构是(   )关系的整体。‎
选项：
A: A.数据元素之间逻辑
B: B.数据项之间逻辑
C: C.数据类型之间
D: D.存储结构之间
答案: 【 A.数据元素之间逻辑】

5、单选题：
‎一个存储结点存放一个 (   ）‍
选项：
A: A.数据项
B: B.数据元素
C: C.数据结构
D: D.数据类型
答案: 【 B.数据元素】

6、单选题：
​每个结点只存储一个数据元素，存储结点存放在连续的存储空间，该存储方是(  )存储方式。‎
选项：
A: A.顺序
B: B.链式
C: C.索引
D: D.散列
答案: 【 A.顺序】

7、单选题：
‌下列时间复杂度中最坏的是(   )。​
选项：
A: A.O(l)
B: B.O (m)
C: C.O (log2n)
D: D.O(n^2)
答案: 【 D.O(n^2)】

8、单选题：
​算法的便于阅读和理解的特性称为(  ).‍
选项：
A: A.正确性
B: B.易读性
C: C.健壮性
D: D.高效率
答案: 【 B.易读性】

9、单选题：
‎算法分析的目的是‎
选项：
A: A.辨别数据结构的合理性
B: B.评价算法的效率
C: C.研究算法中输入与输出的关系
D: D.鉴别算法的可读性
答案: 【 B.评价算法的效率】

10、单选题：
‍算法分析的两个主要方面是​
选项：
A: A.数据复杂性和程序复杂性
B: B.正确性和简明性
C: C.可读性和文档性
D: D.空间复杂性和时间复杂性
答案: 【 D.空间复杂性和时间复杂性】

小测验算法复杂度

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:
答案: 【 】

3月17日预习检测

1、单选题：
‎线性表的顺序存储结构是一种（ ）的存储结构‍
选项：
A: A 随机存取 
B: B 顺序存取 
C: C 索引存取 
D: D 散列存取
答案: 【 A 随机存取 】

2、单选题：
‍线性表采用链接存储时，其地址（ ）。‎
选项：
A: A 必须是连续的
B: B 部分地址必须是连续的
C: C 一定是不连续的
D: D 连续与否均可以
答案: 【 D 连续与否均可以】

3、单选题：
‎若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（ ）存储方法最节省时间。‏
选项：
A: A 顺序表 
B: B 单链表 
C: C 双链表 
D: D 单循环链表
答案: 【 A 顺序表 】

4、单选题：
‏一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（ ）。​
选项：
A: A 4321 
B: B 1234 
C: C 1432 
D: D 3241
答案: 【 B 1234 】

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

6、单选题：
‏如果结点A有3个兄弟，B是A的双亲，则结点B的度是（　　）。​
选项：
A: A 1 
B: B 2 
C: C 3 
D: D 4
答案: 【 D 4】

7、单选题：
​设二叉树有n个结点，则其深度为（ ）。‎
选项：
A: A 、n-1 
B: B、 n 
C: C、+1 
D: D、不能确定
答案: 【 D、不能确定】

8、单选题：
‏二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。‎
选项：
A: A 空或只有一个结点 
B: B 高度等于其结点数
C: C 任一结点无左孩子 
D: D 任一结点无右孩子
答案: 【 B 高度等于其结点数】

9、单选题：
‎线索二叉树中某结点R没有左孩子的充要条件是（ 　　）。‏
选项：
A: A R.lchild=NULL 
B: B R.ltag=0 
C: C R.ltag=1 
D: D R.rchild=NULL
答案: 【 C R.ltag=1 】

10、单选题：
​队列的操作原理是（    ）。‎
选项：
A: A、先进先出
B: B、先进后出        
C: C、后进先出 
D: D、以上都不对
答案: 【 A、先进先出】

小测验堆栈

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、判断题：
‏​下列函数试图求链式存储的线性表的表长，是否正确？​int  Length ( List  *PtrL )​‏​{    List  *p = PtrL;      ​‏​     int  j = 0;​‏​     while ( p ) { ​‏​           p++; ​‏​           j++;                 ​‏​     }   ​‏​     return  j;​‏​}​‏​
选项：
A: 正确
B: 错误
答案: 【 错误】

小测验队列

1、单选题：
‌在一个链表表示的队列中， f和r分别指向队列的头和尾。下列哪个操作能正确地将s结点插入到队列中：  ‏
选项：
A: f->next=s; f=s;
B: r->next=s; r=s;
C: s->next=r; r=s;
D: s->next=f; f=s;
答案: 【 r->next=s; r=s;】

2、单选题：
‏现采用大小为10的数组实现一个循环队列。设在某一时刻，队列为空且此时front和rear值均为5。经过若干操作后，front为8，rear为2，问：此时队列中有多少个元素？ ‍‏‍
选项：
A: 4
B: 5
C: 6
D: 7
答案: 【 4】

小测验二叉树性质

1、单选题：
‎如果一个完全二叉树最底下一层为第六层（根为第一层）且该层共有8个叶结点，那么该完全二叉树共有多少个结点？‍
选项：
A: 31
B: 39
C: 63
D: 71
答案: 【 39】

2、单选题：
​‏若有一二叉树的总结点数为98，只有一个儿子的结点数为48，则该树的叶结点数是多少？‏​‏
选项：
A: 25
B: 50
C: 不确定
D: 这样的树不存在
答案: 【 这样的树不存在】

3、判断题：
‍设深度为d（只有一个根结点时，d为1）的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为2d-1‏
选项：
A: 正确
B: 错误
答案: 【 正确】

小测验树的表示

1、单选题：
‏在分量1~11的数组中按从小到大顺序存放11个元素，如果用顺序查找和二分查找分别查找这11个元素，哪个位置的元素在这两种方法的查找中总次数最少？‌‏‌
选项：
A: 1
B: 2
C: 3
D: 6
答案: 【 1】

2、单选题：
‏在分量1~11的数组中按从小到大顺序存放11个元素，如果进行二分查找，查找次数最少的元素位于什么位置？​‏​
选项：
A: 1
B: 5
C: 6
D: 11
答案: 【 6】

3、单选题：
‏‌一棵度为 m的树有n个节点。若每个节点直接用m个链指向相应的儿子，则表示这个树所需要的总空间是n*(m+1) (假定每个链以及表示节点的数据域都是一个单位空间).。当采用儿子/兄弟（First Child/Next Sibling）表示法时，所需的总空间是：‌‏‌
选项：
A: 3n
B: 2n
C: n*m
D: n*(m-1)
答案: 【