东南大学数据结构试卷

共8页第1页东南大学考试卷（A卷）课程名称数据结构考试学期08-09-3得分适用专业吴健雄学院电类考试形式半开卷考试时间长度120分钟一、选择题（每题1分，共5分）1．下面有关链栈的描述，对常规情况正确的是（）A．在链头插入，链尾删除。B．在链尾插入，链头删除。C．在链尾插入，链尾删除。D．在链头插入，链头删除。2．对线性表进行对半搜索时，要求线性表必须（）A．以数组方式存储B．以数组方式存储并按关键码排序C．以链表方式存储D．以链表方式存储并按关键码排序3．对包含n个元素的散列表进行搜索，平均搜索长度为（）A．O(log2n)B．O(n)C．不直接依赖于nD．三者均不是4．在同一个有向图中，所有结点的入度和与出度和之比为（）A．1B．2C．1/2D．都不对5．在具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。A．nB．n+1C．n-1D．n/2二、判断题（每题1分，共5分）1．链式存储的线性表所有存储单元的地址可连续可不连续。（）2．存储有向图的邻接矩阵是对称的，所以可以仅存矩阵上三角部分。（）3．在采用闭散列法解决冲突时，不要立刻做物理删除，否则搜索时会出错。（）4．二叉树中序遍历结果序列的最后一个结点必是前序遍历的最后一个结点。（）5．堆排序的时间复杂度是O(nlog2n)，但需要额外存储空间。（）三、填空题（每空1分，第1空、第2空为2分，共11分）1．中缀表达式“(a+b)*d+e/(f+a*d)+c)”所对应的后缀表达式为（1）2．后缀表达式“ab&&ef!||”所对应的中缀表达式为（2）学号姓名密封线自觉遵守考场纪律如考试作弊此答卷无效共8页第2页3．高度为h的二叉树最多可以有多少结点（3）4．若对一棵完全二叉树从0开始编号，并按此编号把它顺序存储到一维数组a中，则a[i]元素的左孩子结点为(4)，右孩子结点为(5)，双亲结点为(6)。5．对用邻接矩阵表示的图进行任何一种遍历时，其时间复杂度为(7)。对用邻接表表示的图进行任何一种遍历时，其时间复杂度为(8)。6．折半插入排序的时间复杂度为(9)。四、简答简述题（每题8分，共24分）1．设有一组关键码输入序列{55，31，12，37，46，73，63，02，07}，从空树开始构造平衡二叉搜索树，画出每加入一个新结点时的二叉树形态，需标出平衡因子。包括发生不平衡时，旋转的各步的二叉树形态，并标注旋转类型。2．已知一棵二叉树的前序遍历的结果为ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，试画出这棵二叉树。请用图表示逐步形成二叉树的过程（也可以用文字）。共8页第3页3．请用Kruskal算法，逐步画出下面有权无向图的最小生成树。必须每次添加一条边。05463211011121415162822251824共8页第4页五、综合算法题（每空2.5分，共55分）1．完善改进的归并排序算法。*this是一个待排序的表，而表L2是一个辅助的工作表，帮助完成排序的中间步骤，最终完成*this的排序。所谓改进指在把元素序列复制到辅助表中时，把第2个表的元素顺序逆转，这样两个待归并的表从两端开始处理，向中间归并。可以省去检查子表是否结束的判断。templatetypenameTvoidOrderedlistT::MergeSort(intleft,intright){OrderedlistTL2;improvedMergeSort(L2,left,right);//对序列进行归并排序}templatetypenameTvoidOrderedlistT::improvedMergeSort(OrderedlistT&L2,intleft,intright){intmid=(left+right)/2;//从中间划分为两个子序列improvedMergeSort(L2,left,mid);//对左侧子序列进行归并排序improvedMergeSort(L2,mid+1,right);//对右侧子序列进行归并排序(1);//二路归并}templatetypenameTvoidOrderedlistT::improvedMerge(OrderedlistT&L2,intleft,intmid,intright){ints1=left,s2=right,t=left,k;//s1,s2是检测指针，t是存放指针for(k=left;k=mid;k++){//正向复制(2);}for(k=mid+1;k=right;k++){//反向复制(3);}while(t=right){//归并过程if(L2.slist[s1]=L2.slist[s2])(4);else(5);}}2．完成二叉树前序遍历的非递归算法和层次序遍历算法操作。//非递归前序遍历。每访问一个结点后，在向左子树遍历下去之前，利用栈记录该结点的右子女结点的地址，以便在左子树退回时可以直接从栈顶取得右子树的根结点，继续右子树的前序遍历。共8页第5页templatetypenameTvoidBinaryTreeT::PreOrder1(void(*visit)(BinTreeNodeT*t)){LinkedStackBinTreeNodeT*S;BinTreeNodeT*p=root;S.Push(NULL);while(p!=NULL){visit(p);//访问结点if(p-rightChild!=NULL)(6);//预留右指针在栈中if(p-leftChild!=NULL)(7);//进左子树else(8);//左子树为空，由堆栈弹出}}//层次序遍历。在访问二叉树某一层结点时，把下一层结点指针预先记忆在队列中，利用队列安排逐层访问的次序。因此每当访问一个结点时，将它的子女依次加到队尾。然后访问已在队头的结点。templatetypenameTvoidBinaryTreeT::levelOrder(void(*visit)(BinTreeNodeT*t)){if(root==NULL)return;LinkedQueueBinTreeNodeT*Q;BinTreeNodeT*p=root;visit(p);(9);while((10)){Q.DeQueue(p);if(p-leftChild!=NULL){visit(p-leftChild);(11);}if(p-rightChild!=NULL){visit(p-rightChild);(12);}}}3．完成利用最大堆实现的优先级队列类定义。注意heap[0]不用，从heap[1]开始共8页第6页templatetypenameTclassMaxheap{ElementT*heap;intn;intMaxSize;public:Maxheap(intsz=Defaultsize);//创建空堆，最多可以容纳sz个元素voidInsert(ElementT&item);ElementT*Delete(ElementT&x);voidshow();};templatetypenameTMaxheapT::Maxheap(intsz){MaxSize=sz;n=0;heap=newElementT[MaxSize+1];//注意heap[0]不用，从heap[1]开始}templatetypenameTvoidMaxheapT::Insert(ElementT&x){inti;if(n==MaxSize){cerrheapisfull.\n;return;}n++;for(i=n;i1;){//i==1表示已达到根节点if((13))break;//新元素不大于结点i的双亲，不处理(14);//此时heap[i]未占用，将双亲结点元素移入(15);//i继续向上}heap[i]=x;//位置定了数值再放进去}templatetypenameTElementT*MaxheapT::Delete(ElementT&x){inti,j;if(!n){cerrheapisempty.\n;returnNULL;}x=heap[1];ElementTk=heap[n];n--;共8页第7页for(i=1,j=2;j=n;){//j是i的子女if(jn)if((16))j++;//j指向较大子女if(heap[j]=k)break;//候补的结点大，不再移动(17);//还需移动，将较大子女直接移入(18);//移动(19);}heap[i]=k;return&x;}4．完成的深度优先遍历图算法。//深度优先遍历图，输出所有的连通分量templatetypenameT,typenameEvoidGraphT,E::DFS(){inti,n=NumberOfVertices();//取图中顶点个数bool*visited=newbool[n];//创建辅助数组for(i=0;in;i++){//辅助数组visited初始化visited[i]=false;}for(i=0;in;i++){//从每个顶点开始，各做一次遍历。if((20)){//借助辅助数组，上一趟遍历已访问过的//各顶点不会作为新起点。所以输出了所有连通分量，不会重复。DFS(i,visited);//从顶点0开始深度优先搜索coutendl;}}delete[]visited;//释放visited}//从顶点位置v出发,以深度优先的次序访问所有可读入的尚未访问过的顶点。//算法中用到一个辅助数组visited,对已访问过的顶点作访问标记。templatetypenameT,typenameEvoidGraphT,E::DFS(intv,boolvisited[]){coutgetValue(v)'';//访问顶点vvisited[v]=true;//顶点v作访问标记intw=getFirstNeighbor(v);//找顶点v的第一个邻接顶点wwhile(w!=-1){//若邻接顶点w存在。注意邻接顶点数目不定if((21)){//若w未访问过,递归访问顶点w共8页第8页(22);}w=getNextNeighbor(v,w);//取v排在w后的下一个邻接顶点}}