数据结构模拟题
需积分: 9 93 浏览量
2008-07-03
20:20:32
上传
评论
收藏 56KB DOC 举报
数据结构模拟试题
题号 一 二 三 四 五 总分
分数
一、 单项选择题（每小题 2 分，共 14 分）
1．栈操作的原则是 _________。
A．栈顶插入 B．栈顶删除 C．先进先出 D．后进先出
2．在有 11 个数据元素的有序表中，采用折半查找，查找长度为 4 的元素个数为____
____。
A．4 B．5 C . 2 D． 3
3．在有 15 个元素的顺序表中，删除一个元素时，平均移动元素的次数为________。
A．15 B．8 C．14 D．7
4．含有 n 个顶点的无向连通图，至少包含的边数为________。
A． n(n-1) B．n(n-1)/2 C．n D． n-1
5．具有 12 个记录的序列，采用直接插入排序最少比较次数为________。
A．132 B．144 C．11 D．12
6．设二叉树的先序遍历序列为 ABCDE，则二叉树的中序遍历序列不可能是 。
A．ADEBC B．ABDEC C．EDCBA D．ABCDE
7．深度为 h 的二叉树所含的叶结点个数最多为 。
A．2
h
B．2
h-1
C．2h D．h
二、填空题（每小题 2 分，共 16 分）
1．有 m（m>0）个结点的二叉树，采用二叉链表作为存储结构，则二叉链表中非空
指针的个数为________。
2．Ｇ为无向图，如果从Ｇ的某个顶点出发进行一次广度优先搜索，即可访问图的每
个顶点，则该图一定是_________图。
3．有 m 个叶结点的哈夫曼树中，总结点个数为 。
4．已知循环队列用数组 A[0..n-1] 存放元素，已知其头、尾指针分别是 front 和
rear ，则队列中元素个数为 。
5．已知数组 A[10..20][5..10]按列优先存储，每个元素占有 6 个存储单元，且 A[10][5]
的地址为 2000（十进制），则 A[15][8]的地址为________________。
6．m 个结点的完全二叉树中，从上至下、从左至右进行编号，根结点的编号为 1，
则最大的分支结点的编号为___________。
7．快速排序在最坏情况下的时间复杂度为_____________。
8．有向图 G 采用邻接矩阵存储，其第 i 列所有元素之和等于顶点 i 的______________。
三、判断题（正确的打“√ ”，错误的打“×”，每题 1 分，共 10 分）
1. （ ）在 AOE-网中，任何一个关键活动的提前完成，都可以缩短工程的完成时间。
2. （ ）在用线性探测法解决冲突所构造的散列表中，每组同义词中至少有一个元
素的地址。
3. （ ）对 n 个元素的有序表用直接插入排序方法进行排序，时间复杂是 O(n)。
4. （ ）用邻接矩阵表示图所用的存储空间大小与图的边数成正比。
5. （ ）简单选择排序得比较次数与序列的初始状态无关。
6. （ ）一个带权图的最小生成树不是唯一的。
7. （ ）已知二叉树的层次序列和中序序列，可以唯一的确定一棵二叉树。
8. （ ）线性表在采用链式存储时，其部分地址是连续的。
9. （ ）数组可以看成线性表的推广，因此可以对它进行插入和删除运算。
10. （ ）在顺序表中读取第 i 个元素所花费的时间与 i 成正比。
四、应用题（共 42 分）
第 1 页 共 4 页
评论0