文档介绍：1 《算法与数据结构》模拟试题 5 一、填空题(每小题 2 分,共 18 分) 1、对于给定的 n个元素,可以构造出的逻辑结构有集合,, 和四种。 2、数据结构中评价算法的两个重要指标是和。 3、顺序存储结构是通过表示数据元素之间的( 逻辑) 关系;链式存储结构是通过表示数据元素之间的(逻辑)关系。 4、栈是的线性表,其操作数据的基本原则是。 5、设有一个二维数组 A[0 … 9][0 …9] ,若每个元素占 5 个基本存储单元, A[0][0] 的地址是1000 ,若按行优先(以行为主)顺序存储,则 A[6][8] 的存储地址是。 6、二叉树由根结点, 和三个基本单元组成。 7、若采用邻接矩阵存储一个图所需要的存储单元取决于图的;无向图的邻接矩阵一定是。 8、在查找时,若采用折半查找,要求线性表,而哈希表的查找,要求线性表。 9、对于文件,按物理结构划分,可分为顺序文件、文件、文件和多关键字文件。二、单项选择题(请将答案写在题目后的括号中。每题 2 分,共 18 分) 1、有如下递归函数 fact(n) ,其时间复杂度是( )。 Fact(int n) { if (n<=1) return 1; else return(n*fact(n-1)) ;} 2 (A) O(n) (B) O(n 2)(C) O( ㏒ 2 n)(D) O(n ㏒ 2 n) 2、以 head 为头结点的非空单循环链表的尾结点 p的特点是()。(A) p->next=NULL ;(B) p=NULL ; (C) p->next=head ;(D) p=head ; 3、设有一个栈顶指针为 top 的顺序栈 S, top 为0时表示栈空,则从 S中取出一个元素保存在 P中执行的操作是( )。(A) p=S[top++ ];(B) p=S[++top ]; (C) p=S[--top ];(D) p=S[top-- ]; 4、广义表(a, (a, b), d, e, ((i, j), k)) 的长度是,深度是。() (A)6,3(B)5,3(C)6,4(D)6,2 5、当一棵有 n个结点的二叉树按层次从上到下,同层次从左到右将(结点)数据存储在一维数组 A[1 … n]中时,数组中第 i个结点的左子结点是。() (A) A[2i](2i ≤ n)(B) A[2i+1](2i+1 ≤ n) (C) A[i/2] (D)条件不充分,无法确定 6 、设有一棵二叉树,其先序遍历序列是 acdgehibfkj ,中序遍历序列是 dgcheiabkfj ,则该二叉树的后序遍历序列是。() (A) gdehickjfba (B) gdhiecfkjba (C) dghieckjfba (D) gdhieckjfba 7、在一个有向图中,所有顶点的出度之和等于所有顶点的入度之和的倍, 所有顶点的度之和等于所有顶点的出度之和的倍。() (A) 1/2 ,1(B)1,2(C)2,1(D)1,4 8 、设有一组记录的关键字为{19, 14, 23, 1,68, 20, 84, 27} ,用链地址法构造哈希表,哈希函数为 H(key)=key MOD 13,哈希地址为 1的链表中有个记录。() (A) 4(B)2(C)3(D)1 9、用直接插入法对下列四个序列按非递减方式排序,元素比较次数最少的是()。(