还剩27页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
《数据结构》期末考试试题及答案2017《数据结构》期末考试试题及答案
0、在一个索引文件的索引表中，每个索引项包含对应记录的和9___________两项数据、假定一棵树的广义表表示为则树中所含的结10A B C,D E,F,G,H I,J,点数为个，树的深度为，树的度为,结点的双亲结点为，孩子结点为Ho、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为,整个堆排序11过程的时间复杂度为、在对阶的树插入元素的过程中，每向一个结点插入一个索引项叶子结点12m B_中的索引项为关键字和空指针后，若该结点的索引项数等于个，则必须把它分裂为个结点
三、运算题每小题分，共分
624、已知一组记录的排序码为写出对其进行快速排序的146,79,56,38,40,80,95,24,每一次划分结果.一个线性表为设散列表为散列函数2B=12,23,45,57,20,03,78,31,15,36,HT[
0..12],为并用线性探查法解决冲突，请画出散列表，并计H key=key%13算等概率情况下查找成功的平均查找长度.已知一棵二叉树的前序遍历的结果序列是中序遍历的结果是3ABECKFGHIJ,试写出这棵二叉树的后序遍历结果EBCDAFHIGJ,.已知一个图的顶点集各边集如下4V G；V={0,1,2,3,4,5,6,7,8,9}E={0,1,0,4,1,2,1,7,2,8,3,4,3,8,5,6,5,8,5,9,6,7,7,8,8,9}当它用邻接矩阵表示和邻接表表示时，分别写出从顶点出发按深度优先搜V0索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时
四、阅读算法，回答问题（每小题分，共分）
816、假定从键盘上输入一批整数，依次为请写出输出结果1786345309134-1,#includeiostream.h#includestdlib.h constint stackmaxsize=30;typedef intelemtype;struct stack{elemtype stack[stackmaxsize];int top;）；#include“stack.hvoid mainstack a;initstacka;int x;cin»x;while x!=-1{push a,x;cin»x;while Jstackemptya cout«pop acout«endl;该算法的输出结果为:.阅读以下二叉树操作算法，指出该算法的功能2Template calsstypevoid BinTreeType::unknown BinTreeNodeType*t{BinTreeNode Type*p=t,*temp;ifp!=NULL{temp=pf leftchild;pf leftchild=pf rightchild;p-rightchild=temp;unknownpf leftchild;undnownp frightchild;}该算法的功能是:_________________________________
五、算法填空，在画有横线的地方填写合适的内容分10对顺序存储的有序表进行二分查找的递归算法int BinschElemType A[],int low,int high,Key TypeK iflow=highint mid=1ifK==A[mid].key returnmid;else ifKA[mid].keyreturn2elsereturn3elsereturn4
二、填空题每空分，共分1321集合、线性、树、图；数据描述、操作声名；2:338,56,25,60,42,74；4:HLf next=NULL；HL=HL^next；5:前一个位置；n-1；6:S.stack[S.top];HS^data;7:531边结点、邻接点域、权域、链域；8:索引值域、开始位置域；9:10:
10、
3.
3.B.I和J；11:0log2n Onlog2n;、12:m m-1
三、运算题每小题分，共分
624、1划分次序划分结果第一次
[382440]46
[56809579]第二次24
[3840]46
[56809579]第三次24384046
[56809579]第四次2438404656
[809579]第五次243840465679
[8095]第六次2438404656798095012345678910111278150357452031233612查找成功的平均查找长度:ASLSUCC=14/10=
1.
4.此二叉树的后序遍历结果是:3EDCBIHJGFA、4图深度优先序列广度优先序列邻接矩阵表示时0,1,2,8,3,4,5,6,7,90,1,4,2,7,3,8,6,5,9邻接表表示时0,4,3,8,9,5,6,7,1,20,4,1,3,7,2,8,6,9,5
四、阅读算法，回答问题（每小题分，共分）816该算法的输入结果是
1.
349130456378、该算法的功能是交换二叉树的左右子树的递归算法2
五、算法填空，在画有横线的地方填写合适的内容分10是1low+high/2;是2BinschA,low,mid-1,K;是3BinschA,mid+1,high,K;4是-1；
六、编写算法分10根据编程情况，酌情给分Lnode*P=HL;HL=NULL;While p!=nullLnode*q=p;二P pfnext;qf next=HL;HL=q;《数据结构》期末考试试题及答案3
一、单项选择题对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为
1.o,A、正确・.B,可行..C.健壮…D.输入性
2.设S为C语言的语句，计算机执行下面算法时，算法的时间复杂度为o fori=n-l；i=0；i—forj=0；ji；j++S；、.A n..B.Onlgn..C.On..D.0n2折半查找法适用于
3.o、有序顺序表、有序单链表A B、有序顺序表和有序单链表都可以、无限制C D.顺序存储结构的优势是4o、利于插入操作、利于删除操作A B、利于顺序访问、利于随机访问C D深度为的完全二叉树，其叶子结点必在第层上
5.k、、、和、至A k-1B kC k-l kD1k具有个结点的二叉树，其叶子结点有个，则度过的结点数为
6.
60121、、、、A11B13C48D37图的遍历思想实际上是二叉树遍历方法的推广
7.Depth-First SearchDFS、先序、中序、后序、层序A BC D
98..在Hu下ff列ma链n队树列的带Q权中路，径元长素度a出W队PL的等操于作序列为、A p=Q.front-next;p-next=Q.front-next;、B p=Q.front-next;Q.front-next=p-next;、C p=Q.rear-next;p-next=Q.rear-next;、D p=Q-next;Q-next=p-next;A、除根结点之外的所有结点权值之和B、所有结点权值之和C、各叶子结点的带权路径长度之和D、根结点的值
10.线索二叉链表是利用域存储后继结点的地址A、Ichild B、data Crchild Droot
二、填空题逻辑结构决定了算法的，而存储结构决定了算法的
1.栈和队列都是一种的线性表，栈的插入和删除只能在进行
2.线性表的顺序存储结构中，设每个单元的长度为元素的存储地址
3.al,a2,…,an L,ai LOCai为已知一双向链表如下指针域名为和next prior:现将所指的结点插入到和结点之间，其操作步骤为:P xy任意写出二种拓扑排序序列、o个结点无向完全图的的边数为
5.n已知二叉树的中序遍历序列为后序遍历序列为则该二叉树的先序遍历序列为
7.BCA,CBA,个结点的生成树的边数为，n层序遍历序列为
三、应用题设散列函数设关键字系列为要求用线性探测法处理
1.Hk=k%13,{22,12,24,6,45,7,8,13,21},冲突分6构造表1HASH分别求查找成功和不成功时的平均查找长度2给定表分
2.19,14,22,15,20,21,56,
10.8按元素在表中的次序，建立一棵二叉排序树1对中所建立的二叉排序树进行中序遍历，写出遍历序列21画出对⑵中的遍历序列进行折半查找过程的判定树3i JV ij V13-525224633741325242-152-9529558写出压缩存储的三元组表A-B已知二个稀疏矩阵和的压缩存储三元组表如下:A BA B已知一维数组中的数据为试写出插入排序升序过程并指出具有18,12,25,53,18,分5已知一网络的邻接矩阵如下,求从顶点开始的最小生成树分，要有过程A8A oo6510000B6oo oo53ooC5oo oo7oo2D157oo64E oo3oo6oo6F246000000个元素的插入排序的时间复杂度是多少？分n5求从顶点开始的最小生成树1A分别画出以为起点的生成树和生成树2A DFSBFS《数据结构》期末考试试题及答案1
一、单选题每题分，共分220栈和队列的共同特点是
1.o.只允许在端点处插入和删除元素A都是先进后出B.都是先进先出C.没有共同点D.用链接方式存储的队列，在进行插入运算时.
2.仅修改头指......头、尾指针都要修改….A.B.仅修改尾指….…头、尾指针可能都要修改D.以下数据结构中哪一个是非线性结构？
3.线性.二叉树....AM...B.….C..D设有一个二维数组假设⑼存放位置在⑵⑵存放位置
4.A[m][n],A
[0]64410,A在每个元素占一个空间，问存放在什么位置？脚注表67610,A
[3]
[3]1010示用进制表示10A.688B.678C.692D.696树最适合用来表示
5.o有序数据元素无序数据元素A.B.元素之间具有分支层次关系的数据.元素之间无联系的数据C D二叉树的第层的结点数最多为.
6.k.....A.2k-....B,2K+...C.2K-.D.2k-1若有个元素的有序表存放在一维数组中，第一个元素放
7.18A
[19]A[l]中，现进行二分查找，则查找的比较序列的下标依次为A
[3].A.1,2,3B.9,5,2,
3.C.9,5,3D.9,4,2,3对个记录的文件进行快速排序，所需要的辅助存储空间大致为
8.n....A.
01..B.O n..C.0log2n....D.O n2对于线性表进行散列存储时，若选用
9.7,34,55,25,64,46,20,10H K作为散列函数，则散列地址为的元素有个，=K%91BC D E F已知数
6.据六个字母及在通信中出现频率如下表A
0.
150.
150.
10.
10.
20.3（）把这些字母和频率作为叶子结点及权值，完成如下工作（分，要有过程）17（）画出对应的树2Huffman（）计算带权路径长度3WPL求、的编码A.B.C.D.EFHuffman已知有如下的有向网:2求顶点A到其它各顶点的最短路径（采用Dijkstra算法，耍有过程）（6分）设计题（30分，每题10分，用C语言写出算法，做在答题纸上）已
1.知线性表以顺序存储结构为存储结构,其类型定义如下al,a2,-,an//顺序表初始分配容量#define LIST_INIT_SIZE100typedef struct{//顺序存储空间基址Elemtype*elem;〃当前长度存储元素个数int length;JSqList;设计一个算法，删除其元素值为的结点假若是唯一的并求出其算法的平均时间复杂度x x其算法函数头部如下Status ListDeleteSqlistL,Elemtype x设顺序栈如左图所示
2.其中结点定义如下toptypedef struct{〃栈底指针Elemtype*base;〃栈顶指针Elemtype*top;}Stack;设计算法，将栈顶元素出栈并存入中.e base设二叉链树的类型定义如下
3.typedef intElemtype;typedef struct node{Elemtype data;structnode*lchild,*rchild;JBinNode,*BinTree;试写出求该二叉树叶子结点数的算法Status CountLeavesBinTreeroot,int n{//n isthe numberofleaves第22页共26页试题答案3
一、选择题每题分
1、、、、A8B9CIO C
二、填空题设计、实现
1.特殊、栈顶
2.
3.LOC al+i-l*L
4.p-next=q-next;q-next-prior=p;q-next=p;p-prior=q;
5.nn-l/
2.n-l、
6.ADCBFEG ABCDEFFGABC.ABC
三、应用题
02345678910111211.1表Hash4分地址关键安132164572282412探测次数171231311查找成功的平均查找长度分215*1+1*2+2*3+1*719=2019查找不成功的平均查找长度分12+1+9+8+7+6+5+4+3+2+1/13=、构造分
2.
13、分210141519202122562⑶、行
0.5*13-524633741342-15218558初始关键字
[18]12255318第一趟
[1218]255318第二趟
[121825]5318第三趟
[12182553]18第四趟分
[1218182553]4O n231分、分57分14A分
246.⑴3分、分7A-B:A.B12WPL=0・l*3+0・l*3+0♦2*2+0・15*3+0・15*3+03*21=1分3A:010B:011C:110D:111E:00F；103分分A-C:A.D.C2分A-D:A.D
1、、分A-E:A D E2
四、设计题分30分
1.10Status ListDeleteSqlistL,ElemType xint i,j;fori=0;iL-length;i++ifL-elem[i]=x break;ifi=L-length returnERROR;forj=i;jL-lengthi-lL-elem[j]=L-elem|j+l];L-length—;分}8平均时间复杂度（2分）设元素个数记为则平均时间复杂度为:n,分
2.10void popStackS,Elemtype eifS.top=S.basereturn ERROR;S.top—;e=*s.top;分
3.10voidCountLeavesBinTree T,int nifT{if!T-lchild!T-rchild n++;CountLeaves T-lchild,n;CountLeaves T-rchild,n;第26页共26页A.1B.2C.3D.
4.设有个结点的无向图，该图至少应有…条边才能确保是一个连通图106A.5B.6C.7D.8
二、填空题每空分，共分126通常从四个方面评价算法的质量、、和
1.__________________________O一个算法的时间复杂度为其数量级表示为
2.n3+n21og2n+14n/n2,_______________________O假定一棵树的广义表表示为则树中所含
3.A C,DE,F,G,H I,J,的结点数为个，树的深度为,树的度为o后缀算式-的值为中缀算式对应
4.923+-102/o3+4X-2Y/3的后缀算式为o若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩
5.子的两个指针在这种存储结构中，个结点的二叉树共有个指针域,n其中有个指针域是存放了地址，有个指针是空指针对于一个具有个顶点和条边的有向图和无向图，在其对应的邻接表中,
6.n e所含边结点分别有个和个网是一种的图
7.AOV在一个具有个顶点的无向完全图中，包含有条边，在一个具有
8.n个顶点的有向完全图中，包含有条边n假定一个线性表为若按条件进行划分，使得同
9.12,23,74,55,63,40,Key%4一余数的元素成为一个子表，则得到的四个子表分别为和O向一棵树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树
10.B_的高度O在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为,整个堆排
11.序过程的时间复杂度为O在快速排序、堆排序、归并排序中,排序是稳定的
12.
三、运算题每题分，共分624在如下数组中链接存储了一个线性表，表头指针为试写出该线性表A A[O].next,A01234567data next6050789034403572041请画出图的邻接矩阵和邻接表
2.10已知一个图的顶点集和边集分别为
3.V EV={1,234,5,6,7};E={1,23,1,35,1,48,2,510,2,36,3,415,3,512,3,69,4,64,4,720,5,618,6,725};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边图10画出向小根堆中加入数据时，每加入一个数据后堆的变化
4.4,2,5,8,3
四、阅读算法每题分，共分
7141.LinkList mynoteLinkListL是不带头结点的单链表的头指针{//LifLL-next{；；；q=L L=L—next p=L；51:whilep—next p=p—next；；52:p—next=q q—next=NULL；return L请回答下列问题说明语句的功能；1SI说明语句组的功能；2S2设链表表示的线性表为…声，写出算法执行后的返回值所表示的线3aim,性表
2.void ABCBTNode*BT ifBT{ABC BT-left;ABC BT-right;cout«BT-data«f*;}该算法的功能是
五、算法填空共分8二叉搜索树的查找——递归算法bool FindBTreeNode*BST,ElemType itemifBST=NULL〃查找失败return false;else{ifitem==BST-data{二〃查找成功item BST-data;return;}else ifitemBST-datareturn Find,item;else returnFindJtem;}//if
六、编写算法共分8统计出单链表中结点的值等于给定值的结点数HL Xint CountXLNode*HL,ElemType x试题答案1
一、单选题每题分，共分220LA2,D
3.D
4.C
5.C
6.D
7.D
8.C
9.D10,A
二、填空题每空分，共分126正确性易读性强壮性高效率L
2.On
3.
9334.-134X*+2Y*3/-
5.2n n-1n+
16.e2e有向无回路
7.
8.nn-l/2nn-l
9.12,407423,55,63增加
10.111・Olog2n Onlog2n归并
12.
二、运算题每题分，共分624线性表为:L78,50,40,60,34,90邻接矩阵
2.邻接表如图所示11图11用克鲁斯卡尔算法得到的最小生成树为
3.1,23,4,64,1,35,1,48,2,510,4,720见图
4.12图12
四、阅读算法每题分，共分714查询链表的尾结点
1.1将第一个结点链接到链表的尾部，作为新的尾结点返回的线性表为23a2,a3/*\a,ain递归地后序遍历链式存储的二叉树
2.
五、算法填空每空分，共分28true BST-left BST-right
六、编写算法分8intCountXLNode*HL,ElemType x{inti=0;LNode*p=HL;〃i为计数器whilep!=NULL{if P-data==x i++;p=p-next;出循环时•中的值即为结点个数}//while,i xreturn i;}//CountX《数据结构》期末考试试题及答案2
一、单选题（每小题分，共分）
28、在一个长度为的顺序线性表中顺序查找值为的元素时，查找成功时的1n x平均查找长度（即与元素的平均比较次数，假定查找每个元素的概率都相等）为x（）（）（）A nB n/2C n+l/2D n-l/
2.在一个单链表中，若所指结点是所指结点的前驱结点，若在与之间插入一2q pq p个所指的结点，则执行（）s二A sf link=p-link;p-link=s;B pflink=s;sflinkq;二C p—link=s—link;s-link p;D q-link=s;s-link=p;栈的插入和删除操作在（）进行
3.栈顶栈底任意位置指定位置ABCD由权值分别为的叶子结点生成一棵哈夫曼树，它的带权路径
4.11,8,6,2,5长度为（）A24B71C48D53
二、填空题（每空分，共分）
132.数据的逻辑结构被分为、、和1四种.一种抽象数据类型包括和两个部分
2、在下面的数组中链接存储着一个线性表，表头指针为则该线性3a a[o].next,表为o
0123456786056423874254376201.在以为表头指针的带表头附加结点的单链表和循环单链表中，判断链4HL表为空的条件分别为和o、用具有个元素的一维数组存储一个循环队列，则其队首指针总是指向5n队首元素的,该循环队列的最大长度为.当堆栈采用顺序存储结构时，栈顶元素的值可用6表不;。
个人认证
优秀文档
获得点赞 0
