《数据结构与算法》试卷与答案1

广州大学学年第学期考试卷课程数据结构与算法考试形式（闭卷，考试）信息学院系专业级班学号：姓名：一、填空题：（每格2分，共20分）1．对于一个以顺序实现的循环队列Q[0..m-1]，队头、队尾指针分别是f，r，其判空的条件是，判满的条件是。

2．前序序列和中序序列相同的二叉树为。

3．设根结点处在第一层，那么具有n个结点的完全二叉树，其高度为。

4．快速排序方法的最坏时间复杂度为；平均时间复杂度为。

5．给定表（55，63，44，38，75，80，31，56），用筛选法建立初始堆，则初始堆表为。

6．已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为。

7．已知8个数据元素由（35，75，40，15，20，55，95，65）按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为8．假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做次插入和探测操作。

9．设图G有n个顶点e条边，采用邻接表存储，则拓扑排序算法的时间复杂度为。

10．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用二分法查找100时，需进行次查找时才能确定不成功。

二、单项选择题（每题1分，共10分）1．（）组成数据的基本单位是A．数据项B．数据类型C．数据元素D．数据变量2．（）串的逻辑结构与（）的逻辑结构不同A．线性表B．栈C．队列D．树3．（）设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为A．3，2，5，6，4，1B．1，5，4，6，2，3C．2，4，3，5，1，6D．4，5，3，6，2，14．（）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占一个存储空间，则a85的地址为A．13B．33C．18D．405．（）二叉树在线索化后，仍不能有效求解的问题是A．前（先）序线索二叉树中求前（先）序后继；B．中序线索二叉树中求中序后继；C．中序线索二叉树中求中序前趋；D．后序线索二叉树中求后序后继。

6．（）如果结点A有3个兄弟，而且B为A的双亲，则B的度为A． 3B． 4C．5D．17．（）设有100个元素，用二分法查找时，最大比较次数是A．25B．7C．10D．18．（）快速排序在（）情况下最不利于发挥其长处A．被排序的数据量太大B．被排序的数据中含有多个相同的关键字C．被排序的数据完全无序D．被排序的数据已基本有序9．（）判定一个有向图是否存在回路，除了可以利用拓扑排序外，还可以利用A．求关键路径的方法B．求最短路径的Dijkstra方法C．深度优先遍历算法D．宽度优先遍历算法10．（）对于含有个n顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为（），利用Kruskal时间复杂度为（）A．O(log2n)B．O(n2)C．O(ne)D．o(elog2e)三、判断题（在括号内填上“√”或“╳”，每题1分，共10分，做错不倒扣）1（）具有线性序关系的集合中，若a，b是集合中的任意两个原子，则必定有a<b的关系。

2（）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。

3（）一个满二叉树同时又是一棵平衡树。

4（）任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。

5（）快速排序是排序算法中最快的一种。

6（）删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。

7（）对一个堆按层次遍历，不一定能得到一个有序序列。

8（）在索引顺序表查找方法中，对索引顺序表可以使用顺序表查找方法，也可以使用二分查找方法。

9（）双循环链表中，任一结点的前驱指针均为不空。

10（）哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。

四、（1） （6分）给出如图所示的无向图G 的邻接矩阵和邻接表两种存储结构.（2）解答下面的问题（6分）（1） 求网的最小生成树有哪些算法？各适用何种情况？为什么？ （2） 由以下的网络邻接矩阵，画出一棵最小生成树⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞341534191519111272220116127617222017（3）已知一棵非空二叉树，其按中根和后根遍历的结果分别为：中根：CGBAHEDJFI 后根：GBCHEJIFDA试将这样的二叉树构造出来。

若已知先根和后根的遍历结果，能否构造出这棵二叉树，为什么？5分（4）一项工程由P1、P2、.......P6六项子工程组成, 这些工程之间有下列关系: P1<P2，P3<P6，P4<P3，P2<P6，P4<P5，P1<P3，P5<P6，符号“<”表示“先于”关系，例如P2<P6表示P2完成后P6才能开始。

请给出工程P的三种可能的施工顺序。

（6分）（5）假定用于通信的电文由8个字母A，B，C，D，E，F，G，H组成，各字母在电文中出现的概率为5%,25%,4%,7%,9%,12%,30%,8%，试为这8个字母设计哈夫曼编码。

（7分）五、（1）读程序，分析其时间复杂度：4分m=91;n=100;while(n>0)if (m>0){ m=m-10;n=n-1;}else m=m+1;此程序的时间复杂度是。

（2）以下程序为求二叉树深度的递归算法，请填空完善之6分typedef struct node{ char data;struct node lchild, rchild;} *bitree;int depth(bitree bt) /* bt为根结点的指针*/{ int hl, hr;if (br==NULL) return ( );hl=depth (bt->lchild);hr=depth (bt->rchild);if ( )return (hr+1);}（3）已知N元整型数组a 存放N个学生的成绩，已按由大到小排序，以下算法是用折半查找方法统计成绩大于或等于x分的学生人数，请填空完善之。

6分# define N /*学生人数*/int uprx( int a[N], int x) /*函数返回大于或等于x分的学生人数*/{int head, mid, rear;do {mid=(head+rear)/2;if (x<=a[mid])else ;} while( );if (a[head]<x) return head-1;return head;}（4）简述以下算法的功能：4分void BB(LNode *s, LNode *q){ p=s;while (p->next!=q) p=p->next;p->next=s;}void AA(LNode *pa, LNode *pb){ // pa和pb分别指向单循环链表中的两个结点BB(pa,pb);BB(pb,pa);}六、给定有m个整数的递增有序数组a[1..m]和有n个整数的递减有序数组b[1..n] 。

试写出算法：将数组a和b归并为递增有序数组c[1..m+n]。

（要求：算法的时间复杂度为O(m+n)。

）（10分）试卷答案一、填空题：（每格2分，共20分）1．r=f ，(r+1) % m=f 。

2．单右枝二叉树或孤立结点。

3．⎣⎦1+。

nlog24．O(n2) ；O(nlog2n) 。

5．（31，38，44，56，75，80，55，63）或（80，75，55，56，63，44，31，38）。

6．129 。

7． 28．n(n+1)/29．O(n+e) 。

10*．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用二分法查找100时，需进行 3 次查找时才能确定不成功。

二、单项选择题（每题1分，共10分）1．（ C ）2．（ D ）3．（ B ）4．（ B ）5．（ D ）6．（ D ）7．（ B ）8．（ D ）9．（ C ）*10．（BD ）对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为（），利用Kruskal时间复杂度为（）E．O(log2n)F．O(n2)G．O(ne)H ． O(elog 2e)三、判断题 11 （ F ） 12 （ F ） 13 （ F ） 14 （ T ） 15 （ F ） 16 （ F ） 17 （ T ） 18 （ T ） 19 （ T ） 20 （ T ）四、 （1） （6分） 解：邻接矩阵为邻接表为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=1111011101111111011101111A（2）解答下面的问题（6分）解(1)：求网的最小生成树时可使用Prim算法，此算法适用于边较多的稠密图；也可使用Kruskual算法，此算法适用于边较少的稀疏图。

(2)：一棵最小生成树如图所示：（3）解：由中根和后根所确定的二叉树如图所示前根序列和后根序列不能唯一确定一棵二叉树。

因为根据中根序列，结合前根或后根序列可以把二叉树区分出左右子树来。

而前根序列和后根序列访问左右子树是顺序连在一起的，故无法区分出左右子树来，那么也就无法确定一棵二叉树了。

（4）解：可给出有向图表示各子工程间的关系如下图：P2P1 P3 P6P4P5找出3个可能的施工顺序如下：P1, P2, P3, P4, P5, P6P1, P4, P2, P3, P5, P6P4, P5, P1, P2, P3, P6（5）解：A:1001 B:11C:1000 D:0000E:101 F:001G:01 H:0001五、（1）O(n) 。

（2）typedef struct node{ char data;struct node lchild, rchild;} *bitree;int depth(bitree bt) /* bt为根结点的指针*/{ int hl, hr;if (br==NULL) return ( 0 );hl=depth (bt->lchild);hr=depth (bt->rchild);if ( hl>hr ) return(hl+1)return (hr+1);}（3）# define N /*学生人数*/int uprx( int a[N], int x) /*函数返回大于或等于x分的学生人数*/ {int head, mid, rear;do {mid=(head+rear)/2;if (x<=a[mid])head=mid+1else rear=mid-1 ;} while( head>rear );if (a[head]<x) return head-1;return head;}六、void Merge (A, B, C) //将两个有序表A和B合并成一个有序表C{int i,j,k;i=m;j=1;k=m+n;while (i>=1)&& (j<=n){if A[i]>B[j]{C[k]=A[i];i--; }else{C[k]=B[j];j++;}endk--;}while i>=1{C[k]=A[i];i--;k--; }while j<=n{C[k]=B[j];j++;k--;}}。