数据结构与算法作业

页眉内容数据结构与算法作业PAGE1页眉内容习题11．简述下列术语： 数据数据元素数据结构存储结构数据类型抽象数据类型2．在下面两列中，左侧是算法的执行时间，右侧是一些时间复杂度。请用连线的方式表示每个算法的时间复杂度。100n3(1)(a)O(1)6n2-12n+1(2)(b)O(2n)1024(3)(c)O(n)n+2log2n(4)(d)O(n2)n(n+1)(n+2)/6(5)(e)O(log2n)2n+1+100n(6)(f)O(n3)3.试编写算法，求一元多项式Pn(x)=的值Pn(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法，本题输入为ai(i=0,1,…,n)，x0和n，输出为Pn(x0)。习题2填空题：在顺序表中插入和删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与插入或删除元素的位置有关。顺序表中逻辑上相邻的元素的物理位置要求紧邻。单链表中逻辑上相邻的元素的物理位置不要求紧邻。在单链表中，除了首结点外，任一结点的存储位置由前一结点的指针指示。在单链表中设置头结点的作用是储存指向第一个结点的指针。数据结构与算法作业全文共6页，当前为第1页。数据结构与算法作业全文共6页，当前为第1页。试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1，a2，…,an）逆置为（an，an-1，…，a1）。已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。设线性表A=(a1，a2，…,am)，B=(b1，b2，…,bn)，试写一个按下列规则合并A、B为线性表C的算法，即使得C=(a1，b1，a2，b2，…,am，bm，bm+1，…,bn)当m≤n时；C=(a1，b1，a2，b2，…,an，bn，an+1，…,am)当n≤m时. 线性表A、B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。注意：2-5题完成后在上机实习时，通过程序实现检验算法的正确性（至少上机检验算法2）习题3若按教科书，则请问：如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并说明为什么（即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序列）。试写一个判别表达式中开、闭括号是否合法匹配的算法。按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照3.2节（p.54）例3-1的格式，画出下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B×C／D+E↑F以T=16，各件物品体积={2，5，8，3，4，6}为例，画出背包问题算法执行过程中栈的变化。假设以带头结点的循环链表表示队列，并且只设一个指向尾结点的指针，不设头指针，写出相应的入队出队操作。习题4数据结构与算法作业全文共6页，当前为第2页。4.1已知下列字符串

a=‘THIS’,f=‘ASAMPLE’,c=‘GOOD’,d=‘NE’,b=‘’,

s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)))),

t=Replac(f,SubString(f,3,6),c),

u=Concat(SubString(c,3,1),d),g=‘IS’,

v=concat(s,Concat(b,Concat(t,Concat(b,u)))),

试问：s,t,v,StrLength(s),index(v,g),index(u,g)各是什么？

4.2试问执行一下函数会产生怎样的输出结果？

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));

}//demonstrate

4.3用串的定长顺序存储表示编写算法，实现串的基本操作Replace(SString&NewS,SStringS,SStringT,SStringV);（提示：可利用书中已实现的基本操作）数据结构与算法作业全文共6页，当前为第2页。若设串类型为：typedefstructstrNode{

charchdata;

strNode*next;

}strNode,*strPtr;试编写程序实现下列串的基本操作StrAssign,StrLength,StrCompare和SubString的函数。习题51、设有三对角矩阵(aij)n*n,将其三对角线上的元素存于数组B[3][n]中，使得元素B[u][v]=aij,试推导出从(i,j)到(u,v)的下标变换公式。2、假设按右下标优先存储整数数组A9*3*5*8时，第一个元素的字节地址是100，每个整数占4个字节。问下列元素的存储地址是什么？(1)a0000(2)a1111(3)a3125(4)a82473、按教科书5.5节中图5.8所示结点结构，画出下列广义表的存储结构图，并求它的深度。1)((()),a,((b,c),(),d),(((e))))2)((((a),b)),(((),d),(e,f)))4、三元组顺序表的一种变形是，从三元组顺序表中去掉行下标域得到二元组顺序表，另设一行起始向量，其每个分量是二元组顺序表的一个下标值，指示该行中第一个非零元素在二元组顺序表中的起始位置。试编写一个算法，由矩阵元素的下标值i,j求矩阵元素。试讨论这种方法和三元组顺序表相比的优缺点习题6数据结构与算法作业全文共6页，当前为第3页。数据结构与算法作业全文共6页，当前为第3页。一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，则(1)各层的结点数目是。(2)编号为p的结点的父结点(若存在)的编号是。(3)编号为p的结点的第I个儿子结点(若存在)的编号是。(4)编号为p的结点有右兄弟的条件是。其右兄弟的编号是。已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，…nk个度为k的结点，该树中有个叶子结点。已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。则该树含有的叶子结点的数目为。一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？找出所有满足下列条件的二叉树：它们在先序遍历和中序遍历时，得到的结点访问序列相同？它们在先序遍历和中序遍历时，得到的结点访问序列相同？ABABCDEFGHIJK画出如图所示各棵树对应的二叉树画出如图所示二叉树对应的森林AABCDEFGHIJKM9．假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，试为这8个字母设计哈夫曼编码。数据结构与算法作业全文共6页，当前为第4页。习题7数据结构与算法作业全文共6页，当前为第4页。12126354每个顶点的入度和出度邻接矩阵邻接表逆邻接表强连通分量2．请对如图所示的无向带权图写出它的邻接矩阵，并按PrimAlgorithm求其最小生成树写出它的邻接矩阵，并按KruskalAlgorithm求其最小生成树bbacdegfh934535456756254、对下图所示的AOE-网，计算各活动弧的e(ai)和l(aj)函数值、各事件（顶点）的ve(vi)和vl(vj)函数值；列出各条关键路径116343169934121062188652711104习题10数据结构与算法作业全文共6页，当前为第5页。试以单链表为存储结构实现简单选择排序的算法数据结构与算法