文档介绍：《算法与数据结构》模拟试题3
一、填空题(每小题2分,共18分)
1、数据的逻辑结构包括, 和三种结构。
2、算法分析的两个主要方面是和。
3、在双向链表中,每个结点有两个指针域,一个指向,
另一个指向。
4、空串是,其长度等于。
5、有一个10阶对称矩阵A,采用压缩存储方式,以行为主存储下三角形到一个一维数组中,若A[0][0]的地址是200(每个元素占2个基本存储单元),则A[9][5]的地址是。
6、在非空二叉树的中序遍历序列中,根结点的右边。
7、采用邻接链表存储图,则图的深度优先搜索算法类似于二叉树的。
8、在分块查找方法中,首先查找,然后再查找相应的。
9、对于文件,按其记录的类型可将文件分为文件、文件。
二、单项选择题(请将答案写在题目后的括号中。每题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、设有一个栈顶指针为top的顺序栈S,top为0时表示栈空,则向S中压入一个元素P执行的操作是( )。
(A) S[top++]=p; (B) S[++top]=p;
(C) S[--top]=p; (D) S[top--]=p;
3、稀疏矩阵一般的压缩存储方法有主要有( )两种。
(A) 二维数组和三维数组(B) 三元组和散列
(C) 三元组和十字链表(D) 散列和十字链表
4、一般树的存储结构主要有( )。
(A) 双亲表示法,孩子表示法,链表表示法
(B) 双亲表示法,孩子表示法,孩子—兄弟表示法
(C) 双亲表示法,孩子—兄弟表示法,链表表示法
(D) 双亲表示法,孩子—兄弟表示法,链表表示法
5、一棵有n(n≥0)个结点的满二叉树的叶子结点的数目是,非叶子结点的数目是。( )
(A) 2[㏒2n] 2[㏒2n] (B) 2[㏒2n]-1 2[㏒2n]
(C) 2[㏒2n]-1 2[㏒2n]-1 (D) 2[㏒2n] 2[㏒2n]-1
6、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的倍,
所有顶点的度之和等于所有顶点的入度之和的倍。( )
(A) 1/2,1 (B) 1,2 (C) 2,1 (D) 1,4
7、设有一个长度为12的有序表,采用二分查找方法对该表进行查找时,在表内各元素等概率情况下查找成功所需的平均比较次数为。( )
(A) 35/12 (B) 37/12 (C) 39/12 (D) 43/12
8、设有一组记录的关键字是(37,28,56,80,60,14,25,50),用快速排序法以第一个记录为基准得到的一次划分结果是( )。
(A) 25,28,37,14,56,80,60,50 (B) 25,28,37,14,60,80,56,50
(C) 25,28,14,37,60,80,56,50 (D) 25,28,14,37,60,56,80,50
9、文件在外存上的上的组织方式称为文件的物理结构。基本的物理结构有:( )
(A) 顺序结构,链接结构,线性结构(B) 线性结构