还剩13页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构考试试题及答案2009-05-1209:22计科2班期中考试题答案提交说明写清题号,以word文本格式保存,文件名命名规则为姓名+学号,放到ftp//
192.
168.
130.50的“计科2班考试”文件夹中一.填空题(每题1分,共10分)
(1)已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第0个元素的地址为address则第i个结点的地址是(address+i*m)
(2)线性表有两种存储结构顺序存储结构和链式存储结构,就两种存储结构完成下列填空(顺序存储结构)存储密度较大,(链式存储结构)存储利用率较高,(顺序存储结构)可以随机存取,(链式存储结构)不可以随机存取,(链式存储结构)插入和删除操作比较方便
(3)顺序表中逻辑上相邻的元素在物理位置上(也相邻),在链表中逻辑上相邻的元素的物理位置(不一定)相邻
(4)在一个长度为n的顺序表中,在第i个元素(0=i=n)之前插入一个新元素时须向后移动(n-i+1)个元素
(5)在顺序表la的第i个元素前插入一个新元素,则有效的i值范围是(0=i=length-1);在顺序表lb的第j个元素之后插入一个新元素,则j的有效范围是(0=j=length-1);要删除顺序表lc的第k个元素,则k的有效范围是(0=k=length-1)
(6)设有一个空栈,现有输入序列为1,2,3,4,5,经过操作序列pushpoppushpushpoppushpushpop后,现在已出栈的序列是135,栈顶元素的值是4
(7)设有栈S,若线性表元素入栈顺序为1,2,3,4,得到的出栈序列为1,3,4,2,则用栈的基本运算PushPop描述的操作序列为pushpoppushpushpoppushpoppop
(8)在队列结构中,允许插入的一端为队尾,允许删除的一端为对头
(9)在一个链队列中,若队头指针为front队尾指针为rear,则判断该队列只有一个结点的条件Q.front-next=Q.rear
(10)设循环队列的头指针front指向队头元素,尾指针rear指向队尾元素后的一个空闲元素,队列的最大空间为MAX,则队空的标志为Q.front=Q.rear,队满的标志为Q.rear+1%MAX=Q.当rearfront时队列长度是Q.rear-Q.front+MAX二.判断题(每题
0.5分,共5分正确用T表示,错误用F表示)
(1)栈和队列都是限制存取点的线性结构T
(2)设栈的输入序列是1,2,····n,若输出序列的第一个元素是n,则第i个输出元素是n-i+
1.F
(3)若一个栈的输入序列是1,2,3···n,输出序列的第一个元素是i,则第i个输出元素不确定T
(4)循环队列不会发生溢出F
(5)链队列与循环队列相比,前者不会发生溢出T
(6)直接或间接调用自身的算法就是递归算法T
(7)数据元素是数据的最小单位F
(8)数据结构是带有结构的数据元素的集合T
(9)算法的时间复杂度是算法执行时间的绝对度量F
(10)算法的正确性是指算法不存在错误F三.简答题(满分5分)
(1)假设我们要从线性表中删除一个数据元素b,如图1-1所示,已知p为其单链表存储结构中指向结点a的指针写出删除结点b后,修改指针的语句(此题2分)abcpp→next=p→next→next;图1-1
(2)编制一程序(可用伪码描述,写出解题思路可酌情得分)对于输入的任意一个非负十进制整数,输出与其等值的16进制数(此题3分)voidconversion{InitStackS;scanf“%d”N;whileN{PushSN%16;N=N/16;}while!StackEmptys{PopSe;Printf“%d”e;}}输入一个十进制数N,使N对16求余,构造一个空栈,并将余数入栈,再将N除16的值赋给N;依次循还,再将栈中元素进行出栈操作即可单项选择题1.用单链表方式存储的线性表,存储每个结点需要两个域,一个是数据域,另一个是(.B)A.当前结点的所在地址B.后继结点的所在地址C.空指针域D.空闲域2.在一个单链表中,若p所指结点不是最后结点,则删除p所指结点的后继结点的正确操作是CA.p=p-nextB.p-next=p-nextC.p-next=p-next-nextD.p-next=p3.栈和队列C应该是在顶端进行取数据的操作A.共同之处在于二者都是先进先出的特殊的线性表B.共同之处在于二者都是先进后出的特殊的线性表C.共同之处在于二者都只允许在顶端执行删除操作D.没有共同之处4.设数组Data[
0..m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作的语句为(D)A.front=front+1B.front=front+1%mC.rear=rear+1%mD.front=front+1%m+
15.已知函数Subsij的功能是返回串s中从第i个字符起长度为j的子串,函数Scopyst的功能为复制串t到s若字符串S=〃SCIENCESTUDY〃,则调用函数ScopyPSubS17后得到 A A.P=〃SCIENCE〃 B.P=〃STUDY〃C.S=〃SCIENCE〃 D.S=〃STUDY〃6.在最好和最坏情况下的时间复杂度均为Onlogn且稳定的排序方法是 CA.快速排序 B.堆排序C.归并排序 D.基数排序7.图的邻接表如下所示,从顶点V1出发采用深度优先搜索法遍历该图,则可能的顶点序列是A.V1V2V3V4V5B.V1V2V3V5V4C.V1V4V3V5V2D.V1V3V4V5V28.下列排序方法中,属于不稳定的排序方法是AA.直接插入排序法B.冒泡排序法C.基数排序法D.归并排序法数据结构考试试题及答案1
一、判断下列叙述的对错
(1)线性表的逻辑顺序与物理顺序总是一致的
(2)线性表的顺序存储表示优于链式存储表示
(3)线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续
(4)二维数组是其数组元素为线性表的线性表
(5)每种数据结构都应具备三种基本运算插入、删除和搜索
二、设单链表中结点的结构为typedefstructnode{file://链表结点定义ElemTypedata;file://数据structnode*Link;file://结点后继指针}ListNode;
(1)已知指针p所指结点不是尾结点,若在*p之后插入结点*s,则应执行下列哪一个操作?A.s-link=p;p-link=s;B.s-link=p-link;p-link=s;C.s-link=p-link;p=s;D.p-link=s;s-link=p;
(2)非空的循环单链表first的尾结点(由p所指向)满足A.p-link==NULL;B.p==NULL;C.p-link==first;D.p==first;
三、设有一个顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为多少?
四、一棵具有n个结点的理想平衡二叉树(即除离根最远的最底层外其他各层都是满的,最底层有若干结点)有多少层?若设根结点在第0层,则树的高度h如何用n来表示(注意n可能为0)?
五、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句,将其编号填入相应的括号内
(1)对于一个具有n个结点和e条边的无向图,若采用邻接表表示,则顶点表的大小为(A),所有边链表中边结点的总数为(B)
(2)采用邻接表存储的图的深度优先遍历算法类似于树的(C)
(3)采用邻接表存储的图的广度优先遍历算法类似于树的(D)
(4)判断有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用(E)供选择的答案A
①n
②n+1
③n-1
④n+eB
①e/2
②e
③2e
④n+eC~D
①中根遍历
②先根遍历
③后根遍历
④按层次遍历E
①求关键路径的方法
②求最短路径的Dijkstra方法
③深度优先遍历算法
④广度优先遍历算法
六、填空题
(1)在用于表示有向图的邻接矩阵中,对第i行的元素进行累加,可得到第i个顶点的(
①)度,而对第j列的元素进行累加,可得到第j个顶点的(
②)度
(2)一个连通图的生成树是该图的(
③)连通子图若这个连通图有n个顶点,则它的生成树有(
④)条边
(3)给定序列{100,86,48,73,35,39,42,57,66,21},按堆结构的定义,则它一定(
⑤)堆
(4)在进行直接插入排序时,其数据比较次数与数据的初始排列(
⑥)关;而在进行直接选择排序时,其数据比较次数与数据的初始排列(
⑦)关
(5)利用关键码分别为10,20,30,40的四个结点,能构造出(
⑧)种不同的二叉搜索树
七、设带表头结点的双向链表的定义为typedefintElemType;typedefstructdnode{file://双向链表结点定义ElemTypedata;file://数据structdnode*lLink,*rLink;file://结点前驱与后继指针DblNode;typedefDblNode*DblList;file://双向链表试设计一个算法,改造一个带表头结点的双向链表,所有结点的原有次序保持在各个结点的右链域rLink中,并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来
八、设有一个关键码的输入序列{55,31,11,37,46,73,63,02,07,
(1)从空树开始构造平衡二叉搜索树,画出每加入一个新结点时二叉树的形态若发生不平衡,指明需做的平衡旋转的类型及平衡旋转的结果
(2)计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度
九、下面是求连通网络的最小生成树的Prim算法的实现,中间有5个地方缺失,请阅读程序后将它们补上constintMaxInt=INT_MAX;file://INT_MAX的值在中constintn=6;file://图的顶点数,应由用户定义typedefintAdjMatrix[n[n;file://用二维数组作为邻接矩阵表示typedefstructfile://生成树的边结点intfromVex,toVex;file://边的起点与终点intweight;file://边上的权值TreeEdgeNode;typedefTreeEdgeNodeMST[n-1;file://最小生成树定义voidPrimMST(AdjMatrixG,MSTT,intrt){file://从顶点rt出发构造图G的最小生成树T,rt成为树的根结点TreeEdgeNodee;inti,k=0,min,minpos,v;for(i=0;in;i++)file://初始化最小生成树Tif(i!=rt){T[k.fromVex=rt;T[k.toVex=I;T[k++.weight=G[rt;}for(k=0;kn-1;k++){file://依次求MST的候选边min=MaxInt;for(i=k;in-1;i++)file://遍历当前候选边集合if(T.weightmin)file://选具有最小权值的候选边{min=T.weight;minpos=i;}if(min==MaxInt)file://图不连通,出错处理{cerr《“Graphisdisconnected!”《endl;exit
(1);}e=T[minpos;T[minpos=T[k;T[k=e;v=T[k.toVex;for(i=k+1;in-1;i++)file://修改候选边集合if(G[v[T.toVexT.weight)T.weight=G[v[T.toVex;T.fromVex=v;参考答案
一、
(1)错
(2)错
(3)对
(4)错
(5)对
二、
(1)B
(2)C
三、3
四、h=élog2(n+1)ù-1
五、A.
①B.
③C.
②D.
④E.
③
六、
①出
②入
③极小
④n-1
⑤是(最小)
⑥有
⑦无
⑧14
七、算法如下voidsort(DblNode*L){DblNode*s=L-rlink;file://指针s指向待插入结点,初始时指向第一个结点while(s!=NULL){file://处理所有结点pre=L;p=L-lLink;file://指针p指向待比较的结点,pre是p的前驱指针while(p!=NULLs-datap-data)file://循lLink链寻找结点*s的插入位置{pre=p;p=p-lLink;}pre-lLink=s;s-lLink=p;s=s-rLink;file://结点*s在lLink方向插入到*pre与*p之间}
八、关键码的输入序列{55,31,11,37,46,73,63,02,07}在等概率下查找成功的平均查找长度在等概率下查找不成功的平均查找长度九
①T[k.toVex=i
②min=MaxInt
③minpos=i
④exit
(1)
⑤T.fromVex=v帖子465 精华10 积分923 鹏币632 身份在校生大三 学校北京工业大学 专业计算机科学与技术 在线时间64小时 注册时间2009-4-13 最后登录2009-11-19 查看详细资料数据结构期末考试试题及答案2009-01-0411:22期末样卷参考答案一.是非题(每题1分共10分)
1.线性表的链式存储结构优于顺序存储结构F
2.栈和队列也是线性表如果需要,可对它们中的任一元素进行操作F3.字符串是数据对象特定的线性表T4.在单链表P指针所指结点之后插入S结点的操作是P-next=S;S-next=P-next;F5.一个无向图的连通分量是其极大的连通子图T6.邻接表可以表示有向图,也可以表示无向图T7.假设B是一棵树,B′是对应的二叉树则B的后根遍历相当于B′的中序遍历T8.通常,二叉树的第i层上有2i-1个结点F9.对于一棵m阶的B-树树中每个结点至多有m个关键字除根之外的所有非终端结点至少有ém/2ù个关键字F10.对于任何待排序序列来说,快速排序均快于起泡排序F二.选择题(每题2分共28分)1.在下列排序方法中,(c)方法平均时间复杂度为0nlogn,最坏情况下时间复杂度为0n2;(d)方法所有情况下时间复杂度均为0nlogna.插入排序 b.希尔排序 c.快速排序 d.堆排序
2.在有n个结点的二叉树的二叉链表表示中,空指针数为(b) a.不定 b.n+1 c.n d.n-
13.下列二叉树中,(a)可用于实现符号不等长高效编码a.最优二叉树 b.次优查找树 c.二叉平衡树d.二叉排序树
4.下列查找方法中,(a)适用于查找有序单链表a.顺序查找 b.二分查找 c.分块查找 d.哈希查找
5.在顺序表查找中,为避免查找过程中每一步都检测整个表是否查找完毕,可采用(a)方法a.设置监视哨 b.链表存贮 c.二分查找 d.快速查找
6.在下列数据结构中,(c)具有先进先出特性,(b)具有先进后出特性a.线性表 b.栈 c.队列 d.广义表7.具有m个结点的二叉排序树,其最大深度为(f),最小深度为(b)a.log2m b.└log2m┘+1 c.m/2d.┌m/2┐-1 e.┌m/2┐ f.m 8.已知一组待排序的记录关键字初始排列如下5634582679526437288457下列选择中(c)是快速排序一趟排序的结果(b)是希尔排序(初始步长为4)一趟排序的结果(d)是基数排序一趟排序的结果(a)是初始堆(大堆顶)a.84,79,64,37,57,52,58,26,28,34,56b.28,34,57,26,56,52,58,37,79,84,64c.28,34,37,26,52,56,64,79,58,84,57d.52,34,64,84,56,26,37,57,58,28,79e.34,56,26,58,52,64,37,28,79,57,84f.34,56,26,58,52,79,37,64,28,84,57三.填空题(每题2分共20分)1.有向图的存储结构有(邻接矩阵)、(邻接表)、(十字链表)等方法2.已知某二叉树的先序遍历次序为afbcdeg,中序遍历次序为cedbgfa其后序遍历次序为(edcgbfa)层次遍历次序为(afbcgde)3.设有二维数组A5x7每一元素用相邻的4个字节存储,存储器按字节编址已知A00的存储地址为100则按行存储时,元素A14的第一个字节的地址是
(144);按列存储时,元素A14的第一个字节的地址是
(184) 4.请在下划线上填入适当的语句,完成以下法算StatusPreordertraverseBitreeTStatus*VisitTelemtypee{//先序非递归遍历二叉树InitstackS; PushST;While!stackemptyS{WhilegettopSpp{visitp-data;pushSp-lchild;} PopSp; If!stackemptys{popSp; pushSp-rchild;}}returnok;四.简答题(每题5分共25分)1.将图示森林转换为二叉树,并对该二叉树中序全序线索化hdajibfecmlkg2.已知Hash函数为H(K)=Kmod13,散列地址为0--14,用二次探测再散列处理冲突,给出关键字(23,34,56,24,75,12,4952,36,92,06,55)在散列地址的分布0 1 2 3 4 5 6 7 8 9
10111213143.右图为一棵3阶B树 (20,25)a.画出在该树上插入元素15后的B树 /│\b.接着,再删除元素35,画出删除后的B树 1014
(21)
(35)
4.已知某无向图的邻接表存储结构如图所示 a.请画出该图b.根据存储结构给出其深度优先遍历序列及广度优先遍历序列c.画出其深度优先生成树及广度优先生成树0a 2 4 /\1b 2 3 4 /\2c 0 1 4 /\3d 1 /\ 4e 0 1 2 /\
5.设在某通信系统中使用了八个字符,它们出现的频率分别为
0.08,
0.05,
0.1,
0.12,
0.26,
0.18,
0.14,
0.07,试构造一棵赫夫曼树,并给出赫夫曼编码五.算法设计题(共17分)
1.单链表结点的类型定义如下typedefstructLNode{ intdata; structLNode*next;}LNode*Linklist;写一算法,将带头结点的有序单链表A和B合并成一新的有序表C注:不破坏A和B的原有结构.MergeLinklistALinklistBLinklistCvoidMergeLinklistALinklistBLinklistC{C=LinklistmallocsizeofLNode;pa=A-next;pb=B-next;pc=C;whilepapb{pc-next=LinklistmallocsizeofLNode;pc=pc-next;ifpa-data=pb-data{pc-data=pa-data;pa=pa-next;}else{pc-data=pb-data;pb=pb-next;}}if!papa=pb;whilepa{pc-next=LinklistmallocsizeofLNode;pc=pc-next;pc-data=pa-data;pa=pa-next;}pc-next=NULL;}
2.二叉树用二叉链表存储表示typedefstructBiTNode{ TelemTypedata; StructBiTNode*lchild*rchild;}BiTNode*BiTree;编写一个复制一棵二叉树的递归算法BiTreeCopyTreeBiTreeT{if!TreturnNULL;if!newT=BiTNode*mallocsizeofBiTNodeexitOverflow;newT-data=T-data;newT-lchild=CopyTreeT-lchild;newT-rchild=CopyTreeT-rchild;returnnewT;}//CopyTree数据结构期中考试试题及答案
一、 单选题(每小题2分,共8分)
1.在一个长度为n的线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x同元素的平均比较次数,假定查找每个元素的概率都相等)为 C A.n B.n/2 C.n+1/2 D.n-1/
22.在一个带附加表头的单链表HL中,若要向表头插入一个由指针p指向的结点,则执行 D A.HL=p;p-next=HL; B.p-next=HL;HL=p;C.p-next=HL;p=HL; D.p-next=HL-next;HL-next=p;3.若让元素A,B,C,D依次入栈,则出栈次序不可能出现 D 种情况A.DCBA B.ADCB C.BADC D.DABC4.从一个顺序队列删除元素时,首先需要 B A.前移一位队首指针 B.后移一位队首指针C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素
二、 填空题(每空1分,共32分)1.数据的逻辑结构分为 集合 、 线性 、 树型 、 图形 四种
2.函数重载要求 参数个数、 参数类型或 参数次序有所不同3.在带附加表头的循环双向链表中,表头附加结点的左指针域指向最后一个结点,最后一个结点的右指针域指向表头附加 结点4.在以HL为表头指针的带附加结点的单链表和循环单链表中,链表为空的条件分别为 HL-next==NULL和HL==HL-next5.在由数组a中元素结点构成的单链表中,删除下标为i的结点后,需要把该结点插入到空闲表的表头,具体操作为a[i].next=a
[1].next、a
[1].next=i6.在由数组a中元素结点构成的单链表中,删除下标为i的结点的后继结点并将被删除结点的下标赋给i时,所进行的操作(需要用一个临时变量p)描述为p=a[i].next 和a[i].next=a[p].next;i=p 7.在稀疏矩阵的十字链接存储中,每个结点的down指针域指向 列号 相同的下一个结点,right指针域指向 行号 相同的下一个结点8.一个广义表中的元素分为 单 元素和 表 元素两类9.广义表A=abcde的长度为 1 ,深度为 4 10.向一个顺序栈插入一个元素时,首先应top++,然后再将待插入元素放入栈顶位置11.对于队列,应在 队尾 进行插入,在 队首 进行删除12.中缀表达式2+7/4-1所对应的后缀表达式为2741-/+@ 13.后缀表达式“10354-*-1+32+-”的值为 3
14.一棵二叉树的广义表表示为abcdefg则e结点的双亲结点为 a ,孩子结点为 f ,树的深度为 4
三、运算题(每小题8分,共24分)1.假定线性表L=
(336978224488)i=3x=34y=22则对L进行下列一组操作` ListEmptyL; false GetElemLi; 78 InsertFrontLx; 34336978224488 InsertRearLx; 3433697822448834 DeleteFrontL; 33697822448834 DeleteLy; 336978448834 SortL; 333444697888 InsertL66; 33344466697888 请写出每步操作后的结果 2.假定线性表L=
(338521563063429176)调用顺序表的排序算法voidSortListL对此表进行排序,请写出排序过程(将每一步结果写出)
(1)
[3385]21563063429176
(2)
[213385]563063429176
(3)
[21335685]3063429176
(4)
[2130335685]63429176
(5)
[213033566385]429176
(6)
[21303342566385]9176
(7)
[2130334256638591]76
(8)
[213033425663768591] 3.已知一个中缀表达式为10-3*2+1+3-1/2@,请画出其转换为后缀表达式过程中S2及R栈的变化S 10 3 2 1 R@-*+ S 10 3 2 1 +R@-*S 10 3 2 1 +*-3 1R@+-S 10 3 2 1 +*-3 1 -2 R@+/S 10 3 2 1 +*-3 1 -2 /+RS 10 3 2 1 +*-3 1 -2 /+@\0R
四、 阅读算法,回答问题(每小题8分,共16分)
1.VoidMADELnode*H1
2.VoidAEStackS { {Lnode*p; InitStackS;p=H1; PushS30;H1=NULL; PushS40;whilep!=NULL PushS50;{ intx=PopS+2*PopS; lnode*q=p; PushSx; p=p-next; intia
[4]={581215}; q-next=h1; fori=0;i4;i++ H1=q; PushSa[i];} while!StackEmptyS } coutPopS’’;} 该算法的功能为 该算法被调用后得到的输出结果为将原链表逆序 15 12 8 5 130 30
五、 算法填空,在画有横线的地方填写合适的内容(10分)删除带附加表头的单链表上第pos个元素的算法VoidDelLNode*HLintpos{ ifpos1{cerr”posisoutrange!”endl;exit1;}inti=0;Lnode*p*q;q=HL ;p=HL-next ;int i=1 ;whilep!=NULL{ ifi==pos break; else{ q=p ; p=p-next ; i++ ; }ifp!=NULL{ q-next=p-next ;deletep ; }else{ cerr”posisoutrange!”endl; exit1;}}
六、 编写算法(10分)写出向二叉排序树中插入一个元素的非递归算法VoidinsertBtreeNode*BSTconstElemTypeitem{ BtreeNode*t=BST*parent=NULL; Whilet!=NULL{ Parent=t; Ifitemt-datat=t-left; Elset=t-right; } BtreeNode*p=newBtreeNode; p-data=item; p-left=p-right=NULL; ifparent==NULLBST=p; else ifitemparent-data parent-left=p; else parent-right=p;}。