数据结构习题doc

1、习题一：1、 什么是算法，算法设计的要求有哪些？怎样进行算法评价？2、 简述下列术语：数据、结点、逻辑结构、存储结构、数据结构。 3、 试确定下列程序段中的时间复杂度1) For (i=1;i<=n; +i)for (j=1; j<=i; +j)for (k=1; k<=j; +k) x:=x+1;2) x:=n;y:=0;while (x>=(n+1)*(n+1) y:=y+1;习题二：1、 什么是顺序存储结构？什么是链式存储结构？2、 顺序表、单链表存储结构各有什么特点？3、 分别画出下列数据结构的图示（链表为带头节点的空表与非空表）：顺序表 单链表 双向循环链表。

2、4、 编写算法将一无序链表转换成按升序排列的有序链表。并分析算法的时间复杂度。A=(11,16,8,5,14,10,38,23)5、 已知线性表中的元素以值递增有序排列，试写一算法，删除表中所有值相同的多余的元素。并分析算法的时间复杂度。习题三：1、 何为栈和队列？简述两者的区别和联系。2、 若依次读入数据元素序列a,b,c,d进栈，进栈过程中允许出栈,试写出各种可能的出栈元素序列（含中间步骤）。3、 将下列各算术运算式表示成波兰式和逆波兰式：(A*(B+C)+D)*E-F*GA*(B-D)+H/(D+E)-S/N*T(A-C)*(B+D)+(E-F)/(G+H)4、 对于一个具有m个单元的循

3、环队列，写出求队列中元素个数的公式。习题五：1、 分别写出在按行优先存储方式和列优先存储方式下，三维数组A324的地址计算公式（假设每个数组元素占用L个字节的内存单元，a000的内存地址为Loc(a000)）。2、 求下列广义表的运算的结果：A= (a,b), (c,d) B= (p,h,w) C=(b,k,p,h) (1)head(B)(2)tail(C)(3)head(A)(4)tail(A)(5)head(tail(A)(6)tail(head(A)(7)head(tail(head(A) ) )(8)tail(head(tail(A)习题六：1、 有树如图(a)所示，指出树的根结点、叶

4、子结点、树的度、树的路径长度。2、 将如图(a)所示的树转换成对应的二叉树。3、 有二叉树如图(b)所示。写出其前序、中序和后序遍历的结点序列。 4、 设二叉树的前序序列为ABCDEFGHR，中序序列为BDCEAFHGR，请画出这棵二叉树。5、 设字符A、B、C、D、E、F、G、H、I出现频率分别为1，4，9，16，25，36，49，46，81，试设计哈夫曼编码，并求出哈夫曼树的带权路径长度。习题七：1、 对于图1的带权图，写出其邻接矩阵，并画出其邻接表、逆邻接表的表示。2、 对于图2，从顶点V1出发分别画出按深度方向和按宽度方向的生成树。3、 按Prim算法和Kruskal算法求图3的最小生

5、成树，画出分步结果。4、 求图4有向图中从顶点V1到其它各顶点的最短路径，要求写出此图的邻接矩阵adj和数组dis在算法执行过程中的变化及每一条最短路径 。5、 请写出图5的邻接表与按算法7.12生成的拓扑排序序列。习题九、1、 什么是静态查找表？什么是动态查找表？2、 试比较顺序查找、折半查找查找、分块查找的各自特点。3、 什么是二叉排序树？设从空树出发，查找的关键字序列为（503，87，512，61，908，170，897，275，653，426），画出各次查找后的二叉排序树。4、 什么是哈希表？哈希查找的特点是什么？ 习题十：1、 以关键码序列（503，87，512，61，908，170，897，275，653，426）为例，给出以下算法的每趟