杭州电子科技大学试卷测试题B卷数据结构.docx

杭州电子科技大学试卷测试题B卷数据结构

一、选择题（每题3分，共30分）

1.线性表采用链式存储时，其地址（）。

A.必须是连续的

B.一定是不连续的

C.部分地址必须是连续的

D.连续与否均可以

答案：D。链式存储结构中，每个节点通过指针域指向其后续节点，节点在内存中的存储位置是任意的，连续与否都可以，只要通过指针能正确连接各节点即可。

2.栈和队列的共同点是（）。

A.都是先进先出

B.都是先进后出

C.只允许在端点处插入和删除元素

D.没有共同点

答案：C。栈是先进后出的数据结构，只能在栈顶进行插入和删除操作；队列是先进先出的数据结构，只能在队尾插入元素，在队头删除元素，二者都只允许在端点处进行插入和删除操作。

3.若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（）。

A.ni

B.ni+1

C.i

D.不确定

答案：B。因为输出序列的第一个元素是n，说明是先将1，2，3，…，n依次入栈，然后再依次出栈。那么第一个出栈的是n，第二个出栈的是n1，第i个出栈的就是ni+1。

4.树最适合用来表示（）。

A.有序数据元素

B.无序数据元素

C.元素之间具有分支层次关系的数据

D.元素之间无联系的数据

答案：C。树是一种非线性数据结构，它的特点是元素之间存在明显的分支层次关系，非常适合用来表示具有这种关系的数据。

5.深度为5的完全二叉树的节点数不可能是（）。

A.15

B.16

C.17

D.31

答案：A。深度为h的完全二叉树，节点数最少的情况是第h层只有一个节点，此时节点数为\(2^{h1}\)；节点数最多的情况是满二叉树，节点数为\(2^{h}1\)。深度为5的完全二叉树，节点数最少为\(2^{4}=16\)，最多为\(2^{5}1=31\)，所以不可能是15。

6.对线性表进行二分查找时，要求线性表必须（）。

A.以顺序方式存储

B.以链式方式存储

C.以顺序方式存储，且数据元素有序

D.以链式方式存储，且数据元素有序

答案：C。二分查找的基本思想是将有序序列分成两部分，通过比较中间元素与目标元素的大小，缩小查找范围。它要求线性表以顺序方式存储，这样才能方便地通过下标访问元素，同时数据元素必须有序。

7.已知一个有序表为(12，18，24，35，47，50，62，83，90，115，134)，当用二分查找法查找值为90的元素时，查找成功的比较次数为（）。

A.1

B.2

C.3

D.4

答案：B。第一次查找，取中间元素，\((1+11)\div2=6\)，对应元素50，90大于50，在右半部分查找；第二次查找，右半部分的中间元素，\((7+11)\div2=9\)，对应元素90，查找成功，共比较2次。

8.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。

A.希尔排序

B.归并排序

C.插入排序

D.选择排序

答案：D。选择排序的基本思想是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

9.设有一个无向图G=(V，E)和G=(V，E)，如果G是G的生成树，则下面说法错误的是（）。

A.G为G的子图

B.G为G的连通分量

C.G为G的极小连通子图且V=V

D.G是一个无环图

答案：B。生成树是一个连通图的极小连通子图，它包含图中所有的顶点，且是无环的，是图的一个子图。而连通分量是无向图中的极大连通子图，生成树不是连通分量，所以B选项错误。

10.对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是（）。

A.O(n)

B.O(n^2)

C.O(nlog?n)

D.O(n3)

答案：B。快速排序的最坏情况是每次划分选取的基准元素都是当前无序区中关键字最小（或最大）的记录，此时划分结果是基准左边（或右边）的子区间为空，而另一边的子区间中的记录数仅比划分前的无序区中的记录数少一个，此时时间复杂度为\(O(n^{2})\)。

二、填空题（每题3分，共15分）

1.数据的逻辑结构分为线性结构和__________结构。

答案：非线性。数据的逻辑结构主要分为线性结构和非线性结构，线性结构中元素之间是一对一的关系，非线性结构中元素之间存在一对多或多对多的关系。

2.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈