《2022年数据结构课件题目文件 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课件题目文件 .pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章1.算法的计算量的大小称为计算的（B ） 。A. 效率B. 复杂性C. 现实性D. 难度2.一个算法应该是（B ） 。A程序B问题求解步骤的描述C要满足五个基本特性DA 和 C. 3下面说法错误的是（A ）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A(1) B.(1),(2) C.(1),(4) D.(3) 4.在数据结构中，从逻辑上可以将之分为( D )。A. 动态结构和静态结构B
2、. 紧凑结构和非紧凑结构C. 内部结构和外部结构D. 线性结构和非线性结构5.计算算法的时间复杂度是属于一种( B )。A. 事前统计的方法B. 事前分析估算的方法C. 事后统计的方法D. 事后分析估算的方法6.可以用 ( D )定义一个完整的数据结构: A. 数据元素B. 数据对象C. 数据关系D. 抽象数据类型7.算法分析的目的是_C_。A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性8.设计一个 好 的算法应考虑达到的目标有_BCD_ 。A. 是可行的B. 是健壮的C. 无二义性D. 可读性好第二章1.线性表是具有n
3、个（ C ）的有限序列（n0） 。A表元素B字符C数据元素D数据项E信息项2.若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式 ( A )。A.单链表B.双向链表C.单循环链表D.顺序表3.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D ）存储方式最节省运算时间。A. 单链表B. 仅有头指针的单循环链表C. 双链表D. 仅有尾指针的单循环链表4.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( A )最节省时间。A. 带头结点的双循环链表B. 单循环链表C. 带尾指针的单循环链表D. 单链表5.静态链表中指
4、针表示的是( C ) A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址6.下述哪一条是顺序存储结构的优点？（C ）A插入运算方便B可方便地用于各种逻辑结构的存储表示名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 13 页 - - - - - - - - - C存储密度大D删除运算方便7.下面关于线性表的叙述中，错误的是哪一个？（B ）A线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进行插入和删除操作C线
5、性表采用链接存储，不必占用一片连续的存储单元D线性表采用链接存储，便于插入和删除操作。8.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间。A顺序表B双链表C带头结点的双循环链表D单循环链表9.链表不具有的特点是（B ）A插入、删除不需要移动元素B可随机访问任一元素C不必事先估计存储空间D所需空间与线性长度成正比10.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i 个元素的时间与 i 无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除
6、上类似，不需做元素的移动。以上错误的是（B ）A.(1),(2) B.(1) C.(1),(2),(3) D.(2) 11.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C ） 。A. O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 12.单链表中，增加一个头结点的目的是为了( C ） 。A使单链表至少有一个结点B标识表结点中首结点的位置C方便运算的实现D说明单链表是线性表的链式存储13.对于双向循环链表,在 p 指针所指的结点之后插入s 指针所指结点的操作应为（D ） 。A p-right=s ; s-left=p; p-ri
7、ght-left=s ; s-right=p-right; B p-right=s ; p-right-left=s ; s-left=p; s-right=p-right; C s-left=p; s-right=p-right; p-right=s ; p-right-left=s ; ; D s-left=p; s-right=p-right; p-right-left=s ; p-right=s ; 14.对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是（B ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL
8、第三章无第四章1.下面关于串的的叙述中，哪一个是不正确的？（B）A串是字符的有限序列B空串是由空格构成的串C模式匹配是串的一种重要运算D串既可以采用顺序存储，也可以采用链式存储2.串是一种特殊的线性表，下面哪个叙述体现了这种特殊性？（A）A. 数据元素是一个字符B. 可以顺序存储C. 数据元素可以是多个字符D. 可以链接存储3.串的长度是指（B ）A串中所含不同字母的个数B串中所含字符的个数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 13 页 - - - - - -
9、- - - C串中所含不同字符的个数D串中所含非空格字符的个数4.设 S 为一个长度为n 的字符串，其中的字符各不相同，则S 中的互异的非平凡子串（非空且不同于 S 本身）的个数为（C ） 。A2n-1 B2nC(2n/2)+(n/2) D(2n/2)+(n/2)-1 E. (2n/2)-(n/2)-1 F. 其他情况第五章1.数组是同类型值的集合。（F ）2.从逻辑结构上看，n 维数组的每个元素均属于n 个向量。（T ）3.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（F ）第六章1.n(n0)个结点的树的高度:最低是多少？ (2)最高是多少？ (n) 2.
10、n(n0)个结点的二叉树的高度:最低是多少？最高是多少？3.有关二叉树下列说法正确的是（B ）A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2 4.一棵 124 个叶结点的完全二叉树，最多有( C )个结点。A.247 B.248 C.249; D.250; E.251 5.已知一棵完全二叉树中共有626 个结点，叶子结点的个数应为( C )。A. 311 B. 312 C. 313 D. 314 E. 其它6.一个具有 1025 个结点的二叉树的高h 为（C ）A11 B10 C11 至 1025 之间D10 至 1024 之间
11、7.一棵树高为K 的完全二叉树至少有（C ）个结点A. K2 1 B. 12K 1 C. K2-1 D. K28.已知一棵度为3 的树有 2 个度为 1 的结点， 3 个度为 2 的结点， 4 个度为 3 的结点，则该树有 _12_个叶子结点。9.已知二叉树的先序序列 ABDFCEHG 中序序列 DBFAHECG 请构造该二叉树。10.已知二叉树的后序序列DMFBHELGCA 中序序列DBMFAHECGL请构造该二叉树。11.一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。先序序列为： _ _ C D E _ G H I _ K 中序序列为： C B _ _ F A
12、_ J K I G 后序序列为：_ E F D B _ J I H _ A 12.试找出满足下列条件的二叉树1）先序序列与后序序列相同2）中序序列与后序序列相同3）先序序列与中序序列相同4）中序序列与层次遍历序列相同13.一棵二叉树的前序遍历序列为ABCDEFG ，它的中序遍历序列可能是（B ） 。ACABDEFG B ABCDEFG CDACEFBG DADCFEGB 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 13 页 - - - - - - - - - A B
13、D E F G H I J K L C AB C D EF GHI JK L A G J B C D H I K E F L M N 14.一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足( C )。A. 其中任意一个结点均无左孩子B. 其中任意一个结点均无右孩子C. 其中只有一个叶子结点D. 其中度为 2 的结点最多为一个15.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( B )的二叉树A空或只有一个结点B. 高度等于其结点数C任一结点无左孩子D. 任一结点无右孩子16.二叉树在线索化后，仍不能有效求解的问题是（D ） 。A. 先序线索二叉树中求先序后继B. 中序
14、线索二叉树中求中序后继C. 中序线索二叉树中求中序前驱D. 后序线索二叉树中求后序后继17.引入二叉线索树的目的是（A ）A加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲D使二叉树的遍历结果唯一18.若 X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则x 的前驱为 ( C ) A. X 的双亲B. X 的右子树中最左的结点C. X 的左子树中最右结点D. X 的左子树中最右叶结点19.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( B )。A. 0 B. 1 C. 2 D. 不确定20.将树转换成二叉树树转换成的二叉树其
15、右子树一定为空21.森林转为二叉树22.已知一个森林的先序序列和后序序列如下，请构造出该森林。先序序列： ABCDEFGHIJKLMNO 后序序列： CDEBFHIJGAMLONK 解：森林的前序序列和后序序列对应其转换的二叉树的前序序列和中序序列，应先据此构造二叉树，再构造出森林23.设森林F 中有三棵树，第一，第二， 第三棵树的结点个数分别ABGCEHFJKILMND名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 13 页 - - - - - - - - - 为M1
16、， M2和M3 。 与 森 林F 对 应 的 二 叉 树 根 结 点 的 右 子 树 上 的 结 点 个 数 是（D )。AM1 BM1+M2 CM3 DM2+M3 24.设 F 是一个森林， B 是由 F 变换得的二叉树。若F 中有 n 个非终端结点，则B 中右指针域为空的结点有（C ）个。An-1 Bn Cn+1 Dn+2 25.设 X 是树 T 中的一个非根结点，B 是 T 所对应的二叉树。在 B 中，X 是其双亲的右孩子，下列结论正确的是( D )。A. 在树 T 中， X 是其双亲的第一个孩子B. 在树 T 中， X 一定无右边兄弟C. 在树 T 中， X 一定是叶子结点D. 在树
17、T 中， X 一定有左边兄弟26.设树形 T 在后根次序下的结点排列和各结点相应的次数如：后根次序：次数：请画出的树形结构图。27.给定权值 7，6，3，32，5，26，12，9，构造相应的哈夫曼树，并计算其带权路径长度。为使结果答案唯一，请用左结点的值小于等于右结点的值来构造哈夫曼树。第七章1.图中有关路径的定义是（A ） 。A由顶点和相邻顶点序偶构成的边所形成的序列B由不同顶点所形成的序列C由不同边所形成的序列D上述定义都不是2.设无向图的顶点个数为n，则该图最多有（B ）条边。An-1 Bn(n-1)/2 Cn(n+1)/2 D 0 E2n3.一个有 n 个结点的图，最少有（B ）个连通
18、分量，最多有（D ）个连通分量。A0 B1 Cn-1 Dn 4.要连通具有n 个顶点的有向图，至少需要（b）条边。An-l Bn Cn+l D2n 5.G 是一个非连通无向图，共有28 条边，则该图至少有_9_个顶点。6.用邻接表存储图所用的空间大小A 。A.与图的顶点数和边数都有关B.只与图的边数有关C.只与图的顶点数有关D.与边数的平方有关7.图 G 是 n 个顶点的无向完全图，则下列说法正确的有：BCD A. G 的邻接多重表需要n(n-1)个边结点和n 个顶点结点；B. G 的连通分量个数最少；C. G 为连通图；D. G 所有顶点的度的总和为n(n-1); 8.在有向图的邻接表存储结
19、构中，顶点v 在链表中出现的次数是( B )。A. 顶点 v 的度B. 顶点 v 的出度C. 顶点 v 的入度D. 依附于顶点v 的边数8.图的遍历举例(1)假定以邻接表存储，邻接点按编号升序排列。遍历序列如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 13 页 - - - - - - - - - V11 4 3V2V3V4V5V62 4 5 3 5 2 0 1 2 3 v2 v4 v1 v5 v3 v6 v7 v8 v2 v4 v1 v5 v3 v6 v2 v4
20、v1 v5 v3 v6 16 21 11 14 33 6 19 18 6 5 深度优先搜索：V1-V2-V4-V8-V5-V6-v3-v7 广度优先搜索V1-V2-V3-V4-v5-v6-v7-v8 (2)已知邻接矩阵求遍历序列深度优先搜索：V1-V2-V3-V4-V5 宽度优先搜索：V1-V2-V3-V4-V5 (3)已知邻接表求遍历序列深度优先遍历：V1-V2-V3-V6-V5-V4 宽度优先遍历：V1-V2-V5-V4-V3-V6 9.深度优先 (广度优先 )生成树10.最小生成树v1 v2 v3 v4 v5 v6 1 3 5 2 0 4 1 0 5 4 4 0 2 3 5 1 2 4
21、0011000010010000000001110名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 13 页 - - - - - - - - - 1235461425483234567123546142548323456711.试画出从顶点v1 开始利用 Prim 算法得到的最小生成树12.利用 Kruskal 算法求最小生成树42104952812981105121V2V3V1V4V58 1 12 10 2 5 4 9 名师资料总结 - - -精品资料欢迎下载 - - -
22、 - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 13 页 - - - - - - - - - abedcfb c a * d * * * + + e + V1V2V5V6V0V3V41 4 3 2 10 100 50 20 60 30 5 10 v2 v4 v1 v5 v3 v6 v2 v4 v1 v5 v3 v6 13.用DAG图描述表达式(a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e) 14.AOV- 网的拓扑排序15.写出有向图的所有拓扑排序，并指出应用教材中的算法求得的是哪个序列，设邻接表的边表结点
23、中的邻接点序号是递增的。16.求最短路径17.求最短路径 Floyd 算法18.设图如右所示，在下面的5 个序列中，符合深度优先遍历的序列有多少？（D ）a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c A5 个B4 个C3 个D2 个19.下面哪一方法可以判断出一个有向图是否有环（回路）： （AB ）A. 深度优先遍历B. 拓扑排序 C. 求最短路径D. 求关键路径名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第
24、8 页，共 13 页 - - - - - - - - - 20.在有向图 G 的拓扑序列中， 若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是（ D ） 。AG 中有弧 BG 中有一条从Vi 到 Vj 的路径CG 中没有弧 DG 中有一条从Vj 到 Vi 的路径21.关键路径是AOE 网中 ( B ) A. 从始点到终点的最短路径B. 从始点到终点的最长路径C. 从始点到终点的边数最多的路径D. 从始点到终点的边数最少的路径22.下列关于 AOE 网的叙述中，不正确的是（B ） 。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有
25、的关键活动提前完成，那么整个工程将会提前完成D某些关键活动若提前完成，那么整个工程将会提前完成23.下列有关图的说法错误的是（C ）A. 在有向图中，出度为0的结点 4 称为叶子。B. 用邻接矩阵表示图，容易判断任意两个结点之间是否有边相连，并求得各结点的度。C. 按深度方向遍历图和先根次序遍历树类似，得到的结果是唯一的。D. 若有向图 G 中从结点Vi 到结点 Vj 有一条路径，则在图G 的结点的线性序列中结点Vi必在结点 Vj 之前的话，则称为一个拓扑序列。第八章1.地址为10)1664(大小为10)128(的存储块的伙伴地址是什么？buddy(1664,7)=1664-72=1536 2
26、.地址为10)2816(大小为10)64(的存储块的伙伴地址是什么？buddy(2816,6)=2816+62=2880 3.已知一个大小为512 个字长的存储， 假设先后有6 个用户申请大小分别为23，45，52，100，11 和 19 的存储空间，然后再顺序释放大小为45，52，11 的占用块。假设以伙伴系统实现动态存储管理。（1） 画出可利用空间表的初始状态。（2） 画出为6 个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。（3） 画出在回收3 个占用块之后可利用空间表的状态。第九章1.画出含有 12 个元素的有序表的判定树（1）求查找成功时的平均查找
27、长度（2）求查找失败时的平均查找长度2.若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为( C )。A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 3.对线性表进行二分查找（就是折半查找）时，要求线性表必须（）A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序4.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( C ) A. 必定快B. 不一定C. 在大部分情况下要快D. 取决于表递增还是递减5.在有序表
28、A1 20中，按二分查找方法进行查找，查找长度为4 的元素的下标从小到大依名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 13 页 - - - - - - - - - 次是 _1，3，6， 8，11，13，16，19_ 6.分块检索中， 若索引表和各块内均用顺序查找，则有 900 个元素的线性表分成_30_块最好：若分成25 块，其平均查找长度为_31.5（块内顺序查找）_。7.设关键码序列为：63，90，70，55，67，42，98，83，则构造一棵二叉排序树的过程如下
29、：8.二叉排序树上删除10 或40或45或559.构造二叉排序树将for,case,while,switch,break,do,define,const,if,int中的关键字依次插入初态为空的二叉排序树（按字母在字母表中的序号排序）中，请画出所得到的树T。然后画出删除for 之后的二叉排序树 T。10.按关键字序列15,21,27,43,36,8,11 构造平衡二叉树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 13 页 - - - - - - - - - 11.构
30、造平衡二叉树给定表 25， 18，48，07，76，52，81，70，92，15 ，按表中元素顺序构造一棵AVL 树，并求其在等概率情况下查找成功的平均查找长度。12.已知长度为11 的表（ xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon）按表中元素顺序依次插入一棵初始为空的: (1) 二叉排序树 ; (2) 平衡二叉排序树；(3) 最佳二叉排序树分别求其在等概率的情况下查找成功的平均查找长度。13.二叉查找树的查找效率与二叉树的( （1）C )有关, 在 (（ 2）C )时其查找效率最低(1) A. 高度B. 结点的多少C. 树型D. 结点的位置(2) A
31、. 结点太多B. 完全二叉树C. 呈单枝树D. 结点太复杂。14.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C ) A.(100,80,90,60,120,110,130) B.(100,120,110,130,80,60,90) C.(100,60,80,90,120,110,130) D.(100,80,60,90,120,130,110) 15.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A, 并已知 A 的左孩子的平衡因子为0，右孩子的平衡因子为1,则应作 ( C ) 型调整以使其平衡。A. LL B. LR C. RL D. RR 16.
32、设二叉排序树中关键字由1 到 1000 的整数组成，现要查找关键字为363 的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。（1）51,250,501,390,320,340,382,363 （2）24,877,125,342,501,623,421,363 答：序列（ 2）不可能是二叉排序树中查到363 的序列。查到501 后，因 363501，后面应该出现小于501 的数，但序列中出现了623，故不可能。17.下面关于 m 阶 B 树说法正确的是( B ) 每个结点至少有两棵非空子树；树中每个结点至多有m 一 1 个关键字 ; 所有叶子在同一层上; 当插入一个数据项
33、引起B 树结点分裂后，树长高一层。A. B. C. D. 18.下面关于 B 和 B+ 树的叙述中，不正确的是( C ) A. B 树和 B+树都是平衡的多叉树。B. B 树和 B+树都可用于文件的索引结构。C. B 树和 B+树都能有效地支持顺序检索。D. B 树和 B+树都能有效地支持随机检索。19.一棵 3 阶 B-树中含有 2047 个关键字，包括叶子结点层，该树的最大深度为( B )。A. 11 B. 12 C. 13 D. 14 20.已知 2 棵 2-3 B-树如下（省略外结点） ： 对树（ a）,请分别画出先后插入26，85 两个新结点后的树形；对树（ b）,请分别画出先后删除
34、53，37 两个结点后的树形。21.下面关于哈希 (Hash，杂凑 )查找的说法正确的是( C ) A哈希函数构造的越复杂越好，因为这样随机性好，冲突小B除留余数法是所有哈希函数中最好的45241 0 05061 7 030 3 753 9 03 1 2452410 035361 903770名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 13 页 - - - - - - - - - C不存在特别好与坏的哈希函数，要视情况而定D若需在哈希表中删去一个元素，不管用何种方法
35、解决冲突都只要简单的将该元素删去即可22.假定有 k 个关键字互为同义词，若用线性探测法把这k 个关键字存入散列表中，至少要进行多少次探测？( D ) A. k-1 次B. k 次C. k+1 次D. k（k+1）/2 次23.散列函数有一个共同的性质，即函数值应当以( D )取其值域的每个值。A. 最大概率B. 最小概率C. 平均概率D. 同等概率24.将 10 个元素散列到100000 个单元的哈希表中，则（C ）产生冲突。A. 一定会B. 一定不会C. 仍可能会第十章1.在对一组记录（54，38，96，23，15， 72，60，45，83）进行直接排序时，当把第7 个记录 60 插入到有
36、序表时，为寻找插入位置需比较多少次希尔排序示例：请给出对一组记录（54,38,96,23,15,90,72,60,45,83）进行希尔排序（增量序列为 5， 3，1）时的排序过程。冒泡排序示例：一组关键字（ 19,01,26,92,87,11,43,87,21） ，进行冒泡排序，试列出每一趟排序后的关键字序列快速排序示例对下列一组关键字（46,58,15,45,90,18,10,62）试写出快速排序的每一趟的排序结果堆排序示例已知一组关键字（46,58,15,45,90,18,10,62）试写出堆排序建的初始堆和排序的过程2.已知 8 个记录，其关键字分别为(179，208，306，093，8
37、59，984， 271，033) 试用基数排序法实施排序，描述其排序过程3.以关键码序列（503，087，512，061， 908，170，897，275，653，246）为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：（1）直接插入排序； （2）希尔排序（增量5， 3，1） ； （3）起泡排序（4）快速排序； （5）简单选择排序（6）堆排序；（7）归并排序；（8）基数排序。4.下列内部排序算法中：A. 快速排序B. 直接插入排序C. 二路归并排序D. 简单选择排序E. 起泡排序F. 堆排序(1)其比较次数与序列初态无关的算法是( CD ) (2)不稳定的排序算法是( ADF )
38、 (3)在初始序列已基本有序(除去 n 个元素中的某k 个元素后即呈有序，kn) 的情况下， 排序效率最高的算法是( B ) (4)排序的平均时间复杂度为O(n?logn)的算法是 ( ACF ),为 O(n?n)的算法是 ( BDE ) 5.设被排序的结点序列共有N 个结点， 在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为( C )。A. O(N) ，O(N) ，O(N) B. O(N) ，O(N*log2N), O(N*log2N) C. O(N) ，O(N*log2N), O(N2) D. O(N2) ，O(N*log2N
39、), O(N2) 6.一个排序算法的时间复杂度与( B )有关。A. 排 序 算 法 的 稳 定 性B. 所 需 比 较 关 键 字 的 次 数C. 所 采 用 的 存 诸 结 构D. 所需辅助存诸空间的大小7.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 13 页 - - - - - - - - - 为基准得到的一次划分结果为( C )。A. (38,40,46,56,79,
40、84) B. (40,38,46,79,56,84)C. (40,38,46,56,79,84) D. (40,38,46,84,56,79) 8.有些排序算法在每趟排序过程中，都会有一个元素被放置在其最终的位置上，下列算法不会出现此情况的是( A )。A. SHELL排序（希尔排序）B. 堆排序C. 冒泡排序D. 快速排序9.在下列排序方法中，( D )方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。A、快速排序B、冒泡排序C、堆排序D、插入排序10.就分类算法所用的辅助空间而言，堆分类、快速分类和归并分类的关系是( A )。A. 堆分类 快速分类 归并分类
41、B. 堆分类 归并分类 归并分类 快速分类D. 堆分类 快速分类 归并分类11.设要将序列 (q,h,c,y,p,a,m,s,r,d,f,x) 中的关键码按字母升序重新排序，(1)( B ) 是初始步长为4 的 shell 排序一趟扫描的结果；(2)( C ) 是对排序初始建堆的结果；(3)( A ) 是以第一个元素为分界元素的快速一趟扫描的结果从下面供选择的答案中选出正确答案填入括号内。A.f,h,c,d,p,a,m,q,r,s,y,x B.p,a,c,s,q,d,f,x,r,h,m,y C.a,d,c,r,f,q,m,s,y,p,h,x D.h,c,q,p,a,m,s,r,d, ,x,y
42、E.h,q,c,y,a,p,m,s,d,r,f,x 12.基于比较方法的n 个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是( A )。A. O(nlogn) B. O(logn) C. O(n) D. O(n*n) 13.外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。( F ) 14.在外排序过程中，对长度为n 的初始序列进行 置换选择 排序时，可以得到的最大初始有序段的长度不超过n/2。( F ) 15.外排中使用置换选择排序的目的，是为了增加初始归并段的长度。T 16.在执行某种排序算法的过程中出现了排序码朝着最终排序序列相
43、反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？答： 这种说法不对。 因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对4，3，2，1气泡排序就可否定本题结论了。17.设某文件经内排序后得到100 个初始归并段 (初始顺串 ),若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？答：设归并路数为k，归并趟数为s，则 s=100logk，因为 100logk=3，因为 k 为整数，故 k=5,即最少 5-路归并可以完成排序。18.设有 11 个长度 (即包含记录的个数)不同的初始
44、归并段，它们所包含的记录个数分别为25,40,16,38,77,64,53,88,9,48,98。试根据它们做4路平衡归并，要求：(1)指出总的归并趟数；(3 分)(2)构造最佳归并树；(8 分) (3)根据最佳归并树计算每一趟及总的读记录数。(5 分) 答： （1）三趟归并 （2）最佳归并树图略。（3）设每次读写一个记录。第一趟 50 次读写总的读写次数：5052 (9+16)*3+(25+38+40)*2+(48+53+64+77)*2+(88+98)*2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 13 页 - - - - - - - - -