数据结构与算法分析习题及参考答案.doc 44页

'四川大学《数据结构与算法分析》课程习题及参考答案模拟试卷一一、单选题（每题2分，共20分）1.以下数据结构中哪一个是线性结构？()A.有向图　　B.队列C.线索二叉树　　D.B树2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下()语句序列。A.p=q;p->next=q;B.p->next=q;q->next=p;C.p->next=q->next;p=q;D.q->next=p->next;p->next=q;3.以下哪一个不是队列的基本运算？（）A.在队列第i个元素之后插入一个元素B.从队头删除一个元素C.判断一个队列是否为空D.读取队头元素的值4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成()个不同的字符串？A.14B.5　　C.6　　D.85.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为()。EAGCBDF图1A．11B.35C.19D.53以下6-8题基于图1。6.该二叉树结点的前序遍历的序列为()。A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C、D、F、B7.该二叉树结点的中序遍历的序列为()。A.A、B、C、D、E、G、FB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FE.B、D、C、A、F、G、E44 1.该二叉树的按层遍历的序列为()。A．E、G、F、A、C、D、B　　　B.E、A、C、B、D、G、FC.E、A、G、C、F、B、D　　　　D.E、G、A、C、D、F、B2.下面关于图的存储的叙述中正确的是()。A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关3.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?()A.a，g，h，m，n，p，q，x，z　B.a，g，m，h，q，n，p，x，zC.g，m，q，a，n，p，x，h，zD.h，g，m，p，a，n，q，x，z一、填空题（每空1分，共26分）1.数据的物理结构被分为_________、________、__________和___________四种。2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________;删除一个结点时，需要执行的操作是______________________________（假设栈不空而且无需回收被删除结点）。4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有双亲，则双亲结点的编号为________。5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整到____________位置为止。6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。7.表示图的三种常用的存储结构为_____________、____________和_______________。8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为____________，空间复杂度为___________。10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________个，其子树数目最少为________，最多为________。二、运算题（每题6分，共24分）图21.写出下列中缀表达式的后缀形式：（1）3X/(Y-2)+1（2）2+X*(Y+3)2.试对图2中的二叉树画出其：(1)顺序存储表示的示意图；(2)二叉链表存储表示的示意图。　　3.判断以下序列是否是小根堆?如果不是,将它调整为小根堆。（1）{12,70,33,65,24,56,48,92,86,33}（2）{05,23,20,28,40,38,29,61,35,76,47,100}4.已知一个图的顶点集V和边集E分别为：44 V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。一、阅读算法（每题7分，共14分）1.voidAE(Stack&S){InitStack(S);Push(S,3);Push(S,4);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a[5]={1,5,8,12,15};for(i=0;i<5;i++)Push(S,2*a[i]);while(!StackEmpty(S))cout<left,c1,c2);c1++;if(BT->left==NULL&&BT->right==NULL)c2++;ABC(BT->right,c1,c2);}//if}该函数执行的功能是什么？二、算法填空（共8分）向单链表的末尾添加一个元素的算法。VoidInsertRear(LNode*&HL,constElemType&item){LNode*newptr;newptr=newLNode;If(______________________){cerr<<"Memoryallocationfailare!"<next=NULL;if(HL==NULL)HL=__________________________;else{LNode*P=HL;While(P->next!=NULL)44 ____________________;p->next=newptr;}}一、编写算法（共8分）编写从类型为List的线性表L中将第i个元素删除的算法，（假定不需要对i的值进行有效性检查,也不用判别L是否为空表。）voidDelete(List&L,inti)模拟试卷一参考答案一、单选题（每题2分，共20分）1.B2.D3.A4.B5.B6.C7.A8.C9.B10.B二、填空题（每空1分，共26分）1.顺序链表索引散列2.O(n)O(1)3.p->next=HS;HS=pHS=HS->next4.2i2i+1ëi/2û（或i/2）图35.向上根6.2.97.邻接矩阵邻接表边集数组8.149.O(n)O(nlog2n)O(n)10.ém/2ù-1m-1ém/2ùm三、运算题（每题6分，共24分）1.(1)3X*Y2-/1+(2)2XY3+*+2.（1）012345678910111213141516123456789（2）见图3所示：3.(1)不是小根堆。调整为：{12,65,33,70,24,56,48,92,86,33}(2)是小根堆。4.普里姆算法从顶点1出发得到最小生成树为：(1,2)3,(1,3)5,(1,4)8,(4,6)4,(2,5)10,(4,7)20四、阅读算法（每题7分，共14分）1.302416102102.该函数的功能是：统计出BT所指向的二叉树的结点总数和叶子总数五、算法填空（共8分，每一空2分）newptr==NULLnewptr->=datanewptrp=p->next六、编写算法（8分）voidDelete(List&L,inti){for(intj=i-1;jnext=HL;B.p->next=HL->next;HL->next=p;C.p->next=HL;p=HL;D.p->next=HL;HL=p;2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（）个元素.A.n　B.n-1C.n+1D.不确定3.下述哪一条是顺序存储方式的优点？（）A．存储密度大B.插入和删除运算方便C.获取符合某种条件的元素方便D.查找运算速度快4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3)A．658B．648C．633D．6535.下列关于二叉树遍历的叙述中，正确的是()。A.若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6.k层二叉树的结点总数最多为().A．2k-1B.2K+1C.2K-1　　　D.2k-17.对线性表进行二分法查找，其前提条件是().A.线性表以链接方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.线性表以顺序方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检索频率排好序8.对n个记录进行堆排序，所需要的辅助存储空间为A.O（1og2n）　　B.O（n）　　C.O（1）D.O（n2）9.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（）个，A．1B．2C．3D．410.下列关于数据结构的叙述中，正确的是().A.数组是不同类型值的集合B.递归算法的程序结构比迭代算法的程序结构更为精炼C.树是一种线性结构44 A.用一维数组存储一棵完全二叉树是有效的存储方法一、填空题（每空1分，共26分）1.数据的逻辑结构被分为_________、________、__________和___________四种。2.一个算法的时间复杂度为(3n3+2000nlog2n+90)/n2，其数量级表示为________。3.对于一个长度为n的单链存储的队列，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。4.假定一棵树的广义表表示为A（D（E，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。5.后缀算式79230+-42/*的值为__________。中缀算式（3+X*Y）-2Y/3对应的后缀算式为_______________________________。6.在一棵高度为5的理想平衡树中，最少含有_______个结点，最多含有_______个结点。7.在树中，一个结点的直接后继结点称为该结点的________。一个结点的直接前趋结点称为该结点的________。8.在一个具有10个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。9.假定一个线性表为(12,17,74,5,63,49,82,36)，若按Key%4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。10.对一棵B_树进行删除元素的过程中，若最终引起树根结点的合并时，会使新树的高度比原树的高度___________。11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。12.在线性表的散列存储中，装填因子a又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则a等于________。二、运算题（每题6分，共24分）1．在如下数组A中链接存储了一个线性表，表头指针存放在A[0].next，试写出该线性表。A01234567data605078903440next40527132．已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ,中序遍历的结果是KBCDAFHIGJ,试画出这棵二叉树。3．已知一个图的顶点集V为：V={1,2,3,4,5,6,7};其共有10条边。该图用如下边集数组存储：起点1225522613终点6454767775权1122233457试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。4．画出向小根堆中加入数据4,2,5,8,3,6,10,1时，每加入一个数据后堆的变化。三、阅读算法（每题7分，共14分）1.在下面的每个程序段中，假定线性表La的类型为List，元素类型ElemType为int，并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。（1）InitList(La);Inta[]={100,26,57,34,79};For(i=0;i<5;i++)Insert(La,a[i]);44 TraverseList(La);（1）DeleteFront(La);InsertRear(La,DeleteFront(La));TraverseList(La);（2）ClearList(La);For(i=0;i<5;i++)InsertFront(La,a[i]);TraverseList(La);1.现面算法的功能是什么？voidABC(BTNode*BT){ifBT{cout<data<<"";ABC(BT->left);ABC(BT->right);}}一、算法填空（共8分）二分查找的递归算法。IntBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK){if___________________{intmid=(low+high)/2;if(_____________________)returnmid;//查找成功，返回元素的下标elseif(Kdata==item){returntrue;44 }elsep=p->next;returnfalse;}模拟试卷三一、单选题（每题2分，共20分）1.对一个算法的评价，不包括如下（）方面的内容。A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行()。A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;3.对线性表，在下列哪种情况下应当采用链表表示？()A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是()A.231B.321C.312D.1235.AOV网是一种（）。A．有向图B．无向图C．无向无环图D．有向无环图6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。A．低于链接法处理冲突B.高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。A．值B．函数C．指针D．引用8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。A．行号B．列号C．元素值D．非零元素个数9.快速排序在最坏情况下的时间复杂度为（）。A．O(log2n)B．O(nlog2n)C．0(n)D．0(n2)10.从二叉搜索树中查找一个元素时，其时间复杂度大致为()。A.O(n)B.O(1)C.O(log2n)D.O(n2)二、运算题（每题6分，共24分）1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。2.队列的插入操作是在队列的_________进行，删除操作是在队列的__________进行。3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是_____________________。4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7，列下标j从0到3，则二维数组W的数据元素共占用＿_____＿个字节。W中第644 行的元素和第4列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。1.广义表A=(a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。2.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的总和是_____________。3.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。4.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_____________个，其中_______________个用于指向孩子，_________________个指针是空闲的。5.若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[i]元素的左孩子元素为________,右孩子元素为_______________，双亲元素为____________。6.在线性表的散列存储中，处理冲突的常用方法有________________________和_____________________________两种。7.当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用________________________排序。一、运算题（每题6分，共24分）1.已知一个6´5稀疏矩阵如右所示，试：（1）写出它的三元组线性表；（2）给出三元组线性表的顺序存储表示。2.设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起，逐个输入各个数据而生成的二叉搜索树。3.对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树；4.已知一个图的顶点集V和边集E分别为：图6V={1,2,3,4,5,6,7};E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。二、阅读算法（每题7分，共14分）1.intPrime(intn){inti=1;intx=(int)sqrt(n);while(++i<=x)44 if(n%i==0)break;if(i>x)return1;elsereturn0;}(1)指出该算法的功能；(2)该算法的时间复杂度是多少？1.写出下述算法的功能：voidAJ(adjlistGL,inti,intn){QueueQ;InitQueue(Q);cout<adjvex;if(!visited[j]){cout<next;}}}一、算法填空（共8分）如下为二分查找的非递归算法，试将其填写完整。IntBinsch(ElemTypeA[],intn,KeyTypeK){intlow=0;inthigh=n-1;while(low<=high){intmid=_______________________________；if(K==A[mid].key)returnmid;//查找成功，返回元素的下标elseif(K<[mid].key)______________________________________;//在左子表上继续查找else__________________________________;//在右子表上继续查找}44 return-1;//查找失败，返回-1}一、编写算法（共8分）HL是单链表的头指针，试写出删除头结点的算法。ElemTypeDeleFront(LNode*&HL)模拟试卷三参考答案一、单选题（每题2分，共20分）1.B2.A3.B4.C5.D6.B7.D8.A9.D10.C二、填空题（每空1分，共26分）1.联系图（或图结构）2.尾首3.top==04.O（1）O（n）5.128441086.3365515132-145-2515637图77.有序n-18.有序序列后缀表达式（或逆波兰式）9.2nn-1n+110.2i+12i+2(i-1)/211.开放定址法链接法12.快速归并三、运算题（每题6分，共24分）1.（1）((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))(3分)（2）三元组线性表的顺序存储表示如图7示。图82.如图8所示。3.DFS：BFS：4.拓朴排序为：4365721四、阅读算法（每题7分，共14分）1.(1)判断n是否是素数（或质数）（2）O（）2.功能为：从初始点vi出发广度优先搜索由邻接表GL所表示的图。五、算法填空（8分）(low+high)/2high=mid-1low=mid+1六、编写算法（8分）44 ElemTypeDeleFront(LNode*&HL){if(HL==NULL){cerr<<"空表"<next;ElemTypetemp=p->data;deletep;returntemp;}模拟试卷四一、单选题（每题2分，共20分）1.以下数据结构中哪一个是线性结构？()A.有向图　　B.栈C.二叉树　　D.B树2.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用()存储方式最节省时间。A.单链表B.双链表C.带头结点的双循环链表D.单循环链表3.以下哪一个不是队列的基本运算？（）A.在队列第i个元素之后插入一个元素B.从队头删除一个元素C.判断一个队列是否为空D.读取队头元素的值4.字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成()个不同的字符串？A.15B.14　　C.16　　D.215.由权值分别为4,7,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为()。A．11B.37C.19D.53以下6-8题基于下面的叙述：若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。6.则该二叉树结点的前序遍历的序列为().A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C、D、F、B7.该二叉树有（）个叶子。A．3B.2　　C.5D.48.该二叉树的按层遍历的序列为()A．E、G、F、A、C、D、B　　　B.E、A、C、B、D、G、FC.E、A、G、C、F、B、D　　　　D.E、G、A、C、D、F、B9.下面的二叉树中，()不是完全二叉树。44 1.设有关键码序列(q，g，m，z，a)，下面哪一个序列是从上述序列出发建的小根堆的结果?()A.a，g，m，q，z　B.a，g，m，z,qC.g，m，q，a，zD.g，m，a，q，z一、填空题（每空1分，共26分）1.数据结构是指数据及其相互之间的______________。当结点之间存在1对N（1：N）的联系时，称这种结构为_____________________。2.一个广义表中的元素分为________元素和________元素两类。3.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。4.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是_________________;删除一个结点时，需要执行的操作是___________________________（假设栈不空而且无需回收被删除结点）。5.栈又称为_______________表，队列又称为___________表。6.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_________为主序、_________为辅序的次序排列。7.若一棵二叉树中只有叶子结点和左、右子树皆非空的结点，设叶结点的个数为K，则左、右子树皆非空的结点个数是________。8.以折半（或二分）查找方法从长度为8的有序表中查找一个元素时，平均查找长度为________。9.表示图的三种常用的存储结构为_____________、____________和_______________。10.对于线性表（78，4，56，30，65）进行散列存储时，若选用H（K）=K%5作为散列函数，则散列地址为0的元素有________个，散列地址为4的有_______个。11.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为____________，空间复杂度为___________。12.在n个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为________。WPL称为_____________________。13.在索引表中，若一个索引项对应主表的一个记录，则此索引为__________索引，若对应主表的若干条记录，则称此索引为________索引。二、运算题（每题6分，共24分）1.写出下列中缀表达式的后缀形式：（1）3X/(Y-2H)+1（2）2+X*(Y+3)2.假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结果。先序：中序：后序：44 按层：　　abcde1.已知一个无向图的顶点集为{a,b,c,d,e},其邻接矩阵如下所示(1)画出该图的图形；（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。2.已知一个图的顶点集V和边集E分别为：V={0,1,2,3,4,5,6,7};E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20};按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。一、阅读算法（每题7分，共14分）1.voidAE(Stack&S){InitStack(S);Push(S,3);Push(S,4);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a[5]={2,5,8,22,15};for(i=0;i<5;i++)Push(S,a[i]);while(!StackEmpty(S))cout<data;//查找成功returntrue;}elseif(itemdata)44 BST=BST->_____________;elseBST=BST->_____________;}//whilereturn_____________;//查找失败}一、编写算法（共8分）用递归的算法编写出对存入在a[n+1]数组中的n个有序元素进行二分（又称折半）查找（假定a[0]单元不用）的程序。inthalfsearch(SSTable*a,KeyTypek,intlow,inthigh)模拟试卷四参考答案一、单选题（每题2分，共20分）1.B2.C3.A4.B5.B6.C7.A8.C9.C10.B二、填空题（每空1分，共26分）1.联系树（或树结构）2.单（子）表3.O(n)O(1)4.p->next=HS;HS=pHS=HS->next5.先进后出先进先出6.行列7.k-18.2.6259.邻接矩阵邻接表边集数组10.2111.O(n)O(nlog2n)O(n)12.哈夫曼树带权路径长度13.稠密稀疏三、运算题（每题6分，共24分）1.(1)3X*Y2H*-/1+（2）2XY3+*+2.先序：a,b,c,d,e,f中序：c,b,a,e,d,f后序：c,b,e,f,d,a图9按层：a,b,d,c,e,f3.（1）该图的图形如图9示：（2）深度优先遍历序列为：abdce广度优先遍历序列为：abedc4.普里姆：(0,3)2,(0,2)5,(0,1)8,(1,5)6,(3,6)10,(6,4)4,(5,7)20四、阅读算法（每题7分，共14分）1.1522852102.该函数的功能是：44 求：一、算法填空（共8分，每一空2分）BST->dataleftrightfalse二、编写算法（8分）递归算法：inthalfsearch(SSTable*a,KeyTypek,intlow,inthigh){if(low>high)return0;else{intmid=(low+high)/2ifEQ(k,a[mid].key)returnmid;elseifLT(k,a[mid].key)returnhalfsearch(a,k,low,mid-1);elsereturnhalfsearch(a,k,mid+1,high);}}模拟试卷五一、单选题（每题2分，共20分）1.栈和队列的共同特点是()。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时().A.仅修改头指针　B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？()A.队列　　B.栈C.线性表　　D.二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。A．688B．678C．692D．6965.树最适合用来表示()。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为().A．2k-1B.2K+1C.2K-1　　　D.2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为()A.1，2，3B.9，5，2，344 C.9，5，3D.9，4，2，31.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A.O（1）　　B.O（n）　　C.O（1og2n）D.O（n2）2.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个，A．1B．2C．3D．43.设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。4.后缀算式923+-102/-的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。7.AOV网是一种___________________的图。8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。9.假定一个线性表为(12,23,74,55,63,40)，若按Key%4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。10.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。12.在快速排序、堆排序、归并排序中，_________排序是稳定的。三、运算题（每题6分，共24分）1.在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。A01234567data605078903440next3572041图102.请画出图10的邻接矩阵和邻接表。3.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。4.画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。44 一、阅读算法（每题7分，共14分）1.LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&L->next){q=L；L=L－>next；p=L；S1：while(p－>next)p=p－>next；S2：p－>next=q；q－>next=NULL；}returnL；}请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。2.voidABC(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout<data<<"";}}该算法的功能是：二、算法填空（共8分）二叉搜索树的查找——递归算法:boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失败else{if(item==BST->data){item=BST->data;//查找成功return___________;}elseif(itemdata)returnFind(______________,item);elsereturnFind(_______________,item);}//if}三、编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL,ElemTypex)44 模拟试卷五参考答案一、单选题（每题2分，共20分）1.A2.D3.D4.C5.C6.D7.D8.C9.D10.A二、填空题（每空1分，共26分）1.正确性易读性强壮性高效率2.O(n)3.9334.-134X*+2Y*3/-5.2nn-1n+16.e2e7.有向无回路8.n(n-1)/2n(n-1)9.（12，40）（）（74）（23,55，63）10.增加111.O(log2n)O(nlog2n)12.归并三、运算题（每题6分，共24分）1.线性表为：（78，50，40，60，34，90）2.邻接矩阵：邻接表如图11所示：图113.用克鲁斯卡尔算法得到的最小生成树为：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204.见图122224444 45552444238823584图12一、阅读算法（每题7分，共14分）1.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,…,an,a1）2.递归地后序遍历链式存储的二叉树。二、算法填空（每空2分，共8分）trueBST->leftBST->right三、编写算法（8分）intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i为计数器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循环时i中的值即为x结点个数returni;}//CountX模拟试卷六一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题1分，共10分）1．下面程序段for(i=1;i<=n;i++)for(j=1;j<=i;j++)x=x+1;的时间复杂度为（）。A）O(n)B）O(n2)C）O(n*i)D）O(n+i)2．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）。A）ABCDB）DCBAC）ACDBD）DABC3．当求链表的直接后继与求直接前驱的时间复杂度都相同时，此链表应为（）。44 A）单链表B）双向链表C）单向循环链表D）前面都不正确4．已知串s="BBABBABBA"，t="AB"，c="A"，执行置换操作REPLACE(s,t,c)后，s应为（）。A）"BBABABA"B）"BBAABA"C）"BBAAA"D）"BBABABBA"5．对于下图所示的二叉树，后序遍历结果序列为（）。A）A，B，C，D，E，F，G，HB）A，B，D，F，C，E，G，HC）D，F，B，A，C，G，E，HD）H，F，D，B，G，E，C，A6．下面AOE网中，关键路径长度为（）。A）16B）13C）10D）97．用Dijkstra算法求从源点到其它各顶点的最短路径的时间复杂度为（）。A）O(n)B）O(n2)C）O(n3)D）O(nlogn)8．在下列查找方法中，平均查找速度最快的是（）。A）顺序查找B）折半查找C）分块查找D）二叉排序树查找9．哈希表的地址区间为0~17，哈希函数为H(K)=K%17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到哈希表中。则59存放在哈希表中的地址是()。A）8B）9C）10D）1110．快速排序算法的平均时间复杂度是（）。A）O(n)B）O(n2)C）O(nlog2n)D）O(log2n)二、填空题（每空1分，共15分）1．设有一个记录r，设其类型为LNode，则r实际所占用的存储空间的大小为()。2．一个算法的时间复杂度为(5n3-3nlog2n+7n-9)/(6n)，其数量级表示为()。3．如将n×n的对称矩阵压缩存储于sa[k]中，则k等于（）。44 4．如一二维数组A[1..m，1..n]按行排列，设A[1,1]的相对位置为0，每个元素的大小为1，则任一元素A[i，j]的地址为()。5．线性表的顺序存储结构中存取元素的时间复杂度为是（）。6．队列的插入操作在()进行，删除操作在()进行。7．后缀表达式“45*32++”的值为（）。8．对于一棵具有n个结点的树，此树中所有结点的度数之和为（），设叶子结点数为n0，度为二的结点数为n2，则它们之间的关系为（）。9．在一个无向图中，所有顶点的度数之和等于所有边数的()倍。10．在一个具有n个顶点的无向完全图中，包含有()条边；在一个具有n个顶点的有向完全图中，包含有()条弧。11．每次从无序表中取一个最小或最大元素，把它们交换到有序表的一端，此种排序方法称为()排序。12．一种抽象数据类型应包括数据和()两大部分。三、判断改错题（判断正误，将正确的划上“√”，错误的划上“×”，每小题1分，共10分）1．从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。（）2．数组可看成线性结构的一种推广，所以可对数组进行插入与删除操作。（）3．在删除链表结点时，计算机能自动地将其后继的各个结点向前移动。（）4．利用栈求表达式的值时，设立操作数栈OPND，设OPND只有2个存储单元，则表达式(A-B)*C+D将不会发生发生上溢现象。（）5．串是n个字母的有限序列（n>=0）。（）6．n阶下三角矩阵的非零元素的个数最多为。（）7．二叉树只能采用二叉链表来存储。（）8．图G的某一最小生成树的代价一定小于其它生成树的代价。（）9．B+树是一种特殊的二叉树。（）10．所有的简单排序（即时间复杂度为O(n2)的排序）都是稳定排序。（）四、简答题（每小题4分，共20分）1．对于下列双向链表，设结构为(prior,data,next)，结点类型为lnode，试写出在p所指结点之前插入元素x的语句序列。2．对于下图，用Prim算法从结点1出发构造出一棵最小生成树，要求图示出每一步的变化情况。3．已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。44 先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI4．给定一组权值{3，4，7，14，15，20}，试画出相应的哈夫曼树，并计算带树路径长度WPL的值。5．有关键字序列{7,23,6,9,17,19,21,22,5}，Hash函数为H(key)=key%5，采用链地址法处理冲突，试构造哈希表。五、算法题（共25分）1．程序填空题(每空2分，共8分)下面程序的功能是二叉树的中序遍历的非递归算法，其中二叉树的结点结构为(lchild,data,rchild)，栈的常用方法有：入栈Push，出栈Pop，判空StackEmpty；试将程序补充完整。templateBiTreeNode*BiTree::GoFarLeft(BiTreeNode*T,Stack*>&S){if(!T)returnNULL;while(T->lchild){Push(S,T);T=;}returnT;}templatevoidBiTree::Inorder(BiTreeNode*T,void(*visit)(Type&e)){Stack*>&S;t=GoFarLeft(T,S);//找到最左下的结点while(t){visit(t->data);if(t->rchild)t=GoFarLeft(,S);elseif(!StackEmpty(S))t=;elset=;//栈空表明遍历结束}//while}//Inorder2．程序填空题(每空2分，共8分)下面程序的功能是用线性探测再散列处理冲突（即Hi=(H(key)+i)%m），哈希函数为H(key)=key%m，进行哈希表的插入算法。（如表中已存在关键字相同的记录或无插入位置，则不进行插入），试将程序补充完整。typedefenum{SUCCESS,UNSUCCESS,OVERFLOW}Status;templatetypedefstruct{Type*elem;intm;44 }HashTable;templateStatusSerchHashTable(HashTableH,Typee){inti=0,k=;//i为冲突的次数,k为哈希函数的值while(ielem.key!=e.key){;p=(p+i)%m;}//whileif(i>=m)returnOVERFLOW;elseif(p->elem.key!=e.key)return;else{H.elem[p].elem=;returnSUCCESS;}//if}//SerchHashTable3．（9分）阅读下面算法，试回答：（1）根据邻接表画出对应的图；（2）当图的邻接表如下时，执行算法T(g,1)时，输出的结果是什么？（3）函数T的功能是什么？图的邻接表为：templatevoidAdjGraph::T(AdjGraphg;inti){ArcNode*p;cout<adjvex])T(p->adjvex);p=p->next;}//while}//T六、写算法（共20分）1．(12分)以单链表为存储结构实现简单选择排序，排序的结果是单链表按关键字值升序排序，试编写此算法。算法申明如下：44 templatevoidLinkList::SimpleSelectSort(Lnode*la)2．(8分)下面是一个二叉树的中序遍历的递归算法，试改写此算法，消去第二个递归调用MidOrder(T->rchild,visit)。templatevoidBiTree::PreOrder(BiTreeNode*T,void(*Visit)(Type&e)){if(T){MidOrder(T->lchild,Visit);Visit(T->data);MidOrder(T->rchild,Visit);}//if}//MidOrder模拟试卷六参考答案_一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题1分，共10分）1．B）2．D）3．B）4．A）5．D）6．A）7．B）8．B）9．D）10．C）二、填空题（每空1分，共15分）1．参考答案：sizeof(LNode)2．参考答案：O(n2)3．参考答案：4．参考答案：(i-1)*n+j-15．参考答案：O(1)6．参考答案：队尾队头7．参考答案：258．参考答案：n-1n0=n2-19．参考答案：210．参考答案：n(n-1)/2n(n-1)11．参考答案：选择（直接选择排序或堆排序）12．参考答案：操作三、判断改错题（判断正误，将正确的划上“√”，错误的划上“×”，每小题1分，共10分）1．参考答案：√2．参考答案：×3．参考答案：×4．参考答案：√5．参考答案：×6．参考答案：√7．参考答案：×44 8．参考答案：×9．参考答案：×10．参考答案：×四、简答题（每小题4分，共20分）1．参考答案：s=newlnode;s->data=x;p->prior->next=s;s-prior=p->prior;s->next=p;p->prior=s;2．参考答案：本题用Prim算法构造出最小生成树共需四步，具每一步的变化情况如如：3．参考答案：4．参考答案：哈夫曼树如下图所示：WPL=20*2+15*2+14*2+7*3+3*4+4*4=1475．参考答案：哈希表如下图所示：44 五、算法题（共25分）1．参考答案：T->lchildt->rchildPop(S)NULL2．参考答案：e.key%m++iUNSUCCESSe3．(1)参考答案：（2）参考答案：V1V2V4V3（3）参考答案：从顶点Vi出发进行深度优先搜索图。六、写算法（共20分）1．参考答案：templatevoidLinkList::SimpleSelectSort(Lnode*la)//用单链表为存储结构实现选择排序Lnode*p,q;Typex;if(la->next){p=la->next;while(p->next){minp=p;q=p->next;while(q){if(minp->data>q↑.data)minp=q;q=q->next;}//whileif(minp!=p{x=p->data;p->data=minp->data;minp->data:=x;}//ifp=p->next;}//while}//if}//SimpleSelectSort2．参考答案：44 templatevoidBiTree::MidOrder(BiTreeNode*T,void(*Visit)(Type&e)){while(T){MidOrder(T->lchild,Visit);Visit(T->data);T=T->rchild;}//while}//MidOrder模拟试卷七一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题1分，共10分）1．假设执行语句S的时间为O（1），则执行下列程序段for(i=1;i<=n;i++)for(j=i;j<=n;j++)S;的时间为()A）O（n）B）O（n2）C）O（n*i）D）O（n+i）2．设栈最大长度为3，入栈序列为1，2，3，4，5，6，则不可能的出栈序列是（）。A）1，2，3，4，5，6B）2，1，3，4，5，6C）3，4，2，1，5，6D）4，3，2，1，5，63．设单链表的结点结构为(data,next)，已知指针q所指结点是指针p所指结点的直接前驱，如在*q与*p之间插入结点*s，则应执行的操作为（）。A）s->next=p->next;p->next=s;B）q->next=s;s->next=p;C）p->next=s-next;s->next=p;D）p->next=s;s-next=q;4．串S="ABCDEF"的串长为（）。A）3B）4C）7D）85．下面二叉树按（）遍历得到的序列是FEDBIHGCA。A）先序B）中序C）后序D）层次44 6．用Floyd算法求每一对顶点之间的最短路径的时间复杂度为（）。A）O(n)B）O(n2)C）O(n3)D）O(nlogn)7．具有n个顶点的无向图，它可能具有的边数的最大值为（）。A）(n2+n)/2B）n2C）(n2-n)/2D）n8．二分查找法要求被查找的表是（）。A）顺序表B）链接表C）顺序表且是按值递增或递减次序排列D）不受上述的任何限制9．在一待散列存储的线性表（18，25，63，50，42，32，90），若选用h(k)=k%7作为散列函数，则与元素18冲突的元素有()个。A）0B）1C）2D）310．在下列排序算法中，不稳定的是（）。A）直接插入排序B）折半插入排序C）归并排序D）直接选择排序二、填空题（每空1分，共15分）1．当一个传值型形式参数所占空间较大时，最好说明为()，以节省参数值传输时间和存储参数的空间。2．一个算法的时间复杂度为(5n6-3n2log2n+7n-9)/(3n2+1)，其数量级表示为()。3．有一矩阵为a[-3:1,2:6]，每个元素占一个存储单元，存储的首地址为100，以行序为主，则元素a(-1,4)的地址为（）。4．一维数组的逻辑结构是（）。5．在有n个结点的单链表la中，删除指定结点p的操作delete(la,p)的时间复杂度为（）。6．栈的插入与删除操作在()进行，出栈操作时，需要修改()。7．表达式3*(x+2)-5的后缀表达式为（）。8．对于一个具有9个结点的二叉树的最小深度为()，最大深度为()。9．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要()条边。10．表示图的最常用两种存储结构是()与()。11．每次从无序表中取一个元素，把它插入到有序表中的适当位置，此种排序方法称为()排序。12．已知一有序表（13，20，25，37，48，58，61，78，83，90，128），当二分查找值48的元素时，经过（）次比较后查找成功。三、判断改错题（判断正误，将正确的划上“√”，错误的划上“×”，每小题1分，共10分）1．数据的逻辑结构是指数据元素之间的逻辑关系。（）2．数组不是一种随机存取结构。（）3．顺序表在物理存储空间中一定是连续的。（）4．设一个栈的入栈序列是ABCD，则借助于一个栈能得出栈序列ACDB。（）5．串的长度是指串中不同字符的个数。（）44 6．矩阵压缩存储的方法都是用三元组表存储矩阵元素。（）7．结点数为n的完全二叉树的深度为log2n+1。（）8．在一个有向图的邻接表中，如果某个顶点的链表为空，则此顶点的度一定为零。（）9．在顺序表中取出第i个元素所花费时间与i成正比。（）10．在快速排序算法中，取待排序的n个记录中的某个记录（如第一个记录）的键值为基准，将所有记录分为两组，此记录就排在这两组的中间，这也是此记录的最终位置。（）四、简答题（每小题4分，共20分）1．在双向循环链表中p所指结点之后插入s所指结点，设结点结构为(priou,data,next)，试给出语句序列。2．对于下图，用Kruskal算法构造出一棵最小生成树，要求图示出每一步的变化情况。3．已知一棵二叉树的后序序列与中序序列分别为DBECA与BDAEC，试画出此二叉树。4．对于权值序列w={1,10,8,5,3,1,3}，试画出它对应的哈夫曼树。5．已知关键字序列{12,26,38,89,56}，试构造平衡二叉树。五、算法题（共25分）1．程序填空题(每空2分，共8分)下面程序的功能是二叉树的层次遍历的非递归算法，其中二叉树的结点结构为(lchild,data,rchild)，队列的常用方法有：入队EnQueue，出队DlQueue，判空QueueEmpty；试将程序补充完整。templatevoidBiTree::levelorder(BiTreeNode*T,void(*Visit)(Type&e)){Queue*>&Q;BiTreeNode*pEnQueue(Q,T);;while(!){;if(p->lchild){EnQueue(Q,p->lchild);visit(p->lchild->data)}if(){EnQueue(Q,p->rchild);visit(p->rchild->data)}}//while}//levelorder2．程序填空题(每空2分，共8分)44 下面程序的功能是用链地址法处理冲突，哈希函数为H(key)=key%m，进行哈希表的插入算法。（如表中已存在关键字相同的记录，则不进行插入），试将程序补充完整。typedefenum{SUCCESS,UNSUCCESS}Status;templatetypedefstructNode{Typeelem;structNode*next;}Node,*LinkList;templatetypedefstruct{LinkList*head;intm;}HashTable;templateStatusSerchHashTable(HashTableH,Typee){intk=e.key%m;Node*pre=NULL,*p=H[k].head;while(p&&p->elem.key!=e.key){pre=p;p=;}//whileif(!p){Node*q=newNode;q->elem=;pre->next=;q->next=NULL;//将q追加在相应链表的末尾returnSUCCESS;}elsereturn;}//SerchHashTable3．(9分)阅读下面的算法，试回答：（1）此算法的功能是什么？（2）变量c的结果表明什么？（3）对于如下的有向图，执行此算法后c的值是多少？templateintMGraph::cid(MGraphg){//g是有向图的邻接数组存储结构inti,j,c=0;for(j=0;j=g.vexnum)c++}//forreturnc;}//cid六、写算法（共20分）1．(12分)以单链表为存储结构实现直接插入排序，排序的结果是单链表按关键字值升序排序，试编写此算法。算法申明如下：templatevoidLinkList::StraitInsertSort(Lnode*la)2．(8分)下面是一个二叉树的前序遍历的递归算法，试改写此算法，消去第二个递归调用PreOrder(T->rchild,Visit)。templatevoidBiTree::PreOrder(BiTreeNode*T,void(*Visit)(Type&e)){if(T){Visit(T->data);PreOrder(T->lchild,Visit);PreOrder(T->rchild,Visit);}//if}//PreOrder模拟试卷七参考答案一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题1分，共10分）1．B）2．D）3．B）4．C）5．C）6．C）7．C）8．C）9．C）10．D）二、填空题（每空1分，共15分）1．参考答案：引用型2．参考答案：O(n4)3．参考答案：1124．参考答案：线性结构5．参考答案：O(n)6．参考答案：栈顶栈顶指针7．参考答案：3x2+*5-8．参考答案：499．参考答案：n-110．参考答案：邻接知阵邻接表11．参考答案：插入12．参考答案：444 三、判断改错题（判断正误，将正确的划上“√”，错误的划上“×”，每小题1分，共10分）1．参考答案：√2．参考答案：×3．参考答案：√4．参考答案：√5．参考答案：×6．参考答案：×7．参考答案：×8．参考答案：×9．参考答案：×10．参考答案：√四、简答题（每小题4分，共20分）1．参考答案：在双向循环链表中p所指结点之后插入s所指结点的指针变化图示如下：出语句序列如下：p->next->priou=s;s->next=p->next;s->priou=p;p->next=s;2．参考答案：（只要考生正确写出其中任四步即给满分）本题用Kruskal算法构造出最小生成树共需五步，具每一步的变化情况如如：44 3．参考答案：4．参考答案：5．参考答案：如下图所示：五、算法题（共25分）1．参考答案：Visit(T->data)QueueEmpty(Q)DlQueue(Q,p)p->rchild2．参考答案：p->nexteqUNSUCCESS3．（1）参考答案：求图中入度为零的顶点数。（2）参考答案：图中入度为零的顶点数。（3）参考答案：2六、写算法（共20分）1．参考答案：44 templatevoidLinkList::StraitInsertSort(Lnode*la)//用单链表实现直接插入排序Lnode*p,*q,*pre,*t;Typex;if(la->next){q=la->next->next;la->next->next=NULL;while(q){pre=la;p=la->next;x=q->data;while(p&&x>=p->data){pre=p;p=p->next;}//whilet=q;q=q->next;pre->next=t;t->next=p;}//while}//if}//StraitInsertSort2．参考答案：templatevoidBiTree::PreOrder(BiTreeNode*T,void(*Visit)(Type&e)){while(T){visit(T->data);PreOrder(T->lchild,Visit);T=T->rchild;}//while}//PreOrder模拟试卷八一、单项选择题(在下列每小题四个备选答案中选出一个正确答案，并将其字母标号填入题干的括号内。每小题2分，共30分)1．若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是()A．O(1)B．O(n)C．O(n2)D．O(nlog2n)2．在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则平均比较()个结点。A．nB．n／2C．(n-1)／2D．(n+1)／244 3．研究数据结构就是研究()A．数据的逻辑结构B．数据的存储结构C．数据的逻辑结构和存储结构D．数据的逻辑结构、存储结构及其数据在运算上的实现4．为了方便地对图状结构的数据进行存取操作，则其数据存储结构宜采用()方式。A．顺序存储B．链式存储C．索引存储D．散列存储5．二维数组A[10．．20，5．．10]采用行序为主序方式存储，每个数据元素占4个存储单元，且[A10，5]的存储地址是1000，则A[18，9]的地址是()A．1208B．1212C．1368D．13646．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有()个结点。A．13B．12C．26D．258.设无向图G=(V，E)和C’=(V’,E’)，如C’为G的生成树，则下面不正确的说法是()A.C’为C的连通分量B．C’为C的无环子图C．C’为C的子图D.C’为C的极小连通子图且V’=V9．下列说法中不正确的是()A.无向图中的极大连通子图称为连通分量B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D．有向图的遍历不可采用广度优先搜索方法10．对有序表(18，20，25，34，48，62，74，85)用二分查找法查找85，所需的比较次数为()A．1次B．2次C．3次D．4次11．散列表的平均查找长度()A．与处理冲突方法有关而与表的长度无关B．与处理冲突方法无关而与表的长度有关C．与处理冲突方法有关且与表的长度有关D．与处理冲突方法无关且与表的长度无关12．对ISAM文件的删除记录时，一般()44 A．只需做删除标B．需移动记录C.需改变指针D．一旦删除就要做整理13.顺序文件适宜于()A．直接存取B．成批处理C．按关键字存取D．随机存取14．一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用()方法。A．快速排序B．堆排序C．插入排序D．二路归并排序15．对下列四个序列用快速排序方法进行排序，以序列的第一个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列()A．70，75，82，90，23，16，10，68   B．70，75，68，23，10，16，90，82C．82，75，70，16，10，90，68，23   D．23，10，16，70，82，75，68，90二、填空题(每空2分，共26分)1．下列程序段的时间复杂性的量级为__________。for(i=0；idata=x；______________;q->next=p;4．设链栈的栈顶指针为ls，栈不空的条件为___________5．遍历图的基本方法有深度优先搜索和广度优先搜索。其中，____________是一个递归过程。7．下图为某树的静态双亲链表表示：则结点D、E的双亲结点分别为_________。 0  A  -1 1  B  0 2  C  044 3  D  14  E  29．静态查找表的顺序查找算法中，通常采用设置岗哨的方式以确保查找不成功时循环也能终止执行，若给定值为K，表的长度为n，查找表的数据单元用R.item表示，键值用key表示，则在表尾设置岗哨的相应方法描述为_________。10．对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的_________上继续查找。11．采用二次探测法解决冲突问题，对于键值为K、容量为m的闭散列表，若散列地址为d0，则发生冲突后，其第三个后继散列地址d3为___________。12．对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较________次。13.对n个元素进行冒泡排序时，最少的比较次数是___________。三.应用题（共30分）1．已知序列(17，18，60，40，7，32，73，65，85)，请给出采用冒泡排序法对该序列作升序排序时每一趟的过程。(6分)2．如图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F能否在栈的输出端得到序列DCFKBA及EDDFCA?若能，给出栈操作的过程，若不能，简述其理由。(8分)44 5．设散列函数为H(K)=Kmod11，散列表长度为11(散列地址空间0．．10)，给定表(SUN，MON，TUE，WED，THU，FRI，SAT)中，取单词的第一个字母在英语字母表中的序号为键值K，构造一开散列表，并用拉链法解决有关地址冲突。(7分)四、设计题（共14分）1.设以二叉链表为二叉树的存储结构,结点的结构如下:lchilddatarchild求二叉树中叶子结点的数目2.已知奇偶转换排序如下所述:第一趟对所有奇数i,a[i]和a[i+1]进行比较,第二趟对所有偶数i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>a[i+1],则将两者交换,以后重复上述二趟过程交替进行,直至整个数组有序。（1）试问：排序结束的条件是什么？（2分）（2）编写一个实现上述排序过程的算法：voidoesort(inta[],intn)。44 其中data域为整数,试设计一个算法voidchange(bitreptrr):若结点左孩子的data域的值大于右孩子的data域的值,则交换其左、右子树。（6分）模拟试卷八参考答案一、单项选择题(每小题2分，共30分)1.C2.D3.D4.B5.A6.D7.B8.A9.D10.D11.C12.A13.B14.B15.A二、填空题(每空2分，共26分)1.O(m*n)2.索引表3.p->next=q->next;4.Ls!=NUUL5.深度优先搜索6.pop(s),push(s,5)7.B、Ｃ8.A、D、G9.R.item[n+1].key=k10.左子树11.(do+2)%m12.313.n-1三、应用题(共30分)1.(6分)依题意：1趟(17,18,60,40,7,32,73,65,85)2趟(17,18,40,7,32,60,65,73,85)3趟(17,7,18,32,40,60,65,73,85)4趟(7,17,18,32,40,60,65,73,85)5趟(7,17,18,32,40,60,65,73,85)第5趟元素未交换,则排序结束。(各1分)2.(8分)1.能得到序列:DCFEBA(1分)操作过程如下:push,push,push,push,pop,pop,push,push,pop,pop,pop,pop(4分)44 2.不能得到序列:EDBFCA(1分)因为要得到E需将A,B,C,D顺序入栈,根据LIFO原则,不可能A在C之前出栈(2分)3.(6分)先序遍历序列:ABCDFGHE中序遍历序列:BADGFHCE后序遍历序列:BGHFDECA★各2分4.(3分)V2V4V0V1V344 5.(7分)012345678910^^^^^^SATWED^MON^FRI^SAT^SUNTHU^TUE四、设计题(共14分)1.(6分)：intLeafCount_BiTree(BitreeT)//求二叉树中叶子结点的数目{  if(!T)return0;//空树没有叶子  elseif(!T->lchild&&!T->rchild)return1;//叶子结点  elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree44 2.(8分)：voidOE_Sort(inta[],intn)//奇偶交换排序的算法{  change=1;  while(change)  {    change=0;    for(i=1;ia[i+1])      {        a[i]<->a[i+1];        change=1;      }    for(i=0;ia[i+1])      {        a[i]<->a[i+1];        change=1;      }  }//while}//OE_Sort分析:本算法的结束条件是连续两趟比较无交换发生44'