文档介绍：《算法与数据结构》模拟试题6
一、填空题(每小题2分,共18分)
1、数据的逻辑结构在计算机中的基本存储结构有和。
2、算法的时间复杂度取决于。
3、队列是的线性表,其操作数据的基本原则是。
4、设有一个二维数组A[0…9][0…9],若每个元素占2个基本存储单元,A[0][0]的地址是200,若按列优先(以列为主)顺序存储,则A[6][6]的存储地址是。
5、在高度为h的二叉树的中只有度为0和度为2的结点,则该类二叉树中所包含的结点数至少为。
6、对于一个有n个顶点和e条弧的有向图,若采用正邻接链表存储,则表头向量的大小为,邻接表中的结点总数为。
7、若采用分块查找,要求线性表块内,块间。
8、对于文件,按其记录的类型可将文件分为文件、文件。
9、外部排序的最基本方法是,其主要时间花费在方面。
二、单项选择题(请将答案写在题目后的括号中。每题2分,共18分)
1、下面程序段的时间复杂度是( )。
for (i=1;i<=m;i++)
for (j=1;j<=n;j++) A[i][j]=i+j;
(A) O(m+n) (B) O(m) (C) O(n) (D) O(m*n)
2、判断一个循环队列Q(最多元素个数为m)为满队列的条件是( )。
(A) == ; (B) != ;
(C) ==(+1)%m; (D) !=(+1)%m;
3、设有一个栈顶指针为top的顺序栈S,则将元素p压入栈S中的操作是( )。
(A) S[top++] =p; (B) S[++top] =p;
(C) S[top--] =p; (D) S[--top] = p;
4、广义表((a),((b),c),(((d))))的长度是,深度是。( )
(A) 3, 4 (B) 3, 3 (C) 4, 3 (D) 4, 4
5、在二叉树中,指针P所指的结点是叶子结点的条件是( )。
(A) P->Lchild !=NULL&& P->Rchild !=NULL ;
(B) P->Lchild !=NULL&& P->Rchild ==NULL ;
(C) P->Lchild ==NULL&& P->Rchild !=NULL ;
(D) P->Lchild ==NULL&& P->Rchild ==NULL ;
6、一棵二叉树,其先序遍历序列是abdghcefi,中序遍历序列是bgdhaecfi,则其后序遍历序列是( )。
(A) ghdbiefca (B) ghdbeicfa
(C) ghdbeifca (D) gdheibfca
7、若以{4, 5, 6, 7, 8}作为叶子的权值构造Huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造),则其带权路径长度WPL为( )。
(A) 60 (B) 61 (C) 73 (D) 69
8、在无权图G的邻接矩阵中,若(Vi, Vj)或< Vi, Vj>属于G的边集,则对应元素A[i][j]等于,否则等于。( )
(A) 1,1 (B) 1,0 (C) 0,1 (D) 0,0
9、设有一组记录的关键字是(37,28,56,80,60,14,