数据结构与算法模拟题2.docx

《数据结构与算法模拟题2.docx》由会员分享，可在线阅读，更多相关《数据结构与算法模拟题2.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -数据结构与算法模拟题一、填空题：（共 15 分）（每空一分）1. 根据排序时， 存放数据的设备， 排序可分为 内部排序和外部排序。2. 图的常用的两种储备结构是邻接矩阵和邻接表。3. 数据结构中的三种基本的结构形式是 x 线性结构和树形结构、图形结构。4. 一个高度为 6 的二元树，最多有 63个结点。5. 线性查找的时间复杂度为：On，折半查找的时间复杂 度为：Onlogn、堆分类的时间复杂度为： Onlogn。6. 在采纳散列法进行查找时，为了削减冲突的机会，散列函数 必需具有较好的随机性，在我们介绍

2、的几种散列函数构造法 中，随机性最好的是 随机数法法、最简洁的构造方法是除留余数法。7. 线性表的三种储备结构是：数组、链表、静态链表。二、回答以下问题： （共 30 分）1. 现有如右图的树，回答如下问题：A ）根结点有： 6B） 叶结点有： 5C） 具有作大度的结点： 9 和 10可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学号：姓名：D）结点E）

3、 结点的祖先是： 0 和 2的后代是： 102. 栈存放在数组 Am 中，栈底位置是 m-1。试问：A） 栈空的条件是什么？ top=m-1B） 栈满的条件是什么？ 栈满 top=03. 数据结构和抽象数据型的区分与联系：数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。数据元素相互之间的关系称为结构。抽象数据类型：是指一个数学模型（数据结构）以及定义在该模型（数据结构）上的一组操作。4. 已知一株非空二元树，其先根与中根遍历的结果为：先根： ABCDEFGHI中跟： CBEDAGFHI将此二元树构造出来。5. 分析以下程序的运行时间：Avoidmysteryint n第 2 页（共

4、 5 页）可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学号：姓名：inti, j, k; fori=1; in; i+forj=i+1; j=n; j+ fork=1; k=j; k+somestatementrequiringO1time;这个应当是时间复杂度吧：On3B）voidpoddintnintI, j, x, y; forI=1; I=n;

5、 I+if oddI forj=I; j=n; j+x=x+1; forj=1; j=I; j+y=y+1;O（n2）6. 已知数学表达式是 3+bsinx+5 a/x2，求该表达式的波兰表示法的前缀和后缀表示（要求给出过程）。我感觉它的前缀表示法为-*+3bSIN+x5*/ax0.5，后缀表示法为3b+x5+SIN*ax/0.5*-。第 3 页（共 5 页）可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结

6、归纳 - - - - - - - - - - - -学号：姓名：三、实现以下算法： （共 0 分）1. 在指针实现的线性表L 中，实现在线性表 L中删除关键字为x 的结点。 共 7 分intdeleteValueListstructList*L,elemTypexinti,j;/* 从线性表中次序查找出值为x 的第一个元素 */ fori=0;isize;i+ifL-listi=x break;/* 如查找失败，说明不存在值为x 的元素，返回 0*/ ifi=L-sizereturn0;/* 删除值为 x 的元素 L-listi*/ forj=i+1;jsize;j+L-listj-1=L-l

7、istj;L-size-; return1;2. 设有如下图的双向环形链表L=a, b, c, d。请写出将该表转换为 L=b, a, c, d的简洁操作。（共 7 分）Labcd LLDRLa b c第 4 页（共 5 页）可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学号：姓名：dLL D RLLL-RL-RL=D-RL;D-RL=L-RL;LRL-LL-RL=D-LL;D-LL=L-RL-LL-LL;L-RL=D;四、对下面的带权连通无向图，用 Prim（普里姆）算法，构造一株最小生成树。画出构造过程的每一步。 （ 12 分）第 5 页（共 5 页）可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载