数据结构考试题4

1、要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（每小题2分，共15小题，共计30分）1. 以下不属于存储结构是 。A.栈B.线索树C.哈希表D.双链表2. 以下算法的时间复杂度为 。void fun(int n)int i=1;while (i<=n)i=i*3;A. O(n)B. O(n2)C. O(log2n)D. O(log3n)3. 在含有n个节点的单链表中查找第i个节点的平均时间复杂度是 。A.O(log2n)B.O(1)C.O(n2)D.O(n)4. 设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进入

2、栈S。若每个元素出栈后立即进入队列Q，且7个元素出列的顺序是b，d，c，f，e，a，g，则栈S的容量至少是 。A. 1B. 2C. 3D. 45. 已知循环队列存储在一维数组A0.n-1中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在A0处，则初始时front和rear的值分别是 。A. 0，0B. 0，n-1C. n-1，0D. n-1，n-16. 一个n×n的对称矩阵A，如果采用以列优先（即以列序为主序）的压缩方式存放到一个一维数组B中，则B的容量为 。A. n2B.C. D.7. 若一棵3次树中有a个度为1的节点，

3、b个度为2的节点，c个度为3的节点，则该树中有 个叶子节点。A.1+2b+3cB.a+2b+3cC.2b+3cD.1+b+2c8. 一个无向连通图中有16条边，所有顶点的度均小于5，度为4的顶点有3个，度为3的顶点有4个，度为2的顶点有2个，则该图有 个顶点。A.10B.11C.12D.139. 一个表示工程的AOE网中的关键路径 。A.必须是唯一的B.可以有多条C.可以没有D.以上都不对10. 用邻接矩阵表示图，对于求从某源点到其余各顶点的Dijkstra算法，在图的顶点数为10时计算时间约为10ms，则在图的顶点数为40时计算时间约为 ms。A.10B.80C.160D.20011. 设有

4、100个元素的有序表，用折半查找时，成功时最大的比较次数是 。A.25B.50C.10D.712. 在含有27个节点的二叉排序树上，查找关键字为35的节点，则依次比较的关键字有可能是 。A.28,36,18,46,35B.18,36,28,46,35C.46,28,18,36,35D.46,36,18,26,3513. 采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是 。A. 递归次数与初始数据的排列次序无关B. 每次划分后，先处理较长的分区可以减少递归次数C. 每次划分后，先处理较短的分区可以减少递归次数D. 递归次数与每次划分后得到的分区处理顺序无关14. 数据序列8,

5、9,10,4,5,6,20,1,2只能是 算法的两趟排序后的结果。A.简单选择排序B.冒泡排序C.直接插入排序D.堆排序15. 对一组数据(84,47,25,15,21)排序，数据在排序过程中的变化如下：（1）84，47，25，15，21（2）21，47，25，15，84（3）15，21，25，47，84（4）15，21，25，47，84则所采用的排序方法是 。A.冒泡排序B.快速排序C.堆排序D.直接插入排序二、问答题（共3小题，每小题10分，共计30分）1. 若已知一棵完全二叉树（所有节点值均不同）的先序、中序或后序遍历序列中的一种，能够唯一确定这棵二叉树吗？如果能，请以其中一种遍历序列来

6、说明构造该二叉树的过程。如果不能，并举一个反例予以说明。2. 对于一个带权连通无向图G，可以采用Prim算法构造出从某个顶点v出发的最小生成树，问该最小生成树是否一定包含从顶点v到其他所有顶点的最短路径。如果回答是，请予以证明；如果回答不是，请给出反例。3. 简述堆和二叉排序树的区别。三、算法设计题（共计40分）1. 用单链表来存储集合，并假设这样的单链表中的节点递增有序，设计一个尽可能高效的算法求两个集合A和B的并集C。设A、B中分别有m和n个元素，分析你设计的算法的时间和空间复杂度。（15分）2. 假设二叉树采用二叉链存储结构进行存储，假设每个节点值为单个字符且所有节点值不同，设计一个算法

7、，输出二叉树b中第k的所有节点值，并分析你所设计算法的时间复杂度。（15分）说明：以上两题求算法的时间和空间复杂度只需给出结果，不必给出详细步骤。3. 图的邻接表是一种图的链式存储结构，请给出邻接表的完整类型定义。采用你所设计的邻接表作为存储结构，设计一个算法，求出无向图G的连通分量个数。（10分）“数据结构”考试试题（A）参考答案一、单项选择题（每小题2分，共15小题，共计30分）1. A2. D3. D4. C5. B6. C7. D8. D9. B10. C11. D12. D13. D14. C15. C二、问答题（共3小题，每小题10分，共计30分）1. 答：能够。因为任一种遍历序列

8、中含有节点个数n，当n已知时就可以确定完全二叉树的形态，以给定先序遍历序列a1a2an为例，由该完全二叉树形态得到的先序遍历序列b1b2bn，则bi=ai，这样就可以唯一构造这棵二叉树。评分：回答不能够，计0分。2. 答：不是。如左图从顶点0出发的最小生成树为右图，而从顶点0到顶点的2的最短路径为0®2，而不是最小生成树中的0®1®2。 评分：回答是，计0分。回答不是，给5分，再依据反例另给05分。3. 答：以小根堆为例，堆的特点是双亲节点的关键字必然小于等于孩子节点的关键字，而两个孩子节点的关键字没有次序规定。而二叉排序树中，每个双亲节点的关键字均大于左子树节点

9、的关键字，每个双亲节点的关键字均小于右子树节点的关键字，也就是说，每个双亲节点的左、右孩子的关键字有次序关系。三、算法设计题（共计40分）1. 解：由于单链表是递增有序的，可以采用归并算法提高求并集的效率，结果并集C采用尾插法建表。对应算法如下：void Unionset(LinkList *A,LinkList *B,LinkList *&C)LinkList *pa=A->next,*pb=B->next,*s,*r;C=(LinkList *)malloc(sizeof(LinkList);/建立C的头节点r=C;/r始终指向单链表C的尾节点while (pa!=NU

10、LL && pb!=NULL)if (pa->data<pb->data)/仅复制*pa节点s=(LinkList *)malloc(sizeof(LinkList);s->data=pa->data;r->next=s; r=s;pa=pa->next;else if (pa->data>pb->data)/仅复制*pb节点s=(LinkList *)malloc(sizeof(LinkList);s->data=pb->data;r->next=s; r=s;pb=pb->next;else

11、s=(LinkList *)malloc(sizeof(LinkList);s->data=pa->data;r->next=s; r=s;pa=pa->next;pb=pb->next;while (pa!=NULL)/复制A单链表的余下节点s=(LinkList *)malloc(sizeof(LinkList);s->data=pa->data;r->next=s; r=s;pa=pa->next;while (pb!=NULL)/复制B单链表的余下节点s=(LinkList *)malloc(sizeof(LinkList);s-&

12、gt;data=pb->data;r->next=s; r=s;pb=pb->next;r->next=NULL;本算法的时间复杂度为O(m+n)，空间复杂度为O(m+n)，其中m、n分别为A、B单链表中的节点个数。评分：算法占11分，时间和空间复杂度各占2分。2. 解：采用先序序列，对应的算法如下：void Dispk(BTNode *b,int k)Dispk1(b,k,1);void Dispk1(BTNode *b,int k,int h)if (b!=NULL)if (h=k) printf(“%c “,b->data);Dispk1(b->lch

13、ild,k,h+1);Dispk1(b->rchild,k,h+1);评分：采用先序、中序、后序和层次遍历均可，算法占13分，时间复杂度占2分。3. 解：邻接表的类型定义如下：typedef char ElemType;typedef int InfoType;typedef struct ANode/边的节点结构类型int adjvex;/该边的终点位置struct ANode *nextarc;/指向下一条边的指针InfoType info;/该边的相关信息，对于带权图可存放权值 ArcNode;typedef struct Vnode/邻接表头节点的类型ElemType data;

14、/顶点信息ArcNode *firstarc;/指向第一条边 VNode;typedef VNode AdjListMAXV;/AdjList是邻接表类型typedef structAdjList adjlist;/邻接表int n,e;/分别为图中顶点数和边数 AGraph;/声明图的邻接表类型采用遍历方式求无向图G中连通分量个数。基于深度优先遍历的算法如下：int visitedMAXV=0;int Getnum(AGraph *G)/求图G的连通分量int i,n=0,visitedMAXVEX;for (i=0;i<G->n;i+)if (visitedi=0)DFS(G,i);/对图G从顶点i开始进行深度优先遍历n+;/调用DFS的次数即为连通分量数re