数据结构课件：作业

作业习题讲解第一章习题：1.简要回答术语：数据，数据元素，数据结构，数据类型，抽象数据类型。2.数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？3.数据结构的四种基本结构有哪些？4.算法设计的要求？5.分析以下程序段的时间复杂度，请说明分析的理由或原因。⑴Sum1(intn){intp=1,sum=0,m;for(m=1;m<=n;m++){p*=m;sum+=p;}return(sum);}⑵Sum2(intn){intsum=0,m,t;for(m=1;m<=n;m++){p=1;for(t=1;t<=m;t++)p*=t;sum+=p;}return(sum);}⑶递归函数fact(intn){if(n<=1)return(1);elsereturn(n*fact(n-1));}第二章习题：1.简述下列术语：线性表，顺序表，链表。2.何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?3.在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?4.链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?5.已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。A.删除P结点的直接后继结点的语句序列是

________。B.删除P结点的直接前驱结点的语句序列是

________。C.删除P结点的语句序列是________。D.删除首元结点的语句序列是________。E.删除尾元结点的语句序列是________。(1)P=P->next;(2)P->next=P;(3)P->next=P->next->next;(4)P=P->next->next;(5)while(P!=NULL)P=P->next;(6)while(Q->next!=NULL){P=Q;Q=Q->next;}(7)while(P->next!=Q)P=P->next;(8)while(P->next->next!=Q)P=P->next;(9)while(P->next->next!=NULL)P=P->next;(10)Q=P;(11)Q=P->next；(12)P=L;(13)L=L->next；(14)Free(Q);第三章习题：1.设有一个栈，元素进栈的次序为a,b,c。问经过栈操作后可以得到哪些输出序列？2.循环队列的优点是什么?如何判断它的空和满?3.简述队列和栈这两种数据类型的相同点和差异处？4.写出下列程序段的输出结果（栈的元素类型SElemType为char）voidmain(){

StackS;

charx,y;

InitStack(S);

x='c';y='k';

Push(S,x);Push(S,'a');Push(S,y);

Pop(S,x);Push(S,'t');Push(S,x);

Pop(S,x);Push(S,'s');

while(!StackEmpty(S)){Pop(S,y);printf(y);}

printf(x);}5.假设Q[0,5]是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。d,e,b,g,h入队d,e出队i,j,k,l,m入队b出队n,o,p,q,r入队第四章习题：1.解释空串和空格串的区别，主串和子串的区别。2.设s=‘IAMASTUDENT’,t=‘GOOD’,q=‘WORKER’。求：①StrLength(s)，②StrLength(t)，③SubString(s，8，7)，④SubString(t，2，1)，⑤Index(s，‘A’),⑥Index(s，t),⑦Replace(s，‘STUDENT’，q),⑧Concat(SubString(s，6，2),Concat(t，SubString（s，7,8）))。3.试问执行以下函数会产生怎样的输出结果?

voiddemonstrate()

{

StrAssign(s,'THISISABOOK');

Replace(s,SubString(s,3,7),'ESEARE');

StrAssign(t,Concat(s,'S'));

StrAssign(u,'XYXYXYXYXYXY');

StrAssign(v,SubString(u,6,3));

StrAssign(w,'W');

printf('t=',t,'v=',v,'u=',Replace(u,v,w));

}//demonstrate4.已知：s='(XYZ)+*'，t='(X+Z)*Y'。试利用联接、求子串和置换等基本运算，将s转化为t。第五章习题：1.设有二维数组a[6][8]，每个元素占相邻的4个字节，存储器按字节编址，已知a的起始地址是1000，试计算：①数组a的体积（即存储量）；②数组a的最后一个元素a57起始地址；③按行序优先时，元素a46起始地址。2.什么是广义表？请简述广义表与线性表的区别？3.一个广义表是(a,(b,c),d,e,(f,(i,j),k))，请画出该广义表的图形表示和链式存储结构。0300000000000000-300000040020020001800000000004050B=00-3000004.设有稀疏矩阵B如下图所示，请画出该稀疏矩阵的三元组表存储结构。第六章习题：⑴假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为{(e,i),(b,e),(b,d),(a,b),(g,j),(c,g),(c,f),(h,l),(c,h),(a,c)}，用树型表示法表示该树，并回答下列问题：①哪个是根结点?哪些是叶子结点?哪个是g的双亲?哪些是g的祖先?哪些是g的孩子?那些是e的子孙?哪些是e的兄弟?哪些是f的兄弟?②b和n的层次各是多少?树的深度是多少?以结点c为根的子树的深度是多少?（2）设有下图所示的二叉树。①分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。②写出该二叉树的先序、中序、后序遍历序列。（3）已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。adebfgchkmn（4）设有一棵树，如图下图所示。①请分别用双亲表示法、孩子表示法、孩子兄弟表示法给出该树的存储结构。②请给出该树的先序遍历序列和后序遍历序列。③请将这棵树转换成二叉树。adebfgmhkcn（5）设给定权值集合w={3,5,7,8,11,12}，请构造关于w的一棵huffman树，并求其加权路径长度WPL。（6）假设用于通信的电文是由字符集{a,b,c,d,e,f,g,h}中的字符构成，这8个字符在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。①请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。②求出每个字符的huffman编码。第七章习题：（1）设一有向图G=(V,E)，其中V={a,b,c,d,e}，E={<a,b>,<a,d>,<b,a>,<c,b>,<c,d>,<d,e>,<e,a>,<e,b>,<e,c>}①请画出该有向图，并求各顶点的入度和出度。③

请写出该有向图的邻接矩阵。②分别画出有向图的正邻接链表和逆邻接链表。（2）已知有向图的逆邻接链表如下图所示。①画出该有向图。②写出相应的邻接矩阵表示。③写出从顶点a开始的深度优先和广度优先遍历序列。④画出从顶点a开始的深度优先和广度优先生成树。（3）对于下图所示的带权无向图。①按照Prime算法给出从顶点2开始构造最小生成树的过程。②按照Kruskal算法给出最小生成树的过程。（4）一个AOV网如下图所示，请写出所有可能的拓扑排序序列。

FECDAB（5）假设一个工程的进度计划用AOE网表示，如下图所示。①求出每个事件的最早发生时间和最晚发生时间。②该工程完工至少需要多少时间?③求出所有关键路径和关键活动。

一个AOE网v0v5v4v7v3v2v1v6v8a1=5a2=6a3=3a8=5a4=12a5=3a10=4a9=1a12=5a11=4a6=3a7=3a13=2v9a14=2第八章习题：（1）对于一个有n个元素的线性表，若采用顺序查找方法时的平均查找长度是什么？若结点是有序的，则采用折半查找法是的平均查找长度是什么?（2）输入序列{30、12、57、23、18、3、96、75、83}：①写出生成一棵二叉排序树的过程，求出其平均查找长度。②删除关键字为57的结点之后的二