数据结构期末复习题.doc

一、单选题（每题 2 分，共20分）1 算法指的是（ B ） A计算机程序 B解决问题的计算方法 C排序算法 D解决问题的有限运算序列2 线性表采用链式存储时，结点的存储地址（ B ） A必须是不连续的 B连续与否均可 C必须是连续的 D和头结点的存储地址相连续3 栈和队列的共同特点是( A )。A.只允许在端点处插入和删除元素B.都是先进后出 C.都是先进先出D.没有共同点 4 用链接方式存储的队列，在进行插入运算时( D ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改5 以下数据结构中哪一个是非线性结构？( D ) A. 队列 B. 栈 C. 线性表 D. 二叉树6 设有一个二维数组Amn，假设A00存放位置在644(10)，A22存放位置在676(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用10进制表示。 (C) A688 B678 C692 D6967 树最适合用来表示( C )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据8 二叉树的第k层的结点数最多为( D ). A2k-1 B.2K+1 C.2K-1 D. 2k-19 若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( D ) A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，310 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ D ） A选择排序 B希尔排序 C归并排序 D快速排序11 设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。A.5 B.6 C.7 D.812 双向链表中有两个指针域，llink和rlink分别指向前驱和后继，设p指向链表中的一个结点，现在要删除p所指的结点，则正确的删除是( A )A p-rlink-llink=p-llink; p-llink-rlink=p-rlink;free(p); B free(p);p-rlink-llink=p-llink; p-llink-rlink=p-rlink; C p-rlink-llink=p-llink; free(p); p-llink-rlink=p-rlink; D 以上A，B，C都不对. 13 对一组数据（84，47，25，15，21）排序，数据的排序次序在排列过程中的变化为： （1）84，47，25，15，21 （2）15，47，25，84，21 （3）15，21，25，84，47 （4）15，21，25，47，84 则采用的排序是（ B ） A 冒泡 B 选择 C 快速 D 插入14 栈和列都是( C )A 顺序存储的线性结构 B 链式存储的非线性结构 C 限制存取点的线性结构 D 限制存取点的非线性结构15 设数组Ai,j,数组的每个元素长度为3个字节，i的值为18，j的值为110，数组从首地址BA开始顺序存放，当以行为主序存储时，元素A5，8的存储首地址是（ A ）A BA+141 B BA+180 C BA+222 D BA+22516 设元素X，Y，Z顺序进栈（进栈的过程中允许出栈），得不到的出栈 序列是（ C ）A XYZ B YZX C ZXY D ZYX17 适用于二分查找的数据的存储方式及排列要求是( D ) A 链式方式存储,元素无序 B 链式方式存储,元素有序C 顺序方式存储,元素无序 D 顺序方式存储,元素有序18 向图中,所有的顶点的入度之和等于所有顶点出度之和的( D )倍. A 1/2 B 2 C 4 D 119 归并排序的时间复杂度是( C ) A O(n2) B O(n) C O(nlog2n) D O(log2n)20 (B )遍历一棵二叉排序树所得的结点访问序列是按结点值的递增序列. A 先序 B 中序 C 后序 D 以上均不是21 链表不具有的特点是( B )A 插入删除不需要移动元素 B 可随机访问任意元素C 不必先估计存储空间 D 所需空间与线性长度成正比二、判断题1 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（ yes ）2 如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（yes）3 非空的双向循环链表中任何结点的前驱指针均不为空。（ yes ）4 图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（ yes ）5 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（ yes ）6 当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ yes ）7 完全二叉树中的叶子结点只可能在最后两层中出现。（ yes ）8 哈夫曼树中没有度数为1的结点。（ yes ）9 对连通图进行深度优先遍历可以访问到该图中的所有顶点。（ yes ）10 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（yes）11 由树转化成二叉树，该二叉树的右子树不一定为空。（ NO ）12 线性表中的所有元素都有一个前驱元素和后继元素。（ NO ）13 带权无向图的最小生成树是唯一的。（ NO ）二、 填空题1 数据的逻辑结构是从逻辑关系上描述数据，它与数据的 存储 无关，是独立于计算机的。2 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J），则树中所含的结点数为_9_个，树的深度为_3_，树的度为_3_。3 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有_2n_个指针域，其中有_n-1_个指针域是存放了地址，有_n+1_个指针是空指针。4 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_e_个和_2e_个。5 AOV网是一种_有向无回路_的图。6 在一个具有n个顶点的无向完全图中，包含有_n(n-1)/2_条边，在一个具有n个顶点的有向完全图中，包含有_n(n-1)_条边。7 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为 _（12，40） _、_（ ）_、_（74）_和_（23,55，63）_。8 在快速排序、堆排序、归并排序中， 归并 排序是稳定的。9 计算机执行下面的循环语句时，语句“k+；”的执行次数为 for(i=1;i=i;j-) k+;10 对任意二叉树，叶子数为n0，度为2的结点数为n2，则n0与n2的关系是 n0=n2+1 11 已知有序表为（12，18，24，35，47，50，62，83，90，134）当用二分法查找90时，需要 3 次才能比较成功，查找47时需要 1 次才能比较成功，查找100时需要比较 4 次才能确定不成功。12 设F是由T1，T2，T3三棵树组成的森林，与F对应的二叉树为B，已知T1，T2，T3的结点数分别是n1， n2和 n3。则二叉树B的左子树有 n1-1 个结点，右子树有 n2+n3 个结点。13 有向图G=（V，E）其中V（G）=0，1，2，3，4，5，用三元组表示边及权d,E(G)为0，5，100，0，2，10，1，2，5，0，4，30，4，5，60，3，5，10，2，3，50，4，3，20，则从源点0到顶点3的最短路径长度是 ，经过的中间结点是 14 在直接插入排序、冒泡排序、简单选择排序中稳定的排序方法是直接插入排序.15 已知完全二叉树有30个结点，则整个二叉树有 个度为0的结点。16 在直接插入排序、冒泡排序、简单选择排序中不稳定的排序方法是冒泡排序、简单选择排序。17 栈是一种特殊的线性表，它允许在表的一端进行插入、删除等 操作。18 通常像交通、道路问题的数学模型是一种称为 的数据结构。19 已知如下程序段；问语句2执行的频度（次数）是 。 for(i=n;i0;i-) /*语句1*/ x=x+1; /*语句2*/20 线性表L=（a1,a2an）用数组表示，假定要删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 。21 栈的特点是：后进先出，队列的特点是：先进先出。22 串是零个或多个 字符 组成的有限序列。23 对于二维数组和多维数组，可以分为 按行优先存储 和 按列优先存储 两种不同的存储方式存储。24 具有n个结点的满二叉树，其叶子结点的个数是 。25 无向图中所有的顶点度数之和等于所有边数的 2 倍。 三、运算题1设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。 前序：A B D E C 中序：D B E A C 后序：D E B C A2 设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。 （3+5）*3+（7+9+11）*2=82 7 9 11 3 53设一组初始记录关键字序列为(19，21，16，5，18，23)，要求给出以19为基准的一趟快速排序结果以及第2趟直 接选择排序后的结果。 .快速排序：18 5 16 19 21 23 直接选择：5 16 18 19 21 234 设无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列并给出该图