下载文档原格式
2011〜2012学年第1学期期末考试试卷（A卷）
课程名称：数据结构 ____________ 任课教师姓名：______________
卷面总分：100 分考试时长：100 分钟考试类别：闭卷
院（系）：_________________ 专业：_______________________________ 年级：2010
阅卷教师（签字）：________________________
单项选择题（每题2分，共10题20 分）
1. ________________________________________________ 以下那一个术语与数据的存储结构无关？________________________________________
A. 栈 C .线索树
B .哈希表 D .双向链表
2. ________________________________________ 链表不具有的特点是。
A. 插入、删除不需要移动元素C•不必事先估计存储空间
B. 可随机访问任一元素D.所需空间与线性表长度成正比
3. ________________________________________________________ 算术表达式
a+b* （c+d/e）转为后缀表达式后为______________________________ 。
A . ab+cde/* C. abcde/*++
B. abcde/+*+ D. abcde*/++
4. 二维数组A[10][20]采用列优先的存储方法，若每个元素占2个存储单元，设A[0][0]
的地址为100,则元素A[7][6]的存储地址为____________________ 。
A. 232
B. 234
C. 390 D . 392
5•若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点
个数是 ________ B
。 A . 9
B . 11
C . 15
D .不确定
6•—棵二叉树中序序列为 FEABDC,后序序列为FBADCE ，则层序序列为 D <
A . G 中有弧
C . G 中没有弧
B. G 中有一条从Vi 到Vj 的路径 D . G 中有一条从Vj 到Vi 的路径
8. _________________________________ 对于二叉排序树，下面的说法 C 是正确的。
A .二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂 和组合（不用移动元素的树）
B .对二叉排序树进行层序遍历可得到有序序列（ 应该是中序遍历）
C. 用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的 深度最大
D .在二叉排序树中进行查找，关键字的比较次数不超过结点数的 1/2 （取决于 二叉排序树的形状）
9. 一组记录的关键字为｛47、75、55、30、42、90｝，则用快速排序方法并以第一个
记录为支点得到的第一次划分结果是 A. 30,42,47,55,75,90 B. 42,30,47,75,55,90 10.
下述文件中适合于磁带存储的是 ___________________ 。
A. 顺序文件 C.散列文件
B. 索引文件
D.多关键字文件
顺序文件：原理是顺序表查找法
C. 42,30,47,55,75,90
D. 42,30,47,90,55,75
索引文件：原理是线性索引查找（如最大关键码和次关键码）
多关键字文件: 散列文件：原理是散列函数(哈希函数)
判断(每题1分，共10题10 分)
1 •顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。----()
(如果插入和删除次数较少时顺序存储方式为首选)
2. ------------------------------------------------------------------------------------------------ KMP算法的特点是在模式匹配时指示主串的指针不会变小。----------------------- ()
(主串在匹配过程中是不会移动的，只有匹配的串在移动，所以其指针不会动)
3. 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列325,6,4,1. ---()
4. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除
等操作。------------------------------------ ()
数组不能进行插入删除等操作
5. ---------------------------------------------------------------------------------------------- 若一个广义表的表头为空表，则此广义表亦为空表。----------------------------- ()
6. ------------------------------------------------------------------------------------------------ 完全二叉树中，若一个结点没有左孩子，则它必是树叶。------------------------- ()
完全二叉树的关键之一就是：元素又是有序排列的，顺序不可间断
7. ------------------------------------------------------------------------------------------------ —个有向图的邻接表和逆邻接表中结点的个数可能不等。------------------------- ()
必须相等
8. ------------------------------------------------------------------------------- AOE网一定是有向无环图。-------------------------------------------------- ()
AOE网的特征和定义
9. 对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。---()
应该是中序排列
10. 倒排文件与多重表文件的次关键字索引结构是不同的。---------- ()
o
