数据结构复习题23398

1、一、填空题1、算法的五个重要特性是：有穷性、_、可行性、输入、输出。2、数据元素之间的关系在计算机中有两种不同的表示方法，由此得到两种不同的存储结构： _和链式结构。3在有n个元素的顺序表中删除一个元素，所需要移动元素的平均个数是_，具体移动元素的个数与元素位置有关。4、在一个长度为n的循环链表中，删除其元素的值为x的节点的时间复杂度为_。5、1，2，3，n按照先后顺序入栈，则可能的出栈序列有_个。6假设有三维数组A456，每个元素长度为2个字节，假设从首地址SA0开始以行为主序存放在存储器中，则元素a345的存储位置为_。7、已知一棵二叉树的先序序列为ABCD，中序序列为BCAD，则其后序序

2、列为_。8、有29个结点的赫夫曼树中叶子结点有_个。9在一个图中，所有顶点的度数之和是图中边数之和的 倍。10一个有n个顶点、e条边的无向图的邻接表中有 个顶点结点。11假设G是一个具有21条边的非连通无向图（不含自回路和多重边），则图G至少有_个顶点。12、图的常用存储结构有以下四种：邻接矩阵、邻接表、_、邻接多重链表。13、对n(n>0)个记录进行冒泡排序，最少要交换_次记录。14有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100,当折半查找到值为82的元素时,经过比较的关键字的序列为： 。二、判断题（ ）1. 算法的优劣与算法描述语言无关，但与所

3、用计算机有关。（ ）2. 数据元素是数据的基本单位。（ ）3. 顺序表的存储空间必须连续，单链表的存储空间必须不连续。（ ）4. 存取顺序表中第i个元素时花费的时间同i的大小有关。（ ）5. 栈和队列都是限制了存取点的线性结构。（ ）6. 递归程序执行过程中必须用到栈。（ ）7数组不适合作为任何二叉树的存储结构。（ ）8一棵树中的叶子结点的个数和度为1的结点个数的多少没有关系。（ ）9树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。（ ）10已知二叉树的前序和后序遍历序列，则可以恢复出此二叉树。（ ）11无论是有向图还是无向图，其所有顶点度数之和一定是顶点数的2倍。（ ）12一个网（带权

4、图）都有唯一的最小生成树。（ ）13 求边稠密的无向连通网的最小生成树时，最好使用Kruscal算法。（ ）14顺序查找法适用于存储结构为顺序或链接存储的线性表。 （ ）15 由于哈希查找中是直接计算待查数据的地址，因此其ASL一定为0。（ ）16直接插入排序和希尔排序都是稳定的内部排序方法。三、选择题（ ）1下列算法的时间复杂度为( )。int suanfa(int n) int t=1；       while(t<=n)          t=t*2；r

5、eturn t； A.O(log2n)      B.O(2n)     C.O(n2)   D.O(n)（ ）2. 链表不具有的特点是（ ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比（ ）3. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A 顺序表 B单循环链表 C 双链表 D带头结点的双循环链表（ ）4一个栈的输入序列为1 2 3 4 5，则下列中不可能是栈的输出序列的是

6、（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2（ ）（ ）5. 数组A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是( )。 A. 1175 B. 1180 C. 1205 D. 1210（ ）6. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 （ ）7. 设有一个10阶的对称矩阵A，采

7、用压缩存储方式，以行序为主存储，a11为 第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。A. 13 B. 33 C. 18 D. 40（ ）8对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。A先序 B. 中序 C. 后序 D. 从根开始按层次遍历（ ）9. 在下述结论中，正确的是（ ）。 只有一个结点的二叉树的度为0;二叉树的度为2；二叉树的左右子树可任意交换; 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D （ ）10

8、. 一个具有1025个结点的二叉树的高h为（ ）A11 B10 C11至1025之间 D10至1024之间（ ）11. 利用二叉链表存储树，则根结点的右指针是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空（ ）12. 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A空或只有一个结点 B任一结点无左子树 C高度等于其结点数 D任一结点无右子树 （ ）13. 下列哪一种图的邻接矩阵是对称矩阵？（ ）A有向图 B无向图 CAOV网 DAOE网（ ）14. 下面哪一个算法是用来求解单源点最短路径的算法（ ）。A. 迪杰斯特拉算法 B. 弗洛伊德算法 C. 普利姆算法 D.

9、克鲁斯卡尔（ ）15. 无向图G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是：Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,b,c（ ）16. 分别以下列序列构造二叉排序树，跟其他序列所构造的结果不同的是( ) A（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (10

10、0，80， 60， 90， 120，130，110)（ ）17. 下列关于m阶B-树的说法错误的是( )。A根结点至多有m棵子树 B所有叶子都在同一层次上 C. 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D. 根结点中的数据是有序的（ ）18. 排序趟数与序列的原始状态有关的排序方法是( )排序法。 A插入 B. 选择 C. 冒泡 D. 基数 （ ）19. 对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15；则采用的是（ ）排序。A. 选择 B. 快速 C. 希尔 D. 冒泡（ ）20. 下列四个序列中，哪一个是堆（

11、  ）A. 75,65,30,15,25,45,20,10      B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10      D. 75,45,65,10,25,30,20,15 四、综合应用题1一棵二叉树的先序、中序、后序序列如下，部分未标出，请画出该二叉树。 先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G 后序序列 ：_ E F D B _ J I H _ A2对于表达

12、式a+b*(c-d)-e/f。(1)画出该表达式对应的二叉树。(2)写出对该二叉树分别进行前序，中序和后序遍历所得的表达式序列。3某电文共使用5种字符：a,b,c,d,e,它们的出现频率依次为0.15、0.1、0.25、0.2、0.3。(1)试画出对应的赫夫曼树（请按照同层结点权值由小到大的次序构造，不需要写出构造过程，只画出最后树形结果即可)。(2)求出每个字符的赫夫曼编码。4有图如下，请完成以下要求： 1）写出其深度优先遍历序列（从A开始）： 2）按照Prime算法求出最小生成树（画出最终结果）ABCDEF1015121278106655、下图为一个连通网。(1)画出该网的邻接矩阵表示。(2)写出从v1出发对该网的广度优先搜索序列。(3)从v1开始，用Prim算法构造该网的最小生成树(直接写出构造好的结果，不必写过程)，并求出最小生成树上各边权值之和。v1v2v4v5v6v365155366426. 采用哈希函数H(k) =（3*k）mod 13并用线性探测开放地址法处理冲突，在数列地址空间0.12中对关键字序列22，41，53，46，30，13，1，67，51；（1）构造哈希表（画示意图）； （2）求装填因子；（3）求等概率下查找成功条件下的平均查找长度；7、带权图（权值非空，表示边连接的两个顶点的距离）的最短路