数据结构作业答案

第一次作业：1.下列算法程序的时间复杂度是0(1)y=4;x=2;while(y8)if(x==5){x=1;y+=x;}elsex++;2.写出下列算法的时间复杂度：0(log2n)i=1;while(i=n)i=i*2;第二次作业：1．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是s-next=p-next;p-next=s;。2.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是head-next==NULL。3.线性表L={a1,a2,…,an}采用顺序存储，假定在不同的n个位置上删除的概率相同，则删除一个新元素平均需要移动的元素个数是__N-1/2_______，假定在不同的（n+1）个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是____N/2____。4.数组的第一个元素的存储地址是100，每个元素长度是4，则第8个元素的地址是128。5．在循环链表中插入结点操作（在第i个位置处插入结点s，数据域为t）。算法如下所示，请在空格处填入正确的语句。voidInsert(CNODE*h,inti,intt,int*len){CNODE*p=h-next,*s;intj=1;if(i*len+1||i1)return;while(p!=h&&ji-1){p=p-next;j++;}s=(CNODE*)malloc(sizeof(CNODE));/*创建结点*/s-data=e;;s-next=p-next;;p-next=s;;*len=*len+1;}6.设计一个算法，功能：在单链表中删除第i个结点开始的连续k个结点的操作。(参考书本中算法：在单链表中删除第i个结点)第三次作业：1.一个栈的入栈序列是1、2、3、4、5,则栈不可能的输出序列是___A___。A.43512B.54321C.12345D.453212.设有一空栈，栈顶指针为1000H，现有输入序列为12345，PUSH(进栈),POP(出栈),PUSH,PUSH,PUSH,POP,PUSH,POP后，输出序列为____145____。3.对于队列操作数据的原则是___先进先出_________。4.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是___3__。5.循环队列判空条件是front==rear，判满条件是(rear+1)%M==front。6.设计一个算法，功能：十进制转换成二进制。(参考书本中算法：十进制转换成八进制)第四次作业：1.两个字符串相等的充要条件：两个串的长度相等，并且对应位置的字符都相等。2.设有二维数组A[20][10]，其每个元素占3个字节，第一个元素A[0,0]的存储地址为2000，（1）若按行优先顺序存储时元素A[5,3]的存储地址为多少?（2）若按列优先顺序存储时元素A[3,5]的存储地址为多少?参考第五章ppt的第10页3．广义表A=（a,b,c,（d,（e,f））），（Head与Tail分别是取表头和表尾的函数）则Head(Tail(Tail(Tail(A))))式子的值为（d,（e,f））。4.写一算法，利用数组实现两个矩阵的相乘。两个矩阵0001020n1011121nm0m1m2mnaaaaaaaaaaaaa，0001020m1011121mn0n1n2nmbbbbbbbbbbbbb，则两个矩阵相乘的结果矩阵r等于0001020m0001020n0001020m1011121m1011121n1011121mm0m1m2mmm0m1m2mnn0n1n2nmrrrraaaabbbbrrrraaaabbbbrabrrrraaaabbbb在上式中，r00=a00b00+a01b10+a02b20+…+a0nbn0，r01=a00b01+a01b11+a02b21+…+a0nbn1，…，rmm=am0b0m+am1b1m+am2b2m+…+amnbnm。由此可知，r矩阵的每一个元素都是a矩阵的一行和b矩阵的一列作内积的结果，也就是nijikkjk0rab。参考这章的上机题第五次作业：1.设n为哈夫曼树的叶子结点数目，则该哈夫曼树共有_2n+1_个结点。2.在树中，如果结点A有3兄弟，而且B是A的双亲，则B的度是_4_。3.请给出下面二叉树的先序、中序和后序的遍历结果。参考第六章ppt的第36-44页4.已知一个二叉树的中序序列和后序序列如下，请构造（画）出该二叉树，并给出其前序序列。中序序列：ABCDEFG后序序列：BDCAFGE参考第六章ppt的第47-49页5.设某通讯电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数分别是4、18、9、21、30、12。（1）请为这6个字符设计哈夫曼编码，并画出相应的哈夫曼树。（2）计算出这棵哈夫曼树的带权路径长度WPL（in1iiIwWPL）。参考第六章ppt的第96-99页6.请对下图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。参考第六章ppt的第69页第六次作业：1.下图所示为一无向图，要求：（1）给出该图的邻接矩阵；参考第七章ppt的第17页（2）给出从顶点A出发进行深度和广度优先搜索的过程。参考第七章ppt的第32-39页2.已知如下图的有向图，请给出该图的每个顶点的入、出度；邻接表。参考第七章ppt的第23页3.已知某有向图的邻接表如下图，顶点集合为{V1，V2，V3，V4，V5，V6}，请完成：（1）画出该有向图；（2）写出该有向图从V1开始的一个拓扑排序序列。0V11^1V22^2V33^3V4^4V551^5V63^参考第七章ppt的第72页第七次作业：1.以下列数据为输入序列构造二叉排序树，画出构造结果。{50,72,43,85,75,20,35,45,65,30}参考第九章ppt的第36页2.在一棵二叉排序树上进行__中序__遍历后，其关键字序列是一个有序表。3.已知一组关键字为{19,01,23,14,55,68,11,82,36}，请按哈希函数为H（key）=keyMOD11（表长=11），并用线性探测再散列的方法来处理冲突构造哈希表。参考第九章ppt的第58页第八次作业：1.对一组数据{2，12，16，88，5，10}进行冒泡排序，则第一趟排序结果为{2，12，16，5，10，88}。2.对一组数据{87，42，56，18，25，70}进行直接插入排序，则第三趟排序结果为{18，42，56，87，25，70}。3.以关键码序列（67，58，45，87，76，33，27，15）为例，用快速排序写出从小到大每一趟排序结束时的关键码状态。参考第十章ppt的第30页