《算法与数据结构》模拟试题3

《《算法与数据结构》模拟试题3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法与数据结构》模拟试题3一、填空题（每小题2分，共18分）1、数据的逻辑结构包括，和三种结构。2、算法分析的两个主要方面是和。3、在双向链表中，每个结点有两个指针域，一个指向，另一个指向。4、空串是，其长度等于。5、有一个10阶对称矩阵A，采用压缩存储方式，以行为主存储下三角形到一个一维数组中，若A[0][0]的地址是200（每个元素占2个基本存储单元），则A[9][5]的地址是。6、在非空二叉树的中序遍历序列中，根结点的右边。7、采用邻接链表存储图，则图的深度优先搜索算法类似于二叉树的。8、在分块查找方法中，首先查找，然后再查找相应的。9、

2、对于文件，按其记录的类型可将文件分为文件、文件。二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）1、有如下递归函数fact(n)，其时间复杂度是（）。Fact(intn){if(n<=1)return1;elsereturn(n*fact(n-1));}6（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、；3、稀疏矩阵一般的压缩存储方法有主要有（）两种。（A）二维数组和三维数组（B）三元组和散列（C）三元组和十字链表（D）散列和十字链表4、一般树的存储结构主要有（）。（A）双亲表示法，孩子表示法，链表表示法（B）双亲表示法，孩子表示法，孩子—兄弟表示法（C）双亲表示法，孩子—兄弟表示法，链表表示法（D）双亲表示法，孩子—兄弟表示法，链表表示法5、一棵有n(n≥0)个结点的满二叉树的叶子结点的数目是，非叶子结点的数目是。（）（A）2[㏒2n]2[㏒2n]（B）2[㏒2n]-12[㏒2n]（C）2[㏒2n]-12[㏒2n]-1（D）2[㏒2n]2[㏒

4、2n]-16、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍，所有顶点的度之和等于所有顶点的入度之和的倍。（）（A）1/2，1（B）1，2（C）2，1（D）1，47、设有一个长度为12的有序表，采用二分查找方法对该表进行查找时，在表内各元素等概率情况下查找成功所需的平均比较次数为。（）(A)35/12（B）37/12（C）39/12（D）43/128、设有一组记录的关键字是（37，28，56，80，60，14，25，50），用快速排序法以第一个记录为基准得到的一次划分结果是（）。（A）25，28，37，14，56，80，60，50（

5、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，509、文件在外存上的上的组织方式称为文件的物理结构。基本的物理结构有：（）(A)顺序结构，链接结构，线性结构(B)线性结构，链接结构，索引结构(C)顺序结构，链接结构，线性结构(D)顺序结构，链接结构，索引结构6三、分析题（每题6分，共30分）1、设有一棵二叉树，其先序遍历序列是abdgehicf，中序遍历序列是gdbheiafc，请画出这棵二叉树，然后画出其后序线索化树。2、对于下图中的网，写出

6、该网的邻接链表；然后写出其广度优先搜索生成树（假设从顶点V1出发）；最后给出按Prime算法从顶点V5出发得到的最小生成树。1524389113341373、将关键字序列（14，9，18，7，4，13，25，19，6）依此插入到初态为空的二叉排序树中，请画出所得到的树T；然后画出删除18之后的二叉排序树T1；最后再画出插入18之后的二叉排序树T2。64、线性表的关键字集合{71，25，8，29，42，69，95，33，17，56，47}，共有11个元素，已知散列函数为：H（k）=kMOD11，采用链地址处理冲突，请给出对应的散列表结构，并计算该表

7、成功查找的平均查找长度。5、已知序列{35，29，52，60，17，9，38，27，13，45}，请给出采用归并排序法对该序列做非递减排序时的每一趟结果。四、算法填空（每空2分，共20分）请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。1、循环队列Q的队首元素出队操作算法。#defineMax_Queue_Size100ElemTypeDelete_CirQueue(SqQueueQ){ElemTypex;if()6printf(“TheCircularQueueisNull!”);else{x=Q.Queue_

8、array[Q.front];;}}2、二叉树中序遍历的非递归算法。#defineMax_Node_Num50VoidInorderTr