搜索
1、在一棵具有5层的满二叉树中结点总数为（A）。A)31B）32C）33D）16(2^n)-1,N=2k-1(N总结点数，k层数)2、串的逻辑结构与（A）的逻辑结构不相同。A）线性表B）栈C）队列D）集合串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。P713、下列序列中，执行第一趟快速排序后得到的序列是（A）。A）[d,a,e,d,b]f[h,g]B)[c,e,a,d]f[h,g,b]C)[g,a,e,c,b]f[d,h]D)[a,b,c,d,]f[e,g,h]左大右小4、n个顶点的强连通图至少有（C）条边。A）nB）n+1C）n-1D）n(n-1)单节点除外，so,-15、设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（A）。A）p-next=p-next-nextB）p=p-nextC）p=p-nexe-nextD）p-next=p无限删除6、对下图V4的度为（C）。A）1B）2C）3D）4v1v2v3v47、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（C）。A）4B）5C）6D）7图1-7设度为0的结点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，度为3的个数n3树中结点总数n0+n1+n2+n3，所有边的数量为0*n0+1*n1+2*n2+3*n3树中结点比边多1个，合并这两个式子就可以得到：n0=1+n2+2*n38、在数据结构中，从逻辑上可以把数据结构分为（C）。A）动态结构和静态结构B）紧凑结构和非紧凑结构C）线性结构和非线性结构D）内部结构和外部结构数据的逻辑结构分两大类：线性结构和非线性结构数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法(hash存储)9、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（B）。A）loc(A1)+i*cB）loc(A1)+(i-1)*cC）loc(A1)+i*c+1D）loc(A1)+(i+1)*c10、（C）在进行插入操作时，常产生假溢出现象。A）顺序栈B）循环队列C）顺序队列D）链队列循环队列产生是为了解决顺序队列的假溢出11、下列各种数据结构中属于线性结构的有（A）。A）栈B)二叉树C)广义表D)图数据元素之间的关系称为结构：1.集合；2.线性结构；3.树形结构；4.图/网状结构12、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（B）。A）顺序表示法B）单字符为结点的单链表表示法C）等量分块表示法D）不等量分块表示法13、广义表head(((a,b),(c,d)))的运算结果为（D）。A）(a,b)B）(c,d)C）空表D）（（a,b）,(c,d)）14、n个顶点的图的最小生成树必定（D），是不正确的描述。A）不唯一B）权的总和唯一C）不含回路D）有n条边15、采用链结构存储线性表时，其地址（B）。A）必须是连续的B）连续不连续都可以C）部分地址必须是连续D）必须是不连续的16、队列的操作的原则是（A）。A）先进先出B)后进先出C)只能进行插入D)只能进行删除U字走法，不是Y17、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（A）。A）一个数量级别B）一个平均值C）一个最大值D）一个均方值18、线性表的链接实现有利于（A）运算。A）插入B）读元素C）查找D）定位20、下面程序段的时间复杂度是(A)。s=0;for(i=0;in;i++)for(j=0;jn;j++)s+=B[i][j];sum=s;A）O(n2)B）O(n)C）O(m*n)D）O(1)21、二叉树第i(i≥1)层上至多有（C）结点。A）2iB）2iC）2i-1D）2i-1满二叉树的时候结点最多23、设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（B）。A）3，2，5，6，4，1B）1，5，4，6，2，3C）2，4，3，5，1，6D）4，5，3，6，2，1,堆栈遵循后进先出,B.2.3交换24、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是(B)。A）9B）11C）15D）不能确定N=n0+n1+n2N=1+n1+2*n2N:节点总数;ni:度为i的节点数25、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（A）。A）直接选择排序B）直接插入排序C）快速排序D）起泡排序26、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（B）。A）13B）33C）18D）40首先，你要明白什么是压缩存储，对于这个对称矩阵来说，等于是存对角线的右上半加对角线的元素，或者是左下半加对角线的元素，其他位置一概不存，这题是使用行优先存储，即先存a11，再a12，再a22，再a13，再a23，再a33，以此类推，一直到a85，所以a85的位置计算为：（1+2+3+4+5+6+7）+5=33，即可。1+(2+7)(7-2+1)/2+5=3327、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（B）。A）3B）4C）5D）1度的定义是:结点拥有的子树的个数。结点A有3个兄弟，那么算上本身，双亲B存在的3个子树。度为4.n2+1=n028、线索二叉树中某结点D，没有左孩子的条件是（B）。A）D-Lchild=NullB)D-ltag=1C)D-Rchild=NullD)D-ltag=0LTag{0lchild域指示节点的左孩子;1lchild域指示节点的前驱}Rtag{0rchild域指示节点的左孩子;1rchild域指示节点的前驱}没有前趋结点并没有左子树就没有左孩子，通常没有头结点的情况下，中序遍历的第一个结点就满足条件。29、栈进行插入和删除操作的特点是（A）。A）LIFOB）FIFOC）FCFSD）HPFLIFO=“lastinfirstout”30、与无向图相关的术语有（C）。A）强连通图B）入度C）路径D）弧32、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（D）。A）上三角矩阵B)稀疏矩阵C)对角矩阵D)对称矩阵34、栈进行插入和删除操作的特点是（A）。A）LIFOB）FIFOC）FCFSD）HPF39、在循环队列中，若front与rear分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是(C)。A）front==rear+1B）rear==front+1C）front==rearD）front==0此时我们约定：少用一个元素，“队列头指针在队列尾指针的下一位置”作为队列呈“满”状态的标志。43、在有n个叶结点的哈夫曼树中其结点总数为：（D）。（A）不确定（B）2n（C）2n+1（D）2n–1无论哈夫曼树是几叉，其特点是一致的（假设为m叉），即树中只存在度为0的结点（即叶结点）和度为m的结点。不妨设度为0的结点个数为x，度为m的结点个数为y，则存在一个等式x+y=my+1，即x=(m-1)y+1，x+y是树的总结点个数。就这道题来说，假设哈夫曼树是二叉的话，则度为0的结点个数为N，度为2的结点个数为N-1，则结点总数为2N-1。44、（C）在进行插入操作时，常产生假溢出现象。A）顺序栈B）循环队列C）顺序队列D）链队列1-10这个要记一下,重复就重复48、某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为：(C)A）3B）2C）4D）5后序最后一个为根节点49、在数据结构中假定在一棵二叉树中，度为2的结点数为15个，度为1的结点数为32个，则叶子结点数为（B）个。A）15B）16C）17D）47每个分枝下面都有一个结点，所以总结点数N=2*15+1*32+0*叶子数+1(根节点）=63二叉树中除了双分支结点，单分支结点就是叶子结点。所以叶子数=63-15-32=16.50、树最适合用来表示(C)。A）有序数据元素B）无序数据元素C）元素之间具有分支层次关系的数据D）元素之间无联系的数据51、在顺序存储结构的线性表中第i个元素(1=i=n)前插入一个元素时，需要向后移动（C）个元素。A）n-i-2B）n-i-1C）n-i+1D）n52、在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）A）插入B）删除C）排序D）定位53、对一个满二叉树，m个叶子，n个结点，深度为h，则(D)。A）n=h+mB）h+m=2nC）m=h-1D）n=2h-1（n=2m-1）m=2h-1;n=2h-154、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（C）A）单链表B）仅有头指针的单循环链表C）双链表D）仅有尾指针的单循环链表55、从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（A）。A）n-iB）n-i+1C）n-i-1D）i56、在决定选取何种存储结构时，一般不考虑（A）。A）各结点的值如何B）结点个数的多少C）对数据有哪些运算D）所用的编程语言实现这种结构是否方便。57、顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（D）。A）s.elem［top］=e；B）s.elem［top+1］=e；s.top=s.top+1；s.top=s.top+1；C）s.top=s.top+1；D）s.top=s.top+1；s.elem［top+1］=e；s.elem［top］=e；先进后出58、循环队列sq中，用数组elem［26］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（D）。A）8B）16C）17D）1812+26-20队空：front＝＝rear队满：(rear+1)%maxsize==front队中元素个数n＝（rear-front+maxsize)%maxsize入队：rear=(rear+1)%maxsize;出队：front=(front+1)%maxsize;59、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B）A）3，2，6，1，4，5B）3，4，2，1，6，5C）1，2，5，3，4，6D）5，6，4，2，3，1先进后出60、不带头结点的单链表head为空的判定条件是(A)。A）head==NULLB）head-next==NULLC）head-next==headD）head!=NULL61、二维数组A[3][3]按行优先顺序存储，若数组元素A[1][1]的存储地址为1087，A[2][2]的存储地址为1095，则数组元素A[0][0]的存储地址为（A）。A）1079B）1080C）1078D）1060（1095-1087）/4=2；A[0][0]=A[1][1]-8=107962、在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A）A）队列B）栈C）线性表D）有序表63、对线性表进行折半查找时，要求线性表必须（B）。A）以顺序方式存储B）以顺序方式存储，且结点按关键字有序排列C）以链式方式存储D）以链式方式存储，且结点按关键字有序排列64、节点的带权路径是指从根节点到该节点的路径长度乘以该节点的权值，树的带权路径长度是指树中所有叶子节点的带权路径长度之和，已知叶子节点a,b,c的权分别是2,5,7abc左边给出的树的带权路径长度为（A）A）21B）14C）22D）28(2+5)*2+7=2165、对一棵有n个节点的二叉树按上述方法对节点进行编号，如果编号为i(i=n)的节点与相