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

《数据结构》期末考试试卷试题及答案一、简答题（每题5分，共20分）1、一棵有n个结点的k叉树采用k叉链表存储，空链域的总数目是多少？写出求解过程。2、在图的遍历中，设置访问标志数组的作用是什么？3、折半查找的前提条件是什么？4、分析冒泡排序的最好性能和最坏性能（性能即关键字比拟次数和移动元素的次数）。二、单项选择题（每题1分，共10分）1、栈和队列的共同特点是（）oA）只允许在端点处插入和删除元素B）都是先进后出C）都是先进先出D）没有共同点2、100个结点的完全二叉树采用顺序存储，从工开始按层次编号，那么编号最小的叶子结点的编号应该是（）oA）100B）49C）50D）513、在顺序存储的线性表上R⑶上，从前向后进行顺序查找。假设查找第一个元素的概率是1/2,查找第二个元素的概率是1/3,查找第三个元素的概率是1/6。那么查找成功的平均查找长度为（）oA）7/3B）2C）3D）5/34、在一个有n个顶点的有向图中，假设所有顶点的出度之和为s,那么所有顶点的入度之和为（）A）n-sB）nC）sD）s-15、设某二叉树中度数为。的结点数为NO,度数为1的结点数为NL度数为2的结点数为N2,那么以下等式成立的是（）oA）NO=N1+1B）N0=NI+N2C）N0=N2+lD）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的入度为（）oA）第i行非0元素的个数之和B）第i列非0元素的个数之和C）第i行。元素的个数之和D）第i列。元素的个数之和9、排序时扫描待排序记录序列，顺次比拟相邻的两个元素的大小，逆序时就交换位置。这是（）排序方法的基本思想。A）堆排序B）直接插入排序C）快速排序D）冒泡排序10、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，那么用以下（）方法可以到达此目的。A）快速排序B）堆排序C）归并排序D）基数排序三、填空题（每空2分，共20分）1、下面算法的时间复杂度是。i=l；while（i<=n）i=i*2;BiTNode*Parent(BiTreebt,ElemTypee)〃找e结点的双亲BiTNode*p=NULL;if(bt==NULL)returnNULL;if(bt->LChild->data==e11bt->RChild->data==e)〃访问根returnbt;p=Parent(bt->LChild,e);〃在左子树上找if(!p)p=parent(bt->RChild,e)〃在右子树上找returnp;)2、设线索二叉树中，判断p所指向的结点为叶子结点的条件是2、对任意一棵有n个结点的树，这n个结点的度之和为。3、Prim算法适合求解连通网的最小生成树。（填稀疏或稠密）4、关键路径是从源点到汇点的路径。5、深度为k的二叉树中最少有个结点，最多有个结点。6、设有向图G中有向边的集合E=｛<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+LB为分支总数即非空

链域总数，B二n.l,所以空链域总数为：（k-1）*n+l。2、访问标志数组的作用是：保证图中的每个顶点都被访问到，且仅访问一次。3、折半查找的前提条件是1）列表元素顺序存储；2）列表元素按关键字有序存储;4、冒泡排序最好情况：移动元素次数为0,关键字比拟次数为：n；次；冒泡排序最坏情况：移动元素次数为3n*（n-l）/2,关键字比拟次数为n*（n-l）/2o二、选择题二、选择题l.A2.D二、选择题l.A2.D3.D4,C二、选择题l.A2.D3.D4,C5.C6.A7,D8.B9.D10.B三、填空题22、p->ltag==l&&p->rtag==16、1,4,2,37、高度为42、p->ltag==l&&p->rtag==16、1,4,2,37、高度为432、p->ltag==l&&p->rtag==16、1,4,2,37、高度为43、n-14、稠密8、快速排序四、构造题1.1）该树的孩子兄弟表示法为：（2分）2）转化的二叉树为：（2分）3）先序遍历序列为：ABECFGD（2分）后序遍历序列为:EBFGCDA（2分）1）此为有向图的邻接表表示法，该图为:2）深度优先搜索得到的遍历序列为：VI,V4,V5,V6,V2,V7,V3;深度优先生成树为：

3）其邻接矩阵表示法为:顶点数组：邻接矩阵:VIV2V3V4V5V6V700011010001000000001100000000100010000000000111003、1）构造的哈希表为：（4分）地址0元素地址0元素63比拟次数1233622112401361122)（2（2分）查找成功时的ASL=（2分）查找成功时的ASL=（2分）查找成功时的ASL=(2分)查找不成功时的ASL=(4+3+2+1+1+4+3)/7=18/74、据题意，欲得到递增有序，需要建大根堆（1分）。建初堆过程如下:五.算法设计题1、折半查找算法：1)非递归算法：intBinSearch(RecordListL,KeyTypek){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,kjow,mid-1));elsereturn(BinSearch(L,k,mid+l,high));})2、二叉树中每个结点的level域置值算法：利用二叉树的先序遍历给每个结点的level域置值。voidSetLevel(BiTreebt,intlayer)〃首次调用时，bt参数为二叉树的根指针，layer参数值为1。{if(bt){bt->level=layer;SetLevel(bt->lchild,layer+1)；SetLevel(bt-)rchild,layer+1)；})注：此题也可以借助层次遍历完成。《数据结构》期末考试试卷及答案一、简答题(每题5分，共20分)1、具有n个结点的k叉树，假设采用k叉链表存储，那么空链域有多少个？(要求写出求解步骤)。2、分析二叉排序树的性能(最好、最坏和平均查找性能)。3、希尔排序基本思想。4、图遍历中，设置访问标志数组visited口的作用。二、单项选择题(每题1分，共10分)1、在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是()B)-2~2C)l~2D)0~l2、在单链表中，以下说法正确的选项是()A)单链表中头结点是必不可少的；B)单链表中头指针是必不可少的；C)在单链表中可以实现随机存取；D)单链表的存储密度小于顺序表3、假设以数组A[M]存放循环队列的元素，其头尾指示器分别为front和rear,那么当前队列中的元素个数为()oA)rear-front+1B)(rear-front+l)%MC)(front-rear+M)%MD)(rear-front+M)%M4、广义表L=((a,b,c),(d©f)),运用以下()运算可以得到结果:eoA)head(tail(L))B)tail(head(L))C)head(tail(head(tail(L))))D)head(tail(tail(head(L))))5、线索二叉树中，某结点p是叶子结点,以下()表达式的值为真。A)p->lchild==NULLB)p->ltag==l&&p->rtag==1C)p->ltag==0D)p->lchild==NULL&&p->rchild==NULL6、一个具有567个结点的完全二叉树的高度为()A)9B)10C)11D)127、具有n个顶点的强连通图，至少有()条边A)n-1B)nC)n(n-l)D)n(n-l)/28、在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为()A)eB)2eC)n2-eD)n2-2e9、对关键字序列(20,15,14,18,36,40,10,21)进行快速排序，以第一个关键字为基准得到的一趟划分后的结果是()。A）（10,15,14,18,20,36,40,21）B）（10,15,14,18,20,40,36,21）C）（10,15,14,20,18,40,36,21）D）（15,10,14,18,20,36,40,21）10、以下四种排序方法中，不稳定的方法是（）oA）冒泡排序B）直接插入排序C）归并排序D）快速排序三、填空题（每空2分，共20分）1、一个算法中，基本操作的语句频度为（n3+n210g2n+14n）/n2,该算法的时间复杂度为（）2、65个结点的完全二叉树,按层次,从左到右编号，那么最后一个非叶子结点的编号为（）oTOC\o"1-5"\h\z3、折半查找的两个前提条件分别是（）和（）4、一个有序表为｛4,8,12,16,20,24,28｝,采用折半查找法查找值为24时需要比拟（）次。5、有向图的邻接表表示法中，第i条链上边表结点的个数为该顶点的（）。6、一个带头结点的链栈，其头指针为top；指针s指向一个新结点，要将结点s进栈,那么进栈的语句应为：（）和（）o7、有一种排序算法，其时间复杂度为。（n2）,关键字比拟次数与待排序记录的初始排列顺序无关且排序不稳定，那么该排序算法是（）8、对二叉排序树进行中序遍历，会得到一个（）序列。四、构造题（每题6分，共30分）1、假定用于通信的某电文仅由8个字母构成，各字母在电文中出现的频率分别为（12,5,3,7,14,21,9,15）o请完成：1）构造哈夫曼树；2）为这8个字母设计不等长的Huffman编码，并计算WPL。2、一个图的顶点为A、B、C、D,其邻接矩阵的下三角元素全为0（包括主对角线元素），其他元素均为1。请画出该图，并给出其邻接表。3、用普利姆算法从顶点A出发，构造图1所示连通网的最小生成树（写出过程）。图14、一个线性序列｛38,25,74,63,52,48）,假定采用散列函数Hash（key）=key%7来计算散列地址，将其散列存储在A[0~9]中，采用线性探测再散列解决冲突。构造哈希表，并计算等概率情况下的查找成功和不成功的平均查找长度。5、对序列｛57,40,38,11,13,34,48,75,6,19,9,7｝,采用堆排序算法进行递减排序，请构造相应的初始堆即建初堆（只写初堆结果即可）。五、算法设计题（每题10分共20分）注：算法设计题只要求给出描述算法的子函数，不需要编写完整的实现程序。1、在一个带头结点的循环链队列中只有尾指针rear,请给出这种队列的入队和出队操作的实现过程。队列的定义如下：typedefstructNode（QueueElementTypedata;/*数据域*/structNode*next;/*指针域*/

}LinkQueueNode,*LinkQueue;2、假设二叉树上的结点值各不相同，设计一个在二叉树中求值为e的结点的双亲结点。函数名已给出，如下：/*假设e有双亲，那么返回双亲结点指针；假设e是根结点或二叉树中无e结点，那么返回NULL*/BiTNode*Parent(BiTreebt,ElemTypee)《数据结构》期末考试试卷1参考答案—k、简答题(5分*4=20分)1、n个结点的k叉树，共nk个链域；分支树为n-1个，即n-1个非链域，那么空链域有nk-n+1个2、当二叉排序树的左右子树比拟均衡时，查找性能最好，此时时间复杂度为O(nlogn)；当二叉排序树每个结点为单分支时,查找性能最差，与顺序查找类似,此时时间复杂度为0(n2)。但二叉排序的平均查找时间复杂度为O(nlogn)。3、按某个间隔，将待排序记录序列分割成假设干个子序列，分别进行直接插入排序；继续缩小间隔，对每个子序列进行直接插入排序；最后再对全部记录进行一次直接插入排序。4、