第1单元数据结构预算法
必考的内容！
什么？你觉得下面这些题不是二级Office考试内容？那你可太OUT了！
这叫做公共基础，必考的内容！
这都不知，怎能考过？赶快跟着小编复习吧——
考试A、B、C、D顺序会错乱哦，不要背选项字母
1)下列叙述中正确的是A)设计算法时只需要考虑结果的可靠性B)算法就是程序C)设计算法时要考虑时间复杂度和空间复杂度D)设计算法时只需要考虑数据结构的设计答案：C2)循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为A)2
B)1，或50且产生上溢错误C)26D)51答案：B3)下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是A)在顺序存储的线性表中寻找最大项B)在顺序存储的有序表中进行对分查找C)在链式存储的有序表中进行查找D)在顺序存储的线性表中进行顺序查找答案：A4)设表的长度为20。则在最坏情况下，冒泡排序的比较次数为A)19B)20C)D)90答案：C
5)下列叙述中正确的是A)循环队列是链式存储结构B)循环队列是非线性存储结构C)循环队列是线性逻辑结构D)循环队列是线性结构答案：D6)设某棵树的度为3，其中度为3,2,1的结点个数分别为3,0,4。则该树中的叶子结点数为A)6B)不可能有这样的树C)7D)8答案：C7)设有一个栈与一个队列的初始状态均为空。现有一个序列A,B,C,D,E,F,G,H。先分别将序列中的前4个元素依次入栈，后4个元素依次入队；然后分别将栈中的元素依次退栈，再将队列中的元素依次退队。最后得到的序列为A)D,C,B,A,H,G,F,EB)A,B,C,D,E,F,G,HC)D,C,B,A,E,F,G,HD)A,B,C,D,H,G,F,E答案：C
8)下列叙述中错误的是A)具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构B)具有两个以上指针域的链式结构一定属于非线性结构C)具有两个根结点的数据结构一定属于非线性结构D)具有两个以上叶子结点的数据结构一定属于非线性结构答案：B9)下列结构中属于线性结构链式存储的是A)二维数组B)二叉链表C)双向链表D)循环队列答案：C10)下列叙述中错误的是A)循环链表的存储空间是连续的B)循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点C)循环链表实现了空表与非空表运算的统一D)循环链表中有一个表头结点答案：A
11)度为3的一棵树共有30个结点，其中度为3,1的结点个数分别为3,4。则该树中的叶子结点数为A)16B)15C)不可能有这样的树D)14答案：B12)在长度为97的顺序有序表中作二分查找，最多需要的比较次数为A)96B)7C)48D)6答案：B13)下列结构中属于非线性结构的是A)双向链表B)二叉链表C)循环队列D)二维数组答案：B
14)从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是A)循环链表B)二叉链表C)双向链表D)单向链表答案：A15)设某棵树的度为3，其中度为3,1,0的结点个数分别为3,4,15。则该树中总结点数为A)30B)22C)35D)不可能有这样的树答案：A
注意，人家可没说度为2的结点。。。你得设总结点有x个，度为2的有y个，然后列方程去。“树中的结点数=所有结点的度数+1”，根据这个列方程。
16)下列叙述中正确的是A)线性表中各元素的数据类型可以不同B)对线性表只能作插入与删除运算C)数组是长度固定的线性表D)矩阵是非线性结构答案：C17)在快速排序法中，每经过一次数据交换（或移动）后A)不会产生新的逆序B)能消除多个逆序C)消除的逆序个数一定比新产生的逆序个数多D)只能消除一个逆序答案：B18)线性表的长度为n。在最坏情况下，比较次数为n-1的算法是A)有序表的插入B)同时寻找最大项与最小项C)寻找最大项D)顺序查找答案：C
19)设某棵树的度为3，其中度为2,1,0的结点个数分别为3,4,15。则该树中总结点数为A)不可能有这样的树B)35C)30D)22答案：A20)下列叙述中错误的是A)非空线性结构中只有一个结点没有后件B)只有一个根结点和一个叶子结点的结构必定是线性结构C)向量是线性结构D)非空线性结构中只有一个结点没有前件答案：B21)在希尔排序法中，每经过一次数据交换后A)能消除多个逆序B)消除的逆序个数一定比新产生的逆序个数多C)只能消除一个逆序D)不会产生新的逆序答案：A22)下列叙述中正确的是A)所有的线性结构都可以采用顺序存储结构B)能采用顺序存储的必定是线性结构C)循环队列是队列的链式存储结构D)具有两个以上指针的链表必定是非线性结构答案：A23)设表的长度为n。在下列算法中，最坏情况下时间复杂度最高的是A)希尔排序B)堆排序C)循环链表中寻找最大项D)有序链表查找答案：A
24)设循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。经过一系列正常的操作后，front=rear-1。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为A)49B)0C)1D)50答案：B25)设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则后序序列为A)ABCDEFGHIJB)DGHEBIJFCAC)GHIJDEFBCAD)JIHGFEDCBA答案：B26)设顺序表的长度为16，对该表进行简单插入排序。在最坏情况下需要的比较次数为A)B)30C)60D)15答案：A27)下列叙述中正确的是A)算法的复杂度是指算法程序中指令的数量B)算法的复杂度是指算法所处理的数据量C)算法的复杂度包括时间复杂度与空间复杂度D)算法的复杂度是指算法控制结构的复杂程度答案：C28)设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则按层次输出（从上到下，同一层从左到右）的序列为A)ABCDEFGHIJB)DGHEBIJFCAC)GHIJDEFBCAD)JIHGFEDCBA答案：A29)设循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。经过一系列正常的操作后，front-1=rear。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为A)48B)1C)0D)49答案：A
24)设循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。经过一系列正常的操作后，front=rear-1。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为
A)49
B)0
C)1
D)50
答案：B
25)设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则后序序列为
A)ABCDEFGHIJ
B)DGHEBIJFCA
C)GHIJDEFBCA
D)JIHGFEDCBA
答案：B
26)设顺序表的长度为16，对该表进行简单插入排序。在最坏情况下需要的比较次数为
A)
B)30
C)60
D)15
答案：A
27)下列叙述中正确的是
A)算法的复杂度是指算法程序中指令的数量
B)算法的复杂度是指算法所处理的数据量
C)算法的复杂度包括时间复杂度与空间复杂度
D)算法的复杂度是指算法控制结构的复杂程度
答案：C
28)设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则按层次输出（从上到下，同一层从左到右）的序列为
A)ABCDEFGHIJ
B)DGHEBIJFCA
C)GHIJDEFBCA
D)JIHGFEDCBA
答案：A
29)设循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。经过一系列正常的操作后，front-1=rear。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为
A)48
B)1
C)0
D)49
答案：A
注：谁认为29和24是一样的题，自己面壁去！考虑清楚了，回来看条件，-1在等号哪边？那么不仔细还行，考试咋办？
30)设顺序表的长度为40，对该表进行冒泡排序。在最坏情况下需要的比较次数为A)40B)41C)D)答案：D31)设表的长度为n。在下列结构所对应的算法中，最坏情况下时间复杂度最低的是A)堆排序B)希尔排序C)有序链表查找D)循环链表中寻找最大项答案：D32)设循环队列的存储空间为Q(1:m)，初始状态为front=rear=m。经过一系列正常的操作后，front=1，rear=m。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为A)mB)m-2C)0D)1E)m-1答案：B33)设二叉树的后序序列为DGHEBIJFCA，中序序列为DBGEHACIFJ。则前序序列为A)JIHGFEDCBAB)GHIJDEFBCAC)ABDEGHCFIJD)ABCDEFGHIJ答案：C34)下列结构中为非线性结构的是A)树B)二维表C)矩阵D)向量答案：A35)下列关于栈的叙述中，正确的是A）栈底元素一定是最后入栈的元素B）栈顶元素一定是最先入栈的元素C）栈操作遵循先进后出的原则答案：C36)设二叉树共有个结点，其中度为1的结点有10个，则该二叉树中的叶子结点数为A）71B）70C）69D）不可能有这样的二叉树答案：D37)下列叙述中正确的是A）程序执行的效率与数据的存储结构密切相关B）程序执行的效率只取决于程序的控制结构C）程序执行的效率只取决于所处理的数据量答案：A38)下列与队列结构有关联的是A）函数的递归调用B）数组元素的引用C）多重循环的执行D）先到先服务的作业调度答案：D39)
A）DYBEAFCZXB）YDEBFZXCAC）ABDYECFXZD）ABCDEFXYZ答案：C
40)一个栈的初始状态为空。现将元素1,2,3,A,B,C依次入栈，然后再依次出栈，则元素出栈的顺序是A）1,2,3,A,B,CB）C,B,A,1,2,3C）C,B,A,3,2,1D）1,2,3,C,B,A答案：C41)下列叙述中正确的是A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小D）算法的时间复杂度与空间复杂度没有直接关系答案：D42)下列叙述中正确的是A）循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B）循环队列中的元素个数随队头指针的变化而动态变化C）循环队列中的元素个数随队尾指针的变化而动态变化答案：A43)一棵二叉树中共有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为A）B）C）D）答案：B44)对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为A）9B）10C）45D）90答案：C45)下列叙述中正确的是A）算法的效率只与问题的规模有关，而与数据的存储结构无关B）算法的时间复杂度是指执行算法所需要的计算工作量C）数据的逻辑结构与存储结构是一一对应的D）算法的时间复杂度与空间复杂度一定相关答案：B
46)下列叙述中正确的是A）线性表链式存储结构的存储空间一般要少于顺序存储结构B）线性表链式存储结构与顺序存储结构的存储空间都是连续的C）线性表链式存储结构的存储空间可以是连续的，也可以是不连续的答案：C47)某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度为（根结点在第1层）A）3B）6C）8D）12答案：D48)对长度为n的线性表作快速排序，在最坏情况下，比较次数为A）nB）n-1C）n(n-1)D）n(n-1)/2答案：D49)下列叙述中正确的是A）有且只有一个根结点的数据结构一定是线性结构B）每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构C）有且只有一个根结点的数据结构一定是非线性结构D）有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构答案：D50)下列叙述中错误的是A）在双向链表中，可以从任何一个结点开始直接遍历到所有结点B）在循环链表中，可以从任何一个结点开始直接遍历到所有结点C）在线性单链表中，可以从任何一个结点开始直接遍历到所有结点D）在二叉链表中，可以从根结点开始遍历到所有结点答案：C