下载文档原格式
2022年西安交通大学城市学院计算机科学与技术专业《操作系统》科目期末试卷A（有答案）一、选择题1、下面关于目录检索的论述中，正确的是（）。
A.由于散列法具有较快的检索速度，因此现代操作系统中都用它来替代传统的顺序检索方法B.在利用顺序检索法时，对树形目录应采用文件的路径名，应从根目录开始逐级检索C.在利用顺序检索法时，只要路径名的一个分量名未找到，便应停止查找D.在顺序检索法的查找完成后，即可得到文件的物理地址，2、下面关于文件系统的说法正确的是（）。
A.文件系统负责文件存储空间的管理，但不能实现文件名到物理地址的转换B.在多级目录结构中，对文件的访问是通过路径名和用户目录名进行的C.文件可以被划分成大小相等的若干物理块，且物理块大小也可以任意指定D.逻辑记录是对文件进行存取操作的基本单位3、某系统中有11台打印机，N个进程共享打印机资源，每个进程要求3台打印机。
当N的取值不超过（）时，系统不会发生死锁。
A.4B.5C.6D.74、下列调度算法中，不可能导致饥饿现象的是（）。
A.时间片轮转B.静态优先数调度C.非抢占式短作业优先D.抢占式短作业优先5、下列选项中，会导致进程从执行态变为就绪态的事件是（）。
A.执行P（wait）操作B.中请内存失败C.启动I/O设备D.被高优先级进程抢占6、要保证一个程序在主存中被改变了存放位置后仍能正确地执行，则对主存空间应采用（）技术。
A.静态重定位B.动态重定位C.动态分配D.静态分配7、采用分段存储管理的系统中，若段地址用24位表示，其中8位表示段号，则允许每段的最大长度是（）。
A.224BB.216BC.28BD.232 B8、下列选项中，不是操作系统关心的主要问题的是（）。
A.管理计算机裸机B.设计、提供用户程序与计算机及计算机硬件系统的接口C.管理计算机中的信息资源D.高级程序设计语言的编译9、下列选项中，在用户态执行的是（）。
A.命令解释程序B.缺页处理程序C.进程调度程序D.时钟中断处理程序10、下列有关设备独立性的说法中，正确的是（）。
习题1一、单项选择题1. 数据结构是指（）。
A.数据元素的组织形式B.数据类型C.数据存储结构 D.数据定义2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。
A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3. 树形结构是数据元素之间存在一种（）。
A.一对一关系B.多对多关系C.多对一关系D.一对多关系4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。
for(i=1;i<=n; i++)for(j=i;j<=n; j++)x++;A.O(1) B.O() C.O(n)D.O( )5. 算法分析的目的是（1），算法分析的两个主要方面是（2）。
（1） A.找出数据结构的合理性B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性（2） A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。
（1） A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法（2）A.可行性，可移植性和可扩充性B.可行性，确定性和有穷性C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。
A.低B.高C.相同D.不好说8. 数据结构作为一门独立的课程出现是在（）年。
A.1946B.1953 C.1964 D.19689. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。
31842-2019年西安交通大学814数据结构真题回忆814.数据结构。
选择五个。
忘了-大题avIl的题告诉11个数然后进行排序求平均长度二大题哈希表公共溢出区告诉12个数然后求平均长度三(1) 写图的邻接表结构(2)对一个图进行dfs与bfs(3) prim算法四编程题将一个链表进行逆置求时间复杂空间复杂oS填空10个吧。
忘了问答题三个1、三个调度。
然后进程挂起是靠那个调度完成的为什么?2、3、忘了。
大题一(1) 用ru调度进行22个关键数的页面置换(2) 设计一个ru (用计数器和栈) 有标志位(我好像见过原题)二pv 100个学生50台计算机两个学生必须--组才能去申请一个电脑然后管理员才让他们进去。
然后上机操作操作完了要让老师检查。
然后管理员才让走。
计算机组成原理。
四道大题忘了第一道大题告诉16位指令15-11指令10-8是寻址方式7-5通用寄存器4-0是地址。
有000是一次间接寻址001 010011分布是寄存器间接寻址变址寻址相对寻址第一问指令数量寄存器数量。
还有多少种寻址方式第二问问各个寻址的范围第三问问一个指令的数据是多少。
那个画成2进制然后是相对寻址第二道大题。
10位阶补尾补各带一个符号位,第一问写正数负数的最大值最小值第二问写出x= (-23/32) *2^7与y= (23/32) *2^6第三问x+y=?第四问把第三问结果表示出来915[题型分布与分值]选择10*2判断5*2.填空5*2简答7道应该是15*2+16*1+7*4编程题15*2+10*1代码题1输入有限个xy。
xy代表二伟空间一个点，寻找-个最小矩形，包含所输入的所有点要求输出该矩形左下顶点和右上的顶点2.判断一个字符串是否是回文串(其中有空格,需要排除空格)，第一问递归解决。
第二问用栈解决3.-个无序序列，找出其中的逆序对,要求O(nlogn), 如果不能在这个时间复杂度下实现，自己写一个程序,声明其时间复杂度.大题第一个满k叉树的分支节点数为n其叶子结点满足(K-1)n+1数归法证明第二个是用队列的基本操作实现栈的push和pop后题, hash表, 10个数据，表长17,哈希函数H1(key) = key%17,冲突解决采用双重散列H2(key)= (key%7 ==0 ? 8:key%7),第一问画表，第二问求查找成功ASL还有个是.支撑树定义最小支撑树mst什么的，我不懂还有4个任务abcd,问分别用哪些数据类型可以解决，写出基本算法还有个相似二叉树算法填空题有广义表快排递归时间复杂度深度优先搜索邻接两种复杂度。
2022年西安交通大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A.60B.66C.18000D.332、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A.NB.2N-1C.2ND.N-13、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。
A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。
变邻域算法一、引言在计算机科学中，算法是解决问题的步骤或规程。
而变邻域算法是一类优化算法，其核心思想是通过在当前解的邻域中寻找更好的解来优化问题的解决方案。
本文将介绍变邻域算法的基本原理、应用以及优缺点。
二、基本原理变邻域算法是一种启发式算法，通过搜索当前解的邻域来寻找更优的解。
邻域是指当前解的一组邻近解，变换邻域是指通过改变当前解的某个部分来生成新的邻近解。
在变邻域算法中，通过不断地在邻域中搜索，直到找到满足特定条件的解为止。
三、应用领域1. 旅行商问题(TSP)旅行商问题是指在给定一系列城市和每两个城市之间的距离的情况下，寻找一条最短路径使得旅行商能够遍历每个城市并回到起点。
变邻域算法可以通过改变路径的顺序来寻找更优的解。
2. 排序问题排序问题是指将一组元素按照特定的顺序进行排列的问题。
变邻域算法可以通过交换元素的位置来寻找更好的排序。
3. 图着色问题图着色问题是指给定一个图，寻找一种方式为每个节点分配一个颜色，使得相邻节点不能有相同的颜色。
变邻域算法可以通过改变节点的颜色来寻找更好的着色方案。
四、算法步骤1. 初始化设定初始解。
2. 生成邻域根据当前解生成邻域，即生成一组与当前解相邻的解。
3. 评估邻域对生成的邻域中的每个解进行评估，计算其适应度。
4. 更新解选择邻域中具有更优适应度的解作为新的当前解。
5. 结束条件根据特定的结束条件判断是否终止算法。
五、优缺点1. 优点变邻域算法可以在较短的时间内找到相对较优的解，特别适用于求解NP难问题。
2. 缺点变邻域算法在搜索过程中可能陷入局部最优解，无法找到全局最优解。
另外，搜索过程中需要对每个解进行评估，计算适应度，计算复杂度较高。
六、总结变邻域算法是一种有效的优化算法，通过在当前解的邻域中搜索更优解来解决问题。
它在旅行商问题、排序问题和图着色问题等领域有着广泛的应用。
尽管变邻域算法存在局部最优解和计算复杂度较高的缺点，但其优点在求解NP难问题方面仍然表现出色。
求解多车型车辆路径问题的变邻域搜索算法
陈萍;黄厚宽;董兴业
【期刊名称】《系统仿真学报》
【年(卷),期】2011(23)9
【摘要】多车型车辆路径问题(FSMVRP)是车辆类型不同的车辆路径问题(VRP),基于变邻域搜索,提出一种启发式算法VNS_FSM求解FSMVRP。
该算法设计了实现变邻域搜索中的"抖动"和局部优化过程的邻域结构组合,同时,还提出了一种新的车型调整策略。
在通用的基准测试问题的实验验证了VNS_FSM算法的有效性,并给出问题G_07-G_12的正确解。
实验结果表明,VNS_FSM算法能够获得大多数测试问题的已知最好解。
与已有算法相比,VNS_FSM算法性能相当或更优。
【总页数】6页(P1945-1950)
【作者】陈萍;黄厚宽;董兴业
【作者单位】南开大学泰达学院物流管理系;南开大学现代物流研究中心;北京交通大学计算机与信息技术学院
【正文语种】中文
【中图分类】TP391.9
【相关文献】
1.大规模邻域搜索算法求解时变车辆调度问题
2.改进变邻域搜索算法求解动态车辆路径问题
3.随机需求车辆路径问题及混合变邻域分散搜索算法求解
4.混合变邻域
搜索算法求解大规模电动车辆路径优化问题5.求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法
因版权原因，仅展示原文概要，查看原文内容请购买。
求解TSP问题的几种算法比较侯淑静【摘要】The traveling salesman problem (TSP) is an important problem for the classical discrete optimization, which is very important to study the solving algorithm. After the introduction of the greedy algorithm, taboo search algorithm, simulated annealing algorithm, genetic algorithm, the author put forward the corresponding algorithm. Aiming at the four typical examples in the test base, we realized implementation of these algorithms with procedures, and the running time and the results of these algorithms are compared. The results show that the greedy algorithm can draw the solution in a short time, the taboo search algorithm and genetic algorithm have the same effect, and the results of simulated annealing algorithm is better than those of genetic algorithm.%旅行售货商问题(简称TSP )是离散优化的一个经典的重要问题，对求解算法的研究非常重要。
TSP的几种求解方法及其优缺点一、什么是TSP问题旅行商问题，简称TSP,即给定n个城市和两两城市之间的距商，要求确定一条经过各城市当且仅当一次的是短路线。
其图论描述为：给定图G= (V, A),其中V为顶点集，A 为各顶点相互连接组成的边集，设(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamihon回路，即遍历所有顶点当且仅当一次的最短距离。
旅行商问题可分为如下两类：1)对称旅行商问题3j=dji, ni, j=l, 2, 3, - , n)；2)非对称旅行商问题(dijHdji, Bi, j=1, 2, 3, - , n)o非对称旅行商问题较碓求解，我们一般是探讨对称旅行商问题的求解。
若对于城市V={V H V2, V n - , %}的一个访问顺序为T={l), b, tj, - , tj, - , tj,A其中衣v (i=l, 2, 3,・・・，□),且记t n+l=tl＞则旅行商问题的数学模型为：血工Xzr-l TSP是一个典型的组台优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中槪括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。
因此，快速、有效地解决TSP有着重要的理论价值和板高的实际应用价值。
二、主要求解方法基于TSP的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、最近台并、最近插入、晨远插入、最近添加、贪婪插入等。
但是，由于构造型算法优化质長较差，迄今为止巳开发了许多性能较好的改迸型搜索算法，主要有：1)模拟退火算法2)禁忌搜索算法3)Hopficld神经网络优化算法4)蚁群算法5)遗传算法6)混合优化策路2.1模拟退火算法方法1)编码选择：采用描述TSP解的臺常用的一种策略——路径编码。
2）SA状态产生函数的设计：对于基于站径编码的SA状态产生函数操作，可将其设计为：①互换操作（SV7AP）;②逆序操作（INV）；③插入操作仃NS）。
