《数据结构(c++)模拟试题》由会员分享,可在线阅读,更多相关《数据结构(c++)模拟试题(9页珍藏版)》请在金锄头文库上搜索。
1、模拟试题3一选择题1.当初始序列已按健值有序时,用直接插入算法进行排序,需要比较的次数为( )A.n-1 B.log2n C. 2log2n D.n2冒泡排序n2选择排序n2插入排序n2堆排序nlog n归并排序nlog2n快速排序n2希尔排序n22.以下时间复杂性不是O(n2)的排序方法是( )A.直接插入排序 B.二路归并排序 C.冒泡排序 D.直接选择排序3.对采用二分查找法进行查找运算的查找表,要求按( )方式进行存储。A.顺序存储 B 链式存储C.顺序存储且结点按关键字有序 D.链式存储且结点按关键字有序4.设有序表的关键字序列为1,4,6,10,18,35,42,53,67,71,
2、78,84,92,99,当用二分查找法查找健值为84的结点时,经( )次比较后查找成功。A.2 B. 3 C. 4 D. 125.静态查找表与动态查找表两者的根本差别在于( ). A.逻辑结构不同 B.存储实现不同C.施加的操作不同 D.数据元素的类型不同6用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为 A.O(n2) B. O(nlog2n) C. O(n) D.O(log2n)7.设有6个结点的无向图,该图至少应有( )条边能确保是一个连通图。A. 5 B. 6 C. 7 D 88.在无向图中,所有顶点的度数之和是所有边数的( )倍。A.05 B.1 C.2 D.4 9.深度为6
3、的二叉树最多有( )个结点.A.64 B.63 C.32 D.3110将含有83个结点的完全二叉树从根结点开始编号,根为1号,后面按从上到下、从左到右的顺序对结点编号,那么编号为41的双亲结点编号为 ( )A.42 B.40 C.21 D.2011.已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是( )A.acbed B.deabc C.decab D.cedba12.设二叉树结点的先根序列、中根序列和后根序列中,所有叶子结点的先后顺序( )A.都不相同 B.完全相同 C.先序和中序相同,而与后序不同 D.中序和后序相同,而与先序不同13如果以链表作为栈的存
4、储结构,做退栈操作时( )A.必须判别栈是否满 B.必须判别栈是否空C.判别栈元素的类型 D.对栈不做任何操作14链栈与顺序栈相比,有一个比较明显的优点即( )A.插入操作更方便 B. 通常不会出现栈满的情况C.不会出现栈空的情况 D. 删除操作更方便 15.线性结构中的一个结点代表一个( ) A. 数据元素 B. 数据项 C. 数据 D. 数据结构二填空题1.若待排序的序列中存在多个记录具有相同的键值,经过排序,这些记录的相对次序仍然保持不变,则称这种排序方法是_的,否则称为_的。2.按照排序过程涉及的存储设备的不同,排序可分为_排序和_排序。3.直接插入排序是稳定的,它的时间复杂性为_,空
5、间复杂度为_。4.对于n个记录的集合进行冒泡排序,其最坏情况下所需的时间复杂度是_。5.二叉排序树是一种特殊的、增加了限制条件的二叉树,其限制条件是任一结点的键值_于其左孩子(及其子孙)的键值且_于其右孩子(及其子孙)的键值。6.中根遍历一棵二叉排序树所得的结点访问序列是键值的_序列。7.平衡二叉排序树上任一结点的平衡因子只可能是_、_或_。8.采用散列技术时需要考虑的两个主要问题是:一、_?二、_?9.一个具有n个顶点的完全无向图的边数为_。一个具有n个顶点的完全有向图的弧度数为_。10.遍历图的基本方法有_优先搜索和_优先搜索两种。11.在无向图中,如果从顶点v到顶点v有路径,则称v和v是
6、_的。如果对于图中的任意两个顶点vi,vjV,且vi和vj都是连通的,则称G为_。12.二叉树第i(i=1)层上至多有_个结点。13.深度为k(k=1)的二叉树至多有_个结点。14.具有n个结点的二叉树中,一共有_个指针域,其中只有_个用来指向结点的左右孩子,其余的_个指针域为NULL。15有m个叶子结点的哈夫曼树,其结点总数为_。16需要压缩存储的矩阵可分为_矩阵和_矩阵两种。17队称为_线性表。18.从某种意义是说,数据、数据元素和数据项实际反映了数据组织的三个层次,数据可由若干个_构成,数据元素可由若干个_构成。19.常见时间复杂性的量级有:常数阶O(_)、对数阶O(_)线性阶O(_)、
7、平方阶O(_)、和指数阶O(_)。20.线性结构的基本特征是若至少含有一个结点,则除起始结点没有直接_外,其他结点有且仅有一个直接_;除终端结点没有直接_外,其它结点有且仅有一个直接_.三名词解释题 1.排序 2.堆 3. .查找长度 4.无向完全图 5.有向完全图6. 二叉树 7. 满二叉树 8.栈 9.队列 10.链表 四简答题1. 什么是二叉排序树?2. 什么是顺序表?3. 什么叫稀疏矩阵?4. 静态查找表与动态查找表的区别是什么?5. 什么叫无向图?五解答题1判断下列两序列是否为堆?若不是,按照建堆的思想把它调整为堆,并用图表示建堆的过程。(1)(3,10,12,22,36,18,28
8、,40);(2)(5,8,11,15,23,20,32,7)。2已知数据序列为(12,5,9,20,6,31,24),对该数据序列进行排序,试写出插入排序和冒泡排序每趟的结果。3.对长度为20的有序表进行二分查找,请画出它的一棵判定树,并求等概率情况下的平均查找长度。六算法设计题1.找出数组A1.n中元素的最大值和次最大值(本小题以数组元素的比较为标准操作)。2.在数组A1.n中查找值为K的元素,若找到则输出其位置i(1=i1,试设计一个算法,求数组An的逆序。模拟试题4一、单项选择题1.下面程序段的时间复杂度是( )for(i=0;in;i+) for(j=1;jnext; B.p-next
9、=p-next-next;C.p-next=p; D.p=p-next-next;3.在头指针为head且表长大于1的单循环链表中,指针p指向表中某个结点,若p-next-next=head,则( )A.p指向头结点 B.p指向尾结点C.*p的直接后继是头结点 D.*P的直接后继是尾结点4.判定“带头结点的链队列为空”的条件是( )A. Q.front=NULL B. Q.rear=NULLC. Q.front=Q.rear D. Q.front!=Q.rear5.设有两个串T和P,求P在T中首次出现的位置的串运算称作( )A.联接 B.求子串 C.字符定位 D.子串定位6.广义表A=(a,(
10、b),(),(c,d,e)的长度为( )A.4 B.5 C.6 D.77.一棵含18个结点的二叉树的高度至少为( )A.3 B.4 C.5 D.68.已知二叉树的先序序列为ABDECF,中序序列为DBEAFC,则后序序列为( )A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA9.无向图中一个顶点的度是指图中( )A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数C.通过该顶点的回路数 D.与该顶点连通的顶点数10.在有向图中,所有顶点的入度之和是所有顶点出度之和的( )倍。 A.05 B. 1 C. 2 D.4 11.在下列排序方法中,平均时间复杂度为O(nlogn)
11、且空间性能最好的是( )A.快速排序 B.堆排序 C.归并排序 D.基数排序12.已知一组关键字为25,48,36,72,79,82,23,40,16,35,其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是( )A.25,36,48,72,23,40,79,82,16,35 B.25,36,48,72,16,23,40,79,82,35C.25,36,48,72,16,23,35,40,79,82 D.16,23,25,35,36,40,48,72,79,8213.设有序表的关键字序列为1,4,6,10,18,35,42,53,67,71,78,84,92,99,当用二分查找法查找健值为84的结点时,经( )次比较后查找成功。A.2 B. 3 C. 4 D. 12