资源预览内容
第1页 / 共26页
第2页 / 共26页
第3页 / 共26页
第4页 / 共26页
第5页 / 共26页
第6页 / 共26页
第7页 / 共26页
第8页 / 共26页
第9页 / 共26页
第10页 / 共26页
亲,该文档总共26页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数据结构与算法试题一、选择题1. 在逻辑上可以把数据结构分成( A)A. 线性结构和非线性结构C.紧凑结构和非紧凑结构B. D.动态结构和静态结构内部结构和外部结构C2. 单链表中各结点之间的地址()A.必须连续B.部分必须连续C.不一定连续D.以上均不对3. 在一个长度为 n 的顺序表中向第 i 个元素( 0i=n+1 )之前 插入一个新元素时,需向后P二移动(B )个元素。A 、n-iB、n-i+1C、n-i-1DO、i4. 插入和删除操作只能在一端进行的线性表,称为(A. 队列C )。B.线性表C.栈B. 循环队列A( )5、队列是仅允许在()进行插入,而在()进行删除A. 队尾,队首B. 队尾,队尾C. 队首,队尾D. 队首,队首6.链表适合于(A )查找。A顺序B.二分C.随机D.顺序或二分7. 数据的基本单位是(A.数据元素A )。B.数据结构C.数据项D.数据对象8. 下列哪个不是算法的特性(A.有穷性B)。B.可数性C.可行性D.确定性9. 在表长为 n 的顺序表中进行线性查找,它 的平均查找长度为 ( B)。A. ASL=nB. ASL=(n+1)/2C. ASL=n +1 D.ASL=log2n10. 一个线性表第一个元素 的存储地址是 320,每个元素 的长度 为 3,则第五个元素的地址是(C )。A. 311B. 328C. 332D. 31311. 设front s rear分别为循环双向链表结点的左指针和右指针, 则指针P所指的元素是双D循环链表L的尾元素的条件是()。 A.P=LB. P-front=LC. P=NULLD. P-rear=L12. 已知P为单链表中的非首尾结点,删除P结点的后继结点Q 的语句为(A )。A. P-NEXT=Q-NEXT;FREE(Q);C. Q-NEXT=P-NEXT;FREE(Q);B. Q-NEXT=P; FREE(Q); D.P-NEXT=S;S-NEXT=P;13. 循环队列SQ队满的条件是(B)。A. SQ-rear=SQ-frontB. (SQ-rear+1)%MAXLEN=SQ-frontC. SQ-rear=0D. SQ-front=014. 一组记录 的排序码为( 46, 79,56,38, 40,84),则利 用堆排序的方法建立的初始堆B为( )。A 、 79,46,56, 38,40,80B、84,79,56, 38,40,46C 、 84,79,56, 46,40,38D 、 84,56,79, 40,46,3815. 排序趟数与序列原始状态 (原始排列 )有关 的排序方法是 ( ACD )方法。A 、插入排序 C 、冒泡排序B、选择排序 D 、快速排序B16. 下列排序方法中,()是稳定 的排序方法。 A 、直接选择排 序 C 、希尔排序B 、二分法插入排序 D、快速排序17. 数据序列( 8,9,10,4,5,6,20,1, 2)只能是下列排 序算法中 (C ) 的两趟排序后的结果。 A 、选择排序 C 、插入排序B D、冒泡排序、堆排序18.对序列 (15,9,7,8,20,-1,4)进行排序,进行一趟排序 后,数据的排列变为( 4,9,-1,8,20,7,15),则采用的是(C )排序。A、选择C、希尔B D、快速、冒泡19. 一组待排序记录的关键字为(46,79,56,38,40,84),则利用快速排序,以第一个 记录为基准元素得到的一次划分结果为( C)。A(38,40,46,56,79,84) C 、(40,38,46,56,79,84) D 、(40,38,46,84,56,79)B、(40,38,46,79,56,84)20. 用直接插入排序对下面四个序列进行排序(由小到大) ,元素 比较次数最少的是(C)。A、94,32,40,90,80,46,21,69 C 21,32,46,40,80,69,90,94B、32,40,21,46,69,94,90,80、90,69,80,46,21,32,94,40D 21.若用冒泡排序对关键字序列( 18,16,14,12,10,8)进行从小 到大 的排序,所需进行的关键字比较总次数是( B )。A、10B、15C、21D、3422. 就排序算法所用 的辅助空间而言,堆排序、快速排序和归并排 序 的关系( A)。A 、堆排序 快速排序 归并排序B、堆排序 归并排序 快速排序C、堆排序归并排序快速排序D、堆排序快速排序归并排序23. 最小生成树的构造可使用(B )算法。A. Dijkstra 算法B. Prim 算法C. Haffman 算法D. FIoyd 算法24. 具有 32个结点的完全二叉树的深度为(A. 5B. 6 B)。C. 7D. 825. 在有 n 个叶子结点的哈夫曼树中,其结点总数为( D)。A .不确定 B.2n C . 2n + 1 D . 2n-126. 下列陈述正确的是(B)oA. 二叉树是度为2的有序树C.二叉树必有度为2的结点B.D.二叉树中最多只有二棵树,且有左右子树之分 二叉树中结点只有一个孩子时无左右之分27. 先序为A,B,C的二叉树共有(A)种。A. 3B. 4C. 5D. 628. 在树结构中,若结点B有3个兄弟,A是B的父亲结点,则A的 度为 (B)。A. 3B. 4C. 5D. 629. 在一个图中,所有顶点的度数之和等于所有边数的(A、1、2、3、4 B)倍。B C D30. n个顶点的强连通图至少有(A)边。A、n、n-1 、n+1B C D、n (n-1)31. 在一个无向图中,所有顶点的度数之和等于所有边数的( C) 倍;在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的(C)倍。A、1/2 B、2 C、1 D、432. 任何一个无向连通图的最小生成树(B)。A、只有一棵B、一棵或多棵、可能不存在C、一定有多棵D33. 在图的表示法中,表示形式唯一的是(A)A. 邻接矩阵表示法B、邻接表表示法C、逆邻接矩阵表示法D、逆邻接表表示法34. 在一个具有n个顶点的无向图中,要连通全部顶点至少需要(B. n+1C. n-1D. n+2 C)条边。A.n35. 在一个图中,所有顶点的度数之和等于图的边数的(B)。A 1/2B 2C 1D 4C36有 7个结点 的有向完全图有( )边。 A.30B. 40C. 42D. 5637.假定在一棵二叉树中,度为 2 的分支结点个数为 15,度为 1 的分支结点个数为 30个,则叶子结点数为( B)。A 、 15B、16C、17 D、4738. 设n , m为一棵树上的两个结点,在中根遍历时,n在m前 的条件是(C )。A、n在m右方C、n在m左方B D、n是m祖先、n是m子孙39. 某二叉树 的后序遍历序列为: DABEC ,中序遍历序列为:DEBAC,则前序遍历序列为(D)。 A 、 ACBED C、 DEABCB D、DECAB 、CEDBA40. 将一棵有 100 个结点 的完全二叉树从上到下,从左到右依次 对结点编号,根结点的编号为 1,则编号为 45的结点的左孩子的编 号为( 90),右孩子的编号为( 91)。A 、 46B、47 C 、91D、91C41. 某树中,若结点B有4个兄弟,A是B的父亲结点,则A的 度为()。 A、 3B、4C、5D、642. 下列叙述正确的是(D)A 、二叉树是度为 2的有序树B 、二叉树结点只有一个孩子时无左右之分C 、二叉树中必有度为 2的结点D 、二叉树中最多只有两棵子树,且有左右之分D43. 由带权为 9、2、5、7 的四个叶子结点构造一棵哈夫曼树,该 树 的带树路径长度为()。A 、 23 C、 46B D、37 、44C44 .在图的表示方法中,表示形式是唯一的是()。A.邻接表 B.逆邻接表B. 邻接矩阵D其他44. 下列关键字序列中,构成大根堆的是(D )A. 5,8,1, 3,9,6,2,7 C.9,8,6, 3,5,l ,2,7B. 9,8,1,7,5,6, 2,33 D.9,8,6,7,5,1, 2,3 45.对序列 (15,9,7,8,20,-1,4)进行排序,进行一趟排序后,数据的排列变为( 4,9,C -1,8,20,7,15),则采用的是(A.选择)排序。希尔B.快速C.D.冒泡46.设 n,m 为一棵树上的两个结点,在中根遍历时,n在m前的条件是(C)。是m子孙A. n在m右方是m祖先在m左方B. nC. nD. n二、填空题图1. 树和都属于非线性结构。也2. 顺序表中逻辑上相邻的元素在物理位置上相邻。 3.双向链表有两个指针域,一个指向前趋,另一个指向 4.若进栈的次序是A,B,C,D,E,写出两种出栈顺序_ 5.队列存取数据应遵循 的原则是后继_。 ABCDEEDCBA6. 有 20个结点的完全二叉树,编号为7 的结点 的父结点编号为3。7. 两个序列分别为: L1=3,50,41,42,55,65,70,75, L2=3,50,41,42,65,55,. 10,5,用冒泡排序法对 L1 和 L2 进行排序,交换次数较少的是序列:L1。8. 在排序方法中,从无序序列中选择关键字最小 的记录,与无序 区(初始为空)的第一个选择 记录交换的排序方法,称为排序。9. 有向图的边也称为弧,用邻接矩阵存储有向图,其第i 行 的所有元素之和等于顶点Oi的出度。10树转换成的二叉树,其根结点的右子树一定为空。11. 二叉排序树是一种动态查找表。12. 对一组记录( 50,40,95,20,15,70,60, 45,80)进 行直接插入排序时,当把第 7条记录 60插入到有序表中时,为寻找插入位置需比较15次。113. 在树形结构中,树根结点没有(前驱)结点,其余每个结点有且只有后继结点,其余结点的后继结点可以个前驱结点;叶子结点没有任意多个。 14.在具有 n 个结点的二叉树中,有 15.深度为 k 的完全二叉树至少有n + 1个空指针。2k-1k2 -1个结点,若按自上而下,n/2+1。个结点,至多有从左到右次序给结点从1开始编号,则编号最小的叶子结点的编号是16. 由 a ,b, c 三个结点构成的二叉树,共有 30种不同形态, 若是构成树,共有9种形态。右17. 树所对应的二叉树其根结点的子树一定为空。6818. 已知完全二叉树
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号