华南理工大学理学院数学系数据结构试卷.doc

诚信应考,考试作弊将带来严重后果！ 华南理工大学期末考试 《理学院数学系数据结构》试卷 注意事项：1. 考前请将密封线内填写清楚； 2. 所有答案请直接答在试卷上； 3．考试形式：闭卷； 4. 本试卷共五大题，满分100分， 考试时间120分钟。 题 号 一 二 三 四 五 总分 得 分 评卷人 选择题（从下列答案选项中选出一个正确答案，每小题2分，共18分) 长度为n的顺序存储的线性表,当在任何位置上插入一个元素的概率相等时，插入一个元素需要移动元素的平均次数为（ D ）。 n+1 C. (n-1)/2 (n+1）/2 D. n/2 设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次入栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（ B ）。 2 C. 5 3 D. 6 下列函数中渐近时间复杂度最小的是（ B ）。 C. D. 以下说法不正确的是（ A ）。 在n个结点的无向图中,若边数多于n-1,则该图必是连通图。 对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目。出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。 任何一个无向连通图有一颗或多颗最小生成树。 强连通分量是有向图中的极大强连通子图 一组记录的关键字序列为{45，80，55，40，42，85}，则利用快速排序并以第一个记录关键字为基准得到一次划分的结果是（ C ）。 40，42，45，55，80，85 C. 42，40，45，55，80，85 42，40，45，80，55，85 D. 42，40，45，85，55，80 下列广义表中，长度为1，深度为4的是（ ） ( ( (a,b,(),c), d ) ) C. ( ( (a,b),（），(c) ) ) ( (a,b),(()),(a,(b)) ) D. ( ( ( (a),b ) ) , c ) 一颗完全二叉树上有1001个结点，则其叶子结点的个数是（ D ）。 250 C. 249 505 D. 501 已知关键字序列如下：{54，28，16，34，73，62，95，60，26，43}，按照依次插入结点的方法生成一棵二叉排序树后，查找值为62的结点所需比较的次数为 （C ）。 5 C. 3 4 D. 2 在一个单链表中，若要删除*p结点的后继结点，则执行（ ）。 p=p-next; p-next=p-next-next; free(p) q=p-next; p-next=q-next; free(q); p-next=p-next; free(p-next); p=p-next-next; free(p-next); 答案栏: 1、_____ 2、_____ 3、_____ 4、_____5、_____ 6、_____7、____ 8、_____9、_____ 填空题（每题2分，共20分） 1、若广义表A=(a,b,(c,d),(e,(f,g)))，则经过运算：head[tail[tail[A]]]的结果是______________________________。 2、、对于A[0]~A[7]有序表， 采用二分查找时，成功的平均查找长度ASL是______________________________。 3、下面程序的时间复杂度是______________________________。 void fun(int n) { int i=1,s=0; while(s=n*n*n) { s=s+i; i++; } } 4、设待排序的表有6个记录，其关键字分别为{46，89，56，48，40，84}，则利用堆排序（建立大根堆）的方法建立的初始堆为： ______________________________。 5、某二叉树的先序遍历序列是bcehdigf，中序遍历序列是ehcbidfg，则该二叉树的树形表示为： _______________________________。 6、图1为带权无向图，则从顶点4出发采用普里姆(Prim)算法生成的最小生成树为： _______________________________。 7、若将图2的二叉树转换为森林，则结果为： _________________________________________。 8、图3所示的二叉树的中序遍历序列