数据结构期末样卷参考答案.doc

排序方法 平均情况 最好情况 最坏情况 基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) 2-路归并排序 O(n log n) O(n log n) O(n log n) 堆排序 O(n log n) O(n) O(n log n) 快速排序 O(n log n) O(n log n) O(n2) 希尔排序 O(n) 直接插入排序 O(n2) O(n) O(n2) 简单选择排序 O(n2) O(n2) O(n2) 直接插入排序： 折半插入排序：与折半查找相联系 2-路插入排序：形成环 希尔排序：给定间隔进行排序 冒泡排序 快速排序：方向交替 简单选择排序：与冒泡排序相关 树形选择排序：挑出最大或最小放在根结点，数据放在叶子节点 堆排序：类似树形 归并排序：分小组排序 基数排序：按位排序 数据结构——期末样卷 是非题（每题1分共10分） 1. 线性表的链式存储结构优于顺序存储结构。 F 2. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行插入/删除操作。F 3． 栈是数据对象特定的线性表。F 4． 在单链表P指针所指结点之后插入S结点的操作是：P-next= S ; S- next = P-next; F 5． 一个无向图的连通分量是其极大的连通子图。T 6． 邻接表可以表示有向图，也可以表示无向图。T 7． 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的中序遍历。 T 8． 通常，二叉树的第i层上有2i-1个结点。F 9． 对于一棵m阶的B-树树中每个结点至多有m 个关键字除根之外的所有非终端结点至少有(m/2(个关键字对于任何待排序序列来说，快速排序均快于起泡排序。m个结点的二叉排序树，其最大深度为（ f ），最小深度为（ b ）。 a. log 2 m b. └ log2 m ┘ +1 c. m/2 d .┌ m/2 ┐ -1 e. ┌ m/2 ┐ f. m 8．已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。 下列选择中（ c ）是快速排序一趟排序的结果。 （ b ）是希尔排序（初始步长为4）一趟排序的结果。 （ e ）是起泡排序一趟排序的结果。 （ a ）是初始堆（大堆顶）。 a. 84，79，64，37，57，52，58，26，28，34，56。 b. 28，34，57，26，56，52，58，37，79，84，64。 c. 28，34，37，26，52，56，64，79，58，84，57。 d. 52，34，64，84，56，26，37，57，58，28，79。 e. 34，56，26，58，52，64，37，28，79，57，84。 f. 34，56，26，58，52，79，37，64，28，84，57。 三．填空题（每题2分共20分） 1．有向图的存储结构有（邻接矩阵）、（邻接表）、（十字链表）等方法。 2．已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。 其后序遍历次序为（）。遍历次序为（）3． i=n; i0; i--) {语句1} { x++; {语句2} for( j=n; j=i; i--) {语句3} y++; {语句4} }; 语句1执行的频度为（n+1）；语句4执行的频度为（n(n+1)/2）。 4．请在下划线上填入适当的语句，完成以下法算。 Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)){ //先序非递归遍历二叉树。 Initstack ( S ); Push ( S,T ); While ( !stackempty( S ) ) { While ( gettop( S, p ) p ) { visit (p-data ) ; push(S, p-lchild ;} Pop ( S , p ); If ( !stackempty(s) ) { pop(S, p) ; push( S, p-rchild ); } } return ok; 四．简答题（每题5分共25分） 1．将图示森林转换为二叉树，并对该二叉树中序全序线索化。