数据结构清华大学模拟试题一答案

数据结构清华大学模拟试题一答案数据结构清华大学模拟试题一答案数据结构清华大学模拟试题一答案清华大学模拟试题一一．单项选择题（2分/题）1．一个栈的输入序列为12345，则以下序列中是栈的输出序列的是（）。知道这题的解题思路吗？A.23415B.54132C.31245D.142532．设循环行列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（）。A.r-fB.r-f+1C.(r-f)modn+1D.(r-f+n)modn3．二叉树在线索化后，仍不可以有效求解的问题是（）。这题是线索化问题，可能你没看过。可以等我去给你讲。A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前驱D.后序线索二叉树中求后序后继4．求最短路径的FLOYD算法的时间复杂度为（）。（那Djstla的时间复杂度呢？）A.O(n)B.O(n+e)C.O(n2)D.O(n3)5．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（）。（知道是哪个指针域吗？就是最后一个接见的节点的右指针，由于它没有后继节点。）A.0B.1C.2D.不确立6．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先次序储蓄在初步地点为1000的连续的内存单元中，则元素A[5,5]的地点为（）。这题可要会哟@A.1140B.1145C.1120D.11257．在以下排序算法中，在待排序的数据表已经为有序时，开支时间反而最多的是（）。(要知道为何，这个我跟你讲过)A.迅速排序B.希尔排序C.冒泡排序

D.堆排序8．对有18个元素的有序表做折半查找，则查找A[3]标挨次为（）。（这题的数组下标应当说明一下是

的比较序列的下A[1..18]）A.1-2-3

B.9-5-2-3

C.9-5-3

D.9-4-2-39．以下排序算法中，某一趟结束后未必能选出一个元素放在其最后地点上的是（）。这些题出的都不错！A.堆排序B.冒泡排序C.迅速排序D.直接插入排序10．在均衡二叉树中插入一个结点后造成了不均衡，设最低的不均衡点为A，并已知A的左孩子的均衡因子为-1，右孩子的均衡因子为0，则做（）型调整以使其均衡。A.LLB.LRC.RLD.RR二．判断题（1分/题）1.（）线性表的长度是线性表所占用的储蓄空间的大小。2.（）双循环链表中，随意一结点的后继指针均指向其逻辑后继。3.（）在对链行列做出队操作时，不会改变front指针的值。4.（）假如两个串含有同样的字符，则说它们相等。5.（）假如二叉树中某结点的度为1，则说该结点只有一棵子树。6.（）已知一棵树的先序序列和后序序列，必定能结构出该树。7.（）图G的一棵最小代价生成树的代价未必小于G的其余任何一棵生成树的代价。8.（）图G的拓扑序列独一，则其弧数必为n-1（此中n为极点数）。9.（）对一个堆按层次遍历，不用然能获得一个有序序列。10.（）直接选择排序算法知足：其时间复杂度不受数据的初始特色影响，为O(n2)。三．填空题（2分/空）1．已知完满二叉树的第8层有8个结点，则其叶子结点数是（68）。2．将下三角矩阵A[1..8,1..8]的下三角部分逐行地储蓄到初步地点为1000的内存单元中，已知每个元素占4个单元，则A[7,5]的地点是1100）。3．有n个极点的强连通有向图G最罕有（n）条弧。4．有n个结点而且其高度为n的二叉树的数量是（2n-1）。5．高度为8的均衡二叉树的结点数最少是（54）。6．3个结点可组成（3）棵不同样形态的树。7．对以以下图所示的网，履行prim算法可获得最小生成树，试在下表的空白处填上适合的内容，以说明该算法的履行过程。极点134UV(U,V)(2,1)(2,3)(2,4){2}{1,3,4}1代价4215(U,V)(4,1)(2,3){2,4}{1,3}5代价5434(U,V)(3,1){2,4,3}{1}代价142(U,V){2,4,3,1}{}2代价8．设散列表函数为H(key)，用拉链法解决矛盾，H的值域为0,...,n-1，结构的散列表种类以下：TYPElink=^node;node=RECORDkey:keytype;next:link;...END;openhash=array[0..n-1]oflink;K的结请在以下算法划线处填上适合内容，以达成查找键值等于点，若查找成功，返回该结点的指针，不然返回空指针。FUNCresearch(K:keytype;HP:openhash):link;i:=H(K);SUC:=false;p:=HP[i];while(p<>nil)andnot(SUC)doifp^.key<>Kthenp:=p^.nextelseSUC:=true;return(p)ENDC;{researsh}四．应用题（5分/题）1．对下边两棵二叉树，分别画出它们的次序储蓄结构。AABCBCDEFGDEFIJKIJ123456789101234567891011ABCDEFGIJKABCDEFIJ2．设图G=(V,E),V={1,2,3,4,5,6},E={<1,2>,<1,3>,<2,5>,<3,6>,<6,5>,<5,4>,<6,4>}。请写出图G中顶点的全部拓扑序列。1---2---3---6---5---41253---2---6---5---43646---2---5---43．对下边3阶B-树挨次履行以下操作，画出每步的操作结果。插入300100（1）插入7050200（2）插入303）删除15010406080150260（1）1005020010406080150260300（2）1005070200104060801502603003）501003070200104060801502603004）501003070260104060802003004．求出下边AOE网中的重点路径，要求注明每个极点的最早和最迟发生时间，并画出重点路径。267627453344533545451382105422310618466622542547947912345678910e0454101113141318五．算法设计题（10分/题）1．设计算法将一个带头结点的单循环链表A分解为两个拥有同样结构的链表B和C，此中B表中结点为A表中值为奇数的结点，而C表中结点为A表中值为偶数的结点（要求利用原表结点）。算法思想：B表头结点利用A表头结点；为C表产生一个头结点。从A的首元结点检查每个结点应插入B表仍是C表，进而从A表取下，做响应的插入操作。设节点定义以下：structnode{intkey;structnode*next;}则算法以下：voidgive_b_c( ){structnode*B,*C;B=A;//此刻B和A是一回事，马上奇数留下，偶数取出来放到C中C=(structnode*)malloc(sizeof(structnode));p1=B;p2=p1->next;q=C;//p1p2是B上的工作指针q是

C上的工作指针while(p2!=B){if(p2->keymod2==0)

//偶数则放入

C中{p1->next=p2->next;q->next=p2;q=p2;p2=p1->next}else{p1=p2;p2=p1->next;}

奇//数则不变}q->next=C;}2．设计算法判断无向图G是不是连通的，若连公则返回true，不然返回false。可以使用以下几个函数调用：firstadj(G,v)—返回图G中极点v的第一个毗邻点，若不存在返回0nextadj(G,v,w)—返回图G中极点v的毗邻点中处于w今后的毗邻点，若不存在返回0nodes(G)—返回图G中的极点数算法思想：从某个极点出发深度/广度遍历。设协助数组visited[max]则算法以下：booltotal_search_dfs(GraphG)//这里bool的定义缺省了，这是算法与程序的差异{for(i=0;i<node(G);i++)visited[i]=false;son_search_dfs(G,0);从//第一个元素开始深度遍历，自然，从任何一个都行for(i=0;i<node(G);i++)if(visited[i]==false)returnfalse;returnture;}voidson_search_dfs(GraphG,inti){visited[i]=true;p=firstadj(G,i);while(p){ifvisited[p->adjvex]==falseson_search_dfs(G,p->adjvex);p=nextadj(G,i,p)}}3．已知数组A[1..n]的元素递加有序，试设计算法以数组造一棵二叉排序树，并使其知足均衡二叉树的条件。算法思想：递归算法，以居中的元素作为根结点。设二叉树节点结构定义以下：

A中的元素构structnode{structnode*lchild,*rchild;intkey;}则算法以下：voidget_sort(structnode*root;intlow,high){root=null;while(low<=high){mid=(low+high)/2;root=(structnode*)malloc(sizeof(structnode));root->key=A[mid];get_sort(root->lchild,low,mid-1)