数据结构 形成性考核答案(本)作业1-4

作业1机中的存储表示称为数据的存储结构。可见，数据结构是数据在计算机中的存储表示。尽管因采用的同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点1）在做插入和删除操作时，需移动大量元素2）由于难以估计间，往往使存储空间不能得到充分利用3）表的容量难以扩充。放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。删除操作，则采用链表。答：数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。结点。是其他结点，算法步骤都相同。不带头结点结点还是其他结点。因为两种情况的算法步骤不同。（1）p->data=i（2）p->next=NULL（3）q->next=p（4）q=p（1）head=p（2）q=p（3）p->next=NULL（4）p->next=q->next（5）q->next=p（1）p=q->next（2）q->next=p->next1--线性表栈是否满s->top=MAXSIZE-1栈顶指针栈顶对应的数19d,e,f性表的任何位置进行插入和删除操作。线性表可以在线性表的任何位置进行插入和删除操作。一般不设置头结点。答：（1）栈的操作特点是后进先出，因此输出序列有：A入，A出，B入，B出，C入C出，输出序列为ABC。A入，A出，B入，C入，C出，B出，输出序列为ACB。A入，B入，B出，A出，C入，C出，输出序列为BAC。A入，B入，B出，C入，C出，A出，输出序列为BCA。A入，B入，C入，C出，B出，A出，输出序列为CBA。栈，再把A出栈A不在栈顶位置最后把B出栈，所以序列CAB不可能由输入序列A，B，C通过栈得到。（2）按照上述方法，可能的输出序列有：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。不可能的输出序列有：DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD答：应是SXSSXSXX。各操作结果如下：X1出栈输出序列：1答：从题中可知，要使C第一个且D第二个出栈，应是A入栈，B入栈，C入栈，C出栈，D入栈。之后可以有以下几种情况：（1）B出栈，A出栈，E入栈，E出栈，输出序列为：CDBAE。（2）B出栈，E入栈，E出栈，A出栈，输出序列为CDBEA。（3）E入栈，E出栈，B出栈，A出栈，输出序列为CDEBA所以可能的次序有：CDBAE，CDBEA，CDEBA答：广义表是线性表的的推广，它也是n(n>0)个元素a1,a2…ai…an的有限序列，其中ai或者是原子或者是一个广义表。所以，广义表是一种递归特殊情况，当ai都是原子时，广义表退化成线性表。算法设计如下：{};{{}voidenqueue(LinkQueue*Q,elemtypex){if(Q->rear==NULL)/*原为空队时*/{}else/{p=Q->rear->next;/*p指向第一个结点*/Q->rear=s;/*Q->rea}}{if(Q->rear==NULL){printf("队列为空!\n");}elseif(Q->rear->next==Q->rear)/*只有一个结点时*/{}{t=Q->rear->next;/*t指向第一个结Q->rear->next=t->next;/*}}elemtypegethead(LinkQue{if(Q->rear==NULL)printf("队列为空!\n");return(Q->rear->next->dat}intemptyqueue(LinkQueue*Q){if(Q->rear==NULL)return(1);/*为空,则返回tr}voiddispqueue(LinkQueue*Q){printf("队列元素:");{p=p->next;}printf("%c\n",p->data);}2--栈、队列、递归程序设计2n历的结果。（1）二叉树图形表示如下：AACBCBDFEDFEHIG\JHIG\JKKMLML□由□得单支结点数为1□对于n个结点的完全二叉树，最后一个树叶结点，即序号为n的叶结点其双亲结点即为最后一个非终端结点，（1）先序序列和中序序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树（2）中序和后序序列相同的二叉树为空树或任一结点均无右孩子的非空二叉树（3）先序和后序序列相同的二叉树为空树或仅有一个（1）哈夫曼树如图B-4所示。0010o1030200 ADAD23（3）每个字符的哈夫曼编码为：A:100,B:11,C:1010,D:000,E:0010,F:10110,G:10111,H:0011,I:（1）深度优先遍历：v1,v2,v3,v8,v5,v7,v4,v6广度优先遍历：v1,v2,v4,v6,(2)G的拓扑序列为：v1,v2,v4,v6,v5,v5,v□g1的图示和图g1的邻接表如下图所示。v1v1v4v2v4v2v5v53v3□图G的邻接矩阵如下图所示：010100110024^145^45^123^23^24^145^45^123^23^v1v2v3v4v5defineNULL0typedefstructbtnode{{/*复制一棵二叉树*/if(p!=NULL){t=(bitnode*)malloc(sizeof(bitnot->lchild=CopyTree(p->lchilt->rchild=CopyTree(p->rchilintBTreeLeafCount(structBTreeNo{elseif(BT->left==NULL&&BT->right==NULL)return1;elsereturnBTreeLeafCount(BT->left)+BTreeLeafCount(BT-}3--栈、队列、递归程序设计各趟的结果。答：时各趟的结果。答：列作升序排列时的每一趟结果。（2）以二叉树描述逐次取走堆顶元素后，经调整得到的5答：\\77777(3)平均查找长度=（1*1+2*2+3（1）52244663377（1）□j>=0（2）□a[j]（3）□j--（4）□temp（1）j<=n-1（2）i<=n-j（4）a[i+1]=temp（5）□当某趟冒泡中没有出现交换则已排好序结束循环。折半查找算法如下；intBinary_Search(NODEa[],intn,intk)/*在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1*/{{elseif(a[mid].key<k)}}/*查找成功，返回查找到的记录的下标*//*取后半查找区间*//*取前半查找区间*//*查找失败*/2.编写顺序查找算法