《数据结构》期末考试试卷试题及答案

《数据结构》期末考试试卷试题及答案一、简答题（每题5分，共20分）1、一棵有n个结点的k义树采用k又链表存储，空链域的总数目是多少？写出求解过程。2、在图的遍历中，设置访问标志数组的作用是什么？3、折半查找的前提条件是什么？4、分析冒泡排序的最好性能和最坏性能（性能即关键字比拟次数和移动元素的次数）。二、单项选择题（每题1分，共10分）1、栈和队列的共同特点是（）oA）只允许在端点处插入和删除元素B）都是先进后出C）都是先进先出D）没有共同点2、100个结点的完全二叉树采用顺序存储，从1开始按层次编号，那么编号最小的叶子结点的编号应该是（A）100B）49C）50D）513、在顺序存储的线性表上R⑶上，从前向后进行顺序查找。假设查找第一个元素的概率是1/2,查找笫二个元素的概率是1/3,查找第三个元素的概率是1/6o那么查找成功的平均查找长度为（）。A）7/3B）2C）3D）5/34、在一个有n个顶点的有向图中，假设所有顶点的出度之和为s,那么所有顶点的入度之和为（）A）n-sB）nC）sD）s-15、设某二叉树中度数为。的结点数为NO,度数为1的结点数为NI,度数为2的结点数为N2,那么以下等式成立的是（）oA）NO=N1+1B）N0=NI+N2C）NO=N2+1D）NO=2N1+I6、设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。A）5B）6C）7D）87、单链表中的指针p所指的结点不是链尾结点，假设在p结点后插入s结点，应执行（）。A）s->next=p;p->next=s;B）p->next=s;s->next=p;C）s->next=p->next;p=s;D）s->next=p->next;p->next=s;8、设用邻接矩阵A表示有向图G的存储结构，那么有向图G中顶点i的入度为（）。A）第i行非0元素的个数之和B）第i列非0元素的个数之和C）第i行。元素的个数之和D）第i列0元素的个数之和9、排序时扫描待排序记录序列，顺次比拟相邻的两个元素的大小，逆序时就交换位置。这是（）排序方法的基本思想。A）堆排序B）直接插入排序C）快速排序D）冒泡排序10、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，那么用以下（）方法可以到达此目的。A）快速排序B）堆排序C）归并排序D）基数排序三、填空题（每空2分，共20分）1、下面算法的时间复杂度是i=l；while（i<=n）i=i*2;2、设线索二叉树中，判断p所指向的结点为叶子结点的条件是2、对任意一棵有n个结点的树，这n个结点的度之和为。3、Prim算法适合求解连通网的最小生成树。（填稀疏或稠密）4、关键路径是从源点到汇点的路径。5、深度为k的二叉树中最少有个结点，最多有个结点。6、设有向图G中有向边的集合£=｛<1,2>,<2,3>,<1,4>,<4,2>,<4,3>｝,那么该图的一种拓扑序列为7、根据初始关键字序列（25,22,11,38,10）建立的二叉排序树的高度为。8、用某种排序方法对关键字序列（25,84,21,47,15,27,68,35,20）进行排序时，序列的变化情况如下：TOC\o"1-5"\h\z20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84那么所采用的排序方法是。四、构造题（共30分）1、（8分）设一棵树T中边的集合为｛（A,B）,（A,C）,（A,D）,（B,E）,（C,F）,（C,G）｝,要求：①用孩子兄弟表示法（二叉链表）表示出该树的存储结构；（2分）②将该树转化成对应的二叉树。（2分）③写出该树的先序和后序遍历序列。（4分）2、（8分）某图的邻接表存储结构为图1所示：①画出从VI出发的深度优先生成树；②给出该图的邻接矩阵存储结构。图1第四题第2小题图3、（8分）一个线性序列（36,13,40,63,22,6）,假定采用散列函数Hash（key）=key%7来计算散列地址，将其散列存储在A[0~9]中，采用线性探测再散列解决冲突。构造哈希表,并计算等概率情况下的查找成功和不成功的平均查找长度。4、（6分）欲对关键字｛36,15,13,40,63,22,6｝从小到大排序，假设采用堆排序,写出将关键字序列建初堆过程。五、算法设计题（每题10分，共20分）注：只要求给出描述算法的子函数，不需要编写完整的实现程序。1、编写折半查找算法。（递归、非递归均可）2、二叉树采用二叉链表存放，该结点结构为：LChilddataRChildlevel编写算法，将二叉树中每个结点所在的层次值置入相应的level域。《数据结构》期末考试试卷2参考答案一、简答题1、n个结点的k叉树采用k叉链表存储，链域总数为k*n,又：n=B+l,B为分支总数即非空链域总数，B=n-1,所以空链域总数为：（kJ）*n+l02、访问标志数组的作用是：保证图中的每个顶点都被访问到，且仅访问一次。3、折半杳找的前提条件是1）列表元素顺序存储；2）列表元素按关键字有序存储;4、冒泡排序最好情况：移动元素次数为0,关键字比拟次数为：n-1次；冒泡排序最坏情况：移动元素次数为3n*（n-l）/2,关键字比拟次数为n*（n-l）/2o二、选择题l.A2.D3.D4.C5.C6.A7.D8.B9.D10.B三、填空题1、0(Iog2n)2、p->ltag==l&&p->rtag==15、最少k,最多2k-l6、1,4,2,37、高度为43、n-14、稠密8、快速排序四、构造题1.1）该树的孩子兄弟表示法为：（2分）2）转化的二叉树为：（2分）3）先序遍历序列为：ABECFGD（2分）后序遍历序列为:EBFGCDA（2分）2.1）此为有向图的邻接表表示法，该图为：2）深度优先搜索得到的遍历序列为:VI,V4,V5,V6,V2,V7,V3;深度优先生成树为：

3）其邻接矩阵表示法为：顶点数组：邻接矩阵:VIV2V3V4V5V6V700011010001000000001100000000100010000000000111003、1）构造的哈希表为：（4分）地址地址元素比拟次数地址元素比拟次数0地址元素比拟次数06313612221401361122)（2（2分）查找成功时的ASL=（2分）查找成功时的ASL=（2分）查找成功时的ASL=(2分)查找不成功时的ASL=(4+3+2+1+1+4+3)/7=18/74、据题意，欲得到递增有序，需要建大根堆（1分）。建初堆过程如下:五.算法设计题1、折半查找算法：1)非递归算法：intBinSearch(RecordListLzKeyTypek){low=l;high=L.length;while(low<=high){mid=(low+high)/2;if(L->r[mid].key==k)returnmid;elseif(k<L->r[mid].key)high=mid-l;elselow=mid+l;}return0;}2)递归算法intBinSearch(RecordListL,KeyTypek,intlow,inthigh)〃首次调用，low=l,high=L.length;{if(low<=high){mid=(low+high)/2;if(L->r[mid].key==k)returnmid;elseif(k<L->r[mid].key)return(BinSearch(L,k,low,mid-1));elsereturn(BinSearch(Lzkzmid+l,high));))2、二叉树中每个结点的level域置值算法：利用二叉树的先序遍历给每个结点的level域置