还剩22页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
,专业,整理.《数据构造》期末考试试题及答案2
一、单项选择题（每题2分，共8分）
1、在一个长度为n的挨次线性表中挨次查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为（）A nB n/2C（n+l）/2D（n-l）/
22、在一个单链表中，假设q所指结点是p所指结点的前驱结点，假设在q与P之间插入一个s所指的结点，则执行（）oA sflink=pf link;pf link=s;B p-link=s;s—link=q;C p-link=s-*link;s-link=p;D q-*link=s;s-*link=p;
3、栈的插入和删除操作在〔）进展A栈顶B栈底C任意位置D指定位置
4、由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A24B71C48D53
二、填空题（每空1分，共32分）
1、数据的规律构造被分为、、和四种
2、一种抽象数据类型包括和两个局部
3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next,则该0123456786056387425424376201线性表为odatanext
4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，推断链表为空的条件分别为和O
5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的，该循环队列的最大长度为
06、当堆栈承受挨次存储构造时，栈顶元素的值可用----------------------表示；当堆栈承受链接存储构造时，栈顶元素的值可用表示
7、一棵高度为5的二叉树中最少含有个结点，最多含有个结点；一棵高度为5的抱负平衡树中，最少含有个结点，最多含有_________个结点
8、在图的邻接表中，每个结点被称为,通常它包含三个域一是；二是；三是O
9、在一个索引文件的索引表中，每个索引项包含对应记录的和___________两项数据
10、假定一棵树的广义表表示为A[B C,D E,F,G,H[I,J,则树中所含的结点数为个，树的深度为，树的度为,结点H的双亲结点为,孩子结点为o11＞在堆排序的过程中，对任一分支结点进展筛运算的时间简洁度为,整个堆排序过程的时间简洁度为
12、在对m阶的B_树插入元素的过程中，每向一个结点插入一个索引项叶子结点中的索引项为关键字和空指针〕后，假设该结点的索引项数等于个，则必需把它分裂为个结点
三、运算题每题6分，共24分
1、一组记录的排序码为46,79,56,38,40,80,95,24,写出对其进展快速排序的每一次划分结果
2、一个线性表为B=12,23,45,57,20,03,78,31,15,36,设散列表为HT
10..12],散列函数为H key=key%13并用线性探查法解决冲突,请画出散列表，并计算等概率状况下查找成功的平均查找长度
3、一棵二叉树的前序遍历的结果序列是ABECKFGHIJ,中序遍历的结果是EBCDAFHIGJ,试写出这棵二叉树的后序遍历结果
4、一个图的顶点集V各边集G如下V={0,1,2,3,4,5,6,7,8,9}；E={[0,1,[0,4,[1,2,1,7,⑵8〕，[3,4,[3,8,[5,6,[5,8,[5,9,6,7,[7,8,[8,9}当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V动身按深度优先0搜寻遍历得到的顶点序列和按广度优先搜寻遍历等到的顶点序列假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时
四、阅读算法，答复以下问题每题8分，共16分
1、假定从键盘上输入一批整数，依次为786345309134-1,请写出输出结果#includeiostream.h#includestdlib.h constint stackmaxsize=30;typedef intelemtype;struct stack{；#include“stack,void h”main elemtypestack[stackmaxsize];int top;stack a;initstacka;int x;cin x;while x!=T{push a,x;cin x;while!stackempty acout popacout endl;}该算法的输出结果为:
2、阅读以下二叉树操作算法，指出该算法的功能Template calsstypevoid BinTreeTypeunknown BinTreeNodeType*t{BinTreeNode Type*p=t,*temp;if p!=NULL{temp=p—leftchild;pf leftchild=pf rightchild;pf rightchild=temp;unknownpf leftchild;undnownp^rightchiId;}该算法的功能是
五、算法填空，在画有横线的地方填写适宜的内容10分对挨次存储的有序表进展二分查找的递归算法int BinschElemType A[],int low,int high,KeyType Kif low=highint mid=1ifK二=A[mid].keyreturn mid;else ifKA[mid].key return2else return3}elsereturn4
一、单项选择题每题2分，共8分〕题号1234答案C DA B
二、填空题〔每空1分，共32分1集合、线性、树、图；2数据描述、操作声名；338,56,25,60,42,74；4HL-next=NULL；HL=HL-*next；5前一个位置；n-1；6S.stack[S.top];HS-data;75318边结点、邻接点域、权域、链域；9索引值域、开头位置域；
1010、
3、
3、B、I和J；110log n、0nlog n;2212m、m-1
三、运算题〔每题6分,共24分〕
1、戈陟烽
[382440]飒嘉梁809579]具次次第三次22443
[3884400]4466L5680[9556879J9579]第四次2438404656
[809579]第五次243840465679
[8095]第六次2438404656798095012345678910111278035745203123361215查找成功的平均查找长度ASL=14/10=
1.4oUvv
3、此二叉树的后序遍历结果是EDCBIHJGFA
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
四、阅读算法，答复以下问题每题8分，共16分
1、该算法的输入结果是
3491304563782、该算法的功能是交换二叉树的左右子树的递归算法
五、算法填空，在画有横线的地方填写适宜的内容U0分1是low+high/2;2是Binsch A,low,mid-1,K;3是BinschA,mid+1,high,K;4是-1；
六、编写算法10分依据编程状况，酌情给分Lnode*P=HL;HL=NULL;While p!二nullLnode*q=p;P=pf next;qf next=HL;HL=q;《数据构造》期末考试试题及答案3
一、单项选择题
1.对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为〔A、正确性B.可行性C.强健性D.输入性
2.设S为C语言的语句，计算机执行下面算法时，算法的时间简洁度为〔ofor i=n-l；i=0；i--for j=0；ji;j++S；A、r2B.Onlgn C.0n D.0r
23.折半查找法适用于〔A、有序挨次表[B、有序单链表Ch有序挨次表和有序单链表都可以⑴、无限制
4.挨次存储构造的优势是A、利于插入操作B、利于删除操作[C、利于挨次访问⑴、利于随机访问
5.深度为k的完全二叉树，其叶子结点必在第层上Ah k-1⑻、k©、k-l和k D、1至k
6.具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为A、11山、13C、48⑴、
377.图的Depth-First SearchDFS遍历思想实际上是二叉树〔遍历方法的推广A、先序B、中序C、后序⑴、层序
8.在以下链队列Q中，元素a出队的操作序列为B、p=Q.front-next;Q.front-next=p-next;
0、p=Q.rear-next;p-next=Q.rear-next;D、p=Q-next;Q-next=p-next;
9.Huffman树的带权路径长度WPL等于[A、除根结点之外的全部结点权值之和[B、全部结点权值之和[C、各叶子结点的带权路径长度之和⑴、根结点的值
10.线索二叉链表是利用域存储后继结点的地址A、Ichild B、data〔C、rchild⑴、root
二、填空题
1.规律构造打算了算法的，而存储构造打算了算法的
2.栈和队列都是一种的线性表，栈的插入和删除只能在进展
3.线性表a,a,-,a的挨次存储构造中，设每个单元的长度为L,元素a的存储地址12n iLOCa为
4.一双向链表如下指针域名为next和prior现将P所指的结点插入到x和y结点之间，其操作步骤为:
5.n个结点无向完全图的的边数为n个结点的生成树的边数为
6.一有向无环图如下任意写出二种拓扑排序序列、o
7.二叉树的中序遍历序列为BCA,后序遍历序列为CBA,则该二叉树的先序遍历序列为,层序遍历序列为o
三、应用题
1.设散列函数Hk=k%13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲突6分1构造HASH表2分别求查找成功和不成功时的平均查找长度《数据构造》期末考试试题及答案1
一、单项选择题每题2分，共20分
1.栈和队列的共同特点是A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点
2.用链接方式存储的队列，在进展插入运算时.A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改
3.以下数据构造中哪一个是非线性构造？A.队列B.栈C.线性表D.二叉树
4.设有一个二维数组A[m][n],假设A
[0]
[0]存放位置在644,A
[2]
[2]10存放位置在676，每个元素占一个空间，问A
[3]
[3]存放在什么位置？1010脚注表示用10进制表示10A.688B.678C.692D.
6965.树最适合用来表示oA.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据
6.二叉树的第k层的结点数最多为.A.2k-1B.2K+1C.2K-1D.2i
7.假设有18个元素的有序表存放在一维数组A
[19]中,第一个元素放A[l]中，现进展二分查找，则查找A
[3]的比较序列的下标依次为A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,
38.对n个记录的文件进展快速排序，所需要的关心存储空间大致为A.01B.0n C.0logn D.0n
229.对于线性表[7,34,55,25,64,46,20,10进展散列存储时，假设选用H K=K%9作为散列函数，则散列地址为1的元素有个，
2.给定表（19,14,22,15,20,21,56,10）.（8分）
（1）按元素在表中的次序，建立一棵二叉排序树
（2）对
（1）中所建立的二叉排序树进展中序遍历，写出遍历序列
（3）画出对⑵中的遍历序列进展折半查找过程的判定树ii Vi iV13-525242633742521342-152-9529558（5分〕
3.二个稀疏矩阵A和B的压缩存储三元组表如下:A B
4.一维数组中的数据为（18,12,25,53,18）式写出插入排序〔升序）过程并指出具有n个元素的插入排序的时间简洁度是多少？（5分）
5.A651oo oo「oo53oo00C5oooo7oo2D157oo64E oo3oo6oo600246oo JLOO一网络的邻接矩阵如下，求从顶点A开头的最小生成树（8分，要有过程）A B
（1）求从顶点A开头的最小生成树2分别画出以A为起点的DFS生成树和BFS生成树
6.数据六个字母及在通信中消灭频率如下表:A BC D E F
0.
150.
150.
10.
10.
20.3把这些字母和频率作为叶子结点及权值，完成如下工作7分，要有过程1画出对应的Huffman树2计算带权路径长度WPL3求A、B、C、D、E、F的Huffman编码
7.有如下的有向网:2求顶点A到其它各顶点的最短路径承受Dijkstra算法，要有过程6分
四、设计题30分，每题10分，用C语言写出算法，做在答题纸上
1.线性表a,a，…,a以挨次存储构造为存储构造，其类型定义如下12nttdefine LIST_INIT_SIZE100〃挨次表初始安排容量typedef struct{Elemtype*elem;〃挨次存储空间基址int length;〃当前长度〔存储元素个数}SqList;设计一个算法，删除其元素值为x的结点〔假设x是唯一的并求出其算法的平均时间简洁度其算法函数头部如下Status ListDeleteSqlistL,Elemtype x
2.设挨次栈如左图所示其中结点定义如下typedef struct{topElemtype*base;〃栈底指针Elemtype Mop;〃栈顶指针}Stack;设计算法，将栈顶元素出栈并存入e中.base
3.设二叉链树的类型定义如下:typedef intElemtype;typedef struct node{Elemtype data;structnode*lchild,*rchild;}BinNode,*BinTree;试写出求该二叉树叶子结点数的算法:Status CountLeavesBinTreeroot,int n{//n isthe numberof leaves试题3答案
一、选择题〔每题1分〕
1、C
2、D
3、A
4、D
5、C
6、D
7、A
8、E
9、C
10、C
二、填空题L设计、实现
2.特别、栈顶
3.LOC al+i-1*L
4.p-next=q-next;q-next-prior=p;q-next=p;p-prior=q;
5.nnT/
2、n-l
6.ADCBFEG、ABCDEFFG
7.ABC、ABC
三、应用题
1.⑴Hash表〔4分地址0123456789101112关键安132164572282412探测次数1712313112查找成功的平均查找长度［1分5*1+1*2+2*3+1*71/9二20/9查找不成功的平均查找长度1分2+1+9+8+7+6+5+4+3+2+1/13=
8.⑴、构造3分
2、1014151920212256〔2分〕
3、5分,每行
0.5⑶、3分••1J V13-524633741342-
152185584、初始关键字［18］12255318^18]第一趟［12第255318二趟［12第三182包护18趟［12第四趟182553]18［124分1853]052（1分）
5、7分⑴4分A\\9B/V⑵4分
6、13分A BC D2WPL=O.1*3+
0.1*3+
0.2*2+
0.15*3+
0.15*3+03*21=1分3A010BOil C110D111E00F；10〔3分
7、A-B[A、B1分A-CA、D、C2分A-DA、D1分A_E[A、D、E2分
四、设计题30分
1、10分Status ListDeleteSqlistL,ElemType x{int i,j;for i=0;iL-length;i++ifL-elem[i]==x break;ifi=L-length returnERROR;for j=i;jL-lengthi-l;j++L-elem[j]=L-elem[j+l];L-length--;8分〕平均时间简洁度〔2分设元素个数记为n,则平均时间简洁度为:n2/=i
2、10分void popStack S,Elemtype eif S.top=二S・basereturn ERROR;
5.top一-;e=*s.top;
3、10分voidCountLeavesBinTree T,int n{ifT{if!T-lchild!T-rchild n++;CountLeaves T-lchild,n;CountLeaves T-rchild,n;}A.1B.2C.3D.
410.设有6个结点的无向图，该图至少应有条边才能确保是一个连通图A.5B.6C.7D.8
二、填空题每空1分，共26分
1.通常从四个方面评价算法的质量:、、和O
2.一个算法的时间简洁度为n3+n log n+14n/n2,其数量级表示为22o
3.假定一棵树的广义表表示为A C,DE,F,G,H I,J,则树中所含的结点数为个,树的深度为，树的度为
4.后缀算式923+-102/-的值为o中缀算式3+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.在堆排序的过程中，对任一分支结点进展筛运算的时间简洁度为,整个堆排序过程的时间简洁度为
12.在快速排序、堆排序、归并排序中，排序是稳定的运算题（每题6分，共24分）
1.在如下数组A中链接存储了一个线性表，表头指针为A
[0].next,试写出该线性表请画出图10的邻接矩阵和邻接表
3.一个图的顶点集V和边集E分别为V={1,2,3,4,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};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边
4.的变化
四、阅读算法每题7分，共14分画出向小根堆中参与数据4,2,5,8,3时，每参与一个数据后堆
1.LinkList mynoteLinkListL{//L是不带头结点的单链表的头指针if LL-next{q=L；L=L—next；p二L；SIwhilep—next p=p—next；S2p—next=q；q—next=NULL；}return L；请答复以下问题1说明语句S1的功能；2说明语句组S2的功能；3设链表表示的线性表为a,a,…,a,写出算法执行后的返回值所表示的线性表12n
2.void ABCBTNode*BTif BT{ABC BT-left;ABC BT-right;coutBT-data”该算法的功能是:
五、算法填空共8分二叉搜寻树的查找一一递归算法bool FindBTreeNode*BST,ElemType itemifBST==NULLreturn false;〃查找失败else{if item==BST-data{item=BST-data;〃查找成功return;}else ifitemBST-datareturn Find,item;else returnFind,item;}//if
六、编写算法共8分统计出单链表HL中结点的值等于给定值X的结点数int CountXLNode*HL,ElemType x,专业.整理.试题1答案单项选择题（每题2分，共20分）
1.A
2.D
3.D
4.C
5.C
6.D
7.D
8.C
9.D
10.A填空题〔每空1分,共26分）
61.正确性易读性强壮性高效率.
72.有O向n无回路.
83.nn-l/2nn-l.
94.12,407423,55,
63.
150.增加2n1n-ln+
1.
11.0logn0nlog n
2212.归并运算题（每题6分，共24分）线性表为:78,50,40,60,34,90]2e
01112.邻接矩阵10邻接表如图11所示:图
113.用克鲁斯卡尔算法得到的最小生成树为1,23,4,64,1,35,1,48,2,510,4,
7204.见图12图12
四、阅读算法（每题7分，共14分〕
1.[1）查询链表的尾结点
（2）将第一个结点链接到链表的尾部，作为的尾结点
（3）返回的线性表为（a,a,•••,a,a）23n
12.递归地后序遍历链式存储的二叉树
五、算法填空（每空2分，共8分）true BST-left BST-right
六、编写算法（8分）int CountX（LNode*HL,ElemType x）{int i=0;LNode*p=HL;//i为计数器while（p!=NULL）{if（P-data==x）i++;p=p-next;}//while,出循环时i中的值即为x结点个数return i;}//CountX。
个人认证
优秀文档
获得点赞 0
