数据结构笔试题题目

数据结构笔试题题目

一、 选择题

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 C. ECBADGF, EACBDGF

B. ECBADFG, EFACDBG 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为要插入的新结点。 typedef struct inode { Int data; struct inode *left; struct inode *right;

}b_tree;

b_tree *sort_b_tree(b_tree **tree, b_tree s) { if (NULL == *tree) { *tree = s;

} else if (s->data < (*tree)->data) { } else if (s->data > (*tree)->data) {

} }

三、 简答题

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

2. 排序算法有哪些？< C语言总共有多少种排序法> 3. 怎么理解哈希表,哈希表是什么 4. 请写出以下算法的时间复杂度

冒泡排序法 插入排序法 堆排序法 快速排序法

二叉树排序法 希尔排序法

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

四、 编程题

1. 编写一个程序，把一个有序整数数组放在二叉树中。 2. 在二叉查找树中查找某一个值所在的位置。

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

二叉树，写出插入一个节点或者删除一个节点。 4. 实现单向链表:创建链表、插入链表、查询链表、删除特定序号链表节点、遍历剩余链

表节点

5. 编程实现判断一个链表是否是递增的 6. 编程实现删除链表中的重复节点 7. 只遍历一次链表，实现链表的倒序

8. 将两个有序链表A1,A2表合并为一个有序链表A3 9. 已知链表节点

struct LNode {

int iValue; LNode *next; };

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

bool InsertLink(LinkList *p,int a){};

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

main函数，创建一个链表，里面添加20个学生节点（节点含有姓名和学号），再删除其中任意一个节点，输出任意指定节点，输出最后10名学生节点。 11. 将test.txt文中的整数按顺序依次存入一个链表中，然后按顺序输出 12. 找出单链表的倒数第4个元素 13. 找出单链表的中间元素

14. 判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？ 15. 两个单链表相交，计算相交点 16. 用两个栈实现队列 17. 用两个队列实现栈

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

输出等基本操作 19. 写一个函数，当两个链表中元素data相同时，删除节点。

struct node { Int data;

Struct node* front, next;

}有两个链表struct node* headA, *headB。 20. 写一个双向列表倒序的程序

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

22. 怎样编写一个程序，把一个有序整数数组放在二叉树中 23. 在二叉查找树中查找某一个值所在的位置

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

二叉树，写出插入一个节点或者删除一个节点。 25. 如何判断一棵二叉树是否是平衡二叉树 26. 实现冒泡（图）

27. 找出字符串中的最长子串，要求子串的所有字符相同 28. 递归算法N！

29. 1 1 2 3 5 8 13 ?? 任意语言编程求出第32位数是多少，递归实现 30. 请写一个升序排序函数

31. 请写出冒泡排序，选择排序，快速排序

32. 给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里

33. 一个整数大于0,不用循环和本地变量,按照n、2n、4n、8n的顺序递增，当值大于5000

时，把值按照指定顺序输出来。

本文来源：https://www.bwwdw.com/article/geud.html