数据结构练习

1、一、选择题1 .广度优先遍历的含义是：从图中某个顶点v出发，在访问了 v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且“先被访问的顶点的邻接点”先于“后被访 问的顶点的邻接点” 度优先遍历序列。被访问，直至图中所有已被访问的顶点的邻接点都被访问到。是下图的广B. 1 2 3 4 5 6 C. 1 6 5 2 3 4 D. 1 6 4 5 2 3的顺序存储的有序表，若采用折半查找（向下取整），则找到第5个元素需要与表中的5个元素的比较）。A. 1 2 6 3 4 52.对于长度为11个元素进行比较操作（包括与第A. 53.结点数目为(1)A. nB. 4

2、C. 3D. 2的二叉查找树（二叉排序树）的最小高度为nB. 2、最大高度为（2）。(2)A. nnB. 2C. Iog2 nC. Iog2 n4 .堆排序是一种基于_（1）_的排序方法，（1）A.计数B.插入C.选择D.归并 A . 15, 28, 25, 56, 68, 63, 30C. 68, 28, 63, 25, 15, 56, 305.下面关于串的叙述中，哪一个是不正确的？（A.串是字符的有限序列C .模式匹配是串的一种重要运算(2)B.D.D. Iog2( n+1)D. Iog2( n+1)不是堆。15, 28, 25, 30, 68,68, 56, 39, 63, 28,63,

3、 5625, 15）B.空串是由空格构成的串D .串既可以采用顺序存储，也可以采用链式存储 ）条边。D . 06 .设无向图的顶点个数为 n,则该图最多有（A . n-1 B . n（n-1）/2C . n（n +1）/27.以下数据结构中，（）是非线性数据结构。A .树B.字符串 C.队列8 .下面关于线性表的叙述中，错误的是哪一个？（A .线性表采用顺序存储，必须占用一片连续的存储单元。B .线性表采用顺序存储，便于进行插入和删除操作。C .线性表采用链接存储，不必占用一片连续的存储单元。D .线性表采用链接存储，便于插入和删除操作。9.假设以数组 Am存放循环队列的元素，其头尾指针分别为

4、front和rear,则当前队列中的元素个数为（）。D 栈A .(rear-front+m)%mB.rear-front+1C.(front-rear+m)%mD.(rear-front)%m10 .在单链表指针为p的结点之后插入指针为s的结点，正确的操作是(A .p-next=s; s-next=p-next;B. s-next =p-next;p-next=s;C.p-n ext=s; p-n ext=s-n ext;D . p-n ext=s-n ext;p-n ext=s;11. 设栈的输入序列是 1， 2， 3，A. 1， 2， 4， 3 B. 2， 1，12. 下列四个序列中，哪一

5、个是堆（A. 75,65,30,15,25,45,20,10C. 75,45,65,30,15,25,20,1013. 在下述结论中，正确的是（ 只有一个结点的二叉树的度为 二叉树的度为 2； 二叉树的左右子树可任意交换 深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。A .B .C .D .14. 若一棵二叉树具有 10 个度为 2的结点， 5 个度为 1 的结点，则度为 0 的结点个数是（ ）A. 9B. 11C. 15D .不确定15设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为 叉树根结点的右子树上的结点个数是（）。AM14,则（ ）不可能是其出栈序列。3， 4

6、C1， 4， 3， 2D4， 3， 1， 2，BD）0;)。75.65.45.10.30.25.20.1575.45.65.10.25.30.20.15M1 , M2和M3。与森林F对应的二16在下面的程序段中，FOR i:=1 TO nFOR j:=1 TOx:=x+1;A O（2n）B O（n）17. 一个n个顶点的连通无向图，A n-1B nBM1+M2CM3D对 x 的赋值语句的频度为（DOn DOM2+M3）。CO（n2）D 其边的个数至少为（ Cn+1 18二叉树的第 I 层上最多含有结点数为（DO(log 2n)。 nlogn；）2I-1定能选出一个元素放在其最终位置上。I I-

7、1A2IB 2I-1-1C19下列排序算法中 （ ） 排序在一趟结束后不A .选择B .冒泡C .归并D .堆20散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关 系，则选择好的（ ）方法是散列文件的关键。A .散列函数B .除余法中的质数C .冲突处理D .散列函数和冲突处理D 2I -1二、填空题2122具有 256 个结点的完全二叉树的深度为 深度为 有一个23址是 1007 ， 的存储地址是：h 的完全二叉树上至少有多少个结点20行 20列的对称矩阵 A ，将其下三角矩阵以行序为主序压缩存储在数组 B 中，若 B 的首地 每个数组元素占 4个存储单

8、元，则 A 的第 12行第 1 0列（行、列从第一行第一列开始）元素24数据结构是指数据及其相互之间的25进行，删除操作是在队列的 _ 对于一个长度为 n 的单链存储的线性表，在表头插入元素的时间复杂度为队列的插入操作是在队列的进行。26素的时间复杂度为，在表尾插入元27设 W 为一个二维数组，其每个数据元素占用 4 个字节，行下标 i 从 0 到 7 ，列下标 j 从 0 到 3 ，则二维数组W的数据元素共占用个字节。W中第6行的元素和第4列的元素共占用字节。若按行顺序存放二维数组W,其起始地址为100,则二维数组元素 W6 , 3的起始地址为28. 一棵结点数为N的二叉树，其所有结点的度的

9、总和是 29. 对于一棵具有 n个结点的二叉树，用二叉链表存储时，其指针总数为个用于指向孩子， 个指针是空闲的。30. 若对一棵完全二叉树从 0开始进行结点的编号， 并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到 A0中。其余类推，则A i 元素的左孩子元素为 ，右孩子元素为 双亲元素为个，其中31 .在线性表的散列存储中，处理冲突的常用方法有两种。32.当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用三、应用题33.已知一棵二叉树的中序遍历序列和后序遍历序列分别为 要求：（1）画出这棵二叉树；（2）写出这棵二

10、叉树的前序遍历序列。EBIFJAGDH和 EIJFBGHDA_排序；当待 排序。34.设有正文 MNOPPPOPMMPOPOPPOPNP，字符集为 M , N , 0, P, 正文的编码最短，计算它的带权路径长度。设计一套二进制编码，使得上述35.试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小支撑（或生成） 历的序列和广度优先遍历的序列。求结点树的过程，以及深度优先遍7到结点3的最短路径。36. 用序列（46,88,45,39,70,58,101,10,66,34）建立一个排序二叉树37. 设散列函数为H（K）=K MOD 11,解决冲突的方法为链接法，试将下列关键字集合 35,67,42,21,29,86,95,47,50,36,91依次插入到散列表中（画出散列表的示意图）。38根据给定的关键字集合( 20，15，40，35，45，25，50， 30，10)顺序输入 (1) 画出平衡二叉树；(2) 画出重新调整好的堆树。29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：(1)归并排序每归并一次书写一个次序。(2)快速排序每划分一次书写一个次序。(3)冒泡排序每划分一次书写一个次序。39给出一组关键字：四、编程题40已知带头