数据结构测试题错题归纳 1~10

目录

• 题目一
• 题目二
• 题目三
• 题目四
• 题目五
• 题目六
• 题目七
• 题目八
• 题目九
• 题目十

题目一

int a[5][4], (*p)[4]=a;，数组a的首地址为100，*(p+2)+3等于 （ ）

• A  116
• B  118
• C  144
• D  122

错误思路：(*p)[4]展开成 *(p+0)+4 就是 p+0*4+4 = p+4 = a 地址是100；*(p+2)+3展开成 p+2*4+3 = p+8+3 = p+11 ，与p+4相差7个int单元，就是 7*4个字节 ，最终地址是100+7*4 = 128。

分析：没有搞清楚指针p定义时赋值的格式，自己误把 (*p)[4]看作数组首地址a。

正确思路：指针p是一个二级指针，int (*p)[4]=a;表示将p指向a这个二级地址，p表示的地址是100。*(p+2)+3展开成 p+2*4+3 = p+8+3 = p+11 ，与p相差11个int单元，就是 7*11个字节,最终是地址是144（在32位操作系统中int长度为32个bit）。答案选C。

题目二

问：已知元素的入栈顺序为abcde，则下列哪种出栈顺序是不可能的(出栈和入栈操作可交叉进行）

• A．edcba
• B．cabde
• C．dcbae
• D．bcdea

分析：出栈和入栈操作可交叉进行，说明入栈操作并不一定是连续进行的。由于栈有后入先出的逻辑特点，所以对于该题有如下规律：出栈的第一个元素是在原来的次序中是第几个，那么他的前面的元素必然都还在栈中。比如c先出栈，说明此时ba已经入栈且一定还在栈中

正确思路：

A选项：e先出栈，说明栈中存在元素 d-c-b-a 。正确！

B选项：c先出栈，栈中存在 b-a ，元素b距离栈顶比较近。错误

C选项：d先出栈，栈中存在 c-b-a，正确。

D选项：b先出栈，栈中存在 a，正确。
 

题目三

问：若二维数组 a 有 m 列，则在数组元素 a[i][j] 前的元素个数为（）

• A. j * m + i
• B. i * m + j
• C. i * m + j - 1
• D. j * m + i - 1

错误思路：a[i][j] 表示第i行第j列个元素， a[i][j] 表示第 i*m+j 个元素，除去本身前面有  i*m+j-1 个元素。

错误分析：没有考虑到数组的下标是从0开始的，a[i][0] a[i][1] a[i][2] ....

正确思路：a[i][j] 表示第i行第j列个元素。第i行上有 0 1 2....(i-1)行，共有i行 ，就是i*m个元素；第j列前面有 0 1 2....(j-1)个列，就是j个元素。一共算下来就是 i*m+j 个，选择B

题目四

问：在一个完全二叉树中，编号为i的节点存在左孩子，则左孩子的编号是（  ）设根节点编号为0

• A  2i
• B  2i - 1
• C  2i +１
• D  2i + 2

错误思路：
假设i节点是j层 最后一个节点
深度为j：i = 2^j -1 个节点
深度为j+1 ： 2^(j+1) -1 = （i+1)*2 -1 个节点
此时，(i+1)*2 -1 代表第j+1层的最后一个节点(属于i节点的右孩子)
因为根节点编号是0开始计算，又因为是i节点的左孩子。结果是（i+1)*2 -1 -1 -1 = 2i -1

错误分析：因为题目给的是节点编号i,所以把i直接当成"2^j -1"节点个数是不正确滴~ 这是一到找规律的题目，简单做法就是把数值代进入验证每个选项。也可以尝试逻辑推理(上面就是这种方法，，失败了 -_-||)

正确思路：

1.简单的判断：因为根节点的编号是0，它的左子节点是1.带入4个选项就可以轻轻松松的选出正确答案C...

2.推理判断：
假设i节点是j层 最后一个节点
深度为j：i+1 = 2^j -1 个节点
深度为j+1 ： 2^(j+1) -1 = （i+2)*2 -1 个节点
此时，(i+2)*2 -1 代表第j+1层的最后一个节点(属于i节点的右孩子)
因为根节点编号是0开始计算，又因为是i节点的左孩子。结果是（i+2)*2 -1 -1 -1 = 2i +1

题目五

深度为k的完全二叉树中，最少有（  ）个节点

A  2^(k-1)-1
B  2^(k-1)
C  2^(k-1)+1
D  2^(k-)

错误思路：深度为k的满二叉树有2^k 个节点，也就是说深度为k-1的满二叉树有2^(k-1)个节点。至少再加一个节点 2^(k-1) +1 个构成深度为k的完全二叉树

分析：这里是公式弄错了，深度为k的满二叉树有2^k-1个节点，，这个可证明的...

正确思路：深度为k的满二叉树有2^k - 1 个节点，也就是说深度为k-1的满二叉树有2^(k-1) - 1 个节点。至少再加一个节点 2^(k-1) -1 +1 个构成深度为k的完全二叉树。所以选C。

题目六

问：若用一个大小为 6 的数组来实现循环队列，且当 rear 和 front 的值分别为 0 和 3 。当从队列中删除一个元素，再加入两个元素后， rear 和 front 的值分别为 。

• A. 1和5
• B. 2和4
• C. 4和2
• D. 5和1

错误思路：把队头和队尾搞反了(以为数组下标小的就是队头，在对尾的前面)

分析：这是一个循环队列，rear表示队尾 front表示队头。方向是 0(rear) - 5 - 4 - 3(rear) - 2 - 1...

正确思路：在队列中，出队，头指针向队尾方向偏移1；入队，尾指针向同样的方向加1。也就是，删除一个元素 front+1=4 再加入两个元素后 rear+2=2。选B

题目七

在程序设计中，要对两个16K×16K的多精度浮点数二维数组进行矩阵求和时，行优先读取和列优先读取的区别是（）

• A. 没区别
• B. 行优先快
• C. 列优先快
• D. 2种读取方式速度为随机值，无法判断

正确思路：二维数组默认是行优先存储，在内存中每行数据的存储是连续的，而每列的数据不是连续的。按行读取只要每读一个数据地址偏移一下，要是按照列来读取还有根据下标来计算当前存储位置再读取。所以按行读取的速度更快些

题目八

若某线性表最常用得操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？

• A. 顺序表
• B. 双链表
• C. 带头结点的双循环链表
• D. 单循环链表

错误思路：根据链表方便进行插入和删除节点的特性，选择了D

分析与正确思路：顺序表适合存取序号位置的元素，对任意位置存取最方便的就是数组了；在最后进行插入啥删除运算，也不用涉及表中元素节点进行位移的额外操作。选择A。

题目九

假设有60行70列的二维数组A[1……60,1…70]以列序为主序顺序存储,其基地址为10000,每个素占2个存储单元,那么第32行第58列的元素A[32,58]的存储地址为( )。(无第0行第0列元素)

• A. 16902
• B. 16904
• C. 14454
• D. 其它选项均不对

错误思路：先计算A[32][58]前面有多少个元素，因为是数组下标从1开始计算的，A[32][58]前面应该有(32-1)行(58-1)列。31*70+57=2227个元素，一共有2227*2=4454个存储单元。加上基地址，4454+10000=14454

分析：以列序为主序顺序存储....而我上面是按照行为主序计算的。

正确思路：先计算A[32][58]前面有多少个元素，该数组是按照列为主序顺序存储，也就是数组列元素上的数据是地址相邻的。因为是数组下标从1开始计算的，A[32][58]前面应该有(32-1)行(58-1)列。31+57*60=3451个元素，一共有3451*2=6902个存储单元。加上基地址，6902+10000=16902。故选A

题目十

若数组S[1..n]作为两个栈S1和S2的存储空间，对任何一个栈，只有当[1..n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（）

• A. S1的栈底位置为0，S2的栈底位置为n+1
• B. S1的栈底位置为0，S2的栈底位置为n/2
• C. S1的栈底位置为1，S2的栈底位置为n
• D. S1的栈底位置为1，S2的栈底位置为1

正确思路：由于栈的操作都是在栈顶一端进行，根据"只有当[1..n]全满时才不能进行进栈操作"这个条件，S1栈底设置在数组的0位置，向上(数组索引增加方向)进行压栈；S2栈底设置在数组的n位置，向下(数组索引减少方向)进行压栈。可以实现空间的最大利用，选C。

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/85093441