数据结构第二套题(带答案)

数据结构第二套题

一、选择题 1.

下面关于线性表的叙述错误的是（ ）

D.线性表采用顺序存储便于插入和删除操作的实现

2.

设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ ）。 C.树形结构

3.

设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（ ）。

C.s->left=p；s->right=p->right；p->right->left=s； p->right=s；

4.

设用链表作为栈的存储结构，则退栈操作（ ） D.必须判别栈是否为空

5.

设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ ） B.n+1-i

6.

栈和队列的共同特点是

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

7.

设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ） D.11

8.

对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个， A.4

9.

若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为 A.9，4，2，3

10. 设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向

被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ ）。 B.q->next=s； s->next=p；

11. 以下数据结构中哪一个是非线性结构？

C.二叉树

12. 设顺序表的长度为n，则顺序查找的平均比较次数为（ ）。

C.(n+1)/2

13. 设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ ）。

B.head->next==head

14. 数据的最小单位是（ ）

D.数据项

15. 设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，

则该操作的时间复杂度为（ ） A. O(n)

16. 设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（ ）存储方式

最节省运算时间。 D.双向循环链表

17. 建立一个长度为n的有序单链表的时间复杂度为（ ）

D.O(n2)

18. 建立一个长度为n的有序单链表的时间复杂度为（ ）

D.O(n2)

19. 以下数据结构中哪一个是非线性结构？

A.二叉树

20. 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45

为基准而得到一趟快速排序的结果是（ ）。 C.42，40，45，55，80，85 二、判断题

1.

不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为

O(n)。（ ） 正确

2.

线性表的顺序存储结构比链式存储结构更好。（ ） 错误

3.

线性表的顺序存储结构比链式存储结构更好。（ ） 错误

4.

哈夫曼树中没有度数为1的结点。（ ） 正确

5.

线性表中的所有元素都有一个前驱元素和后继元素。（ ） 错误

6.

对链表进行插入和删除操作时不必移动链表中结点。( ) 正确

7. 完全二叉树中的叶子结点只可能在最后两层中出现。（ ）

正确

8. 对连通图进行深度优先遍历可以访问到该图中的所有顶点。（ ）

正确

9. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ ）

正确

10. 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( )

正确

11. 如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（ ）

正确

12. 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边

数有关。( ) 错误

13. 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（ ）

正确

14. 由树转化成二叉树，该二叉树的右子树不一定为空。（ ）

错误

15. 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（ ）

错误

16. 快速排序是排序算法中平均性能最好的一种排序。（ ）

正确

17. 设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（ ）

错误

18. 带权无向图的最小生成树是唯一的。（ ）

错误 三、填空题

1. 在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。

A 0 1 2 3 4 5 6 7 data next

3 60 5 50 7 78 2 90 0 34 4 40 1 答案：线性表为：（78，50，40，60，34，90）

2. 已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。

(8,9,4,3,6,1),10,(12,18,18) (1,6,4,3),8,(9),10,12,(18,18) 1,(3,4,6),8,9,10,12,18,(18) 1,3,(4,6),8,9,10,12,18,18 1,3, 4,6,8,9,10,12,18,18

3. 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用

二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。 2,ASL=91*1+2*2+3*4+4*2)=25/9

4. 已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边 标准答案：

用克鲁斯卡尔算法得到的最小生成树为：

(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20

四、综合体

阅读算法，回答问题： void ABC(BTNode * BT)

{

if BT {

ABC (BT->left); ABC (BT->right); cout<data<<' '; } }

该算法的功能是： 标准答案：

递归地后序遍历链式存储的二叉树