数据结构复习提纲。带所有答案

数据结构复习提纲一，选择题1.数据结构是指（A）。A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（C）。A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3.设语句x++的时间是单位时间，则以下语句的时间复杂度为（B）。for(i=1;i=n;i++)for(j=i;j=n;j++)x++;A.O(1)B.O(2n)C.O(n)D.O(3n)4.计算机内部数据处理的基本单位是（B）。A.数据B.数据元素C.数据项D.数据库-------25.在一个长度为n的顺序表中删除第i个元素(1=i=n)时，需向前移动A个元素。A．n-iB．n-i+lC．n-i-1D．i6.线性表采用链式存储时，其地址___D___。A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以7.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较__C个元素结点。A．n/2B．nC．（n+1）/2D．（n-1）/28.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是D__。A．p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B．s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;C．p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;D．s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;9.设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为A。A．p-next=p-next-next;B．p=p-next;C．p=p-next-next;D．p-next=p;10.在一个长度为n的顺序表中向第i个元素(0in+l)之前插入一个新元素时，需向后移动B个元素。A．n-iB．n-i+lC．n-i-1D．i11.在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行-B-A．s-next=p-next;p-next=sB．q-next=s;s-next=pC．p-next=s-next;s-next=pD．p-next=s;s-next=q12.在顺序表中，只要知道__D_，就可在相同时间内求出任一结点的存储地址。A．基地址B．结点大小C．向量大小D．基地址和结点大小13.设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列_C_。A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A14.向一个栈顶指针为hs的链栈中插入一个s结点时，应执行_B_。A．hs-next=s;B．s-next=hs;hs=s;C．s-next=hs-next;hs-next=s;D．s-next=hs;hs=hs-next;15.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为___D__。A．rear％n==frontB．（front+l）％n==rearC．rear％n-1==frontD．(rear+l)％n==front16.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为_C__。A．rear％n==frontB．front+l=rearC．rear==frontD．(rear+l)％n=front17.在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为__A____。A．front=front-nextB．rear=rear-nextC．rear=front-nextD．front=rear-next------418.设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（A）。A.p+[i*n+j-1]*kB.p+[(i-1)*n+j-1]*kC.p+[(j-1)*n+i-1]*kD.p+[j*n+i-1]*k19.若数组A[0…m][0…n]按列优先顺序存储，则aij地址为（A）。A.LOC(a00)+[j*m+i]B.LOC(a00)+[j*n+i]C.LOC(a00)+[(j-1)*n+i-1]D.LOC(a00)+[(j-1)*m+i-1]20.若下三角矩阵An×n，按列顺序压缩存储在数组Sa[0…(n+1)n/2]中，则非零元素aij的地址为（B）。（设每个元素占d个字节）A.[(j-1)*n-2)1)(2(jj+i-1]*dB.[(j-1)*n-2)1)(2(jj+i]*dC．[(j-1)*n-2)1)(2(jj+i+1]*dD．[(j-1)*n-2)1)(2(jj+i-2]*d21.设有广义表D=(a,b,D)，其长度为（B），深度为（A）。A.无穷大B.3C.2D.522.广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（A）。A.xB.(a,B)C.(x,(a,B))D.A23.稀疏矩阵一般的压缩存储方法有两种，即（C）。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表24.一个广义表的表头总是一个（D）。A.广义表B.元素C.空表D.元素或广义表25.一个广义表的表尾总是一个（A）。A.广义表B.元素C.空表D.元素或广义表--------526.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（C）个。树中结点数等于所有结点度数的和加1.所以：2+1+2+X=2*3+1*2+2*1+X*0+1所以X=6A.4B.5C.6D.727.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（B）个。N=n0+n1+n2;no=n2+1——16A.15B.16C.17D.4728.假定一棵三叉树的结点数为50，则它的最小高度为（C）。最小高度就是除叶子外,每个结点都有3个孩子的三叉树的高度：x层公有1+3+9+…+3^(x-1)=(3^x-1)/2要让结果50x=5A.3B.4C.5D.629.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（B）。右孩子节点为AA.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]30.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（D）。画出哈夫曼树(6+5+8)*2+（2=3）*3=53A.24B.48C.72D.5331.设n,m为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（B）。中序遍历就是一竖一竖列的读，只要在左方就okA.n在m右方B.n在m左方C.n是m的祖先D.n是m的子孙32.如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（B）。A.中序B.前序C.后序D.层次序--------633.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为(A)。A.sB.s-1C.s+1D.n34.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为(D)。A.sB.s-1C.s+1D.2s35.在一个具有n个顶点的无向完全图中，所含的边数为(C)。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/236.在一个具有n个顶点的有向完全图中，所含的边数为(B)。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/237.若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用(A)次深度优先搜索遍历的算法。A.kB.1C.k-1D.k+138.若要把n个顶点连接为一个连通图，则至少需要(C)条边。A.nB.n+1C.n-1D.2n39.在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为(D)。A.nB.neC.eD.2e40.在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为(C)。A.nB.neC.eD.2e41.在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为(A)。A.nB.2nC.eD.2e42.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为(C)。对应邻接表中该顶点单链表中的边结点数为(B)。A.k1B.k2C.k1-k2D.k1+k243.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为(B)。A.A,B,C,F,D,EB.A,C,F,D,E,BC.A,B,D,C,F,ED.A,B,D,F,E,C44.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为(D)。A.A,B,C,D,E,FB.A,B,C,F,D,EC.A,B,D,C,E,FD.A,C,B,F,D,E45.若一个图的边集为{1,2,1,4,2,5,3,1,3,5,4,3}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为(A)。A.1,2,5,4,3B.1,2,3,4,5C.1,2,5,3,4D.1,4,3,2,546.若一个图的边集为{1,2,1,4,2,5,3,1,3,5,4,3}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为(C)。A.1,2,3,4,5B.1,2,4,3,5C.1,2,4,5,3D.1,4,2,5,347.由一个具有n个顶点的连通图生成的最小生成树中，具有(B)条边。A.nB.n-1C.n+1D.2n48.已知一个有向图的边集为{a,b,a,c,a,d,b,d,b,e,d,e}，则由该图产生的一种可能的拓扑序列为(A)。A.a,b,c,d,eB.a,b,d,e,bC.a,c,b,e,dD.a,c,d,b,e--------749.对具有n个元素的有序表采用折半查找，则算法的时间复杂度为(D)。A.O(n)B.O(n2)C.O(1)D.O(log2n)50.若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为(D)。A.nB.n+1C.(n-1)/2D.(n+1)/251.对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为(A)的9分之一。A.20B.18C.25D.2252.对具有n个元素的有序表采用折半查找，则算法的时间复杂度为(D)。A.O(n)B.O(n2)C.O(1)D.O(log2n)A.n+kB.k+n/kC.(k+n/k)/2D.(k+n/k)/2+153.在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为(A)。A.13B.24C.12D.7954.从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为(C)。A.O(n)B.O(1)C.O(log2n)D.O(n2)55.在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是(A)。A.-11B.-22C.12D.0156.若根据查找表(23,4