《华南理工大学理学院数学系数据结构试卷》由会员分享，可在线阅读，更多相关《华南理工大学理学院数学系数据结构试卷（9页珍藏版）》请在金锄头文库上搜索。
1、姓名 学号 学院 专业 座位号 ( 密 封 线 内 不 答 题 )密封线线_ _ 诚信应考,考试作弊将带来严重后果！ 华南理工大学期末考试理学院数学系数据结构试卷注意事项：1. 考前请将密封线内填写清楚； 2. 所有答案请直接答在试卷上； 3考试形式：闭卷； 4. 本试卷共五大题，满分100分，考试时间120分钟。题 号一二三四五总分得 分评卷人一、 选择题（从下列答案选项中选出一个正确答案，每小题2分，共18分)1. 长度为n的顺序存储的线性表,当在任何位置上插入一个元素的概率相等时，插入一个元素需要移动元素的平均次数为（D ）。A. n+1 C. (n-1)/2B. (n+1）/2 D.
2、n/2 2. 设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次入栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（B）。A. 2C. 5B. 3 D. 63. 下列函数中渐近时间复杂度最小的是（ B ）。A. C. B. D. 4. 以下说法不正确的是（ A ）。A. 在n个结点的无向图中,若边数多于n-1,则该图必是连通图。B. 对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目。出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。C. 任何一个无向连通图有一颗或多颗最小生成树。D. 强连通分量是有向图中的极大强连通子
3、图5. 一组记录的关键字序列为45，80，55，40，42，85，则利用快速排序并以第一个记录关键字为基准得到一次划分的结果是（C）。A. 40，42，45，55，80，85 C. 42，40，45，55，80，85B. 42，40，45，80，55，85D. 42，40，45，85，55，806. 下列广义表中，长度为1，深度为4的是（ ）A. ( ( (a,b,(),c), d ) )C. ( ( (a,b),（），(c) ) ) B. ( (a,b),(),(a,(b) )D. ( ( ( (a),b ) ) , c )7. 一颗完全二叉树上有1001个结点，则其叶子结点的个数是（ D
4、）。A. 250C. 249B. 505D. 5018. 已知关键字序列如下：54，28，16，34，73，62，95，60，26，43，按照依次插入结点的方法生成一棵二叉排序树后，查找值为62的结点所需比较的次数为 （C）。A. 5C. 3B. 4 D. 29. 在一个单链表中，若要删除*p结点的后继结点，则执行（ ）。A. p=p-next; p-next=p-next-next; free(p)B. q=p-next; p-next=q-next; free(q); C. p-next=p-next; free(p-next); D. p=p-next-next; free(p-next
5、);答案栏:1、_ 2、_ 3、_ 4、_5、_ 6、_7、_ 8、_9、_ 二、 填空题（每题2分，共20分）1、若广义表A=(a,b,(c,d),(e,(f,g)，则经过运算：headtailtailA的结果是_。2、对于A0A7有序表，采用二分查找时，成功的平均查找长度ASL是_。3、下面程序的时间复杂度是_。void fun(int n)int i=1,s=0;while(s0 /递归体f(x,n)=10、设环形队列类型SqQueue中的成员data数组中元素个数最大不超过整数MaxSize；同时q-front为环形队首下标，q-rear为环形队尾下标；则利用MaxSize, q-fr
6、ont和q-rear计算当前环形队列中元素个数的公式为： _。三、 计算题（每小题6分，共30分）1. 已知8个字符的频数如下表：字符ABCDEFGH频数231163871428试画出哈夫曼树，并计算出带权路径长度WPL.2. 按顺序读入关键字序列33, 41, 20, 24, 30, 13, 01, 67建立哈希表A0.10，其哈希函数为h(k)=(3k)%11，用线性探测法解决冲突。填充下面的哈希表，并在结点查找概率相等的情况下，计算出查找成功的平均查找长度ASLsucc和查找不成功的平均查找长度ASLunsucc。0123456789103. 将整数序列10，20，40，50，60，30
7、，5，7中的数依次插入到一棵空的平衡二叉树（AVL）中，用图形画出构造过程。并在结点查找概率相等的情况下，计算出查找成功的平均查找长度ASLsucc4. 已知带权有向图G，试写出其邻接矩阵、邻接表。 并画出各强连通分量。 5. 设目标串为s= “abbababaab”，模式t= “ababaa”，计算模式t的next函数和nextval函数（填入表中），并写出KMP模式匹配过程（采用nextval函数）。j012345模式tababaanextjnextvalj四、 算法填空题（每空2分，共12分）1. 下面是将元素x入顺序栈s的入栈算法，请填空。int Push(SqStack *&s ,
8、ElemType x ) if (s-top=MaxSize-1) return 0; s-top+ ; (A) ; return 1; 2. 下面是循环队列q的出队列算法，出队列的元素为e。请填空。int deQueue( SqQueue *&q , ElemType &e) if (q-front=q-rear) return 0; （B） ; e=q-dataq-front; return 1; 3. 设有不带表头结点的单链表（其结点类型是LinkList），下面是“正向显示以h为头指针的单链表的所有结点值”的递归算法，请填空。 void DispList ( LinkList * h
9、) if ( h=NULL) return ; else (C) ; (D) ; return; 4. 下面是按深度优先搜索遍历连通图的算法，出发点是v 。请填空。void DFS(ALGraph *G , int v ) ArcNode *p; visitedv=1; printf(%d ,v); p=G-adjlistv.firstarc; while (p!=NULL) if (visitedp-adjvex=0) (E) ; p = (F) ; 答案栏：(A) (B) (C) (D) (E) (F) 五、 算法设计题（2小题，共20分） 每题评分标准：给出类型（2分），编写算法（6分），给出关键地方的必要的注释（2分）。1、采用单链表存储线性表：1）给出单链表结点（其中data域的类型为int）的数据类型的定义。2）编写采用尾插法建立带头结点的单链表L的算法：CreateListR(&L )，开始时，表L不存在。不断循环输入整数值，若输入值不为0，则将输入值插入表尾；若输入值为0，则建表结束。函数结束时返回函数值是插入的数据结
