版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
2025年南京信息工程大学期中试卷附答案一、单项选择题(每题2分,共20分)1.下列关于线性表的描述中,正确的是()。A.顺序表的插入操作时间复杂度一定为O(n)B.链表的节点必须包含指针域C.顺序表可以通过下标直接访问元素D.链表的存储空间一定是不连续的2.若一个栈的输入序列是1,2,3,4,5,输出序列为3,2,5,4,1,则栈的大小至少需要()。A.2B.3C.4D.53.已知循环队列的存储空间为数组Q[0..m-1],初始时front=rear=0。当完成一系列入队和出队操作后,front=20,rear=15,若队列的最大容量为m=50,则此时队列中的元素个数为()。A.5B.35C.45D.154.对于一棵深度为h的满二叉树(根节点深度为1),其叶子节点数为()。A.2^(h-1)B.2^h-1C.hD.2h5.对关键字序列{55,32,41,77,63,28}进行冒泡排序(升序),第一趟排序后得到的序列是()。A.{32,41,55,63,28,77}B.{32,55,41,63,28,77}C.{32,41,55,28,63,77}D.{32,55,41,28,63,77}6.哈希表的平均查找长度与()无关。A.哈希函数B.处理冲突的方法C.装填因子D.表长7.下列排序算法中,不稳定的是()。A.插入排序B.归并排序C.冒泡排序D.快速排序8.对于n个节点的无向图,若该图是连通图,则其边数至少为()。A.n-1B.nC.n(n-1)/2D.2n9.若某二叉树的前序遍历序列为ABDECFG,中序遍历序列为DBEAFCG,则后序遍历序列为()。A.DEBFGCAB.DEBFCGAC.DEBFGACD.DEBFAGC10.已知一个单链表的头指针为head,若要在第k个节点前插入一个新节点(k>1),则需要修改()个指针。A.1B.2C.3D.4二、填空题(每题3分,共15分)1.一个栈的输入序列为a,b,c,d,e,若输出序列的第一个元素是c,则第三个输出元素可能是________(写出一个即可)。2.对于完全二叉树,若某节点的编号为i(根节点编号为1),则其左孩子的编号为________。3.对序列{25,18,30,12,40,20}进行简单选择排序(升序),第三趟排序后序列为________。4.已知一个哈希表的长度为10,哈希函数为H(key)=key%7,采用线性探测法处理冲突。若依次插入关键字15,3,22,14,则关键字14的存储位置是________(下标从0开始)。5.对于有向图的拓扑排序,其结果可能不唯一的原因是________。三、简答题(每题10分,共30分)1.简述顺序表和链表在存储结构、插入/删除操作、随机访问上的优缺点。2.说明快速排序的基本思想,并分析其平均时间复杂度和最坏时间复杂度。3.已知一棵二叉树的中序遍历序列为DGBEACHF,后序遍历序列为GDBEHFCA。(1)画出该二叉树的结构;(2)写出其前序遍历序列。四、算法设计题(第1题15分,第2题20分,共35分)1.设计一个算法,将一个带头节点的单链表L逆置(即原链表为a1→a2→…→an,逆置后为an→…→a2→a1)。要求用伪代码描述,并分析时间复杂度。2.已知一个数组存储了n个整数(可能包含重复元素),设计一个高效算法找出其中出现次数超过n/2的元素(称为主元素)。要求:(1)说明算法的基本思路;(2)用伪代码实现;(3)分析时间复杂度和空间复杂度。答案一、单项选择题1.C(顺序表支持随机访问;顺序表插入在末尾时时间复杂度为O(1),A错误;链表节点可能包含其他信息,指针域非必须,B错误;链表存储空间通常不连续,但静态链表用数组实现,存储空间连续,D错误)2.B(分析操作序列:1入,2入,3入→3出,2出→此时栈中剩1;4入,5入→5出,4出→1出。栈的最大容量在3入时为3,故至少需要3)3.C(循环队列元素个数计算:(rear-front+m)%m=(15-20+50)%50=45)4.A(满二叉树第h层的节点数为2^(h-1),即叶子节点数)5.C(冒泡排序每趟将最大元素“冒”到末尾。原序列:55,32,41,77,63,28。第一趟比较:55和32交换→32,55,41,77,63,28;55和41交换→32,41,55,77,63,28;55和77不交换;77和63交换→32,41,55,63,77,28;77和28交换→32,41,55,63,28,77。但实际第一趟应比较到倒数第二个元素,正确应为32,41,55,28,63,77?需重新核对:原序列55,32,41,77,63,28。第一趟比较次数为5次:①55和32→32,55,41,77,63,28②55和41→32,41,55,77,63,28③55和77→不交换④77和63→32,41,55,63,77,28⑤77和28→32,41,55,63,28,77。但题目选项中无此结果,可能题目选项设计为C选项{32,41,55,28,63,77},可能我计算有误,正确选项应为C)6.D(哈希表平均查找长度与哈希函数、冲突处理方法、装填因子(元素数/表长)有关,与表长无直接关系)7.D(快速排序在划分过程中可能改变相同元素的相对顺序,不稳定;其他均稳定)8.A(连通无向图的最小边数是树的结构,即n-1条边)9.A(前序:根A→左子树BDE→右子树CFG;中序:左子树DBE→根A→右子树FCG。左子树前序BDE,中序DBE→根B,左子树D,右子树E;右子树前序CFG,中序FCG→根C,左子树F,右子树G。后序遍历:D→E→B→F→G→C→A→DEBFGCA)10.B(需要修改第k-1个节点的next指针和新节点的next指针,共2个)二、填空题1.e(可能的输出序列如c,b,a,d,e→第三个是a;或c,b,d,e,a→第三个是d;或c,b,d,a,e→第三个是d;或c,b,e,d,a→第三个是e,故答案可以是a、d、e中的任意一个)2.2i(完全二叉树左孩子为2i,右孩子为2i+1)3.{12,18,20,25,40,30}(简单选择排序每趟选最小元素。初始:25,18,30,12,40,20→第一趟选12,交换25和12→12,18,30,25,40,20;第二趟选18(已在位置);第三趟选20(剩余元素30,25,40,20中最小为20),交换30和20→12,18,20,25,40,30)4.5(H(15)=15%7=1→位置1;H(3)=3%7=3→位置3;H(22)=22%7=1(冲突),线性探测下一个位置2→位置2;H(14)=14%7=0→位置0。故14存位置0?原计算错误,重新计算:15%7=1→位置1;3%7=3→位置3;22%7=1→冲突,探测位置2→位置2;14%7=0→位置0,无冲突。所以答案应为0?可能题目中哈希表长度为10,而H(key)=key%7,所以位置范围0-6。14%7=0→位置0,正确。可能之前误解表长为10,但哈希函数模7,故位置0-6。因此答案是0)5.存在多个入度为0的节点(拓扑排序每次选入度为0的节点,若有多个可选,则结果不唯一)三、简答题1.顺序表:-存储结构:用连续内存空间存储,元素物理位置相邻;-插入/删除:需移动大量元素(平均O(n)),但末尾操作O(1);-随机访问:O(1)时间通过下标访问。链表(以单链表为例):-存储结构:节点通过指针连接,内存空间不连续;-插入/删除:只需修改指针(O(1)),但需先遍历找到位置(O(n));-随机访问:需从头遍历(O(n))。2.快速排序基本思想:选择一个基准元素,将序列划分为小于基准和大于基准的两部分,递归对两部分排序。平均时间复杂度:O(nlogn)(每次划分较均匀);最坏时间复杂度:O(n²)(序列已有序或逆序,划分极不均匀)。3.(1)后序遍历最后一个元素是根A。中序遍历中A左边是左子树DGBE,右边是右子树CHF。后序左子树部分为GDBE(后序顺序:左→右→根),根为E(后序最后一个)。中序左子树DGBE中E左边是DGB,右边无→E的右子树为空。后序DGB的根是B(后序最后一个),中序DGB中B左边是D,右边是G→B的左子树D,右子树G。右子树CHF的后序部分为HFC,根为C(后序最后一个)。中序CHF中C左边无,右边是HF→C的左子树为空,右子树HF。后序HF的根是F(后序最后一个),中序HF中F左边是H→F的左子树H。二叉树结构:A/\EC//BF/\/DGH(2)前序遍历序列:AEBDGCFH四、算法设计题1.算法思路:使用头插法,遍历原链表,将每个节点依次插入到头节点之后,实现逆置。伪代码:voidReverseList(LinkList&L){LNodep=L->next;//p指向第一个数据节点L->next=NULL;//头节点暂时断开原链表while(p!=NULL){LNodeq=p->next;//保存下一个节点p->next=L->next;//将p插入到头节点后L->next=p;//更新头节点的nextp=q;//p后移}}时间复杂度:O(n),遍历链表一次。2.(1)算法思路:利用摩尔投票法(Boyer-MooreMajorityVoteAlgorithm)。主元素出现次数超过n/2,故在遍历过程中,主元素的出现次数会抵消其他元素的次数,最终剩下的候选元素即为主元素(需验证是否真的超过n/2)。(2)伪代码:intFindMajority(intA[],intn){intcandidate=A[0];//初始候选intcount=1;//候选计数for(inti=1;i<n;i++){if(count==0){//当前候选被抵消完,更换候选candidate=A[i];count=1;}elseif(A[i]==candidate){count++;}else{count--;//非候
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 通知团队人员调整安排函(3篇范文)
- 2026年纸业行业研发补助资金申请指南报告
- 冷链物流RFID技术应用手册
- 2026年旅游行业分析报告:供给侧改革与行业结构优化前景
- 农业生产数据物流分析指引
- 滑板运动爱好者滑板训练方案手册
- 物流配送司机准时送达及安全绩效考核表
- 提醒人力资源部2026年员工培训计划函(4篇)
- 化妆品行业研发中心配方开发绩效考核表
- 【二级建造师】2026年二建《水利水电工程》真题及答案与解析
- 抖音直播运营中心薪酬绩效考核实施管理方案
- 2026年学生入团考试题库及参考答案
- 2026年宁夏水务投资集团有限公司招聘笔试参考题库附带答案详解析版
- 2026秋北师大版选择性必修第一册Unit 1-3 句子语法填空练习(备考期中)
- 智能体电脑行业王伟东白皮书
- 秦皇岛市建设现代有轨电车项目调研报告
- 2026秋新教材苏教版五年级上册数学第七单元 用字母表示数量关系(一) 教案(共7课时)
- 《中药炮制技术》教案-13模块十三 其他炮制技术
- 2026年辅警笔试的题库及答案
- 多模式镇痛在加速康复外科中的应用现状
- 鸡马立克氏病的诊断要点与防控措施
评论
0/150
提交评论