大学MOOC 数据结构(邵阳学院)1455986162 最新慕课完整章节测试答案

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】

第三章栈和队列单元测验

1、单选题：

‍一个栈的入栈序列为1,2,3,…,n，其出栈序列是。若，则可能取值的个数是（        ）。

​选项：
A: n-3
B: n-2
C: n-1
D: n
E:

F: n(n-1)
G:
答案: 【 n-1】

2、单选题：
‌循环队列 Q 采用数组空间 Q.base[0,n-1] 存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列中的元素个数是（    ）。‎
选项：
A: rear-front
B: rear-front+1
C: rear-front+n
D: (rear-front+n)%n
E: rear-front-1
F: (rear-front)%n
答案: 【 (rear-front+n)%n】

3、单选题：
‍已知操作符包括 “+”，“-”，“/”，“(” 和 “)”。将中缀表达式 a+b-a*((c+d)/e-f)+g 转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是(        )。‎
选项：
A: 5
B: 7
C: 8
D: 11
答案: 【 5】

4、单选题：
‎在宾馆的客房管理中，为了保证每间客房硬件设施的磨损率尽可能均等，可以利用（    ）这种数据结构来管理空闲的客房，以使得每间客房的使用率尽可能均等。‍
选项：
A: 线性表
B: 栈
C: 队列
D: 双端队列
E: 双栈
F: 超栈
G: 超队列
答案: 【 队列】

5、单选题：
‏下列链表中最不适合用作链栈的是（        ）。‎
选项：
A: 只有表头指针没有表尾指针的双向循环链表。
B: 只有表尾指针没有表头指针的双向循环链表。
C: 只有表尾指针没有表头指针的单循环链表。
D: 只有表头指针没有表尾指针的单循环链表。
E: 同时设有表头指针和表尾指针的单链表。
答案: 【 只有表头指针没有表尾指针的单循环链表。】

6、单选题：
‏以下方法中，（        ）不能区分循环队列的满与空。​
选项：
A: 牺牲一个存储单元
B: 设置一个标志变量
C: 判断头尾指针相等
D: 使用一个计数器
答案: 【 判断头尾指针相等】

7、多选题：
‍下列关于栈的叙述中，错误的是（        ）。​‍​
选项：
A: 采用非递归方式重写递归程序是必须使用栈。
B: 函数调用时，系统要用栈保存必要的信息。
C: 只要确定了入栈次序，即可确定出栈次序。
D: 栈是一种受限的线性表，允许在其两端进行操作。
E: 消除递归不一定需要使用栈。
F: 进栈和出栈操作的算法时间复杂度均为 O(n)。
G: 两个栈共享一片连续的内存空间时，为了提高内存利用率、减少溢出，应当把两个栈的栈底分别设置在整篇内存空间的两端。
答案: 【 采用非递归方式重写递归程序是必须使用栈。;
只要确定了入栈次序，即可确定出栈次序。;
栈是一种受限的线性表，允许在其两端进行操作。;
进栈和出栈操作的算法时间复杂度均为 O(n)。】

8、多选题：
‍下列关于循环队列的叙述中，正确的是（        ）。‎
选项：
A: 循环队列不会产生假溢出。
B: 循环队列也存在空间溢出问题。
C: 循环队列比非循环队列节省空间。
D: 循环队列一定优于非循环队列。
E: 循环队列入队操作的复杂度比非循环队列高。
F: 循环队列是一种顺序存储的线性结构。
答案: 【 循环队列不会产生假溢出。;
循环队列也存在空间溢出问题。;
循环队列是一种顺序存储的线性结构。】

9、多选题：
‍银行柜台有2个服务窗口，客户可以在其中任意一个窗口排队办理业务，一旦开始排队，就不能够再进入到另一个队列中。客户x的业务办理完成后，银行系统会在今日流水记录的尾部新增一条流水记录 x。已知在某日银行开门营业后，依次有 a,b,c,d,e,f,g 共7位客户前来办理业务，且每人只办理一次。以下四个流水记录中，一定错误的是（        ）。‍
选项：
A: abcdefg
B: abdcfeg
C: abfcgde
D: gfedcba
E: adcbgef
F: afbgcde
G: dacbegf
H: eabdfcg
答案: 【 gfedcba;
adcbgef;
dacbegf;
eabdfcg】

5.1数组的定义及顺序存储

1、单选题：

‍如果一个二维数组 A[1..m, 1..n] 按行优先顺序存储，设 的相对地址为 0，则任一元素 A[i,j] 的相对地址为（    ）。

​选项：
A: i+j
B: i*n+j
C: (i-1)*n+j
D: (i-1)*n+j-1
答案: 【 (i-1)*n+j-1】

2、单选题：
‏如果一个二维数组 A[4][6] 按列优先顺序存储（数组下标从0开始），每个元素占一个存储单元，数组首地址为100，则元素 a[1,4] 的地址为（    ）。‍
选项：
A: 125
B: 120
C: 117
D: 113
答案: 【 117】

3、单选题：

‍数组 A 三维的长度分别为 ，每个数组元素占一个存储单元，LOC(0,0,0) 为基址。若以行序为主序，则元素 A[i][j][k] 的地址为（    ）（其中，）。

‌选项：
A:
B:
C:
D:
答案: 【 】

4、判断题：
‌二维数组是一种非线性结构。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

5.2矩阵的压缩存储一——特殊矩阵

1、单选题：
‎在 n*n 对称矩阵的压缩存储中，需要保存的元素个数是（    ）。​
选项：
A: n(n+1)/2
B: n(n-1)/2
C:
D: 不确定
答案: 【 n(n+1)/2】

2、单选题：

‎将一个三对角矩阵 按列优先顺序存储到一维数组 B 中，则 B 的长度至少为（    ）。

‏选项：
A: 3n-2
B: 3n-1
C: 3n
D: 3n+1
答案: 【 3n-2】

3、单选题：
‏对一些特殊矩阵采用压缩存储的目的主要是为（    ）。‎
选项：
A: 表达变得简单
B: 减少不必要的存储空间的开销
C: 去掉矩阵中的多余元素
D: 对矩阵元素的存取变得简单
答案: 【 减少不必要的存储空间的开销】

5.2矩阵的压缩存储二——三元组顺序表

1、单选题：
‌设已知一个稀疏矩阵的三元组顺序表为：((1,2,3)，(1,6,1)，(3,1,5)，(3,2,-1)，(4,5,4)，(5,1,-3))，则其转置矩阵的三元组表中的第 3 个三元组为（    ）。​
选项：
A: (2,1,3)
B: (3,1,5)
C: (3,2,-1)
D: (2,3,-1)
答案: 【 (2,1,3)】

2、判断题：
‌若采用三元组顺序表来压缩存储稀疏矩阵，只要把每个三元组的行下标和列下标互换，就完成了对该矩阵的转置运算。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

3、判断题：
‌稀疏矩阵压缩存储之后，就失去了随机存取的特性。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

5.3广义表

1、单选题：
‍广义表 E = (e, a, E) 的长度为（    ）。‏
选项：
A: 2
B: 3
C: 5
D: 无穷大
答案: 【 3】

2、单选题：
‌广义表 (a,(a,b),d,e,((i,j),k)) 的长度和深度分别为（    ）。​
选项：
A: 6和4
B: 8和4
C: 5和3
D: 5和2
答案: 【 5和3】

3、单选题：
​广义表操作 GetTail(GetHead(GetTail(((e,f),(g,h))))) 得到的结果是（    ）。‌
选项：
A: ()
B: h
C: (h)
D: (g,h)
答案: 【 (h)】

4、单选题：
‎广义表的存储结构应采用（    ）。‍
选项：
A: 顺序存储
B: 链式存储
C: 十字链表存储
D: 循环链表存储
答案: 【 链式存储】

第四章数组和广义表单元测验

1、单选题：

‏有一个 100 阶的三对角矩阵 M，其元素 （1≤i≤100，1≤j≤100）按行优先次序压缩存入下标从0开始的一维数组 N 中。 元素  在 N 中的下标是（        ）。

‎选项：
A: 86
B: 87
C: 88
D: 89
E: 85
F: 90
答案: 【 87】

2、单选题：
​4 行 5 列的二维数组 M （数组下标从 0 开始），M 按行优先顺序存储时元素 M[2][4] 的起始地址与 M 按列优先顺序存储时元素（        ）的起始地址相同。‍
选项：
A: M[1][3]
B: M[2][3]
C: M[2][4]
D: M[3][3]
E: M[3][2]
F: M[3][1]
G: M[4][2]
答案: 【 M[2][3]】

3、单选题：
‎对广义表 E = ((a, ((b), c)), e, E) 实施由取表头 GetHead 和取表尾 GetTail 组成的操作序列（        ）得到的结果是 c 。‏
选项：
A: GetHead(GetTail(GetHead(GetTail(GetHead(E)))))
B: GetHead(GetTail(GetTail(E)))
C: GetHead(GetHead(GetTail(GetHead(GetHead(GetTail(GetHead(GetHead(E))))))))
D: GetHead(GetTail(GetHead(E)))
E: GetHead(GetTail(GetHead(GetTail(E))))
答案: 【 GetHead(GetTail(GetHead(GetTail(GetHead(E)))))】

4、单选题：
​若广义表满足 GetHead(A)=GetTail(A)，则 A 为（        ）。‏
选项：
A: ( )
B: (( ))
C: (( ),( ))
D: (( ),( ),( ))
E: ((( )))
答案: 【 (( ))】

5、单选题：
​设采用一维数组来存放一个 m 行 n 列的对称矩阵，且只存放矩阵的下三角阵。当需要访问上三角阵第 i 行，第 j 列的元素（j>i）， 其数组下标是（        ）。‎​（说明：i、j及一维数组下标均从0开始）‎
选项：
A:
B:
C:
D:
E:
F:
G:
答案: 【 】

6、单选题：
‎数组 A[4][5][6][7] 的每个元素占4个字节，将其按列优先次序存储在起始地址为 300（即 LOC(A[0][0][0][0]) = 300）的内存单元中，则元素 A[1][3][5][2] 的地址为（        ）。​
选项：
A: 1712
B: 653
C: 508
D: 1132
E: 1792
F: 673
答案: 【 1712】

7、单选题：
‍设广义表 A = (a,(((b,c),(d,e)),f),g)，Head(p) 为求广义表 p 的表头的函数，Tail(p)为求广义表 p 的表尾的函数，那么从表 A 中取出子表 (b,c) 的操作为（        ）。‏
选项：
A: Head(Head(Head(Tail(A))))
B: Tail(Head(Head(Head(A))))
C: Head(Head(Head(Head(Tail(A)))))
D: Tail(Head(Head(Head(Head(A)))))
E: Head(Head(Head(Head(Head(Head(Tail(A)))))))
F: Tail(Head(Head(Head(Head(Head(Head(A)))))))
答案: 【 Head(Head(Head(Tail(A))))】

8、单选题：

​对于五对角矩阵 ，已按行压缩存储到一维数组 B 中，则 B 的长度至少是（        ）。

‏选项：
A: 5n
B: 5n-2
C: 5n-4
D: 5n-6
E: 5n-8
答案: 【 5n-6】

9、多选题：
‌下列关于广义表的叙述中，正确的是（        ）。​
选项：
A: 广义表可以是一个多层次的结构、
B: 广义表至少有一个元素。
C: 广义表可以被其他广义表所共享。
D: 广义表不能是递归表。
E: 广义表的长度总是有限的。
F: 广义表必须至少有一个元素是子表。
G: 广义表不可以是自身的子表。
H: 广义表的深度总是有限的。
答案: 【 广义表可以是一个多层次的结构、;
广义表可以被其他广义表所共享。;
广义表的长度总是有限的。】

10、多选题：
‏适用于压缩存储稀疏矩阵的两种存储结构是（        ）和（        ）。​
选项：
A: 十字链表
B: 三元组表
C: 双向链表
D: 邻接矩阵
答案: 【 十字链表;
三元组表】

6.1树的定义

1、单选题：
‍在一棵度为 3 的树上，度为 3 的结点数为 3 个，度为 2 的结点数为 2 个，度为 1 的结点数为 2 个，则度为 0 的结点数为（    ）个。​
选项：
A: 不确定
B: 8
C: 9
D: 10
答案: 【 9】

2、单选题：
‎树最适合用来表示（    ）。‎
选项：
A: 有序数据元素
B: 无序数据元素
C: 元素之间具有分支层次关系的数据
D: 元素之间无联系的数据
答案: 【 元素之间具有分支层次关系的数据】

3、单选题：
‌假设一棵树的嵌套括号表示为 (a(b(e),c(f(h,i,j),g),d))，则该树上终端结点的个数为（    ）。‏
选项：
A: 4
B: 5
C: 6
D: 7
答案: 【 6】

4、单选题：
‍一棵含有 n 个结点的 m (m>=3) 叉树，其分支数为（    ）。​
选项：
A: mn
B: n+m
C: n-1
D: 无法确定
答案: 【 n-1】

6.2二叉树一——定义和性质

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

2、单选题：
‎深度为6（根的层次为1）的二叉树至多有(   )个结点。‍
选项：
A: 62
B: 63
C: 64
D: 65
答案: 【 63】

3、单选题：
‏设高度为 h 的二叉树中只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点上下限分别为（    ）。 ‌
选项：
A:
B:
C:
D:
答案: 【 】

4、多选题：

‌在一棵含有 n 个结点的二叉树中，若度为 2 的结点数为 ，度为 1 的结点数为 ，度为 0 的结点数为 ，则该树的最大高度为（    ）。

‏选项：
A: n
B:

C:
D:
答案: 【 n;

】

5、填空题：
‎4个结点的二叉树可以有             种不同的形态。‍
答案: 【 14】

6.2二叉树二——存储结构

1、单选题：
​假设二叉树的顺序存储结构如下图所示：‎1‎2‎3‎4‎5‎6‎7‎8‎9‎10‎11‎12‎13‎14‎a‎b‎c‎Æ‎d‎Æ‎e‎Æ‎Æ‎f‎g‎Æ‎Æ‎h‎​则该二叉树的中序遍历序列为（    ）。‎
选项：
A: fdgbache
B: bfdgache
C: bfdgahec
D: fdgbahec
答案: 【 bfdgache】

2、单选题：
‎含有 n 个结点的二叉树采用顺序存储结构，至少需要分配（    ）个存储单元。‌
选项：
A: n
B: 2n
C:
D:
答案: 【 】

3、单选题：
‎含有 n 个结点的二叉树，若采用二叉链表存储，则整个存储结构中只有（    ）个非空指针域。‌
选项：
A: n-1
B: n
C: n+1
D: 不确定
答案: 【 n-1】

4、单选题：
‎含有 n 个结点的二叉树，若采用三叉链表存储，则整个存储结构中有（    ）个空的指针域。​
选项：
A: n-1
B: n
C: n+1
D: n+2
答案: 【 n+2】

6.3二叉树的遍历一——递归算法

1、单选题：
‌任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序（    ）。‎
选项：
A: 不发生变化
B: 发生变化
C: 不能确定
D: 以上都不对
答案: 【 不发生变化】

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

3、单选题：
‏在一非空二叉树的中序遍历序列中，根结点的右边（    ）。​
选项：
A: 只有右子树上的所有结点
B: 只有右子树上的部分结点
C: 只有左子树上的部分结点
D: 只有左子树上的所有结点
答案: 【 只有右子树上的所有结点】

6.3二叉树的遍历三——应用

1、单选题：
​设一棵二叉树的中序遍历序列为 BDCAE，后序遍历序列为 DBEAC，则这棵二叉树的前序遍历序列为（    ）。​
选项：
A: CAEBD
B: CDBEA
C: CBDAE
D: CBDEA
答案: 【 CBDAE】

2、单选题：
‎设一棵二叉树的先序遍历序列为 ABCDEFG，中后序遍历序列为 BDCEAGF，则这棵二叉树的后序遍历序列为（    ）。‎
选项：
A: CABDEFG
B: DACEFBG
C: DECBGFA
D: ADCFEG
答案: 【 DECBGFA】

3、单选题：

​设一棵二叉树的扩展后序遍历序列为 ，则这棵二叉树的前序和中序遍历序列分别为（    ）。

‌选项：
A: ABCDEFG 和 DECBGFA
B: ABCDEFG 和 BDCEAG
C: AFGBDEC和 CBEDAFG
D: ABCDEFG 和 CBEDAFG
答案: 【 ABCDEFG 和 CBEDAFG】

6.3二叉树的遍历二——非递归算法

1、单选题：
‏欲实现二叉树的非递归后序遍历算法而不必使用栈结构，则二叉树应采用（    ）存储结构。‏
选项：
A: 二叉链表
B: 三叉链表
C: 顺序
D: 广义表
答案: 【 三叉链表】

2、单选题：
​非递归中序遍历（空指针进栈）含有 n 个结点高度为 h 的二叉树时，为了确保栈在处理过程中不会发生上溢，则该栈至少要有（    ）个存储单元。̴