《算法与数据结构》模拟试题6.doc

《算法与数据结构》模拟试题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 ；i++ for j 1；j ；j++ A[i][j] i+j; （A） O +n （B） O （C） O （D） O*n 2、 判断一个循环队列Q（最多元素个数为m）为满队列的条件是（ ）。 （A） Qfront Q.rear ； （B） Qfront! Q.rear ； （C） Qfront Q.rear+1 %m； （D） Qfront! Q.rear+1 %m； ] 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，25，50）（A） 25，28，14，37，60，80，56，50 （B） 25，28，37，14，60，80，56，50 （C） 25，28，14，37，60，56，80，50 （D） 25，28，37，14，56，80，60，50 17，，1，7，，，25T的过程；然后画出删除13之后的二叉排序树T1。 4、 线性表的关键字集合 21，25，8，9，42，7，15，3，17，36，4 ，共有13个元素，已知散列函数为：H（k） k MOD 1 35，2