2006年吉林大学珠海学院数据结构期末卷.doc

2006年 A卷 【 字号： 大 中 小 】 A 一、 10分） 在下列备选答案中选出一个正确的, 将其号码填在“_____”上。 1. 若已有一个栈，输入序列为A，B，C，D，E，那么下面哪种序列不可能得到？（ ） a．ABCDE b．EDCBA c．BAEDC d．ECDBA 2. 在用邻接表表示图时, 对图进行深度优先有哪些信誉好的足球投注网站遍历的算法的时间复杂度为______。 a. Ｏ(n) b. Ｏ(n+e) c. Ｏ(n2)　 d. Ｏ(n3) 3. 下列排序算法中, 只有____排序算法是不稳定的。 a. 快速排序 b. 冒泡排序 　 c. 二路归并排序 　 d. 直接插入排序 4. 快速排序算法的平均时间复杂度是（ ） a．O（n2） b. O (nlog2n) c. O(n) d. O(logn) 5. 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根 结点的编号为1。编号为49的结点X的双亲编号为（ ） a．24 b. 25 c.23 d.无法确定 二、判断题：（每小题2分，共20分） 　　判断下列各题是否正确，若正确，在（）内打“√”，否则打“×”。 　 1. ( ) 线性表只能用顺序方式存放。 2. ( ) 在带表头结点的双循环链表中，每个结点的前趋和后继指针均不为空。 　 3. ( ) 如果两个串含有相同的字符，则这两个串相等。　　。 4. ( ) 连通网络的最小生成树不一定是唯一的，并且权值可以不相等。 　 5. ( ) 栈可以作为实现程序设计语言过程调用时的一种数据结构。 6. ( ) 无向图G（设G中至少有2个顶点）采用邻接矩阵存储，若从某顶点开始对无向图G进行广度优先遍历, 则所得的遍历序列总是唯一的。 7. ( ) 图的深度优先遍历是通过使用队列队列来实现的。 8. ( ) 冒泡排序算法在最好情况下所作的比较元素的次数为n次。 9. ( ) 广义表的深度是指其中所含的不同原子的个数。 10. ( ) 一棵非空的二叉树的后序遍历序列的最后一个元素是其最右下结点。 三、填空（每空２分,共20分）: 1. 在带头结点的单链表L中, 第一个元素所对应的结点的指针表达式是_____________。 2. 在双向循环链表中，在结点*Ｐ之前插入结点*Ｓ的语句序列是： S- prior = P- prior ; S-next=P; P-prior=S; __________________。 3. 如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。 4. 以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。 void straightsort(list r); {for(i=___________;i=n;i++) {r[0]=r[i];j=i-1; 5． while(r[0].keyr[j].key){r[j+1]=________;j--;} 6． r[j+1]=_______; } } 7. 7层有20个结点, 则整个完全二叉树的叶子结点数是__________。 8. 树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和_________________ . 9 . 所谓二叉排序树是指满足如下条件的二叉树：其中每个结点的值______于其左子树中任 10. 意结点的值，_____于其右子树中任意结点的值。 ? 四、解答下列各题（每小题10分，共40分） 1. 已知一棵二叉树的后序、中序序列如下，画出该二叉树。 　　　　后序：ＤＥＣＧＦＢＫＪＩＬＨＡ 　　　　中序：ＤＣＥＢＧＦＡＩＫＪＨＬ 　 2. .对下面的数据表, 写出采用快速排序算法排序的每一趟的结果。 　　 （24 10 19 41 7 50 81 58 200 1 12 400） ? 3. 已知一个无向图的顶点集为{a,b,c,d,e}，其邻接矩阵如下所示 (1)画出该图的图形；（2分） (2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍 历序列。（8分） 4. 已知一表为（43，21，67，9，40，78，2，41，70，90）,按表中顺序依次插入初始为 空的二叉排序树，要求：