东师《数据结构》2012秋第一次在线作业(随机)第1份

2012秋第一次在线作业
试卷总分：100
单选题
判断题
一、单选题（共 20 道试题，共 60 分。）
V
1. 下面关于算法说法错误的是（）。
A. 算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
此题选: D 满分：3 分
2. 一个栈的入栈序列是a、b、c、d，则栈的不可能的输出序列是 ( )。
A. acbd
B. abcd
C. dbca
D. adcb
满分：3 分
3. 串是一种特殊的线性表，其特殊性体现在 ( )。
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链接存储
D. 数据元素可以是多个字符
满分：3 分
4. 一个算法应该是（）。
A. 程序
B. 问题求解步骤的描述
C. 要满足五个基本特性
D. A和C
满分：3 分
5. 某二叉树结点的前序序列为ECBAD，中序序列为EBCDA，则该二叉树结点的后序序列为 ( )。
A. ABCED
B. DECAB
C. DEABC
D. BDACE
此题选: D 满分：3 分
6. 每一个(存储)结点不仅含有一个数据元素，还包含一组指针，该存储方式是 ( )。
A. 顺序存储
B. 链接存储
C. 索引存储
D. 散列存储
满分：3 分
7. 设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为 ( )。
A. 求子串
B. 求串长
C. 联接
D. 模式匹配
此题选: D 满分：3 分
8. 若X是中序线索二叉树中一个有左子女的结点，且X不为根，则X的中序前驱为 ( )。
A. X的双亲
B. X的右子树中最左下的结点
C. X的左子树中最右下的结点
D. X的左子树中最右下的叶结点
满分：3 分
9. 一个顺序栈一旦被说明，其占用空间的大小 ( )。
A. 可以改变
B. 不能固定
C. 已固定
D. 动态变化
满分：3 分
10. 在k叉树中，度为0的结点称为 ( )。
A. 根
B. 叶
C. 祖先
D. 子孙
满分：3 分
11. 将一棵有100个结点的完全二叉树从上到下、从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右子女编号为 ( )。
A. 48
B. 50
C. 98
D. 99
此题选: D 满分：3 分
12. 设二叉树有n个结点且根结点的层数为0，则二叉树的高度为 ( )。
A. n-1
B. élog2(n+1)ù -1
C. ëlog2nû
D. 不确定
此题选: D 满分：3 分
13. 设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是 ( )。
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无左子女
D. 任一结点无右子女
满分：3 分
14. 设根结点的层数为0，若高度为h的二叉树上只有度为0和度为2的结点，则此二叉树上所包含的结点数至少为 ( )。
A. h+1
B. 2h-1
C. 2h
D. 2h+1
此题选: D 满分：3 分
15. head指向的带表头结点的单链表为空的判定条件是 ( )。
A. head = = NULL
B. head- next = = head
C. head ! = NULL
D. head- next = = NULL
此题选: D 满分：3 分
16. 顺序存储结构的优点是( )。
A. 存储密度大
B. 插入运算方便
C. 删除运算方便
D. 结构可动态变化
满分：3 分
17. 经过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,a); push(ST,b); pop(ST,x);
A. a
B. b
C. 1
D. 2
满分：3 分
18. 递归过程的实现需用到 ( )。
A. 线性表
B. 链表
C. 栈
D. 队列
满分：3 分
19. 二叉树在中序线索化后，仍不能有效求解的问题是 ( )。
A. 求指定结点的前序后继
B. 求指定结点的中序前驱
C. 求指定结点的中序后继
D. 求指定结点的后序后继
此题选: D 满分：3 分
20. 树最适合用来表示 ( )。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
满分：3 分
2012秋第一次在线作业
试卷总分：100
单选题
判断题
二、判断题（共 20 道试题，共 40 分。）
V
1. 二叉树的中序遍历序列中，任意一个结点均处在其右子女结点( 若存在 )的前面。
A. 错误
B. 正确
满分：2 分
2. 链表中的表头指针与表头结点起到相同的作用。
A. 错误
B. 正确
满分：2 分
3. 链表中的表头指针与表头结点起到不同的作用。
A. 错误
B. 正确
满分：2 分
4. 消除递归不一定需要使用栈。
A. 错误
B. 正确
满分：2 分
5. 循环链表不是线性表。
A. 错误
B. 正确
满分：2 分
6. 用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n-1个空指针。
A. 错误
B. 正确
满分：2 分
7. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A. 错误
B. 正确
满分：2 分
8. 任何一棵二叉树都可以不用栈实现前序线索二叉树的前序遍历。
A. 错误
B. 正确
满分：2 分
9. 非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。
A. 错误
B. 正确
满分：2 分
10. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
A. 错误
B. 正确
满分：2 分
11. 必须把一般的树转换成二叉树后才能进行存储。
A. 错误
B. 正确
满分：2 分
12. 完全二叉树的存储结构通常采用顺序存储结构。
A. 错误
B. 正确
满分：2 分
13. 二叉树结点的中序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。
A. 错误
B. 正确
满分：2 分
14. 树形结构中元素之间存在一对多的关系。
A. 错误
B. 正确
满分：2 分
15. 二叉树结点的前序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。
A. 错误
B. 正确
满分：2 分
16. 在指定结点之前插入新结点时，双链表比单链表更方便。
A. 错误
B. 正确
满分：2 分
17. 二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继结点的线索。
A. 错误
B. 正确
满分：2 分
18. 算法的优劣与算法描述语言无关，但与所用计算机有关。
A. 错误
B. 正确
满分：2 分
19. 给定一棵树，可以找到唯一的一棵二叉树与之对应。
A. 错误
B. 正确
满分：2 分
20. 数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。
A. 错误
B. 正确
满分：2 分