《数据结构与算法作业(1)》由会员分享，可在线阅读，更多相关《数据结构与算法作业(1)（19页珍藏版）》请在金锄头文库上搜索。
1、作业 1,计算下列各片断程序中语句的执行次数及其大O形式： （1） for i=1 to n for j=1 to i for k=1 to j x=x+1 end end end,(2) for i=1 to n j=1 for k=j+1 to n x=x+1 end end,（3） i=1; while (i100) x=x+1 i=i+1 end,(4) i=1 while (i=n) x=x+1 i=2*i end,（5） x=91 ; y=100 ; while (y0) if (x100) x - = 10 ; y- else x+ ; ,2. 设数据元素的集合为D=d1, d2
2、, d3, d4, d5,试指出下列关系R所对应的数据结构B=（D，R）中哪些是线性结构，哪些是非线性结构。 (1) R=(d1,d2), (d2,d4),(d4,d2),(d2,d5),(d4,d1) (2) R=(di, di+1)|i=4,3,2,1 (3) R=(di, dj)|j=(5i2+4i+1,3. 为一个课题组定义一个数据结构。每组一位教师，13名研究生，16名本科生，关系是教师指导研究生，每名研究生指导12名本科生，画出该数据结构的逻辑结构图。 4.按增长率由小至大的顺序排列下列各函数： 2100, (3/2)n, (4/3)n, nn, n3/2, n2/3, n1/2,
3、 n!, n, log2n, n/log2n, log22n, log2(log2n), nlog2n, nlog2n,作业 2,已知线性表L(x1, x2,xn)各元素按递增有序排列，用向量方式做存储结构。试编写算法，删除表中值分布在c与d(cd)之间的元素 编写一算法，将向量L(x1, x2,xn)倒置 试编写算法，求已知单链表的长度，并考虑表空情况 已知一循环链表中各数值已按递增有序排列，现要求插入一结点后，链表仍有序 缩写单链表倒置算法 在双向链表的值为a、b的两个结点之间插入值为x的结点,7. 简述以下算法的功能: Sample(head) /head是无表头结点的单链表 if(he
4、ad ,作业 3,Q0：10为循环队列，初态front=rear=1，画出下列操作后，队的头、尾指示器状态： d,e,b,g,h入队； d, e出队； i,j,k,l,m入队； b出队； n,o,p,q,r入队 2. 试画出表达式：A*(B-C)+D*(E/F)执行过程中NS，OS栈的变化情况，并给出相应的后缀表达式结果,3. 设置一个单元，作为队满或队空的标志，写出循环队列插入和删除的算法d,e,b,g,h入队； 4.一个栈的输入序列为ABCDEF，经一次退压栈能否得到如下序列，若不能，则经过两次退压栈能否得到？ I: CBEFDA II: AEDFBC,1. 设一个二维数组A1：m; 1：
5、n，假设A3，2地址为1110，A2，3地址为1115，若每个单元占一个空间，求A1,4的地址。 2. 采用三元组和带行辅助向量形式，表示下列稀疏矩阵：,作业 4,3. 二维数组Aij, 0=i=5, 2=j=9,问按行存储A24和按列存储哪一个矩阵元素在相同位置？,作业 5,设一棵完全二叉树，共有1001个结点，试问： (1)有多少个叶子结点； (2)有多少度为2的结点； (3)有多少结点只有非空左子树。 2. 设一棵二叉树，其中序和后序遍历为： 中序：BDCEAFHG； 后序：DECBHGFA 画出该二叉树的逻辑结构，并写出先序遍历结果。 3. 给出一组元素17，28，36，54，30，2
6、7，94，15，21，83，40，17，要求画出由此生成的二叉排序树 4. 给出一组权值W=8，2，5，3，2，17，4，画出由此生成的huffman树,5. 将下列一般树转为二叉树,A,B,C,D,E,F,G,I,J,K,L,6. 三个结点A、B、C 可以构造多少种不同的树？ 7. 深度为4的只有4个结点的单支二叉树共有几 种？画出只有左子树的深度为4的单支二叉树的顺序存储结构。 8. 已知二叉树的先序序列为abdgcefh，中序序 列为：dgbaechf，画出二叉树并求后序序列。 9. 满足下列条件的二叉树是什么样的二叉树？ 1) 先序序列和中序序列相同； 2) 中序序列和后序序列相同。
7、10. 已知信源符号a、b、c、d、e的出现频率分别为10、5、20、10、18，求1)huffman编码；2)画出huffman码树；3)求平均码长；4)求最大压缩比,作业 6,有一有向图如图1所示，写出其邻接矩阵和邻接表。 求图2中结点a到各结点之间最短路径。 求图3中所示AOV网的拓扑排序结果（按栈存储方式）,作业 6,4. 设一AOE网如下图,求 （1）每一事件最早开始时间和最迟开始时间； （2）该计划最早完成时间。,作业 6,5.从邻接矩阵A可以看出，该图共有_ 个顶点。如果是有向图，该图共有_条弧；如果是无向图，则共有_条边。,6. 一个有向图的邻接表为： 从顶点v1出发，求DFS
8、、BFS序列。,7. 有A、B、C、D四个村庄要建乡村俱乐部，应设在哪个村才能使各村到俱乐部的路径之和最小？写出各村庄到中心俱乐部的路径及长度。,作业 7,画一棵对20个记录1,2,3,20进行对分查找的判定树，并求等概率情况下的平均查找长度。 设有10记录的关键字分别为: ICKES,BARBER,ELYOT,KERN,FRENCE,LOWES,BENSD,FONK,ERVIN,KNOW。构造=10/13的Hash表，怪关键字首字母在字母表中的序号为Hash函数值，采用随机探测解决冲突，dj=(d1+Rj) mod 13,Rj取自随机数列：3，7，1，12，10，,统计该表的平均查找长度ASL。 100个记录的表，关键字为中国人名姓氏，给出hash表的设计方案，要求等概情况下查找长度3。,1. 对于给定的一组关键字：41，62，13，84，35，96，57，39，79，61，15，83。分别写出简单插入排序、简单选择排序、堆排序、冒泡排序、快速排序的排序过程，并对每一种排序方法进行分析、讨论。,作业 8,
