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

1四川大学《数据结构与算法分析》课程习题及参考答案模拟试卷一一、单选题（每题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.5C.6D.85.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为()。A．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、E8.该二叉树的按层遍历的序列为()。EAGCBDF图12A．E、G、F、A、C、D、BB.E、A、C、B、D、G、FC.E、A、G、C、F、B、DD.E、G、A、C、D、F、B9.下面关于图的存储的叙述中正确的是()。A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?()A.a，g，h，m，n，p，q，x，zB.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分）1.写出下列中缀表达式的后缀形式：（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分别为：V={1,2,3,4,5,6,7};图23E={(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;i5;i++)Push(S,2*a[i]);while(!StackEmpty(S))coutPop(S)'';}该算法被调用后得到的输出结果为：2.voidABC(BTNode*BT,int&c1,int&c2){if(BT!=NULL){ABC(BT-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(______________________){cerrMemoryallocationfailare!endl;exit(1);}________________________=item;newptr-next=NULL;if(HL==NULL)HL=__________________________;else{LNode*P=HL;While(P-next!=NULL)____________________;4p-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）5.向上根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;jL.size-1;j++)L.list[j]=L.list[j+1];//第i个元素的下标为i-1L.size--;图35}模拟试卷二一、单选题（每题2分，共20分）1.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行()。A.HL=p;p-next=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.nB.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进制表示,m3)A．658B．648C．633D．6535.下列关于二叉树遍历的叙述中，正确的是()。A.若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6.k层二叉树的结点总数最多为().A．2k-1B.2K+1C.2K-1D.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.树是一种线性结构D.用一维数组存储一棵完全二叉树是有效的存储方法6二、填空题（每空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.在树中，一个结点的直接后继结点称为该结点的________