1、数据结构与算法练习试卷 1-1 及答案解析(总分：58.00，做题时间：90 分钟)一、选择题(总题数：28，分数：58.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。_下列各题基于下面的叙述：某二叉树节点的对称序序列为 A、B、C、D、E、P、G，后序序列为B、D、C、A、F、G、E。（分数：6.00）(1).该二叉树节点的先序序列为 _。（分数：2.00）A.E、G、F、A、C、D、BB.E、A、C、B、D、G、FC.E、A、G、C、F、B、DD.E、G、A、C、D、F、B(2).该二叉树对应的树林包括多少棵树? _。（
2、分数：2.00）A.1B.2C.3D.4(3).该二叉树对应的树林节点的层次次序序列为 _。（分数：2.00）A.E、G、F、A、C、D、BB.E、A、C、B、D、G、FC.E、A、G、C、F、B、DD.E、G、A、C、D、F、B2.有 6 个元素 6，5，4，3，2，1 顺序进栈，问下列哪一个不是合法的出栈序列 _。（分数：2.00）A.5，4，3，6，1，2B.4，5，3，2，1，6C.3，4，6，5，2，1D.2，3，4，1，5，63.下面关于串的叙述中，哪一个是不正确的? _。（分数：2.00）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用
3、顺序存储，也可以采用链式存储4.下列排序方法中，哪一个是稳定的排序方法? _。（分数：2.00）A.直接选择排序B.二分法插入排序C.希尔排序D.快速排序5.下面关于 B 和 B+树的叙述中，不正确的是 _。（分数：2.00）A.B 树和 B+树都是平衡的多分树B.B 树和 B+树都可用于文件的索引结构C.B 树和 B+树都能有效地支持顺序检索D.B 树和 B+树都能有效地支持随机检索6.下面关于线性表的叙述中，错误的是 _。（分数：2.00）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链接存储，不必占用一片连续的存储单元D.线
4、性表采用链接存储，便于插入和删除操作7.用直接插入排序方法对下面四个序列进行排序(由小到大)，元素比较次数最少的是 _。（分数：2.00）A.94、32、40、90、80、46、21、69B.32、40、21、46、69、94、90、80C.21、32、46、40、80、69、90、94D.90、69、80、46、21、32、94、408.设森林 F 中有三棵树，第一、第二和第三棵树的节点个数分别为 M1、M2 和 M3。与森林 F 对应的二叉树根节点的右子树上的节点个数是 _。（分数：2.00）A.M1B.M1+M2C.M3D.M2+M39.对下列关键字序列用快速排序法进行排序时，速度最快的
5、是 _。（分数：2.00）A.21、25、5、17、9、23、30B.25、23、30、17、21、5、9C.21、9、17、30、25、23、5D.5、9、17、21、23、25、3010.在完全二叉树中，若一个节点是叶节点，则它没 _。（分数：2.00）A.左子节点B.右子节点C.左子节点和右子节点D.左子节点、右子节点和兄弟节点11.在下列存储形式中，哪一个不是树的存储形式 _。（分数：2.00）A.双亲表示法B.孩子链表表示法C.孩子兄弟示法D.顺序存储表示法12.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的方法是 _。（分数：2.00）A.分块法B.顺序法C.
6、二分法D.散列法13.在二叉树节点的先序序列、中序序列和后序序列中，所有叶子节点的先后顺序 _。（分数：2.00）A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同14.设栈 S 和队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5 和 e6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出队的顺序是 e2、e4、e3、e6、e5、e1，则栈 S 的容量至少应该是 _。（分数：2.00）A.6B.4C.3D.215.设有一个己按各元素的值排好序的线性表，长度大于 2，对给定的值 k，分别用顺序查找法和二分查找法查找一个与 k 相等的
7、元素，比较的次数分别为 s 和 b，在查找不成功的情况下，正确的 s 和 b 的数量关系是 _。（分数：2.00）A.总有 s=bB.总有 sbC.总有 sbD.与 k 值大小有关16.对下列四种排序方法，在排序过程中关键码比较次数与记录的初始排列无关的方法是 _。（分数：2.00）A.直接插入排序B.二分法插入排序C.快速排序D.归并排序17.对下列四个序列用快速排序方法进行排序，以序列的第一个元素为划分的基准。在第一趟划分过程中，元素移动次数最多的是哪个序列? _。（分数：2.00）A.70，75，82，90，23，16，10，68B.70，75，68，23，10，16，90，82C.82
8、，75，70，16，10，90，68，23D.23，10，16，70，82，75，68，9018.对树中的一个节点 x，在先根序列中的序号为 pre(x)，在后根序列中的序号为 post(x)。若树中节点x 是节点 y 的祖先，下列四个条件哪个条件正确? _。（分数：2.00）A.pre(x)pre(y)和 post(x)post(y)B.pre(x)pre(y)和 post(x)post(y)C.pre(x)pre(y)和 post(x)post(y)D.pre(x)pre(y)和 post(x)post(y)19.有关二叉树的下列说法正确的是 _。（分数：2.00）A.二叉树的度为 2B.
9、一棵二叉树的度可以小于 2C.二叉树中任何一个节点的度都为 2D.任何一棵二叉树中至少有一个节点的度为 220.若进栈序列为 1，2，3，4，假定进栈和出栈可以穿插进行，则可能的出栈序列是 _。（分数：2.00）A.2，4，1，3B.3，1，4，2C.3，4，1，2D.1，2，3，421.有一棵非空二叉树(第 0 层为根节点)，其第 i 层上至多有多少个节点? _。（分数：2.00）A.2 iB.2 i-1C.2 i+1D.i22.某二叉树的先序遍历节点访问顺序是 ABCDEFG，中序遍历的节点访问顺序是 CBDAFGE，则其后序遍历的节点访问顺序是 _。（分数：2.00）A.CDBGFEAB
10、.CDGFEABC.CDBAGFED.CDBFAGE23.下面关于数据结构的叙述中，正确的叙述是 _。（分数：2.00）A.顺序存储方式的优点是存储密度大，且插入、删除运算效率高B.链表中的每一个节点都恰好包含一个指针C.包含 n 个节点的二叉排序树的最大检索长度为 log 2 nD.将一棵树转换为二叉树后，根节点没有右子树24.为了有效地利用散列查找技术，需要解决的问题是 _。 找一个好的散列函数 设计有效的解决冲突的方法 用整数表示关键码值（分数：2.00）A.和B.和C.和D.、和25.用链表表示线性表的优点是 _。（分数：2.00）A.便于随机存取B.便于插入和删除操作C.花费的存储空
11、间较顺序存储少D.元素的物理顺序与逻辑顺序相同26.数组 Q0.n-1作为一个环形队列，f 为当前队头元素的前一位置，r 为队尾元素的位置，则队列中元素个数的计算公式是 _。（分数：2.00）A.r-fB.n+f-rC.n+r-fD.(n+r-f)mod n27.若待排序序列已基本有序，要使它完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是 _。（分数：2.00）A.归并排序B.直接插入排序C.直接选择排序D.快速排序数据结构与算法练习试卷 1-1 答案解析(总分：58.00，做题时间：90 分钟)一、选择题(总题数：28，分数：58.00)1.选择题（）下列各题 A、B、C、D
12、 四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。_解析：下列各题基于下面的叙述：某二叉树节点的对称序序列为 A、B、C、D、E、P、G，后序序列为B、D、C、A、F、G、E。（分数：6.00）(1).该二叉树节点的先序序列为 _。（分数：2.00）A.E、G、F、A、C、D、BB.E、A、C、B、D、G、F C.E、A、G、C、F、B、DD.E、G、A、C、D、F、B解析：(2).该二叉树对应的树林包括多少棵树? _。（分数：2.00）A.1B.2 C.3D.4解析：(3).该二叉树对应的树林节点的层次次序序列为 _。（分数：2.00）A.E、G、F、A、C、D、BB.
13、E、A、C、B、D、G、FC.E、A、G、C、F、B、D D.E、G、A、C、D、F、B解析：2.有 6 个元素 6，5，4，3，2，1 顺序进栈，问下列哪一个不是合法的出栈序列 _。（分数：2.00）A.5，4，3，6，1，2 B.4，5，3，2，1，6C.3，4，6，5，2，1D.2，3，4，1，5，6解析：3.下面关于串的叙述中，哪一个是不正确的? _。（分数：2.00）A.串是字符的有限序列B.空串是由空格构成的串 C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储解析：4.下列排序方法中，哪一个是稳定的排序方法? _。（分数：2.00）A.直接选择排序B.二分
14、法插入排序 C.希尔排序D.快速排序解析：5.下面关于 B 和 B+树的叙述中，不正确的是 _。（分数：2.00）A.B 树和 B+树都是平衡的多分树B.B 树和 B+树都可用于文件的索引结构C.B 树和 B+树都能有效地支持顺序检索 D.B 树和 B+树都能有效地支持随机检索解析：6.下面关于线性表的叙述中，错误的是 _。（分数：2.00）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作 C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于插入和删除操作解析：7.用直接插入排序方法对下面四个序列进行排序(由小到大)，元
15、素比较次数最少的是 _。（分数：2.00）A.94、32、40、90、80、46、21、69B.32、40、21、46、69、94、90、80C.21、32、46、40、80、69、90、94 D.90、69、80、46、21、32、94、40解析：8.设森林 F 中有三棵树，第一、第二和第三棵树的节点个数分别为 M1、M2 和 M3。与森林 F 对应的二叉树根节点的右子树上的节点个数是 _。（分数：2.00）A.M1B.M1+M2C.M3D.M2+M3 解析：9.对下列关键字序列用快速排序法进行排序时，速度最快的是 _。（分数：2.00）A.21、25、5、17、9、23、30 B.25、2
16、3、30、17、21、5、9C.21、9、17、30、25、23、5D.5、9、17、21、23、25、30解析：10.在完全二叉树中，若一个节点是叶节点，则它没 _。（分数：2.00）A.左子节点B.右子节点C.左子节点和右子节点 D.左子节点、右子节点和兄弟节点解析：11.在下列存储形式中，哪一个不是树的存储形式 _。（分数：2.00）A.双亲表示法B.孩子链表表示法C.孩子兄弟示法D.顺序存储表示法 解析：12.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的方法是 _。（分数：2.00）A.分块法 B.顺序法C.二分法D.散列法解析：13.在二叉树节点的先序序列、中
17、序序列和后序序列中，所有叶子节点的先后顺序 _。（分数：2.00）A.都不相同B.完全相同 C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同解析：14.设栈 S 和队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5 和 e6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出队的顺序是 e2、e4、e3、e6、e5、e1，则栈 S 的容量至少应该是 _。（分数：2.00）A.6B.4C.3 D.2解析：15.设有一个己按各元素的值排好序的线性表，长度大于 2，对给定的值 k，分别用顺序查找法和二分查找法查找一个与 k 相等的元素，比较的次数分别为 s 和
18、b，在查找不成功的情况下，正确的 s 和 b 的数量关系是 _。（分数：2.00）A.总有 s=bB.总有 sbC.总有 sbD.与 k 值大小有关 解析：16.对下列四种排序方法，在排序过程中关键码比较次数与记录的初始排列无关的方法是 _。（分数：2.00）A.直接插入排序B.二分法插入排序C.快速排序D.归并排序 解析：17.对下列四个序列用快速排序方法进行排序，以序列的第一个元素为划分的基准。在第一趟划分过程中，元素移动次数最多的是哪个序列? _。（分数：2.00）A.70，75，82，90，23，16，10，68 B.70，75，68，23，10，16，90，82C.82，75，70，
19、16，10，90，68，23D.23，10，16，70，82，75，68，90解析：18.对树中的一个节点 x，在先根序列中的序号为 pre(x)，在后根序列中的序号为 post(x)。若树中节点x 是节点 y 的祖先，下列四个条件哪个条件正确? _。（分数：2.00）A.pre(x)pre(y)和 post(x)post(y)B.pre(x)pre(y)和 post(x)post(y) C.pre(x)pre(y)和 post(x)post(y)D.pre(x)pre(y)和 post(x)post(y)解析：19.有关二叉树的下列说法正确的是 _。（分数：2.00）A.二叉树的度为 2B.
20、一棵二叉树的度可以小于 2 C.二叉树中任何一个节点的度都为 2D.任何一棵二叉树中至少有一个节点的度为 2解析：20.若进栈序列为 1，2，3，4，假定进栈和出栈可以穿插进行，则可能的出栈序列是 _。（分数：2.00）A.2，4，1，3B.3，1，4，2C.3，4，1，2D.1，2，3，4 解析：21.有一棵非空二叉树(第 0 层为根节点)，其第 i 层上至多有多少个节点? _。（分数：2.00）A.2 i B.2 i-1C.2 i+1D.i解析：22.某二叉树的先序遍历节点访问顺序是 ABCDEFG，中序遍历的节点访问顺序是 CBDAFGE，则其后序遍历的节点访问顺序是 _。（分数：2.0
21、0）A.CDBGFEA B.CDGFEABC.CDBAGFED.CDBFAGE解析：23.下面关于数据结构的叙述中，正确的叙述是 _。（分数：2.00）A.顺序存储方式的优点是存储密度大，且插入、删除运算效率高B.链表中的每一个节点都恰好包含一个指针C.包含 n 个节点的二叉排序树的最大检索长度为 log 2 nD.将一棵树转换为二叉树后，根节点没有右子树 解析：24.为了有效地利用散列查找技术，需要解决的问题是 _。 找一个好的散列函数 设计有效的解决冲突的方法 用整数表示关键码值（分数：2.00）A.和B.和 C.和D.、和解析：25.用链表表示线性表的优点是 _。（分数：2.00）A.便于随机存取B.便于插入和删除操作 C.花费的存储空间较顺序存储少D.元素的物理顺序与逻辑顺序相同解析：26.数组 Q0.n-1作为一个环形队列，f 为当前队头元素的前一位置，r 为队尾元素的位置，则队列中元素个数的计算公式是 _。（分数：2.00）A.r-fB.n+f-rC.n+r-fD.(n+r-f)mod n 解析：27.若待排序序列已基本有序，要使它完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是 _。（分数：2.00）A.归并排序B.直接插入排序 C.直接选择排序D.快速排序解析：
