数据结构笔试题题目.pdf

数据结构笔试题题目

数据结构笔试题题目

一、选择题

1.下面哪种排序法对123456798在空间和时间上最优()

A.快速排序

B.冒泡排序

C.插入排序

D.堆排序

2.2.就排序算法所用的辅助空间而言，堆排序，快速排序，归并

排序的关系是（）

A．堆排序〈快速排序〈归并排序B．堆排序〈归并排序〈快速排

序

C．堆排序〉归并排序〉快速排序D．堆排序快速排序归并排

序

E．以上答案都不对

3.3.一株二叉树的以某种遍历方式的序列为A、B、C、D、E、F、

G，.若该二叉树的根结

点为E,则它的一种可能的前序遍历为____,相应的后序遍历为____

A.ECBADFG,BDCAFGE

B.ECBADFG,EFACDBG

C.ECBADGF,EACBDGF

D.EACBDGF,BDCAFGE

（常见题型，给出树的前序遍历和中序遍历，中序和后续遍历，

推出二叉树）

4.关于图和树，下面说法正确的是________

A.树和图都允许有环

B.图的深度遍历和广度遍历结果可能一样

C.二叉树是每个节点都有两个孩子节点的树

D.二叉树的前序遍历和后序遍历结果肯定不一样

5.完成在双循环链表结点p之后插入s的操作是（）

A．p-next=s;s-priou=p;p-next-priou=s;

s-next=p-next;

B．p-next-priou=s;p-next=s;s-priou=p;

s-next=p-next;

C．s-priou=p;s-next=p-next;p-next=s;

p-next-priou=s;

D．s-priou=p;s-next=p-next;p-next-priou=s;

p-next=s;

二、填空题

1.用链表表示的数据的简单选择排序，结点的域为数据域data，

指针域next；链表首

指针为head，链表无头结点。

selectsort(head)

p=head;

while(p(1)_______)

{

q=p;r=(2)_______

while((3)______)

{if((4)_______)q=r;

r=(5)_______;

}

tmp=q-data;q-data=p-data;p-data=tmp;p=

(6)_______;

}

2.二叉树对称序列为ABCDEFG,后序序列为BDCAFGE,问前序序

列为：_________

3.填空：要求用递归的方法实现二叉树排序,第二个参数s为要插

入的新结点。

typedefstructinode{

Intdata;

structinode*left;

structinode*right;

}b_tree;

b_tree*sort_b_tree(b_tree**tree,b_trees)

{

if(NULL==*tree){

*tree=s;

}elseif(s-data(*tree)-data){

}elseif(s-data(*tree)-data)

{

}

}

三、简答题

1.数组和链表的区别，请详细解释。