《数据结构》 期末试题及答案 共3套

《数据结构》期末考试试卷1一，简答题(每题5分，共20分)1、具有n个结点的k又树，若采用k又链表存储，则空链域有多少个？(要求写出求解步骤)。2、分析二叉排序树的性能(最好、最坏和平均查找性能)。3、希尔排序基本思想。4、图遍历中，设置访问标志数组visited]]的作用。二、单项选择题(每题1分，共10分)1、在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是()A)-l~lB)-2~2C)1-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,e,f)),运用下列()运算可以得到结果:eoA)head(tail(L))B)tail(head(L))C)head(tai1(head(tai1(L))))D)head(tai1(tai1(head(L))))5、线索二叉树中，某结点p是叶子结点，下列()表达式的值为真。A)p->lchild==NULLB)p->ltag==1&&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个顶点和。条边的无向图的邻接矩阵中，零元素的个数为()A)eB)2eC)n2-eD)n2-2e

《数据结构》期末考试试卷2参考答案一、简答题1、n个结点的k叉树采用k叉链表存储，链域总数为k*n,又：『B+1.B为分支总数即非空链域总数,B=n-1,所以空链域总数为:（k-l）*n+U2、访问标志数组的作用是：保证图中的每个顶点都被访问到，且仅访问一次。3、折半查找的前提条件是1）列表元素顺序存储：2）列表元素按关键字有序存储：4、冒泡排序最好情况：移动元素次数为0,关键字比较次数为：n-I次；冒泡排序最坏情况：移动元素次数为3n*（n-l）/2,关键字比较次数为n*（n-l）/2o二、选择题二、选择题LA2.D3.D二、选择题LA2.D3.D二、选择题LA2.D3.D4.C5.C二、选择题LA2.D3.D4.C5.C6.A7.D8.B9.DI0.B三、填空题三、填空题三、填空题1、O(log2n三、填空题1、O(log2n)5、最少k,最多2k-l2、p->itag==1&&p->rtag==13、n-14、稠密6、1.4237、高度为48、快速排序四、构造题1.1）该树的孩子兄弟表示法为：（2分）2）转化的二叉树为：（2分）3）先序遍历序列为：ABECFGD（2分）后序遍历序列为:EBFGCDA（2分）2.I）此为有向图的邻接表表示法，该图为:2）深度优先搜索得到的遍历序列为：VI,V4,V5,V6,V2,V7,V3;深度优先生成树为：3）其邻接矩阵表示法为：顶点数组：邻接矩阵:1VI00011012V200010003V300000114V400000005V501000106V600000007V700111003、1）构造的哈希表为：（4分）2)地址0I23456789元素63362240136比较次数112112(2分)查找成功时的ASL=(l+l+2+l+l+2)/6=8/6or4/3(2分)查找不成功时的ASL=(4+3+24-1+1+4+3)/7=18/74、据题意，欲得到递增有序，需要建大根堆（I分）。建初堆过程如下:初始状态（从13开始调整（1初始状态（从13开始调整（1分））初始状态（从13开始调整（1分））初始状态（从13开始调整（1分））（调整完毕，从15开始调整（1初始状态（从13开始调整（1分））（调整完毕，从15开始调整（1分））（调整完毕，从36开始调整（1分））（调整完毕，从36开始调整（1分））（调整完毕，从36开始调整（1分））（调整完毕，建好初堆（1分））（调整完毕，从36开始调整（1分））（调整完毕，建好初堆（1分））1)非递归算法：intBinSearch(RecordLislL,KeyTypek){low=1;high=L.length;while(low<=high){mid=(Iow+high)/2;if(L->r[midJ.key==k)returnmid;elseif(k<L->r[mid].key)high=mid-l;elselow=mid+l；)return0;)2)递归算法intBinSearch(RecordListL,KeyTypek,intlow,inthigh)//首次调用，low=1,high=L.length;{if(low<=high){mid=(low+high)/2;if(L->r[mid].kcy==k)returnmid;elseif(k<L->r[mid].key)retum(BinSearch(L,k,low,mid-l));elsereturn(BinSearch(L,k,mid+l,high));2、二叉树中每个结点的level域置值算法：利用二叉树的先序遍历给每个结点的level域置值。voidSctLcvcl（BiTrecbt,intlayer）〃首次调用时，bt参数为二叉树的根指针，layer参数值为1。{if（bt）{bt->lcvcl=laycr;SetLevel(bt->lchild»layer+1)；SctLcvel(bt-)rchild,laycr+1)；}注：此题也可以借助层次遍历完成。数据结构试卷3.（判断题）在有n个叶子结点的哈夫曼树中,其结点总数2n+lo（）（本题2.0分）rA、正确⑤B、错误学生答案：B标准答案：B解析：得分：2.（判断题）链表由头指针唯一确定。（）（本题2.0分）'•A、正确CB、错误学生答案：A标准答案：A解析：得分：2.（判断题）完全二叉树的叶子结点只能出现在最后一层上。（）（本题2.0分）rA、正确出B、错误学生答案：B标准答案：B解析：得分：2.（判断题）由树转化来的二叉树一定没有右子树。（）（本题2.0分）⑸A、正确°B、错误学生答案：A标准答案：A解析:得分：2.（判断题）折半查找要求数据必须有序,且采用顺序存储结构。（）（本题2.0分）④A、正确rB、错误学生答案：A标准答案：A解析：得分：2.（判断题）有回路的图不能进行拓朴排序。（）（本题2.0分）⑤A、正确CB、错误学生答案：A标准答案：A解析：得分：2.（判断题）在顺序存储的线性表中,逻辑上相邻的两个数据元素在物理位置上并不一定紧邻。（）（本题2.0分）CA、正确⑤B、错误学生答案：B标准答案：B解析：得分：2.（判断题）链式存储的线性表可以随机存取。（）（本题2.0分）CA、正确④B、错误学生答案：B标准答案：B解析：得分：2.（判断题）散列表的查找效率主要取决于建表时所选取的散列函数和处理冲突的方法。（）（本题2.0分）eA、正确rB、错误学生答案：A标准答案：A解析：得分：2.（判断题）对于同一组记录,生成的二叉排序树的形态与记录的输入次序无关。（）（本题2.0分）A、正确⑤B、错误学生答案：B标准答案：B解析：得分：2.（单选题）设有一个二维数组A[10][15],数组按行存放,假设A[0][0]存放位置在644,每个元素占一个空间,则A[4][5]在（）位置。（本题2.0分）rA、672CB、626⑤C、709rD、724学生答案：C标准答案：C解析：得分：212.（单选题）顺序查找方法适用于存储结构为（）的线性表。（本题2.0分）rA、压缩存储B、散列存储C、顺序存储1D、以上都不是学生答案：C标准答案：C解析：得分：213.(单选题)下面程序段的时间复杂度是()。for(i=0;i<n;i++)for(j=0;j<n;j++)(本题2.0分)CA、0(n)CB、O(n+n+l)CC、O(n+n)⑤D、O(n*n)学生答案：D标准答案：D解析：得分：214.(单选题)具有线性结构的数据结构是()(本题2.0分)rA、树B、图9、对关键字序列（20,15,14,18,36,40,10,21）进行快速排序，以第一个关键字为基准得到的一趟划分后的结果是（）oA）（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）1（）、下列四种排序方法中，不稳定的方法是（）。A）冒泡排序B）直接插入排序C）归并排序D）快速排序三、填空题（每空2分，共20分）1、一个算法中，基本操作的语句频度为（r+n210g2n+142//,该算法的时间复杂度为（）2、65个结点的完全二叉树，按层次，从左到右编号，则最后一个非叶子结点的编号为（）oTOC\o"1-5"\h\z3、折半查找的两个前提条件分别是（）和（）4、一个有序表为{4,8,12,16,20,24,28},采用折半查找法查找值为24时需要比较（）次。5、有向图的邻接表表示法中，第i条链上边表结点的个数为该顶点的（）o6、已知一个带头结点的链栈，其头指针为top；指针s指向一个新结点，要将结点S进栈，则进栈的语句应为：（）和（）o7、有一种排序算法，其时间复杂度为O（/）,关键字比较次数与待排序记录的初始排列顺序无关且排序不稳定，则该排序算法是（）8、对二叉排序树进行中序遍历，会得到一个（）序列。四、构造题（每题6分，共30分）1、假定用于通信的某电文仅由8个字母构成，各字母在电文中出现的频率分别为（12,5,3,7,14,21,9,15）。请完成：1）构造哈夫曼树；2）为这8个字母设计不等长的Huffman编码，并计算WPLo2、己知一个图的顶点为A、B、C、D,其邻接矩阵的下三角元素全为0（包括主对角线元素），其他元素均为1。请画出该图，并给出其邻接表。'•C、栈和队列rD、以上都不对学生答案：C标准答案：C解析：得分：2.（单选题）长度为n的线性表,实施顺序查找,在查找不成功时,与关键字的比较次数为（）。（本题2.0分）rA、1⑸B、n+1Cc、n-1「D、n学生答案：B标准答案：B解析：得分：2.（单选题）设一个栈的输入序列为12345,则借助一个栈所得到的输出序列不可能是（）。（本题2.0分）rA、54321B、45321C、43512'D、12345学生答案：C标准答案：C解析：得分：2.（单选题）一个队列的入队序列是A,B,C,D,则队列的输出序列是（）。（本题2.0分）rA、D,C,B,ArB、A,BCD⑤C、A,D,C,BCD、CBD,A学生答案：C标准答案：C解析：得分：218.（单选题）将一棵有50个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点编号为1,则编号为17的结点的左孩子的编号为（）（本题2.0分）rA、4849C、34CD、35学生答案：C标准答案：C解析：得分：219.（单选题）非空的循环单链表head的尾指针p满足（）（本题2.0分）「A、p->next==NULLrB、p==NULLp->next==headp==head学生答案：C标准答案：C解析：得分：2.（单选题）若线性表最常用的操作是存取第i个元素及其前趋的值,则采用（）存储方式节省时间。（本题2.0分）rA、单链表B、双链表'C、单循环链表°D、期表学生答案：D标准答案：D解析：得分：2.（填空题）有一个不含头结点的单链表,头指针为head,则判断其是否为空的条件为—o（本题2.0分）我的答案：head.next二二head标准答案：Head==NULL解析：得分：点评：.（填空题）在顺序表（即顺序存储的线性表）中删除一个元素,需要平均移动—的元素。（本题2.0分）我的答案：1标准答案：n/2或一半解析:得分：点评：.（填空题）一组记录的关键字为（46,79,56,38,40,84）,利用选择排序的方法，第一趟排序结果为（本题2.0分）我的答案：40,38,46,56,79,84标准答案：38,79,56,46,40,84解析：得分：点评：.（填空题）对于关键字序列（12,13,11,18,60,15,7,18,,100）,用筛选法建堆，必须从键值为—的结点开始。（本题2.0分）我的答案：60标准答案：60解析：得分：点评:25.（填空题）我们学过的构造散列函数的方法有数字分析法、一分段叠加法、—、伪随机数法。（本题4.0分）我的答案：（1）平方取中法（2）直接定址法标准答案：平方取中法除留余数法解析：得分：点评：.（填空题）在使用Kruskal算法构造连通网络的最小生成树时,只有当一条候选边的两个端点不在同一个—上,才会被加入到生成树中。（本题2.0分）我的答案：连通分量标准答案：同一个连通分量或同一个集合解析：得分：点评：.（填空题）栈和队列是运算—的线性表。（本题2.0分）我的答案：受限标准答案：受限的解析：得分：点评：.（填空题）设有向图的邻接矩阵为A,如果图中不存在弧＜Vi,Vj〉,则A[i,j]的值为（本题2.0分）我的答案：1标准答案：0解析：得分：点评:29.（填空题）n个顶点的连通无向图的生成树含有一条边。（本题2.0分）我的答案：n-1标准答案：n-1解析：得分：点评：.（简答题）给定关键字序列｛32,13,49,55,22,38,21）,散列函数为H（k）=k%7,散列表的地址从0到6,用线性探测法解决冲突,建立散列表ht。（本题20.0分）我的答案：k:32134955223821k%7：46061301地址：01234526关键字：49552238322113标准答案：解析：・・・0・・・1・,・2・・••3•・4一・5・・・6・・・・49|552238322113得分：点评：.（简答题）给定叶子结点权值：（3,35,13,15,20,5,9）,构造哈夫曼树，并计算其带权路径长度。（本题20.0分）我的答案：树带权路径长度254得分：点评：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结点，则返回NULL*/BiTNode*Parent（BiTreebt,ElemTypee）《数据结构》期末考试

试卷1参考答案一、简答题(5分*4=20分)1、n个结点的k叉树，共nk个链域；分支树为n-1个，即n-1个非链域，则空链域有nk-n+1个2、当二叉排序树的左右子树比较均衡时,查找性能最好，此时时间复杂度为O(nlogn)；当二叉排序树每个结点为单分支时，查找性能最差，与顺序查找类似，此时时间复杂度为0(/)。但二叉排序的平均查找时间复杂度为O(nlogn)。3、按某个间隔，将待排序记录序列分割成若干个子序列，分别进行直接插入排序：继续缩小间隔，对每个子序列进行直接插入排序；最后再对全部记录进行一次直接插入排序。4、防止重复访问；防止遗漏访问。二、选择题(I分*10=10分)(1-5)ADDC(6-10)BBDB三、填空题(2分*10=20分)1、O(n)或O(n+logn)3、元素有序顺序存储5、出度7、简单选择排序2、324、26、s->next=top->next;top->next=s;8、递增或非递减或从小到大四、构造题(6分*6=3。分)1、(该哈夫曼树有多种形态)WPL=21*2+(14+15+9+12+7)*3+(5+3)*4=2454、构造的哈希表为：6338257452480123456789①①①②④②ASLsucc=(1+1+1+2+2+4)/6=11/ASLuncuss=(2+1+1+6=5+4+3)/7=5、五、算法题(10分*2=20分)1、intEntcrQucuc(LinkQucucrcar,ElcmTyp({LinkQueueNode*newNocle;newNode=(LinkQueue)malloc(sizeof(Liiif(!newNode)returnfalse;newNode->data=x;newNode->next=rear->next;rear->next=newNode;rear=newNode;622/7Jx)〃进队nkQueueNode));returntrue;intDeleteQueue(LinkQueuerear,ElemType*x)〃出队(if(rcar->ncxt==rcar)returnfalse;p=rear->next->next;rear->next->next=p->nexl;*x=p->data;free(p);returntrue;IBiTNode*Parent(BiTreebt,ElemTypee)//找e结点的双亲(BiTNode*p=NULL;if(bt==NULL)returnNULL;if(bt->LChild->data==e||bt->RChild->data==e)〃访问根returnbt;p=Parenl(bl->LChild,e);〃在左子树上找if(!p)p=parent(bt->RChild,e)〃在右子树上找returnp;《数据结构》期末考试试卷2

一、简答题（每题5分，共20分）1、一棵有n个结点的k叉树采用k叉链表存储，空链域的总数目是多少？写出求解过程。2、在图的遍历中，设置访问标志数组的作用是什么？3、折半查找的前提条件是什么？4、分析冒泡排序的最好性能和最坏性能（性能即关键字比较次数和移动元素的次数）。二、单项选择题（每题1分，共10分）TOC\o"1-5"\h\z1、栈和队列的共同特点是（）oA）只允许在端点处插入和删除元素B）都是先进后出C）都是先进先出D）没有共同点100个结点的完全二叉树采用顺序存储，从1开始按层次编号，则编号最小的叶子结点的编号应该是（）oA）100B）49C）5（）D）513、在顺序存储的线性表上R[3]上，从前向后进行顺序查找。若查找第一个元素的概率是1/2,查找第二个元素的概率是1/3,查找第三个元素的概率是1/6«则查找成功的平均查找长度为（）。A）7/3B）2C）3D）5/34、在一个有n个顶点的有向图中，若所有顶点的出度之和为s,则所有顶点的入度之和为（）A）n-sB）nC）sD）s-15、设某二叉树中度数为。的结点数为No,度数为1的结点数为Ni,度数为2的结点数为N2,则下列等式成立的是（）。A）N0=Ni+lB）No=Ni+N2C）No=N2+1D）N0=2Ni+16、设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。A）5B）6C）7D）87、己知单链表中的指针p所指的结点不是链尾结点，若在p结点后插入s结点，应执行（）oA)s->next=pA)s->next=p;p->next=s;C)s->next=p->next;p=s;A)s->next=p;p->next=s;C)s->next=p->next;p=s;B)p->next=s;s->next=p;D)s->next=p->next;p->next=s;8、设用邻接矩阵A表示有向图A)s->next=p;p->next=s;C)s->next=p->next;p=s;A）第i行非0元素的个数之和B）第i列非0元素的个数之和C）第i行0元素的个数之和D）第i列0元素的个数之和9、排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是（）排序方法的基本思想。A）堆排序B）直接插入排序C）快速排序D）冒泡排序10、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。A）快速排序B）堆排序C）归并排序