自学考试-数据结构导论自考题模拟2

《自学考试-数据结构导论自考题模拟2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构导论自考题模拟2一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的。丄、具有10个顶点的有向完全图应具有（）A.20条弧B.50条弧C.90条弧D.100条弧2、在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的（A.先根遍历B.中根遍历C.后根遍历D.按层次遍历3、在无向图中，所有顶点的度数Z和是所有边数的（）A.0・5倍B.丄倍C.2倍D.4倍4、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）A・n条边B.n+丄条边5、从V］出发，对下图按广度优先搜索遍历,C.n-l条边D.?条边则可能得到的i种顶点序列为（V3v5v6v4V6v4

2、v5v2A.V1V2V3V5V/]VgB.ViV2C・Viv5V2v3v6V4D・Viv36、设图G采用邻接表存储，则拓扑排序算法的时间复杂度为（）A.0（n）B・O（n+e）C・0肝）D.0（n*e）7、设顺序表的长度为n,则其每个元素的平均查找长度是（）A・nB・（n-l）/2C・n/2D・（n+1）/28、对一棵二叉排序树采用中序遍历进行输出的数据一定是（）A.递增或递减序列B.递减序列C.无序序列D.递增序列9、二分查找算法要求被查找的表是（）A・键值有序的链表B・键值不一定有序的链表C.键值有序的顺序表D.键值不一定有序的顺序表10.适用于静态查找表的方法为（）A.

3、二分查找、二叉排序树查找B.二分查找、索引顺序表查找C.二叉排序树查找、索引顺序表查找D.二叉排序树查找、散列法查找11＞排序屮关键字比较次数与序列的原始状态有关的排序方法是（）A.插入排序法B.希尔排序法C.直接选择排序法D・堆排序法12、下面给出的四种排序法中，属于不稳定的排序法的是（）A.插入排序法B.冒泡排序法C.二路归并排序法D.堆排序法13、若用冒泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序，需要进行比较的次数是（）A・33B・45C.70D.9114、直接插入序列在最好情况下吋间复杂度为（）A.0（

4、log2n）B.0（n）C.0（n*log2n）D.0（n2）丄5、一组记录的关键字为｛45,80,55,40,42,85）,则利用堆排序的方法建立的初始堆为（）A・80,45,55,40,42,85B・40,42,55,80,45,85C.40,42,45,55,80,85D・85,55,80,42,45,40二、填空题16、要连通具有n个顶点的有向图，至少需要条弧。17、在无向图的邻接矩阵A中，若等于1,则A[jzi]等于o18、含n个顶点的连通图中的任意一条简单路径，其长度不可能超过o19、有向图G用邻接矩阵A[l・・n,l・・n]存储，其第i列的所有元素Z和等于顶点V

5、）的。20、对含有n个结点，e条边的无向连通图，利用Prim算法生成最小生成树的时间复杂度为21、用来标识数据元素的数据项称为o22、对于具有n个元素的数据序列，若采用二分查找法，当n的值较大吋其平均查找长度为‘23、在索引顺序表上的查找分两个阶段：一是,二是在块内查找待查的元素。24、直接插入排序需要个记录的辅助空间。25、在插入和选择排序中，若初始数据基木正序，则选用排序。26、归并排序要求待排序列由若干个的子序列组成。27、对n个记录的集合进行快速排序，其最坏情况下所需的吋间复杂度是o28、排序通常可分为内部排序和外部排序，其中内部排序是指排序的整个过程中，数据全部存放

6、在计算机的中。三、应用题29、已知无向图G的邻接矩阵如图所示，假设对其每行元素访问吋必须从右到左，请写出从V。开始的深度优先搜索的序列。rD110Vl1011111011D1101V.101110VoV]Vjv330、求下图的最小生成树。31、用二分查找法对一个长度为10的有序表进行查找，填写查找每一元素需要的比较次数。元素下标：12345678910比较次数：32、对于下列一组关键字(46,58,15,45,90,18,10,62),试写出快速排序每一趟的排序结果，并标出第一趟中各元素的移动方向。33、有一组初始的无序序列为（98,65,38,40,12,51,100,77

7、,26,88）,给出对其进行二路归并排序（升序）的每一趟的结果。四、算法设计题34、试写岀从大到小输出二叉排序树中所有不小于X的元素的算法。35、设计一个用链表表示的直接选择排序算法。答案：一、单项选择题1>C［解析］木题主要考查的知识点是一个具有n个顶点的有向完全图的弧数。［要点透析］任何两点Z间都有弧的有向图称为有向完全图。一个具有n个顶点的有向完全图的弧数为Pj；=n（n—1）,则本题中的有向完全图应具有的弧数为90条。2、D［解析］本题主要考查的知识点是广度优先搜索。［要点透析］连通图广度优先搜