数据结构各章强化练习题.doc

数据结构各章强化练习题线性表一、选择题1下述哪一条是顺序存储结构的优点？（ ）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示2下面关于线性表的叙述中，错误的是哪一个？（ ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3线性表是具有n个（ ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项 4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表6. 链表不具有的特点是（ ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比二、判断1. 链表中的头结点仅起到标识的作用。2. 顺序存储结构的主要缺点是不利于插入或删除操作。3线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。4顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。5. 对任何数据结构链式存储结构一定优于顺序存储结构。6顺序存储方式只能用于存储线性结构。7. 取线性表的第i个元素的时间同i的大小有关. 8. 循环链表不是线性表.9. 线性表只能用顺序存储结构实现。10. 线性表就是顺序存储的表。11为了很方便的插入和删除数据，可以使用双向链表存放数据。12. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。13. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( ) 栈习题一 选择题1. 对于栈操作数据的原则是（ ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序2. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 3. 栈在（ ）中应用。A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，4、用链接方式存储的队列，在进行删除运算时（ ）。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改5、循环队列A0.m-1存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front6. 循环队列存储在数组A0.m中，则入队时的操作为（ ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 7. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 8. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front9. 栈和队列的共同点是（ ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点10. 栈和队都是（ ）A顺序存储的线性结构 B. 链式存储的非线性结构C. 限制存取点的线性结构 D. 限制存取点的非线性结构11. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。A 6 B. 4 C. 3 D. 212. 用单链表表示的链式队列的队头在链表的（ ）位置。A链头 B链尾 C链中二、. 名词解释：栈队列循环队列数组和广义表一 选择题1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。A. 13 B. 33 C. 18 D. 402. 设有数组Ai,j，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为( )。A. BA+141 B. BA+180 C. BA+222 D. BA+2253. 假设以行序为主序存储二维数组A=array1.100，1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5，5=（ ）。 A. 808 B. 818 C. 1010 D. 10204. 数组A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是( )。 A. 1175 B. 1180 C. 1205 D. 12105. 对稀疏矩阵进行压缩存储目的是（ ）。A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度6. 已知广义表L=（x,y,z），a，（u，t，w），从L表中取出原子项t的运算是（ ）。A. head（tail（tail（L） B. tail（head（head（tail（L） C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）)）7. 已知广义表LS(a,b,c),(d,e,f),运用head和tail函数取出LS中原子e的运算是( )。 A. head(tail(LS) B. tail(head(LS)C. head(tail(head(tail(LS) D. head(tail(tail(head(LS)8. 广义表A=(a,b,(c,d),(e,(f,g),则下面式子的值为（ ）。Head(Tail(Head(Tail(Tail(A)A. (g) B. (d) C. c D. d9. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C) =( )。A.（a） B. A C. a D. (b) 10. 广义表运算式Tail(a,b),(c,d)的操作结果是（ ）。A. (c,d) B. c,d C. (c,d) D. d11. 广义表L=（a，（b，c），进行Tail（L）操作后的结果为（ ）。A. c B. b，c C.（b，c） D.（b，c）12. 广义表（a,b,c,d）的表头是（ ），表尾是（ ）。A. a B.（） C.（a,b,c,d） D.（b,c,d）13. 广义表（a,(b,c),d,e）的表头为（ ）。 A. a B. a,(b,c) C. (a,(b,c) D. (a)14. 设广义表L=（a,b,c），则L的长度和深度分别为（ ）。 A. 1和1 B. 1和3 C. 1和2 D. 2和315. 下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构树和二叉树1、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）A5 B6 C7 D82. 在下述结论中，正确的是（ ）只有一个结点的二叉树的度为0; 二叉树的度为2； 二叉树的左右子树可任意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D3. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）Am-n Bm-n-1 Cn+1 D条件不足，无法确定 4若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定 5在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个A4 B5 C6 D7 6设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。AM1 BM1+M2 CM3 DM2+M37具有10个叶结点的二叉树中有（ ）个度为2的结点， A8 B9 C10 Dll8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A不确定 B2n C2n+1 D2n-19. 有n个叶子的哈夫曼树的结点总数为（ ）。A不确定 B2n C2n+1 D2n-110一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A2h B2h-1 C2h+1 Dh+1 11对于有n 个结点的二叉树, 其高度为（ ）Anlog2n Blog2n Clog2n|+1 D不确定12. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）Alogn+1 Blogn+1 Clogn Dlogn-113深度为h的满m叉树的第k层有（ ）个结点。(1=k=h) Amk-1 Bmk-1 Cmh-1 Dmh-114在一棵高度为k的满二叉树中，结点总数为（ ）A2k-1 B2k C2k-1 Dlog2k+115高度为 K的二叉树最大的结点数为（ ）。A2k B2k-1 C2k -1 D2k-1-116. 一棵树高为K的完全二叉树至少有（ ）个结点A2k 1 B. 2k-1 1 C. 2k-1 D. 2k17对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。A先序 B. 中序 C. 后序 D. 从根开始按层次遍历18树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列 C. 后序序列19若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。A前序 B中序 C后序 D按层次20在下列存储形式中，哪一个不是树的存储形式？（ ）A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法21一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）ACABDEFG BABCDEFG CDACEFBG DADCFEG 22已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。ACBEFDA B FEDCBA C CBEDFA D不定 23已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。 Aacbed Bdecab Cdeabc Dcedba 24. 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不对 25. 上题的二叉树对应的森林包括多少棵树（ ）Al B2 C3 D概念上是错误的 26二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： A、 E B、 F C、 G D、 H 27将一棵树t 转换为孩子兄弟链表表示的二叉树h，则t的后根序遍历是h 的A前序遍历 B中序遍历 C后序遍历（ ） 二、填空题1二叉树由_(1)_，_(2)_，_(3)_三个基本单元组成。 2树在计算机内的表示方式有_(1)_，_(2)_，_(3)_。 3在二叉树中，指针p所指结点为叶子结点的条件是_。4已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_个叶子结点。5深度为k的完全二叉树至少有_(1)_个结点，至多有_(2)_个结点。 6深度为H 的完全二叉树至少有_(1)_个结点；至多有_(2)_个结点；H和结点总数N之间的关系是 (3)_。7已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为_(1)_，左子树中有_(2)_， 右子树中有_(3)_。8、线索二元树的左线索指向其_，右线索指向其_。9哈夫曼树是_。10若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_。11有数据WG=7，19，2，6，32，3，21，10，则所建Huffman树的树高是_(1)_，带权路径长度WPL为_(2)_。12有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)_，字符c的编码是_(2)_。13设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有_个结点。图1设无向图的顶点个数为n，则该图最多有（ ）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 2一个n个顶点的连通无向图，其边的个数至少为（ ）。An-1 Bn Cn+1 Dnlogn；3要连通具有n个顶点的有向图，至少需要（ ）条边。An-l Bn Cn+l D2n4n个结点的完全有向图含有边的数目（）。An*n n（n） Cn2 Dn*（nl）二、填空题1.判断一个无向图是一棵树的条件是_。2有向图G的强连通分量是指_。3一个连通图的_是一个极小连通子图。4具有10个顶点的无向图，边的总数最多为_。5若用n表示图中顶点数目，则有_ _条边的无向图成为完全图。6N个顶点的连通图的生成树含有_条边。7构造n个结点的强连通图，至少有_条弧。8在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_ _；对于有向图来说等于该顶点的_ _。9. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是_ _。10. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为_ _，邻接表的边结点个数为_。11. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_ _存放被访问的结点以实现遍历。12求图的最小生成树有两种算法，_ _算法适合于求稀疏图的最小生成树。13. Prim（普里姆）算法适用于求_ _的网的最小生成树；k