DS考研试卷及答案-2007[Bin]

1南京邮电大学2007攻读硕士研究生入学考试数据结构试题（参考答案）一、判断题（每题2分，共12分，请答“是”或“否”）（）1算法必须至少有一个输入，否则就不能称为一个算法。【答案】否。（）2设有一个堆栈和一个队列。现有元素序列（A，B，C，D），依次进栈，进栈允许出栈，出栈的元素被加入队列。那么，从队列输出的元素序列可以是（D，C，B，A）。【答案】是。（）3循环队列是一种链式队列。【答案】否。（）4一棵二叉树中，必须有一个根结点，其余结点分属于左右两棵子二叉树。【答案】否。（）5散列表在元素的存储位置和它的关键字之间建立了一个确定的函数关系，所以，无论是否表中存在同义词，在查找记录时，只需计算地址，而无需作关键字之间的比较。【答案】否。（）6在胜方树上输出一个结点后，从根到该结点的路径上所有结点都必须更新。【答案】是。二、选择题（每题3分，共30分）1现实生活中具有谱系结构的数据，在计算机处理时一般采用（）结构表示。A线性B树C图D集合【答案】B2设后缀表达式：“4 3 * 2 9 3 / + 2 - /”，式中每个操作数均为一位整数，则表达式的值为（）。A6 B4 C8 DA,B,C三者都不是【答案】B3设二叉树根结点的层次为1。在所有含135个结点的二叉树中，最小高度是（）。A6 B7 C8 D9【答案】C4设A、X和Y是二叉树B中的三个结点，X是A的左孩子，Y是A的左孩子。T是与B对应得树；在T中，A是Y的（）。A孩子B兄弟C双亲D祖先（非双亲）【答案】D5下面哪一种结构必定是完全二叉树（）。2A哈夫曼树B二叉搜索树CAVL树D堆【答案】D6在有序表（10,20,30,40,50,60,70,80,90）中以对半搜索算法查找元素30和45时，所需的关键字之间的比较次数分别为（）。A3,3 B3,4 C4,4 DA,B,C三者都不是【答案】B7假定从无向图G的任何一个顶点出发进行一次深度优先搜索，都可以访问图中的每个顶点，则该图一定是（）。A连通图B完全图C有回路的图D一棵树【答案】A8用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（）。A逆拓扑有序B拓扑有序C无序的D按关键字有序【答案】A9初始序列经第一趟排序后，不能确定任何一个元素最终位置的排序算法是（）。A两路合并排序B冒泡排序C快速排序D简单选择排序【答案】A10快速排序和冒泡排序的最坏情况时间复杂度分别为（）。AO(nlog2n),O(nlog2n) BO(nlog2n),O(n2)CO(n2),O(nlog2n) DO(n2),O(n2)【答案】D三、填空题（每题6分，共30分）1已知三维整型数组A，其维数为：A456（C/C+）或A0.30.40.5（pascal），每个元素占2个单元，按行优先（即最右下标变化最快）的次序存储。现已知A345（A3,4,5在内存中的地址是238，则A000的地址是（），A233的地址是（）。【答案】0，1622设有模式串p=“abscdabscdxab”，若采用简单匹配算法，则当匹配在字符x处失败时，则下一趟匹配从串p的第（）字符开始。若采用KMP算法，则下一趟匹配从串p的第（）个字符开始。【答案】0（第1个a），5（第2个a）【解释】考察模式匹配算法。简单匹配算法中，匹配失败时，主串有回溯，模式串从下标为0的字符；KMP匹配算法中，匹配失败时（模式串匹配字符的下标为j），主串无回溯，模式串从下标为改进nextj的字符进行比较。下标0 1 2 3 4 5 6 7 8 9 10 11 12字符a b s c d a b s c d x a BNext -1 0 0 0 0 0 1 2 3 4 5 0 1改进的Next -1 0 0 0 0 -1 0 0 0 0 5 -1 03设散列表如图1，X代表该位置处已经存储了元素。现在表中插入新元素y，设h(y)=7。若此表是线性探查法探查散列表，则y应插入下标为（）的位置处。若此表是二次探查法探查散列表，则y应插入下标为（）的位置处。30 1 2 3 4 5 6 7 8 9 10 11 12X X X X X X X X X图1【答案】9，34已知某二叉树的中序遍历序列是becad，后序遍历序列是ecbda，它的先序遍历序列是（），此二叉树上的叶子结点有（）。【答案】abced，d和e（2个）5迪杰斯特拉算法用于求解（）最短路径问题，它按（）次序逐一产生最短路径。【答案】单源，路经长度的递增四、解答题（每题8分，共48分）1设有字符集A,B,C,D,E的哈夫曼编码为：A：00，B：01，C：10，D：110，E：111。（1）画出该哈夫曼树；（2）已知电文：ADCEB，求编码得到的码文；（3）已知码文：010011011111110，求译码得到的电文。【答案】（1）对应的哈夫曼树是（2）00,110,10,111,01（3）01（B）00（A）110（D）111（E）111（E）10（C）对应的编码是BADEEC2给定关键字集合40,30,50,60,70,10,20,80。（1）求以该集合元素所构造的二叉搜索树的最小和最大高度（设根结点的层次为1）。（2）从空树出发，依次插入序列40,30,50,60,70,10,20,80中元素构造一棵二叉搜索树。画出该树。（3）给定无序序列（40,30,50,60,70,10,20,80），构造一个min堆。画出该堆。【答案】（1）构造的二叉搜索树最小的高度为4（相对平衡的二叉搜索树）。最大高度为8（单支树）。ab dae4（2）从空树出发，依次插入序列40,30,50,60,70,10,20,80中元素构造的二叉搜索树如下所示。（3）给定无序序列（40,30,50,60,70,10,20,80），构造的最小堆如下图所示。通过逐个插入元素建立的堆：通过反向调整元素建立的堆：3二叉搜索树和堆是两种特殊的二叉树。（1）给定一棵n个结点的二叉搜索树，通过什么途径可以产生元素的有序序列，其时间复杂度是多少？（2）给定一个n个结点的堆，通过什么途径可以产生元素的有序序列，其时间复杂度是多少？【答案】（1）中序遍历一个二叉搜索树，其时间复杂度是O(n)。（2）堆排序：输出堆顶元素，输出后作调整，保持堆的特性。重复上述步骤，直到输出堆中为空。得到的输出序列就是一个有序序列。其时间复杂度是O(nlog2n)。1030 20d7080 60 50 40d54设有向图如图2所示，（1）给出图的所有强连通分量；（2）画出此图从顶点A开始的深度优先遍历生成森林。（3）画出此图从顶点A开始的广度优先遍历生成森林。图2【答案】（1）图所有强连通分量：（2）图从顶点A开始的深度优先遍历生成森林：（深度优先遍历得到的森林结果不唯一，上图只是其中的一个解）（3）图从顶点A开始的广度优先遍历生成森林：5设无向图如图3所示，（1）画出以A为源点，普里姆算法得到的最小代价生成树。（2）如果对每条边的权值增加相同的正数，则得到的最小代价生成树是否与原树结构相同？说明你的理由。图3【答案】（1）以A为原点，普里姆算法得到的最小代价生成树，如下图所示。6（2）如果对每条边的权值增加相同的正数，则得到的最小代价生成树与原树结构相同。因为增加相同的正数，边权值的相对顺序不发生改变，不影响选边的次序，所以得到的最小代价生成树与原树结构相同。另：原来的构造是唯一的。6求解下列B-树问题（1）从空树出发，依次插入关键字：99，75，25，31，15，90，45，50，100，画出建成的4阶B-树。（2）从（1）所建成的B-树上依次删除：99，75，31，50，画出删除后的B-树。【答案】（1）从空树出发，依次插入关键字：99，75，25，31，15，90，45，50，100，构建成的4阶B-树，如下图所示。（2）从（1）所建成的B-树上依次删除：99，75，31，50，画出删除后的B-树。五、算法设计题（共30分）解题要求：（1）只允许使用pascal，C和C+语言中的一种语言解答本题。（2）算法描述中不允许直接调用教材上已实现的过程或函数。（3）要求对程序加上足以说明算法设计思想的明确注释。1（18分）设G（V，E）是一个无向连通图。如果顶点集V被分成两个互不相交的子集，并且图中任意一条边所关联的两个顶点分属于两个不同的子集。这样的图被称为二部图。可以设计一个算法来判定任意给定的一个无向图是否是二部图。提示：一个二部涂可以仅使用两种颜色对途中顶点着色（即每个顶点分配一种颜色），并且保证每一条边的两个端点分配不同颜色。可以采用深度优先搜索图的做法来实现这一判定算法。无向连通图采用邻接矩阵存储。本题要求设计如下两个算法并分析算法的时间和空间复杂度。（1）写出深度优先遍历无向连通图的算法，分析算法的时间和空间复杂度。457（2）写出采用深度优先搜索图的思想判定任意给定一个无向连通图是否二部图的算法，分析算法的时间和空间复杂度。【答案】（2）boolMGraph:DFS(intv;intcol)visitedv=TRUE;colorv=col;for(intj=0;j0;j+)if(avj!=noEdge) if(visitedj) if(colorj=col)returnfalse;elseDFS(j,!col);returntrue;voidMGraph:DFS(intk) if(DFS(k,0) cout”是二部图”endl;elsecout”不是二部图”endl;2（12分）请设计一个数据结构只包括下列三个运算：C