文档介绍：共 9页第 1页《算法与数据结构》模拟试题 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) 共 9页第 2页{ if (n<=1) return 1; else return(n*fact(n-1)) ;}(A) O(n) (B) O(n 2)(C) O( ㏒ 2 n)(D) O(n ㏒ 2 n) 2、线性表若采用链式存储结构时,要求内存中可用存储单元的地址是( )。(A)必须是连续的(B)部分地址必须是连续的(C)一定是不连续的(D)是否连续没有要求 3、判断一个循环队列 Q(最多元素个数为 m)为满队列的条件是( )。(A)Q. front==Q . rear ;(B)Q. front!=Q . rear ; (C)Q. front==(Q . rear+1)%m ;(D)Q. front!=(Q . rear+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, addre ss (19 )=6, addre ss(41 )=2, addre ss (57 )=5, addre ss (85 )=7 ,其余地址为空。对于关键字 31 ,若用线性探测法解决冲突,其地址是;若用二次探测法解决冲突,其地址是。() (A)8,4(B) 11,4(C)4,8(D)4, 11 8