部分习题参考答案(数据结构 李春葆).ppt

练习题2练习2.2、2.3、2.4、2.5和2.6。2.2设计了将x插入到按从小到大顺序排列的线性表(顺序存储结构)中的适当位置并保持线性表顺序的算法。voidInsert(SqList*，2.3表示前导节点的数据域为a1、a2、设计一种算法，用于反向指定an(n3)的单个链接表中的所有节点。也就是说，第一个节点的数据域将成为an，最后一个节点的数据域将成为a1。voidReverse(LinkList*/p指向下一个节点)，2.4除了具有prior、data和next三个域外，还具有访问频率域freq，其值在使用关联的表之前初始化为0。每次发生LocateNode(h，x)操作时，元素值为x的节点将freq字段中的值加1，表中节点的顺序按访问频率的降序排序，以确保经常访问的节点总是接近标头。请写下符合上述要求的LocateNode运算的算法。boollocatenode (dlink list * h，elemtype x) dlink list * p=h-next，* q；While(p)！=NULL，2.5集ha=(a1，a2，an)和HB=(B1，B2，BM)是两个进退刀节点的回路单一连结，它为将这两个表格合并到进退刀节点的回路单一连结表格HC撰写演算法。voidmerge (linklist * ha，linklist * HB，linklist */循环单链路表free(HB)；/HB释放单个链接表的头节点 2.6非空线性表ha和HB都显示为进退刀节点的循环双链接表。设计算法Insert(ha，hb，I)。I=0时，具有将定线表格HB插入定线表格ha开头的功能。I0时，在定线表格ha的第I个节点后插入定线表格HB。如果I大于路线表ha的长度，则将路线表HB插入到路线表ha的最后。void insert (dlink list *，if(I=0)/HB中的所有数据节点在ha的头节点和第一个数据节点之间 p=h B- prior；/p指向HB中的最后一个节点/p-next=ha-next。/在ha的第一个数据节点之前，*p链为ha-next-prior=p；ha-next=h B- next；h B- next-prior=ha；/ha头节点与HB的第一个数据节点链 else if(inext；while(jn ext；j； q=p-next；/q *指向p节点的后续节点/p-next=hb- next；/hb-prior是hb的最后一个节点h B- next-prior=p；h B- prior-next=q；q-prior=h B- prior；，将HB链连接到else/ha后， ha-prior-next=h B- next；/ha-prior是指向ha的最后一个节点h B- next-prior=ha-prior；h B- prior-next=ha；ha-prior=h B- prior； free(HB)；/释放HB头节点以练习3练习3.1、3.2、3.3、3.4和3.6。3.1有5个元素a、b、c、d和e。所有可能的堆栈顺序中，c、d元素首先出现的顺序(即c是第一个，d是第二个)是什么？答：如果c是第一个，d是第二个堆栈，则a是堆栈，b是堆栈，c是堆栈，c是堆栈，d是堆栈，d是堆栈，d是堆栈，d是堆栈，d是堆栈，d是堆栈，b是堆栈，a是堆栈，a是堆栈，e是堆栈，e是堆栈，e是堆栈，输出序列是CDBAE中选择所需的构件。(2)B堆栈、e堆栈、e堆栈、a堆栈、输出序列CDBEA；(3)E堆栈、E堆栈、b堆栈、a堆栈、输出序列为CDEBA。可能的顺序为CDBAE、CDBEA和CDEBA。3.2假定堆栈和堆栈操作分别用I和o表示，堆栈的初始和结束堆栈为空，堆栈和堆栈操作序列只能用I和o表示。(1)以下显示的序列中，哪一个是合法的？a . ioiioioob . ioiioc . iiioioid . iii ooioo(2)编写算法，通过(1)的分析确定给定操作序列是否合法。合法地返还1；否则，返回0。(假定标识的操作序列存储在一维数组中)。解决方案：(1)A，d都合法，b，c无效。在b中，高级堆栈将堆叠一次，立即堆叠三次，因此堆栈可能会溢出。c到5，3，堆栈的最后状态不是空的。(2)此问题使用链堆栈确定操作序列是否有效。其中a是存储操作序列的字符数组，n是该数组中的元素数(其中ElemType类型设置为char)。算法如下：intjudge(charA，intn) inti；ElemTypexLiStack * lsinit stack(ls)；for(I=0)；I0时ai进入团队时airear=qu-front=0；While(1)printf(输入 a值： )；scanf(“% d”，3.6输入n(用户输入)的10个以内，每次输入I(0I9)时都将其插入I号队列。最后，将10个组中的非空队列从最小队列号到最大队列号串到一个链，并输出该链中的所有元素。typedefstructnode intdataStructnode * next qmode，void insert (qmode * qh ，qode * Qt ，intx)/将x插入相应的队列 qmode * s；s=(q mode *)malloc(size of(qmode)；/创建节点s-data=x。s-next=NULL；If(QHx=NULL)/如果队列为NULL，则为 QHx=s；QTx=s； else QTx-next=s；/QTx指向的节点后面的*s节点QTx=s；/QTx仍然指向尾部节点，voidcreate (qode * qh ，qmode * Qt /根据用户输入排队intn，x，Iprintf( n : )；scanf(“% d”，)，voidlink (qode * qh ，qmode * Qt /连接非空队列，然后输出qmode * head，* TTM/完整连接列表中的第一个节点指针和尾部节点指针intfirst=1，I；for(I=0)；inext=QHI；tail=QTI； printf(“ n所有元素：”)；While(head！=NULL) printf(“% d”，head-data)；head=head-next； printf(“ n”)；，void main() inti；Qmode * qh maxqnode，* Qtmaxq node；/每个队列的队列QH和队列指针QTfor(I=0；Ilchild、A、2 * I)；Ctree(b-rchild，A，2 * I 1)； elseAI=#；，7.7假定使用二进制链存储结构，其中二进制树使用指向根节点的t、指定任意节点的p、根节点到p的指定节点之间的路径输出算法。int path (btnode * t，Bt node * s) Bt node * STmaxsize；Bt node * p；Inti、flag、top=-1；/将初始值dowhile(t)/t的所有左侧节点堆叠到堆叠顶部指针上 topSTtop=t；t=t-lchild； p=NULL/p指向当前节点以前访问的节点flag=1。/t的访问设置显示为已访问while(top！=-1/其他情况下为0，7.9设计一种算法，该算法假定二进制树采用二进制链存储结构，并确定二进制树是否对称同构。所谓对称同构意味着左右子树的结构是对称的。解决方案：判断二叉树是否对称同构的递归模型如下：f(b)=true b=NULL或b-lchild和b-rchild均为NULLf(b)=false b-lchild和b-rchild之一NULLf(b)=Printf(“旁边的表： n”)；for(I=0)；in；I )p=G-adjlisti。firstarcPrintf(-: ，I)；While(p)！=NULL)printf(-，p-adj vex)；p=p-nextarc； printf(“ n”)；，8.6假定(1)使用相邻表存储，方法是分别设计从g获取每个顶点的打印的算法。(2)输出g最常出图的顶点之一，以输出顶点号码。(3)在出图g中，计算出图为零的顶点数。(4)确定图g中是否存在边。解决方案：对应的(1)、(2)、(3)和(4)功能的函数分别为OutDs()、MaxOutDs()、ZeroDs()和Arc()。intutdegree (algraph * g，intv) arc node * p；intn=0；P=G-adjlistv。firstarcWhile(p)！=NULL) n；p=p-nextarc； returnn，voidOutDs(ALGraph*G)/g，其中每个顶点的出图速度 intiPrintf(1)每个顶点输出： n )；for(I=0)；in；I )printf(“顶点360% d n”，I，outdegree (g，I)；，voidmaxoutds (alggraph * g)/g出图其中一个最常出图的顶点intmaxv=0，maxds=0，I，x；for(I=0)；in；I )x=OutDegree(G，I)；if(XM axds) max ds=x；maxv=I； printf(“(2)最大输出：顶点%d的输出=%dn”、maxv、maxds)；，voidZeroDs(ALGraph*G)/出图的G中出图的0顶点数inti，x；Printf(3)出图为零的顶点： )；for(I=0)；in；I )x=OutDegree(G，I)；If(x=0)printf(-，I)； printf(“ n”)；，voidArc(ALGraph*G)/插图G中的边inti，j；arc node * p；Printf(4)输入边： )；Scanf(%d%d ，)，练习9教科书中的p271练习1，2，3，5。9.1 A0.对于10顺序表，使用二进制查找方法可以在成功和失败时查找平均查找长度。而且，对于井然有序的表格12，18，24，35，47，50，62，83，90，115，134，您可以确定在寻找二分法查找器90时需要多少查找。查找47所需的搜索次数决定了成功。查找100时需要多少次查询才能确认失败？答：如图9.1(a)所示，A0.10的有序表结构的决策树。因此，ASL succ=3 aslunscc=3.67，9.2整数序列4，5，7，2，1，3，6的数量依次插入空的辅助排序树中，以配置相应的辅助排序树，并要求以图形方式提供配置过程，而无需编程。9.3将整数序列4，5，7，2，1，3，6依次插入到空平衡二进制树中，以构建相应的平衡二进制树。必须以图形方式提供配置过程，而不需要合成过程。9.5编写判断给定二叉树是否为二进制排序树的算法。KeyTypepredt=-32768；/predt是全局