数据结构各章强化练习题

数据结构各章强化练习题第一部分线性表选择题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.链表是采用链式存储结构的线性表，进行插入，删除操作时，在链表中比在顺序存储结构中效率高答案：ABCADB×√√×××××××√×√第二部分栈和队列选择题1.对于栈操作数据的原则是（）A.先进先出B.后进先出C.后进后出D.不分顺序2.有六个元素6,5,4,3,2,1,的顺序进栈，问下列哪一个不是合法的出栈序列（）A.543612B.453126C.346521D.2341563.栈在（）中应A.递归调用B.子程序调用C.表达式求值D.A,B,C4.用连接方式存储的队列，在进行删除运算时（）A.仅修改头指针B.仅修改尾指针C.头，尾指针都要修改D.头，尾指针可能都要修改5.循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素是A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front6.循环队列存储在数组A.[0..m]中则入队时的操作为（）A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)7.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素以后，rear和front的值分别为多少（）A.1和5B.2和4C.4和2D.5和18.最大容量为n的循环队列，队尾指针式rear，队头是front，则对空的条件是（）A.（rear+1）modn=frontB.rear=frontC.rear+1=frontD.(rear-1)modn=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.6B.4C.3D.212.用单链表表示耳朵链式队列的队头在链表的（）位置A.链头B.链尾C.链中名词解释栈队列循环队列答案：1-5BCDDA6-10DBBCC11-12CA栈：限制仅在表的一端进行插入和删除运算的线性表队列：一种运算有限制的线性表，它只允许在表一端进行。循环队列：第三部分数组和广义表选择题1.设有一个10阶的对称矩阵A，采用压缩存储方式面议行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）A.13B.33C.18D.402.设有数组A[i,j]，数组耳朵每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始，当用以列优先为主存放时，元素A[5，8]的存储首地址为（）A.BA+141B.BA+180C.BA+222D.BA+2253.假设以行优先为主存储二位数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=()A.808B.818C.1010D.10204.数组A[0..5,0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元，则元素A[5,5]的地址是（）/A.1175B.1180C.1205D.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.cD.d9.已知广义表A=(a,b),B=(A,A),C=(a,(b,A,)B),，则tail(head(tail(C)))=()A.（a）B.AC.aD.（b）10.广义表运算式tail(((a,b),(c,d)))的操作结果是（）A.（c,d）B.c,dC.((c,d))D.d11.广义表L=(a,(b,c)),进行tail(L)操作后结果为（）A.cB.b,cC.(b,c)D.((b,c))12.广义表((a,b,c,d))的表头是（），表尾是（）A.aB.()C.(a,b,c,d)D.(b,c,d)13.广义表(a,(b,c),d,e)的表头为（）A.aB.a,(b,c)C.a,(b,c))D.(a)14.设广义表L=((a,b,c)),则L的长度和深度分别为（）A.1和1B.1和3C.1和2D.2和315.下面说法不正确的是（）A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构D.广义表可以说一个多层次的结构答案：1~5BBBAC6~10DCDBC11.D12.BC13.A14.C15.A第四部分树和二叉树选择题1.设树T的度为4，其中度为1,2,3,和4的结点个数分别为4,2,1,1,则T中叶子数为（）A.5B.6B.7D.82.在下述结论中正确的是（）A.只有一个结点的二叉树度为0B.二叉树的度为2C.二叉树的桌游子树可以任意交换D.深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树3.设森林F的对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一个树的结点个数是()A.m-nB.m-n-1C.n+1D.条件不足，无法确定4.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A.9B.11C.15D.不确定5.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的及诶单个数为2个，则度为0的结点个数为（）A.4B.5C.6D.7、6.设森林中有三棵树，第一第二第三棵树的结点个数分别为M1,M2,M3.与森林F对应的二叉树根结点的右子树上的结点个数是（）A.M1B.M1+M2C.M3D.M2+M37.具有10个叶结点的二叉树中有（）个度为2的结点A.8B9C.10D.118.设给定权值总数有n个，其哈夫曼的结点总数为（）A.不确定B.2nC,2n+1D.2n-19.有n个叶子结点的哈夫曼树的结点总数为（）A.不确定B.2nC.2n+1D.2n-110.一棵二叉树高度为h，所有结点的度或为0或为2，则这棵二叉树最少有（）个结点A.2hB.2h-1C.2h+1D.h+111.二叉树的结点从1开始进行连续编号，要求每个结点的标号大于其左，右孩子的编号，同一节点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）次序的遍历实现编号。A.先序B.中序C.后序D.从根开始按层次遍历12.根的后根遍历序列等同于该树对应的二叉树德尔（）A.先序序列B.终须序列C.后序序列13.若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用（）遍历最为合适A.前序B.中序C.后序D.按层次14.在下列存储形式中，哪一个不是树的存储形式（）A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法15.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能为（）A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG16.已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF则后序遍历结果为（）A.CBEFDAB.FEDCBAC.CBEDFAD.不确定17.一棵二叉树的先序遍历为EFHIGJK,中序遍历为HFIEJKG,该二叉树的右子树的根式（）A.EB.FC.GD.H18.将一棵树t转换为孩子—兄弟链表表示的二叉树h，则t的后根遍历是h的（）A.前序遍历B.中序遍历C.后序遍历填空题1.二叉树由三个基础单元组成2.树在计算机内的表示方法有3.在二叉树中，指针p所指结点为叶子结点的条件是4.已知一棵度为3树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则有个叶子结点。5.深度为k的完全二叉树至少有个结点，至多有个结点，结点总数和k之间的关系是6.深度为h的满二叉树的第k层有（）个结点。（1=kh）7.已知一棵二叉树的前序序列为abdecfhg，中序序列为dbeahfcg，则该二叉树的根为左子树中有右子树中有8.线索二叉树的左线索指向其右线索指向其9.哈夫曼树是10.若以{4,5,6,7,8}左为叶子结点的权值构造哈夫曼树，则其带权路径长度为11.有数据WG={7,19,2,6,32,3,21,10}则所建哈夫曼树的树高时，带权路径长度WPL是12.有一份电文中共使用6个字符：a，b，c，d，e，f，他们的出现概率依次是2,3,4,7,8,9，是构造一棵哈夫曼树，其加权路径长度WPL为字母c的编码是13.设n0为哈夫曼树的叶子结点数目，则哈夫曼树共有个结点第五部分图选择题1.设无向图的顶点个数为n，则该图最多有（）条边A.n-1B.n(n-1)/2C.n(n+1)/2D.02.一个n个顶点的连通无向图，其边数的个数至少为（）A.n-1B.nC.n+1D.nlogn3.要连通具体有n个顶点的有向图，至少需要（）条边A.n-1B.nC.n+1D.2n4.n个结点的完全有向图含有边的数目（）A.n*nB.nC.n/2D.2n填空题1.判断一个无向图是一棵树的条件是2.有向图G的强连通分量是指3.一个连通图的是一个