数据结构与算法作业

1、习题11 .简述下列术语：数据 数据元素 数据结构 存储结构 数据类型 抽象数据类型2 .在下面两列中，左侧是算法的执行时间，右侧是一些时间复杂度。请用连线的方式表示 每个算法的时间复杂度。100n(1)(a)O(1)6n2-12n+1(2)(b)O(2n)1024(3)(c)O(n)n+210g 2n(4)(d)O(n2)n(n+1)(n+2)/6(5)(e)O(log 2n)2n+1+100n(6)(f)O(n3)n3 .试编写算法，求一元多项式Pn(x)=axi的值Pn(X0),并确定算法中每一语句的执行次i 0数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法，本题输入为ai

2、(i= 0,1，n), xo和 n,输出为 Pn(xo)。习题21. 填空题：a)在顺序表中插入和删除一个元素，需要平均移动表中一半 元素,具体移动的元素个数与插入或删除元素的位置有关。b) 顺序表中逻辑上相邻的元素的物理位置要求紧邻。单链表中逻辑上相邻的元素的物理位置不要求 紧邻。c)在单链表中，除了首结点外，任一结点的存储位置由前一结点的指针指示。d) 在单链表中设置头结点的作用是 储存指向第一个结点的指 针。2. 已知顺序线性表 A和B中各存放一个英语单词，字母均为小写。试编写一个判定那个单词在字典中排在前面的算法。3. 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a

3、i,a2,，an）逆置为（an, an-i,，ai）。4. 已知指针 ha 和 hb 分别指向两个单链表的头结点，并且已知两个链表的长度分别为 m 和 n 。 试写一算法将这两个链表连接在一起 （即令其中一个表的首元结点连在另一个表的最后一个结点之后） ，假设指针hc 指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。5. 设线f表A=（ ai,a2,，am）,B=（ bi, b2,，bn）,试写一个按下列规则合并A、B为线性表 C 的算法，即使得C=（ ai,bi, a2,b2,，am,bm, bm+i, ，bn） 当 mwn 时；C=（ ai,b

4、i, a2,b2,，an,bn,an+i,，am）当 nwm 时.线性表 A 、 B 和 C 均以单链表作存储结构， 且 C 表利用 A 表和 B 表中的结点空间构成。注意：单链表的长度值m 和 n 均未显式存储。注意： 2-5 题完成后在上机实习时， 通过程序实现检验算法的正确性 （至少上机检验算法 2）习题 31. 若按教科书3.i.i节中图3.i（b）所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道） ，则请问：（i）如果进站的车厢序列为i23,则可能得到的出站车厢序列是什么？（2）如果进站的车厢序列为i23456,则能否得到 4356i2和i35426的出站序列，并说明为什么（即写出

5、以'S'表示进栈和以'X'表示出栈的栈操作序列）。2. 试写一个判别表达式中开、闭括号是否合法匹配的算法。3. 按照四则运算加、减、乘、除和哥运算（T）优先关系的惯例，并仿照 3.2节（p.54） 例 3-i 的格式，画出下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B X C/D+E T F4. 以 T=i6 ，各件物品体积=2 ， 5， 8， 3， 4， 6为例，画出背包问题算法执行过程中栈的变化。5. 假设以带头结点的循环链表表示队列，并且只设一个指向尾结点的指针，不设头指针，写出相应的入队出队操作。习题 44.1 已知下列字符串a=THIS ,

6、f= A SAMPLE , 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 试问执行一下函数会产生怎样的输出结果？void dem

7、onstrate( )StrAssign( s, THIS IS A BOOK );Replace( s, SubString(s,3,7), ESE ARE );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.3 用串的定长顺序存储表示编写算法，实现串的基本操作Replace(SString &NewS, S

8、StringS, SString T, SString V); (提示：可利用书中已实现的基本操作) 。4.4 假设以结点大小为 1(且附设头结点)的链表结构表示串。若设串类型为：typedef struct strNodechar chdata;strNode *next;strNode,*strPtr;试编写程序实现下列串的基本操作StrAssign , StrLength , StrCompare 和 SubString 的函数。习题 51、 设有三对角矩阵(aij )n*n ,将其三对角线上的元素存于数组 B3n 中， 使得元素 Buv=a ij ,试推导出从(i,j)到(u,v)的下

9、标变换公式。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、三元组顺序表的一种变形是，从三元组顺序表中去掉行下标域得到二元组顺序表，另设一行起始向量， 其每个分量是二元组顺序表的一个下标值， 指示该行中第一个非零元素在二元组顺序表中的起始位置。试

10、编写一个算法，由矩阵元素的下标值i,j 求矩阵元素。试讨论这种方法和三元组顺序表相比的优缺点习题 61.2.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。从而对比一棵度为2的树与一棵二叉树有何区别?一棵深度为H的满k叉树有如下T质：第 H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，则(1)各层的结点数目是。(2)编号为p的结点的父结点(若存在)的编号是 。(3)编号为p的结点的第I个儿子结点(若存在)的编号是 。(4)编号为p的结点有右兄弟的条件是。其右兄弟的编号.7.已知一棵度为k的树中有m个度为1的结点，n2

11、个度为2的结点，nk个度为k的结点, 该树中有个叶子结点。已知在一棵含有n个结点的树中，只有度为 k的分支结点和度为0的叶子结点。则该树 含有的叶子结点的数目为。一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少? 找出所有满足下列条件的二叉树：a)它们在先序遍历和中序遍历时，得到的结点访问序列相同? b)它们在先序遍历和中序遍历时，得到的结点访问序列相同? c)它们在先序遍历和中序遍历时，得到的结点访问序列相同? 画出如图所示各棵树对应的二叉树8.画出如图所示二叉树对应的森林CBDCBDFGHKMKI9.假设用于通信白电文仅由8个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10,试为这 8个字母设计哈夫曼编码。习题82）写出它的邻接矩阵，并按Kruskal Algorithm求其最小生成树1 .已知图所示的有向图，请给出该图的1）每个顶点的入度和出度2）邻接矩阵3）邻接表4）逆邻接表5）强连通分量2 .请对如图所示的无向带权图1）写出它的邻接矩阵，并按 Prim Algorithm求其最小生成树4、对下图所示的 AOE-网，计算各活动弧的e（ai）和l（aj）函数值、各事件（顶点）的 ve（vi）和vl（vj）函数值；列出各条关键路径1010112112习题