样题习题ds复习及答案

（12） 】1.组成数据的基本单位[A]数据 [B]数据元 [C]数据类 [D]数据变 】2.采用链式结构便于实现对线性表[A]插 [B]遍 [C]查 [D]定 】3.若循环队列用数组A[0,m-1]存放元素，其头尾指针分别为front和rear，[A](rear–front+m)% [B][C] [D](rear–front)% =（a，b，c（d，e，f，[A] [B][C]tail(head(tail(head(A))))[D] 】5.具有2000个结点的二叉树，其高度至少[A] [B] [C] [D] 】6.在邻接矩阵A中，第i顶点的入度为A[A]第i行非∞元素个 [B]第i∞元素个[C]第i行非∞且非0元素个 [D]第i∞且非0元素个 】7.对一个长度为12的有序表进行等概率的折半查找，查找成功所需的关键字[A] [B] [C] [D] 】8.如果对下列顺序表分别作快速排序，所需比较次数最少的[A] [B][C] [D]12构成抽象数据类型的三个要素是 a11的地址为1，每个元素占用1个存储单元，则a85的地址 具有n个顶点的强连通图至少 条弧外排序是指在排序过程中需要外 散 （3617（5EEDBCKAF18.（10分）1213，哈希函数H（k）i/2，其中i为关键字k中第一个字母在4，19.（5分）假设电文中仅由a到h8请画出由此构造的树（要求树中所有结点的左右孩子必须是左大右小，并写出这8个字母相应的编码。步长为4的一趟排序的结果21.（8分）对于右边的带权图G画出G画出G（4022（6）函数f22定义如下，其中函数调用Insert(Lik)在顺序表L的第位置插入kvoidf22(SqList&L,inti){if(i>0){f22(L,i-for(intk=1;k<=i;k++)Insert(L,i,k);}}＝（L 23.（6分）算法f23(L)将结点的单链表L逆置。请在画线处填空voidf23(LinkList&L)LinkListp=L-L->next;while(p)LinkLists;p->next=L-L->next;p=}}24.（6）s是一个升序静态查找表，请简要说明函数调用f24(s1s.length,intf24(SSTables,intlow,inthigh,KeyTypek){if(low>high)return0;intif(k==s.elem[mid].key)returnif(k>s.elem[mid].key)returnelsereturnf24(s,low,mid-}25（6intf25(BiTreeT)if )return-else um=f25(T->lchild)+;returnT- }}26（6#defineMaxNumtypedefstructcharintint}intf26(MGraphG,inti){intd=0;for(intj=0;j<G.n;j++){if(G.arcs[i][j])d++;if(G.arcs[j][i])}return}已知一个