数据结构作业答案.docVIP

第一次作业： 1.下列算法程序的时间复杂度是0(1) y=4; x=2; while(y8) if (x==5) { x=1;y+=x; } else x++; 2. 写出下列算法的时间复杂度：0(log2n) i=1; while (i=n) i=i*2;  第二次作业： 1．s-next = p-next; p-next = s; 。 2. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是 head-next ==NULL 。 3.线性表L={a1,a2,…,an}采用顺序存储，假定在不同的n个位置上的概率相同，则一个新元素平均需要移动的元素个数是_________，假定在不同的n+1）个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是________。 插入结点操作在第i个位置处插入结点s域为t算法如下所示，请在空格填入正确的语句。 void Insert(CNODE *h, int i, int t, int *len) { CNODE *p=h-next, *s; int j=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. 43512 B. 54321 C. 12345 D. 45321 2. 设有一空栈，栈顶指针为1000H，现有输入序列为12345，PUSH(进栈), POP(出栈) ,PUSH, PUSH,PUSH,POP,PUSH,POP后，输出序列为____145____。 3. 对于队列操作数据的原则是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. 两个字符串相等的充要条件：。 广义表A=（a,b,c,（d, （e,f））），Head与Tail分别是取表头和表尾的函数则式子的值为 （d, （e,f）） ，， 则两个矩阵相乘的结果矩阵r等于 在上式中，r00=a00b00+a01b10+ a02b20+…+a0nbn0，r01=a00b01+a01b11+a02b21+…+a0nbn1，…，rmm=am0b0m+am1b1m+am2b2m+…+amnbnm。由此可知，r矩阵的每一个元素都是a矩阵的一行和b矩阵的一列作内积的结果，也就是。 参考这章的上机题 第五次作业： 1. 设n为哈夫曼树的叶子结点数目，则该哈夫曼树共有__个结点。2.在树中，如果结点A有3兄弟，而且B是A的双亲，则B的度是_ 4 _。 3. 请给出下面二叉树的先序、中序和后序的遍历结果。 参考第六章ppt的第36-44页 4.已知一个二叉树的序序列和序序列如下，请构造（画）出该二叉树，并给出其序序列。 序序列：AB序序列：）。 参考第六章ppt的第96-99页 6.请对下图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。 第六次作业： 1.下图所示为一无向图，要求： 该图的邻接从顶点出发进行深度优先有哪些信誉好的足球投注网站的。 2.已知如下图的有向图，请给出该图的每个顶点的入、出度；邻接表。 已知某有向图的邻接表如下图，顶点集合为{V1，V2，V3，V4，V5，V6 }，请完成（1）画出该有向图； （2）写出该有向图从V1开始的拓扑排序序列。 0 V1 1 ^ 1 V2 2 ^ 2 V3 3 ^ 3 V4 ^ 4 V5 5 1 ^ 5 V6 3 ^ 2.在一棵二叉排序树上进行____遍历后，其