资源描述：
《数据结构作业答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一次作业：1.下列算法程序的时间复杂度是0(1)y=4;x=2;while(y<8)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个位置上删除的概率相同，则删除一个新元素平均需要移动的元素个数是__
2、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
3、
4、i<1)return;while(p!=h&&jnext;j++;}s=(CNODE*
5、)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后，输出序
6、列为____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]，
7、其每个元素占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分别是取表头和表尾的函数）则式子的值为（d,（e,f））。4.写一算法，利用数组实现两个矩阵的相乘。两个矩阵，，则两个矩阵相乘的结果矩阵r等于在上式中，r00=a00b00+a01b10+a02b20+…+a0nbn0，r01=a00b01+a01b11+a02b21+…+a0nbn1，…，rmm=am0b0m
8、+am1b1m+am2b2m+…+amnbnm。由此可知，r矩阵的每一个元素都是a矩阵的一行和b矩阵的一列作内积的结果，也就是。参考这章的上机题第五次作业：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六个字符组成
9、，它们在电文中出现的次数分别是4、18、9、21、30、12。（1）请为这6个字符设计哈夫曼编码，并画出相应的哈夫曼树。（2）计算出这棵哈夫曼树的带权路径长度WPL（）。参考第六章ppt的第96-99页6.请对下图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。参考第六章ppt的第69页第六次作业：1.下图所示为一无向图，要求：（1）给出该图的邻接矩阵；参考第七章ppt的第17页（2）给出从顶点A出发进行深度和广度优
