资源描述
第 18 页 共 18 页习题 一1 填空题（1） 数据的逻辑结构可形式地用一个二元组B(K，R)来表示，其中K是_，R是_。（2） 存储结构可根据数据元素在机器中的位置是否连续分为，。（3） 算法的基本要求有，。 （4） 度量算法效率可通过，两方面进行。 2 简述下列术语： 数据 数据元素 数据对象 数据结构 存储结构 数据类型。3. 常用的存储表示方法有哪几种?4.举例说明一下数据结构和算法的关系。5.设有数据逻辑结构为B=（K，R），K=k1，k2，k9r=, ,画出这个逻辑结构的图示，并确定相对于r哪些结点是开始结点，哪些结点是终端结点？6.试举一个数据结构的例子，并叙述其逻辑结构、存储结构、运算三方面的内容。7.何谓算法？试详述算法设计的目的和算法必须满足的条件。8.编写一个算法，对三个两位数按由大到小的顺序进行排序。描述构造该算法的思维过程。习题二1.如定理2.1所描述的，从盒子中往外取球，在1-4所给的答案中，哪一个是i，j，k对应的值。Red，5，6Blue，5，6Blue，3，Red6，5，Red2如定理2.1所描述的，从盒子往外取球，在1-4所给的答案中，哪一个是i,j,k对应的值。6，7，RedBlue,7,38,2,Red9,Red,13.假设T1（N）= O（F（N），T2（N）= O（F（N），说明下列哪一个正确？T1 (N)+ T2 (N) = O(F(N)T1 (N)- T2 (N) = O(F(N)T1 (N)/ T2 (N) = O(1)T1 (N) = O(T2 (N)4.假设两个算法的时间复杂度分别为T1（N）=O（N）和T2（N）=O（N2），说明下列哪一个正确（估算）？T1（N）* T2（N）= O（N3）T1（N）+ T2（N）= O（N2）T2（N）/ T1（N）= O（N）T2（N）- T1（N）= O（N）5.基于定理2.2的描述，为什么不能充分获得一个最大连续子序列之和的次平方运行时间？6.读者思考：由算法2.1到算法2.2的改进过程中，时间复杂度由三次降到二次，那么算法的空间复杂度有没有变化？这种改进是不是无条件的？7.将下列各式组合成与Big-Oh相等的函数。x2，x2 + x，x2 - x，x3/( x 1 )8确定以下各式的等价Big-Oh函数(估算)。x4/(x+1),x3-x2，x2+x39.程序A和程序B经分析，有不超过150NlogN和N2的最坏情况下的运行时间，如可能，分别回答下列各问题：当N值很大时（N 10,000）,哪个程序对运行时间有保证？N值较小（N 1000）时，哪一个程序对运行时间有更好的保证？在N = 1，000的平均情况下，哪个程序运行更好？在所有可能的输入中，程序B总比程序A运行的快吗？10程序A和程序B经分析，有不超过150NlogN和N2的最坏情况下的运行时间，读者计算一下输入的值N在哪个范围里程序A的运行效率高于程序B，在哪个范围里程序B的运行效率高于程序A？（提示：可以通过建立方程式求解）11.对于这些你用手工来计算的典型算法，确定其运行时间。两个N位整数相加两个N位整数相乘两个N位整数相除12设一个N位整数x，对于表达式x2 + x-x3/( x 1 )，试确定其运行的时间复杂度（考虑“最坏情况分析法”）。13.对于N个项来说，以下计算XN的算法运行时间是多少？double power（double x，int n） double result = 1.0; for（int i = 0; i n; i+） result *= x; return result;14试确定下面递归算法的时间复杂度：Int func（int n）if（n= =0）return（0）；return（n+func（n-1）；15.对于求最大子序列之和问题的平方算法而言，精确的确定语句最内部循环被执行多少次？16试计算在算法2.1中，精确的确定语句最内部循环被执行多少次？17.一个算法在输入规模为100时，花费0.5ms的时间，在下列情况下，输入规模为500时，它将花费多少时间（低次项不考虑）？线性算法O(NlogN)平方算法立方算法18一个算法在输入规模为10时，花费0.05ms的时间，在下列情况下，输入规模为1000时，它将花费多少时间（低次项不考虑）？线性算法O(NlogN)平方算法立方算法19.一个算法在输入规模为100时，花费0.5ms的时间，在下列情况下，一分钟可以解决一个多大的问题（低次项不考虑）？线性算法平方算法立方算法20一个算法在输入规模为10时，花费0.05ms的时间，在下列情况下，0.5分钟可以解决一个多大的问题（低次项不考虑）？线性算法平方算法立方算法习题三1填空题(1) 线性表(a1,a2,an)有两种存贮结构：顺序存贮结构和链接存贮结构，请就这两种存贮结构完成下列填充： _存贮密度较大；_存贮利用率较高； _可以随机存取；_不可以随机存取；_插入和删除操作比较方便。 (2) 在单链表中，删除指针P所指结点的后继结点的语句是_。（1） 带头结点的单循环链表Head的判空条件是_；不带头结点的单循环链表的判空条件是_。（2） 删除带头结点的单循环链表Head的第一个结点的操作是_；删除不带头结点的单循环链表的第一个结点的操作是_。（3） 如果线性表中最常用的操作是存取第I个元素及其前驱的值，则采用_存储方式节省时间。 A单链表 B双链表 C单循环链表 D顺序表2 动态与静态数据结构在计算机内存中的存储方式有何不同？各有何优缺点？3 描述以下三个概念的区别：头指针、头结点、第一个结点。4 试写出一个计算线性链表P中结点个数的算法，其中指针P指向该表中第一个结点，尾结点的指针域为空。5 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?6 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?7 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?8 假设LA、LB为两个递增有序的线性链表，试写出将这两个线性链表归并成一个线性链表LC的操作算法。9 将学生成绩按成绩高低排列建立了一个有序单链表，每个结点包括：学号、姓名和课程成绩。（1） 输入一个学号，如果与链表中的结点的学号相同，则将此结点删除；（2） 在链表中插入一个学生的记录，使得插入后链表仍然按成绩有序排列。10 某仓库中有一批零件，按其价格从低到高的顺序构成一个单链表存于计算机内，链表的每一个结点说明同样价格的若干个零件。现在又新有m个价格为s的零件需要进入仓库，试写出仓库零件链表增加零件的算法。链表结点结构如下：11 设指针P指向单链表的首结点，指针X指向单链表中的任意一个结点，写出在X前插入一个结点i的算法。12 设多项式A和B采用线性链表的存储方式存放，试写出两个多项式相加的算法，要求把相加结果存放在A中。13 设指针a和b分别为两个带头结点的单链表的头指针，编写实现从单连表La中删除自第i个数据元素起，共length个数据元素、并把它们插入到单链表Lb中第j个元素之前的算法。14 设La和Lb是两个有序的循环链表，Pa和Pb分别指向两个表的表头结点，是写一个算法将这两个表归并为一个有序的循环链表。15 已知有一个单向循环链表，其每个结点中含三个域：pre、data和next，其中data为数据域，next为指向后继结点的指针域，pre也为一个指针域，但是他的值为空（null），试编写一个算法将此单链表改为双向循环链表，即使pre成为指向前驱结点的指针域。16 画出执行下列各行语句后各指针及链表的示意图。L=（linklist）malloc （size of（lnode）；P=l；for（i=1；inext=(linklist)malloc(size of (lnode);p=p-next;p-data=i*2-1;p-next=null;for (i=4;i=1;i- -；) insert_linklist（l;i+1;i*2）;for(i=1;i=2)的k叉链表表示中，有多少个空指针?14. 设计一个算法，以判断二叉树T是否为二叉排序树（假设T中任意两个结点的值均不相等）。15. 以二叉树作存储结构，试编写求二叉树高度的算法。16.一棵n个结点的完全二叉树以数组作为存储结构，试编写非递归算法实现对该树进行前序遍历。17. 算法判断两棵二叉树是否等价。称二叉树T1和T2是等价的：如果T1和T2都是空的二叉树；或者T1和T2的根结点的值相同，并且T1的左子树与T2的左子树是等价的，T1和T2的右子树是等价的。18. 设计算法按后序序列打印二叉树T中所有叶子结点的值，并返回其结点个数。19. 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别是7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码并用程序实现。20.二叉链表为存储结构，分别写出求二叉树高度及宽度的算法，所谓宽度是指二叉树的各层上，具有结点数最多的那一层上的结点总数。习题八1. 判断题 (判断下列各题是否正确，若正确在（）内打“”，否则打“”)(1) （ ）用相邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。(2) （ ）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。(3) （ ）若从某顶点开始对有向图G进行深度遍历，所得的遍历序列唯一，则可断定其弧数为n-1。(4) （ ）邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。 (5) （ ）任何有向图网络（AOV-网络）拓扑排序的结果是唯一的。(6) （ ）有回路的图不能进行拓扑排序。(7) （ ）存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了。(8) （ ）用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为0即可。(9) （ ）在AOV网中一定只有一条关键路径。(10) （ ）连通分量是有向图的极小连通子图。(11) （ ）强连通分量是有向图中的极大强连通子图。(12) （ ）若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。(13) （ ）图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。2. 单选题 (请从下列A，B，C，D选项中选择一项）(1) n个顶点的强连通图至少有（ ）条边。A. n B. n+1 C. n-1 D. n（n-1） (2) 如果带权有向图G采用邻接矩阵存储结构来存储，设其邻接矩阵为A，那么顶点i的入度等于A中（ ）A. 第i行非无穷的元素之和B. 第i列非无穷的元素之和C. 第i行非无穷且0的元素个数D. 第i列非无穷且0的元素个数(3) 对于含有n个顶点e条边的无向连通图，利用prim算法生成最小代价生成树其时间复杂度为（ ）A. O（n） B. O（n*n） C. O（n*e） D. O（elog2e） (4) 设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为（ ）A. O（en） B. O（n+e） C. O（nlog2e） D. O（elog2n） (5) 关键路径是事件结点网络中（ ）A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 (6) 任何一个无向连通图的最小生成树有（ ）A. 只有一棵 B. 有一棵或多棵C. 一定有多棵 D. 可能不存在(7) 图的生成树（ ），一个连通图的生成树是一个（ ）连通子图，n个顶点的生成树有（ ）条边，最小代价生成树（ ）。A. 是唯一的、最大、n、不是唯一的 B. 不是唯一的、最小、n+1、唯一性不能确定 C. 唯一性不能确定、最小、n-1、是唯一的 D. 不是唯一的、最小、n-1、不是唯一的 (8) 对于含有N个顶点e条边的无向连通图，利用Kruskal算法生成最小代价生成树其时间复杂度为（）A. O（log2n） B. O（nlog2n） C. O（elog2e） D. O（nlog2e） (9) 设无向图G中顶点数为n，则图最少有（）条边；最多有（ ）条边。A. n（n+1）/2 B. n（n-1） C . n（n-1）/2 D. n（n+1） (10) n个顶点的无向完全图的边数为（）A. n（n-1） B. n（n+1） C. n（n+1）/2 D. n（n-1）/2 (11) 设T是树图，则T中最长路径的起点和终点的度数为（）A. 1 B. 2 C. n D. 不确定 3. 对于图8-29的有向图，试给出： 各个顶点的出度和入度； 它的强连通分量； 将该图改造为一个有向完全图。图 8-294. 对于图 8-29所示的有向图，试给出：（不带权值） 它的邻接矩阵； 它的邻接表； 它的逆邻接表； 它的十字链表； 635869374852ABCEFHD5. 图 8-30中的有向图是连通图吗？分别用深度优先搜索法和广度优先搜索法，列出遍历图中顶点的次序。图 8-306. 对于无向图（如图8-31），试给出： 用普里姆算法构造其最小生成树的过程； 用克鲁斯卡尔算法构造其最小生成树的过程。5234363422ABCEFHDG5图 8-317.对图 8-32中的有向网，求： 各活动的最早开始时间和最迟开始时间; 完成工程的最短时间； 网中的关键活动；图 8-328.给出建立有向图的邻接表的算法。9.给出建立有向图的十字链表的算法。10.若有向图采用邻接表作为存储结构，试给出计算图中各个顶点的入度的算法。11.试给出求有向图的强连通分量的算法。12.以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路(若存在)。13.利用拓扑排序算法的思想写一算法判别有向图中是否存在有向环，当有向环存在时，输出构成环的顶点。习题九1. 判断题 (判断下列各题是否正确，若正确在（）内打“”，否则打“”)(1) （ ） 二叉排序的查找和折半查找的时间性能相同。(2) （ ） 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。(3) （ ） 哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法。(4) （ ） 当所有的结点的权值都相等时，用这些结点构成的二叉查找树的特点是只有右子树。 (5) （ ） 采用线性探测法处理哈希地址的冲突时，当从哈希表删除一个记录时，不应该将这个记录的所在位置置空，因为这会影响以后的查找。(6) （ ）任一二叉查找树的平均查找时间都小于用顺序查找同样结点的线性表的平均查找时间。(7) （ ） 对二棵具有相同关键字集合的而形状不同的二叉查找树，按中序遍历它们得到的序列的顺序是一样的。(8) （ ） 在二叉查找树上插入新的结点时，不必移动其他结点，只要将该结点的父结点的相应的指针域置为空即可。2. 单选题 (请从下列A，B，C，D，E选项中选择一项)(1) 如果要求一个线性表既能较块地查找，又能适应动态变化的要求，则可采用（ ）（A）查找方法。采用折半查找方法进行查找时，数据文件应为（ ）（B），且限于（ ）（C）。 要进行顺序查找，则线性表（ ）（D）。 供选择的答案 (A): 1.分块 2.顺序 3.折半 4.基于树型(B)，(C): 1.有序表 2.随机表 3.散列存储结构 4.链式存储结构 5.顺序存储结构 6.线性表(D): 1.必须以顺序方式存储 2.必须以链式方式存储 3.既可以以顺序方式存储，也可以以链式方式存储 (2) 折半查找的查找速度（ ）（A）比顺序查找法的速度快。设有 100 个元素，用折半法查找时，最大比较次数是（ ）（B）。最小比较次数是（ ）（C）。 供选择的答案 (A): 1.一定 2.不一定(B)，(C): 1. 25 2. 50 3. 10 4. 7 5. 4 6. 2 7. 1 (3) 设哈希表长 m=14，哈希函数 H(k)=k MOD 11。表中已有四个记录，如果用二次探测再散列处理冲突，关键字为 49 的记录的存储地址是（ ）（A）。0 1 2 3 4 5 6 7 8 9 1011 12 13| | | | |15|38|61|84| | | | | | | 供选择的答案(A): 1. 8 2. 3 3. 5 4. 9 3.对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?4.画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。5. 将(for, case, while, class, protected, virtual, public, private, do, template, const ,if, int)中的关键字依次插入初态为空的二叉排序树中，请画出所得到的树T。然后画出删去for之后的二叉排序树T,若再将for 插入T中得到的二叉排序树T是否与T相同?最后给出T的先 序、中序和后序序列。6. 对给定的关键字集合，以不同的次序插入初始为空的树中，是否有可能得到同一棵二叉排序树?7. 设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗?窗体底部8. 假设线性表中结点是按关键字递增的顺序存放的，试写一顺序查找算法，将监视哨设为低下标端。然后，分别求出等概率情况下查找成功和不成功的平均查找长度。9. 设单链表的结点是按关键字从小到大排列的，试写出对此表的查找算法，并说明是否可以采用折半查找。10. 试编写递归的折半查找算法。11. 试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表为存储结构，且树中结点的关键字均不相同。12. 试写一递归算法，从大到小输出二叉排序树中所有其值不小于x的关键字。要求算法的时间为O(lgn+m)，n为树中结点数，m为输出关键字个数(提示：先遍历右子树，后遍历左子树)。习题十1. 填空题（1）下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？ A. 直接插入排序 B. 起泡排序 C. 快速排序 D. 直接选择排序（2）两个序列如下： L1=25，57，48，37，92，86，12，33 L2=25，37，33，12，48，57，86，92用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列_。（3）对序列（80，31，27，56，92，11，42）进行排序，使用直接插入排序方法的比较次数为_；使用冒泡排序法的比较次数_；使用直接选择排序法的比较次数为_；使用快速排序方法的比较次数为_。2. 下面给出了起泡排序算法，请填写算法中的空框，使算法正确。TYPE struct int key； datatypeinfo;node;inti，j；intflag；nodeX；node R1.n; 每循环一次作一次起泡 循环 i以1为步长，从1到n1，执行下列语句 (1)() (2)循环 j以1为步长，()，执行 若()Rj.key 则flag 1； XRj；()；Rj1 X (3)若() 则跳出循环。 算法结束。3. 有一个关键字序列为：138，219，365，513，206，211，511，276，868，641，试用图表示下列排序方法每一趟结束时的状态。（1） 直接插入排序（2） 折半插入排序（3） 希尔排序4. 有一个数据序列：（25,50,70,100,43,7,12）。现采用堆排序算法进行排序，写出每趟的结果。5. 初始输入序列的键值如下：（72，73，71，23，94，16，05，68，48，19，26）试采用二路归并排序法进行从小到大的排序，写出该序列在每遍扫描时的合并过程。6. 有一个关键字序列为：15，2，17，38，9，30，5，12，22，7，19试用图表示下列排序方法每一趟结束时的状态。（1） 快速排序（2） 归并排序（3） 基数排序7. 试举例说明各种内部排序方法中，哪些是稳定的，哪些是不稳定的？8. 若待排序的关键字序列为24，67，11，80，123，3，给出希尔排序的过程示意图。9. 判别以下序列是否为堆？是大根堆还是小根堆？如果不是，则把它调整为堆：（1）（13，60，33，65，24，56，48，92，86，56）（2）（100，88，40，68，35，39，43，56，65，20）（3）（108，98，54，34，66，23，42，12，30，52，06，20）（4）（05，56，18，22，40，38，29，60，35，76，28，100）10. 对于下列关键字序列用快速排序法进行排序时，哪一种情况速度最快？哪上种情况最慢？考虑有7个关键字的序列，进行快速排序，最快的情况下需要多少次比较？请说出理由。（1）（19，23，3，15，7，21，28）（2）（23，21，28，15，19，3，7）（3）（19，7，15，28，23，21，3）（4）（3，7，15，19，21，23，28）（5）（15，21，3，7，19，28，23）11. 证明快速排序是一种不稳定的排序。12. 若待排序的关键字序列为113，96，55，43，67，32，46，11，30，51，给出用归并排序进行排序的过程示意图。13. 从时间代价和空间代价出发，说明本章中各种排序方法的特点。14. 当Rlow.high中的关键字均相同时，Partion返回值是什么?此时快速排序的的运行时间是多少?能否修改Partion,使得划分结果是平衡的(即划分后左右区间的长度大致相等)?15. 若文件初态是反序的，则直接插入，直接选择和冒泡排序哪一个更好? 16. 判别下列序列是否为堆(小根堆或大根堆)，若不是，则将其调整为堆：(1) (100,86,73,35,39,42,57,66,21);(2) (12,70,33,65,24,56,48,92,86,33);(3) (103,97,56,38,66,23,42,12,30,52,06,20);(4) (05,56,20,23,40,38,29,61,35,76,28,100). 17. 若关键字是非负整数、快速排序、归并、堆和基数排序啊一个最快?若要求辅助空间为O(1)，则应选择谁? 若要求排序是稳定的，且关键字是实数，则应选择谁?18. 将哨兵放在Rn中，被排序的记录放在R0.n-1中，重写直接插入排序算法。19. 设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。请分析算法的时间复杂度。 20. 设向量A0.n-1中存有n个互不相同的整数，且每个元素的值均在0到n-1之间。试写一时间为O(n)的算法将向量A排序，结果可输出到另一个向量B0.n-1中。习题十一1 何谓递归过程？2 用C语言编写一个递归程序用来计算：1*2+2*3+3*4+（n-1）*n3 阅读下列算法，写出该递归算法实现的功能。再写一个循环算法的算法实现同样的功能。Int func（int n）if（n= =0）return（0）；return（n+func（n-1）；4 试写出模拟递归算法的汉诺塔问题的非递归算法。5 已知Ackerman函数的定义如下:(1) 写出递归算法(2) 写出非递归算法6 函数P以递归方式定义如下:(1) 请问此函数p的功能是什么?(2) 用C语言写出此函数的递归程序。习题十二1 填空题（1） 文件是_。（2） 文件的检索有_、_、_三种方式。（3） 文件的修改有_、_、_三种操作。（4） 顺序文件的检索可采用_检索方式。（5） 索引文件的检索可采用_或_检索方式。2 试叙述各种文件组织的特点，比较顺序文件、索引顺序文件、散列文件各自的优点和缺点。3 记录的插入、删除操作和记录的检索操作有什么联系？4 索引文件、散列文件和多关键字文件适合存放在磁带上吗?为什么?5 B+树和B-树的主要差异是什么?6 试比较ISAM文件和VSAM文件的特点。7 文件管理系统文件和数据库文件有什么相同和不同？8 记录的插入、删除操作和记录的检索操作有什么联系？9 散列文件为什么要按桶散列？桶的大小m时如何确定的？10 为什么组织文件索引一般采用多分树而不采用二叉树？ 11 B+树索引是动态索引结构还是静态索引结构？为什么？12 设有一个职工文件，其记录格式为:职工号姓名性别职务工资其中职工号为关键字，并设该文件由如下五个记录组成。表11.11物理地址职工号姓名性别职务工资10130王健男程序员300010253孙含男分析员400010312张金女程序员350010476丁一男测试员250010524赵华女分析员5000(1) 若该文件为顺序文件，请写出文件的存储结构；(2) 若该文件为索引顺序文件，请写出索引表；(3) 若该文件
展开阅读全文