中学教育数据结构复习.docx

中学教育数据结构复习.docx

《中学教育数据结构复习.docx》由会员分享，可在线阅读，更多相关《中学教育数据结构复习.docx（7页珍藏版）》请在冰点文库上搜索。

<<数据结构>>复习题

<<数据结构>>复习题

1.klusWirth的观点，程序等于什么?

算法+数据结构

2.算法的重要特性。

有穷性，确定性，可行性，输入，输出

3.好算法的标准。

正确性，可读性，健壮性，高效率低存储

4.线性结构的特点。

（一）存在唯一的一个称做"第一个"的数据元

（二）存在唯一的一个称做"最后一个"的数据元素

（三）除了第一个外，其余的每个元素都有前驱

（四）除了最后一个外，其余的每个元素只要一个后继

5.线性结构与非线性结构的区别。

6.列出所学过的线性结构与非线性结构。

线性：

线形表，链表，静态链表,栈，队列

非线形：

树，图,数组,广义表

7.头指针、头结点、首元结点的区别。

头结点：

表头结点，不含有数据

头指针：

一个指针变量，指向链表中的第一个结点

首元结点：

链上第一个含有数据的结点

8.带头结点和不带头结点的线性链表的区别。

带头结点的线形链表：

便于单个链表的操作，操作比较方便

不带头结点的线形链表：

便于多个链表的收集（基数排序）

9.单链表、双链表、循环链表的区别及各自的优缺点。

单链表：

每个结点中只包含一个指针域

优点：

插入和删除时候不需要移动大量的元素

双链表：

有两个指针域，其一指向直接后继，其二指向直接前驱

优点：

查找直接前驱的时候，则从头指针出发，能够克服单链表这种单向性的缺点

循环链表：

最后一个结点的指针域指向头结点

使两个表连接起来就很简单，这个操作仅需两个指针即可

10.栈和队列是什么样的线性表?

栈与队列是操作受限制的线性表

11.指出顺序线性表、顺序栈、顺序队列的区别。

相同：

他们都是线性表，都是一维数组，

不相同：

操作不同而已；

12.举出几个栈和队列的实例及用栈和队列所能解决的问题。

实例：

栈：

铁路中转站，餐厅的食物盘,子弹壳。

队列：

操作系统作业排队，排队买东西

栈解决的问题是：

后进先出的数据（LIFO）

队列解决的问题：

先进先出的数据（FIFO）

13.指出通常解决"队列"、"栈"的"溢出"时所能用到的方法。

队列：

双向队列，链队列，循环队列

栈：

双栈共享，多栈共享，链栈

14.循环队列是怎样实现的?

比队列多两个分别指向队头元素和队尾元素，尾指针指向队尾元素的当前位置；

头指针指向对头元素的前一个位置

15.给出对称矩阵、三角矩阵的节省内存的存贮结构并写出相应的输入、输出算法

。

Aij=Aji

K=I（I-1）/2+JI>=J;

K=J（J-1）/2+II

一维数组SA（k）存放n（n+1）/2;

三角距阵再加上一个存储常数C的空间

算法：

16.给出稀疏矩阵的节省内存的存贮结构并写出相应的输入、输出算法。

17.用十字链表存贮稀疏矩阵时,矩阵的每个元素同时在几条链上,分别被称为什

么链？

两条链，行链和列链

18.给出树的不同的几种表示形式。

四种方式：

（一）层次表示法

（二）嵌套表示法

（三）广义表表示法（四）凹入法表示法

19.在二叉树的第i层上至多有多少个结点。

2（I-1）

20.深度为K的二叉树至多有多少个结点。

2k-1=20+21+…+2k-1

21.在一颗二叉树中,其终端结点数n0和度为二的结点数n2之间的关系。

n0=n2+1;

22.有n个结点的完全二叉树的深度。

[Log2n]+1

23.在二叉树的顺序存贮结构中如何求结点的双亲、孩子?

双亲：

[i/2]左孩子：

2*i右孩子：

2*i+1

24.有n个结点的二叉树用二叉链表存贮时有多少个空链域，用三叉链表存贮时有

多少个空链域。

二叉：

n+1个空链域三叉：

n+2个

25.为什么可在不增加指针域的情况下，对二叉树进行线索化，线索化的目的是什

么?

利用n+1个空链域目的：

遍历方便

26.对于已线索化的二叉树如何识别指针域是指向孩子还是指向其后继结点?

增加标志域lflag,rflag

27.树的几种存贮结构（双亲表示法、孩子表示法、孩子兄弟表示法）的优缺点，各

自适应的运算。

双亲表示法：

利用了每个结点只有一个双亲的性质,便于查找双亲，缺点：

找孩子时

要多次遍历整个数组

孩子表示法：

便于涉及到孩子的操作，

缺点：

找双亲比较麻烦。

孩子兄弟法：

二叉链表表示法，（一个指针是指向孩子，另一个指向兄弟）这个适用

于各种树的操作，（左指针为空就是叶子）

28.哪种存贮结构可将森林转为二叉树。

对此种结构的各个域给予注释。

说明在这

个结构中怎样找到森林的n棵树。

孩子兄弟表示法，左指针是第一个孩子，右指针是第一个兄弟，最右的为第n棵树

29.树的先根遍历、后根遍历对应其二叉树的哪种遍历，森林的先根遍历、中根遍

历对应其二叉树的哪种遍历?

树的先根遍历对应二叉树的先序遍历；

树的后根遍历对应二叉树的中序遍历；

森林的先根遍历对应于二叉树的先序遍历；

森林的中根遍历对应于二叉树的中序遍历。

30.写算法求树中结点的度；树的度；树中的叶子结点数；树中的非终端结点数；

树中某结点的兄弟、祖先、子孙、层次、堂兄弟；树的高度；森林中树的数目。

31.何为完全图、稀疏图、稠密图。

完全图：

有n*（n-1）/2条边的无向图

稀疏图：

有很少条边的图（e

稠密图：

有很多条边的图（e>=nlogn）

32.写算法求无向图中结点的度；有向图中结点的入度和出度。

33.图的数组表示法、邻接表存贮结构各自的优缺点，适应的运算。

图的数组表示法（邻接矩阵表示法）：

二维数组存储图

优点：

容易求各个顶点的度

缺点：

当图为稀疏图时浪费空间

邻接表表示法：

优点：

容易找到第一个邻接点和下一个邻接点，

缺点：

不方便找一个结点的出度

34.最小生成树的实际应用背景。

公路，铁路，通讯网等等

35.什么图适合用Prim算法求最小生成树，什么图适合用Kruskal算法求最小生成

树。

Prim算法稠密的网最小生成树kruskal适合求稀疏的网的最小生成树

36.图示用Prim算法及Kruskal算法求最小生成树的过程.。

37.举例简述"拓扑排序"所解决的实际问题。

流程图，施工流程图，课程决定的优先权

38.请图示"拓扑排序"的过程。

39.举例简述"关键路径"所解决的实际问题。

一个工程的并行的进行过程

40.顺序查找、折半查找、分块查找算法适合的关键字结构。

41.怎样从二叉排序树得到有序表。

中序便利

42.已知长度为n的表按表中元素顺序构造二叉平衡树，图示构造过程。

43.各种查找算法的平均时间复杂度。

44.为一组关键字构造哈希函数并建立哈希表。

45.指出希尔排序，归并排序，快速排序，堆排序，基数排序中稳定的排序方法，

并对不稳定的举出反例。

不稳定的是三中：

快速，堆，希尔排序

46.堆排序算法选用什么样的存贮结构，按此算法得到的有序表是递增还是递减的

。

一唯数组存储，是递减的

47.藉助于"比较"进行排序的算法能达到的最好的时间复杂度是什么?

N*logn

48.指出归并排序，快速排序，堆排序，基数排序算法各适合的关键字结构。

归并：

快速：

混乱的情况

堆：

非常多的情况

基数；多关键字排序

49.指出各种排序算法的平均时间复杂度、最坏情况的时间复杂度。

排序方法平均时间最坏情况辅助存储

简单排序n*nn*n1

快速排序n*lognn*nlogn

堆排序n*lognn*logn1

归并排序n*lognn*lognn

基数排序n+rdn+rdrd

50.请对学习<<数据结构>>这门课程进行全面总结，你认为应该如何学？

教师应该

如何教？