华清远见成都中心-数据结构笔试题题目

数据结构笔试题题目

一、选择题

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,BDCAFGEB.ECBADFG,EFACDBG

C.ECBADGF,EACBDGFD.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(l))

(

q=P；r=(2)

while((3))

{if(⑷)q=G

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.数组和链表的区别，请详细解释。

2.排序算法有哪些？<C语言总共有多少种排序法》

3.怎么理解哈希表,哈希表是什么

4.请写出以下算法的时间复杂度

冒泡排序法插入排序法堆排序法二叉树排序法

快速排序法希尔排序法

5.数据结构，二叉树的相关知识，开销量，为何使用二叉树等。

四、编程题

1.编写一个程序，把一个有序整数数组放在二叉树中。

2.在二叉查找树中查找某一个值所在的位置。

3.二叉树，比父节点大的元素，都在右子树，比父节点小的元素都在左子树。也就是排序

二叉树，写出插入一个节点或者删除一个节点。

4.实现单向链表:创建链表、插入链表、查询链表、删除特定序号链表节点、遍历剩余链

表节点

5.编程实现判断一个链表是否是递增的

6.编程实现删除链表中的重复节点

7.只遍历一次链表，实现链表的倒序

8.将两个有序链表A1,A2表合并为一个有序链表A3

9.已知链表节点

structLNode{

intiValue;

LNode*next;

)；

已创建一个有序的链表，从小到大排列。实现以下函数，将数据插入到链表中，并且有

序。请实现以下函数：

boollnsertLink(LinkList*p,inta){};

10.写一个链表，实现创建链表，添加链表节点，删除链表节点，查找链表节点，写一个

main函数，创建一个链表，里面添加20个学生节点(节点含有姓名和学号)，再删除

其中任意一个节点，输出任意指定节点，输出最后10名学生节点。

11.将test.txt文中的整数按顺序依次存入一个链表中，然后按顺序输出

12.找出单链表的倒数第4个元素

13.找出单链表的中间元素

14.判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？

15.两个单链表相交，计算相交点

16.用两个栈实现队列

17.用两个队列实现栈

18.请实现一个双向循环链表，包含新增，查询，插入，删除，销毁等判断是否为空，打印

输出等基本操作

19.写一个函数，当两个链表中元素data相同时，删除节点。

structnode{

Intdata;

Structnode*front,next;

}有两个链表structnode*headA,*headB(.

20.写一个双向列表倒序的程序

21.一个双向链表，将两个连续的节点交换

22.怎样编写一个程序，把一个有序整数数组放在二叉树中

23.在二叉查找树中查找某一个值所在的位置

24.二叉树，比父节点大的元素，都在右子树，比父节点小的元素都在左子树。也就是排序

二叉树，写出插入一个节点或者删除一个节点。

25.如何判断一棵二叉树是否是平衡二叉树

26.实现冒泡（图）

27.找出字符串中的最长子串，要求子串的所有字符相同

28.递归算法N!

29.11235813……任意语言编程求出第3