数据结构试卷3(含答案)汇.docVIP

一、 判断题 1．简单地说,数据结构是带有结构的数据元素的集合。 ( T ) 2．线性表的顺序存储结构具有可直接存取表中任一元素的优点。（ T ） 3．二叉排序树的平均查找长度为O(logｎ)。（ T ） 4．邻接多重表可用来表示有向图。( F ) 5。栈是限定仅在表头进行插入和表尾进行删除运算的线性表。 ( F ) 二．选择题（共12分，每个迭择项2分） 1．若要按升序对关键字序列（59,41,75,26,33,16,61,20,55,71,15,44）进行排序,则（ 3）是堆排序初始建堆的结果（小堆顶）。（ 1 ）是以第一个元素作为枢轴的快速排序一趟扫描的结果。（ 6 ）是希尔排序（初始步长为4）一趟扫描的结果。（ 5 ）是冒泡排序一趟扫描的结果。 1 44,41,15,26,33,16,55,20,59,71,61,75 2 20,41,61,71,33,44,75,55,15,26,16,59 3 15,20,16,26,33,44,61,59,55,71,41,75 4 41,59,75,26,33,16,20,61,55,15,71,44 5 41,59,26,33,16,61,20,55,71,15,44,75 6 33,16,15,20,55,41,61,26,59,71,75,44 2.先序遍历图示二叉树可得到（ a ）的序列。 a) A B H D E F I C G (A) b) H B E D F I A CG ／ ＼ c) H E I F D B G C A (B) (C) ／ ＼ ＼ (H) (D) (G) ／ ＼ (E) (F) ＼ (I) 3.图示的三棵二叉树中( c)为最优二叉树。 A) B) C) c a 2 7 a b c d d b 7 5 2 4 4 5 a b c d 7 5 2 4 三．填空题（共24分， 每空2分） 1．对于一棵二叉排序树，通过按( 中序 )次序遍历，可以得到结点的有序序列。 2．设循环队列存于一维数组Ｑ[ｍ]中，尾指针rear指示队尾元素在队列中的当前位置，头指针front指示队列中队头元素的前一个位置， 则队列长度＝( (rear-front + m )mod m )。 3.一棵ｍ阶的Ｂ-树，第一层至少有一个结点；第二层至少有2个结点，除根之外的所有非终端结点至少有（ ┌ m/2 ┐ ）棵子树，树中每个结点至多有（ m ）棵子树。 4. 对任何一棵二叉树T,若其终端结点数为n0.度为2的结点为n2,则n0与n2的关系为( n0=n2+1 )。 5．折半插入排序是对直接插入排序算法的改进，它着眼于减少 比较次数 。 6. 如果对完全二叉树中结点从1开始按层进行编号，设最大编号为n；那么，可以断定编号为i (i1)的结点的父结点编号为 i/2 ； 所