文档介绍：《算法与数据结构》模拟试题7
一、填空题(每小题2分,共20分)
1、数据及其联系在计算机内存中的存储称为数据的物理(存储)结构,基本的物理结构有和。
2、数据结构中评价算法的两个重要指标是和。
3、堆栈是操作受限的线性结构,只能在插入和删除元素;不能进行插入和删除元素的一端称为。
4、有一个10阶对称矩阵A,采用压缩存储方式(以行为主存储),A[0][0]的地址是100,若每个元素占3个基本存储单元,则A[5][8]的地址是。
5、设有一棵深度为n的二叉树,它至少有个结点,至多有个结点。
6、动态存储管理主要是解决系统如何_______________、_____________ 的两大问题。
7、对线性表进行二分查找时,要求线性表必须是,且要求。
8、对于内部排序,有多种排序方法。按排序基本思想(策略),可分为、
、、归并排序和基数排序。
9、索引表是存储记录的和记录的之间的对照表,每个元素称为一个索引项。
10、对于文件,按物理结构划分,可分为顺序文件、文件、
文件和多关键字文件。
二、单项选择题(请将答案写在题目后的括号中。每题2分,共18分)
1、有如下递归函数fact(n),其时间复杂度是( )。
Fact(int n)
{ if (n<=1) return 1;
else return(n*fact(n-1)) ;
}
(A) O(n) (B) O(n2) (C) O(㏒2n) (D) O(n㏒2n)
2、线性表若采用链式存储结构时,要求内存中可用存储单元的地址是( )。
(A) 必须是连续的(B) 部分地址必须是连续的
(C) 一定是不连续的(D) 是否连续没有要求
3、判断一个循环队列Q(最多元素个数为m)为满队列的条件是( )。
(A) == ; (B) != ;
(C) ==(+1)%m; (D) !=(+1)%m;
4、一棵二叉树,其先序遍历序列是abdehicfg,中序遍历序列是dbheiafcg,则其后序遍历序列是( )。
(A) dhiebafgc (B) dhiebfgca
(C) dhiebfgac (D) dbhiefgca
5、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的倍,
所有顶点的度之和等于所有顶点的入度之和的倍。( )
(A) 1/2,1 (B) 2,1 (C) 1,2 (D) 1,4
6、对于有n个顶点e(e>n)条边的带权无向图,以下关于该图的最小生成树的描述正确的是( )。
(A) 最小生成树是唯一的。
(B) 最小生成树中所有边上的权值之和是唯一的。
(C) 最小生成树有n条边。
(D) 最小生成树有n个顶点e-1条边。
7、设哈希表长m=14,H(key)=key MOD 13,address(19)=6,address(41)=2,address(57)=5,address(85)=7,其余地址为空。对于关键字31,若用线性探测法解决冲突,其地址是;若用二次探测法解决冲突,其地址是。( )
(A) 8,4 (B) 11,4 (C) 4,8 (D) 4,11
8、从未排序序列中挑选元素,并将其