《数据结构》自考同步习题

数据结构习题集1概述、选择题:1、下列算法的时间复杂度是（）for(i=0;i〈n;i++)c[i]=i;A.O（1）B.O（n）C.O（log2n）D.O（nlog2n）2、数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（）索引存储方法B.顺序存储方法C.链式存储方法D.散列存储方法3、以下哪一个术语与数据的存储结构无关？（）。顺序表B.链表C.散列表D.队列4、算法在发生非法操作时可以做出处理的特性称为（）。正确性B.易读性C.健壮性D.高效性5、逻辑结构是指数据元素的（）A•关联方式B•存储方式C•结构D.数据项6、研究数据结构就是研究（）数据的逻辑结构数据的存储结构数据的逻辑结构和存储结构数据的逻辑结构、存储结构及其数据的运算7、从逻辑上可以把数据结构分为（B.B.紧凑结构和非紧凑结构D.内部结构和外部结构C.线性结构和非线性结构8、以下有关数据的叙述中错误的是（计算机能够处理的数据包括整数、实数、字符、声音、图像等数据的逻辑结构是从逻辑关系上描述数据，它取决于数据的存储方式C•数据存储结构的实现依赖于计算机语言D.数据的运算是定义在数据的逻辑结构上的9、数据的基本单位是（）数据结构B.数据元素数据项D.文件10、下列算法的时间复杂度是（）for(i=0;i〈m;i++)#63个稠密图G的最小生成树，最好用（）算法来求解。三、判断题：1、有回路的图不能进彳丁拓扑排序。2、连通分量是无向图中的极小连通子图。3、强连通分量是有向图中的极大强连通子图。4、任何一个有向图，其全部顶点可以排成一个拓扑序列。四、应用题：（）（）（）（）V1（）（）（）（）V1►Q2、写出下面有向图的邻接矩阵表示和拓扑排序序列。3、求下图的最小生成树，要求画出最小生成树的生成过程。16211151963314644、图G=(V,E),V={0,1,2,3,4,5},E={v0,l>,v0,2>,vl,4>,v2,5>,v5,4>,v4,3>,v5,3>}。写出图G中顶点的所有拓扑排序。六、查找一、选择题：TOC\o"1-5"\h\z1、二叉排序树中，关键字值最大的结点（）左指针一定为空B.右指针一定为空C.左、右指针均为空D.左、右指针均不为空2、顺序查找法适合于存储结构为的线性表。（）A•散列存储B.顺序存储或链接存储C•压缩存储D•索引存储3、在查找过程中，若同时还要做增、删工作，这种查找则称为（）A.静态查找B.动态查找C.内查找D.外查找4、对线性表进行二分查找时，要求线性表必须（）A.以顺序方式存储B.以顺序方式存储且兀素有序C.以链接方式存储D.以链接方式存储且兀素有序5、一棵二叉排序树匚用（）方法进行遍历，可以得到各结点键值的递增序列A.先根遍历B.中根遍历C.层次遍历D.后根遍历6、使用折半查找，线性表必须（）A.以顺序方式存储B.以链式方式存储，且元素已按值排好序C.以链式方式存储D.以顺序方式存储，且元素已按值排好序7、散列表的地址区间为0〜16,散列函数为H1（K）=K%17，采用线性探测法解决冲突，将关键字序列26,25,72,38,1,18,59依次存储到散列表中。元素59存放在散列表中的地址为（）。A.8B.9C.10D.118、索引顺序表的特点是顺序表中的数据（）。A•有序B•无序C•块间有序D•散列9、静态查找表与动态查找表两者的根本差别在于（）。A.逻辑结构不同B.存储实现不同C.施加的操作不同D.数据元素的类型不同10、设有序表的关键字序列为{1，4,6,10,18,35,42,53,67,71,78,84,92,99},当用二分查找法查找键值为84的结点时，经（）次比较后查找成功。TOC\o"1-5"\h\zA.2B.3C.4D.1211、索引顺序表中包含（）。A.顺序表B.索引表C.顺序表和索引表D.索引12、与其他查找方法相比，散列查找法的特点是（）。通过关键字比较进行查找通过关键字计算记录存储地址,并进行地址的比较。通过关键字计算记录存储地址，并进行一定的比较查找通过关键字比较进行查找，并计算记录存储地址13、在散列函数H（k）=kMODm中，一般来讲，m应取（）。A.奇数B.偶数C.素数D.充分大的数二、填空题：1、对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的（）上继续查找。2、（）查找法的平均查找长度与元素个数n无关。三、判断题：TOC\o"1-5"\h\z1、采用二分查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。（）2、散列法中的冲突指的是具有不同关键字的元素对应于相同的存储地址。（）3、中序遍历二叉排序树的结点不能得到排好序的结点序列。（）四、应用题：1、已知散列函数为H（k）=kmod13,关键值序列为19,01,23,14,55,20,84,27,68,11,10,77,处理冲突的方法为线性探测法，散列表长度为13,试画出该散列表。2、画出对长度为10的有序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。3、已知序列{4,5,2,9,1,3},给出二叉排序树的构造过程。4、已知散列函数为H(K)=Kmod12，关键字序列为25,37,52,43,84,99,120,15,26,11,70,82,采用拉链法处理冲突，构造开散列表。5、在地址空间为0〜16的散列区域中，对给定表(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec),取散列函数为H(x)=i/2，其中i为键值中第一个字母在英语字母表中的序号，画出以线性探测法处理的闭散列表。五、程序设计题：1、写出折半查找算法。6、排序一、选择题：TOC\o"1-5"\h\z1、对n个不同的排序码进行冒泡排序，在元素无序的情况下的次数为（）A.n+1B.nC.n-1D.n（n-1）/22、快速排序算法在最坏情况下的时间复杂度为（）A.O（n）B.O（nlog2n）C.O（n2）D.0（log2n）3、从未排序序列中挑选元素，将其放在已排序序列的一端，这种排序方法称为（）A.选择排序B.插入排序C.快速排序D.冒泡排序4、堆排序是一种（）排序A.插入B.选择C.交换D.归并5、下列排序方法中，排序趟数与序列的原始状态有关的方法是（）A•选择排序B•希尔排序C.堆排序D•冒泡排序6、堆的形状是一棵（）A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树7、在下列排序方法，不稳定的排序方法是（）A.直接插入排序B.直接选择排序C•冒泡排序D•归并排序8、快速排序在（）情况下最易发挥其长处被排序的数据中含有多个相同排序码被排序的数据已基本有序被排序的数据完全无序被排序的数据中的最大值和最小值相差悬殊9、若用冒泡排序对关键字序列｛18，16，14，12，10，8｝进行从小到大的排序，所需进TOC\o"1-5"\h\z行的关键字比较总次数是（）A.10B.15C.21D.3410、就平均时间而言，下列排序方法中最差的一种是（）A.堆排序B•快速排序C•归并排序D•选择排序11、记录的关键字序列为（7,6,8,4,3,5）,采用快速排序以第一个记录为基准得到的第一次划分结果是（）A.（5,3,6,4,7,8）B.（3,5,6,4,7,8）C.（6,4,3,5,7,8）D.（5,6,3,4,7,8）12、稳定的排序方法是（）A•直接插入排序和快速排序B•直接插入排序和冒泡排序C.简单选择排序和直接插入排序D.堆排序和归并排序13、对以下几个关键字序列进行快速排序，以第一个元素为轴，一次划分效果不好的是()。A.4，1，2，3,6，5，7B.4，3，1，7，6,5,2C.4，2，1，3,6，7，5D.1，2，3，4，5,6,714、堆排序属于()。A•归并排序B.选择排序C.快速排序D.直接插入排序15、若待排序序列已基本有序，要使它完全有序，从关键字比较次数和移动次数考虑，应TOC\o"1-5"\h\z当使用的排序方法是()。A.直接插入排序B.快速排序C.直接选择排序D.归并排序16、若一组记录的排序码为(46，79，56，38,40，84)，则利用堆排序的方法建立的初始堆为()。A.79，46，56，38，40，84B.84，79，56，38，40，46C.84，79，56，46，40，38D.84，56，79，40，46，3817、快速排序在最坏情况下的时间复杂度是()A.O(log2n)B.O(nlog2n)C.0(n2)D.0(n3)18、以下稳定的排序方法是()A.快速排序B.冒泡排序C.直接选择排序D.堆排序19、用冒泡排序的方法对n个数据进行排序，第一趟共比较()对元素。A.1B.2C.n-1D.n20、一个记录的关键字为(46,79,56,38,40,84),采用快速排序以第一个记录为基准得到的第一次划分结果是()A.(38,40,46,56,38,79,84)B.(40,38,46,79,56,84)C.(40,38,46,56,79,84)D.(40,38,46,56,79)二、填空题：1、在选择排序、堆排序、快速排序、直接插入排序中，稳定的排序方法是()2、快速排序在最坏情况下的时间复杂度是()3、()排序方法是从未排序序列中挑选元素，并将其依次放入已排序序列的一端。4、对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是()5、在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较()次。三、判断题：1、对于n个记录的集合进行冒泡排序，所需要的平均时间是O(n)()2、快速排序是一种稳定的排序方法。()3、冒泡排序是不稳定排序。()4、在堆排序和快速排序中，若原始记录已基本有序，则较适合