资源描述：
《《算法与数据结构》模拟试题4》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《算法与数据结构》模拟试题4一、填空题（每小题2分，共18分）1、数据的逻辑结构包括，和三种结构。2、队列是操作受限的线性结构，只能在插入元素，而在删除元素。3、串是一种特殊的线性表，其特殊性体现在。4、有一个10阶对称矩阵A，采用压缩存储方式采用压缩存储方式，以行为主存储下三角形到一个一维数组中，A[0][0]的地址是100（每个元素占2个基本存储单元），则A[5][9]的地址是。5、在高度为h的二叉树的中只有度为0和度为2的结点，则该类二叉树中所包含的结点数至少为。6、对于一个有n个顶点和e条边的无向图，若采用邻接链表存储，则表头向量的
2、大小为，邻接表中的结点总数为。7、对线性表进行二分查找时，要求线性表必须是，且要求。8、对于文件，按物理结构划分，可分为顺序文件、文件、文件和多关键字文件。9、外部排序的最基本方法是，其主要时间花费在方面。二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）1、如下函数是求1!+2!+…+n!，其时间复杂度是（）。LongintSum(intn){longintsum=0,t=1;intp;for(p=1;p<=n;p++){t=t*p;sum+=t;}return(sum);}6（A）O(n)（B）O(n2)（C）O(㏒2n)
3、（D）O(n㏒2n)2、设有一个栈顶指针为top的顺序栈S，则弹出S的栈定元素的操作是（）。（A）p=S[top++]；（B）p=S[++top]；(C)p=S[top--]；（D）p=S[--top]；3、广义表((a),((b),c),(((d))))的表头是，表尾是。（）（A）(a)((b),c),(((d)))（B）(a)(((b),c),(((d))))（C）((a),((b),c)),(((d)))（D）(a)(((d)))4、一棵二叉树，其先序遍历序列是abdgehicf，中序遍历序列是gdbheiafc，则其后序遍历序列是(
4、)。（A）abdgehicf（B）gdbheiafc（C）gdhiebfca（D）gdheibfca5、具有五层结点的平衡二叉树至少有。（）（A）10（B）12（C）17（D）156、在无权图G的邻接矩阵中，若(Vi,Vj)或属于G的边集，则对应元素A[i][j]等于，否则等于。（）（A）1，1（B）1，0（C）0，1（D）0，07、判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。(A)广度优先遍历算法(B)求关键路径的方法(C)深度优先遍历算法(D)求最短路径的Dijkstra算法8、设有一个长度为n的
5、线性表，当采用顺序查找方法时，每个元素的平均查找长度是；而采用二分查找方法时，其平均查找长度是。（）(A)n/2,O(n)（B）n/2,O(㏒2n)（C）(n+1)/2,O(n㏒2n)（D）(n+1)/2,O(㏒2n)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，8
6、0，60，50三、分析题（每题6分，共30分）61、设有一份电文中工使用了7个字符：a，b，c，d，s，m，n，它们出现的频率依次为3，6，4，2，8，9，7，请画出对应的Huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)，并求其带权路径长度WPL。2、对于下图中的网，写出该网的邻接链表；然后写出其深度优先搜索生成树（假设从顶点V3出发）；最后给出按Kruskal算法得到的最小生成树。1243812561173、将关键字序列（14，19，16，7，4，13，25，9，18，12）依此插入到初态为空的二叉排序树中，请画出
7、所得到的树T；然后画出删除13之后的二叉排序树T1；最后再后画出插入13之后的二叉排序树T2。64、线性表的关键字集合{31，25，18，29，42，67，15，33，17，36，46}，共有11个元素，已知散列函数为：H（k）=kMOD11，采用线性探测法处理冲突，请给出对应的散列表结构，并计算该表成功查找的平均查找长度。5、已知序列{35，29，22，16，17，9，38，27，13，45}，请给出采用希尔排序法对该序列做非递减排序时的每一趟结果，增量序列为5，3，1。四、算法填空（每空2分，共20分）请在下面各个算法的空白处填上相应的
8、语句，以实现算法功能。每个空白处只能填一个语句。1、循环队列Q的入队操作算法。#defineMax_Queue_Size100VoidInsert_CirQueue(SqQueu
