下载文档原格式
2022年复旦大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。
A.5B.6C.8D.92、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A.NB.2N-1C.2ND.N-13、线性表的顺序存储结构是一种（）。
A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。
A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、在下述结论中，正确的有（）。
①只有一个结点的二叉树的度为0。
②二叉树的度为2。
③二叉树的左右子树可任意交换。
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③B.⑦③④C.②④D.①④9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。
2022年复旦大学数据科学与大数据技术专业《计算机系统结构》科目期末试卷B(有答案）一、选择题1、IBM360/91属于（）A.向量流水机B.标量流水机C.阵列流水机D.并行流水机2、指令间“一次重叠”说法有错的是( )A.仅“执行k”与“分析k+1”重叠B."分析k”完成后立即开始“执行k”C.应尽量使“分析k+1”与“执行k”时间相等D.只需要一套指令分析部件和执行部件3、不同系列的机器之间，实现软件移植的途径不包括（）。
A.用统一的高级语言B.用统一的汇编语言C.模拟D.仿真4、输入输出系统硬件的功能对（）是透明的。
A.操作系统程序员B.应用程序员C.系统结构设计人员D.机器语言程序设计员5、推出系列机的新机器，不能更改的是（）。
A.原有指令的寻址方式和操作码B.系统总线的组成C.数据通路宽度D.存储芯片的集成度6、对系统程序员不透明的应当是( )。
A.Cache存贮器XB.系列机各档不同的数据通路宽度C.指令缓冲寄存器D.虚拟存贮器7、全相联地址映象是指（）。
A.任何虚页都可装入主存中任何实页的位置B.一个虚页只装进固定的主存实页位置C.组之间是固定的，而组内任何虚页可以装入任何实页位置D.组间可任意装入，组内是固定装入8、若输入流水线的指令既无局部性相关，也不存在全局性相关，则（）。
A.可获得高的吞吐率和效率B.流水线的效率和吞吐率恶化C.出现瓶颈D.可靠性提高9、微指令由（）直接执行。
A.微指令程序B.硬件C.汇编程序D.编译程序10、传统机器语言机器级，是用（）来（）机器指令。
A.硬件，翻译B.编译程序，翻译C.微指令程序，解释D.微指令程序，翻译二、填空题11、Cache存贮器采用组相联的映象规则是组间________映象，组内各块间________映象。
12、层次存储系统的设计的目的是使有效存取时间接近于________的存取时间，使总体的平均每字成本接近于________的每字成本，容量接近于最大存储器的容量。
![[考研类试卷]计算机专业基础综合数据结构(排序)历年真题试卷汇编9.doc](https://img.taocdn.com/s1/m/20c93de3011ca300a7c39083.png)
[考研类试卷]计算机专业基础综合数据结构（排序）历年真题试卷汇编9一、综合题1 如果只要找出一个具有n个元素的集合的第k(1≤k≤n)个最小元素，你所学过的排序方法中哪种最适合?给出实现的思想。
【北方交通大学1998六(10分)】2 设结点个数为n，请问采用堆排序法进行排序，其时间复杂性是多少?请以大O 形式给出，并给出证明。
【上海交通大学2004四(10分)】2 已知待排序的序列为(503，87，512，6l，908，170，897，275，653，462)，试完成下列各题。
3 根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。
4 输出最小值后，如何得到次小值(并画出相应结果图)。
【同济大学2001二(10分)】4 试将关键字序列(56，塾，55，67，46，58，18，88)5 调整成一个初始大顶堆，用二叉树形式说明调整过程；6 简要说明如何从初始大顶堆开始进行排序。
【华中科技大学2007四、24(10分)】7 一组记录的关键字为(50，79，8，56，32，41，85)，给出利用重建堆方法建立的初始堆(堆顶最大)，并给出堆排序的过程。
【吉林大学2007二、5(4分)】8 已知序列{503，87，512，61，908，170，897，275，653，462)将其调整为堆(大堆顶，即K i≥K2i，K i≥K2i+1)。
【中国海洋大学2006一、4(8分)】9 给定关键字序列(20，18，9，86，72，12，27，40)。
试将该序列建成小根堆。
10 判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。
①100，90，80，60，85，75，20，25，10，70，65，50②100，70，50，20，90，75，60，25，10，85，65，80【复旦大学1997二(8分)】11 全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。
中科院计算机技术研究所1995年硕士生入学试题程序设计一.选择1.一棵深度为6的平衡二叉树,其每个非终端结点的平衡因子均为1,则该树共有_ d _个终端结点.(2分)a.14b.16c.18d.20e.22f.242.一个有18条边的非连通无向图,至少应有_c_个结点.(2分)a.6b.7c.8d.9e.10f.113.一棵124个叶结点的完全二叉树,最多有_ a _个结点.a.247b.248c.249d.250e.251(2分)4.按锦标赛排序的方法，决定出8位运动员之间的名次顺序排列,至少需编排e __场次的比赛.(考虑最坏)a.13b.14c.15d.16e.17(2分)5.已知Head(Tail([Head(S),Head(Tail(Tail(S))]))广义表满足上式,则S为_ d __.a.[[a,b],b,a]b.[[b,a],[a],[b]]c.[[a],[a,b],[b]]d.[b,[a],[a,b]]e.[[a],[b],[b,a]]f.[[b],[b,a],[a]](其中,方括号表示广义表,圆括号表示函数,Head()表示取广义表的头部)(2分)6.在下列三种次序的线索二叉树中,_ c __对查找指定结点在该次序下的后继效果较差.(2分)a.前序线索树b.中序线索树c.后序线索树7.由二叉树的前序和后序遍历序列_ b __唯一地确定这棵二叉树.(2分)a.能b. 不能8.在下列两种求图的最小生成树的算法中, b __算法最适合于求边稀疏的网的最小生成树(2分)a.Primb.Kruskal9.下列无向图的存储结构中,在对无向图的边进行操作时,(如删除一条边)_ b __存储结构更为适合.a.邻接表b.邻接多重表.10.在下述几种树当中, a __可以表示静态查找表.a.次优查找树;b.二叉排序树;c.B-树d.平衡二叉树11(1).在文件局部有序或文件长度较小的情况下,最优内部排序的方法是_A_1_.(2).快速排序在最坏的情况下,时间复杂度是_B2__,_C_1_的性能差;(3)就平均时间而言,_D_2_最佳.A.: (1)直接插入排序 (2)起泡排序 (3)简单选择排序;B.: (1)O(nlog(n)) (2)O(n^2) 3.O(n^3)C.: (1)堆排序 (2)起泡排序 (3)选择排序.D.:(1)堆排序 (2)快速排序 (3) 归并排序.12.一程序规定的职能是"输入三个整数作为三边的边长构成三角形,判别是等腰三角形,等边三角形,或是一般三角形.再做计算..."若用等价类划分方法对该程序作功能测试,至少应对该程序的输入数据考虑_A_个等价类,其中包括_B_个有效等价类和_C_个无效等价类.A.___B.___C.___(1)3; (2)5; (3)7; (4)12; (5)15; (6) 18; (7)21; (8)25; (9)33; (10)40;13.设二叉树如图所示:1.给出先序遍历的结点,访问顺序________.2.给出中序遍历的结点,访问顺序________.3.给出后序遍历的结点,访问顺序________.4.若用二叉链表作为存储结构,将出现多少个空指针域?_ n+1_ (共四分)14.下列函数function calc(x,y :integer): integer;beginif y=1 then calc:=xelse calc:=calc(x,y-1)+xend;a,b均为正整数,则 calc(a,b)= 2___.(1).a*(b-1)(2).a*b(3)a+b(4)a+a15.程序段read(a,b);c:=3.0*a+b;if c=0 then a:=1else a:=1.0+1.0/c+1.0/b;保证该程序段运行不出错的必要条件是:_ 3__(1).b>0;(2).a>0 and b>0;(3).b!=0;(4).b!=0 and c!=0;二.程序改错与填空:1.指出下列程序段中的错误位置,对错误编号说明理由:程序段1:(8分)Label 1:const max=50;type day={Mon,Tue,Wed,Thu,Fri,Sat,Sun};var date:day;N:integer;begina: N:=N-ord('0');b: for date:=Mon to Sun doN:=ord(succ(date))-1c: for n:=1 to 10 dobegin......1:语句;end;......goto 1;......end.答:__________________________.程序段二.(8分)Program type(input,output);var R:real;Procedure print(var x:integer,y:real);var z:real;Procedure sum(x:integer; y:real);var k:real;beginz:=x+y;k:=3*z;x:=x+y;end;{sum}beginsum(x,y);writeln(x,y,z,k);end;{print}beginreadln(R);print(15,R);print(R,R)end.{main progam}2.阅读下列程序,填空使之成为一个完整的程序: 该程序输出N个元素的全排列.程序:program pic(input,output);const n=10;var A:array[1..n] of integer;i,k:integer;procedure output1;beginfor i:=1 to n dowrite(A[i]:3);writeln;end{output1}procedure permute(k:integer);var i,t:integer;beginif k=1 then output1else begin________;for i:=1 to ___dobeginT:=A[k];A[k]:=A[i];A[i]:=T;____________;T:=_________;____________;end;end;end;{permute}beginK:=n;for i:=1 to k do A[i]:=i;permute(k);end.三.编程题:(语言任选)1.(15分)编写程序将一个循环队列的内容倒置,该循环队列存储在一个数组A[1..n] 中,例如图a中为倒置前的队列,图b中为倒置后的队列.要求倒置后的队列从数组的第一个元素开始,整个程序的运行时间为O(n).2.设计一个程序,使输入的句子按如下方式改造后输出:(1).单词之间只留一个空格作间隔;(2).句子结束后必须紧跟句号;(3).如果把句子的单词从左到右依次编号为1,2,3...,则对于第奇数个单词,只要直接复制就行了,而对于第偶数个单词,应按反序打印.。
一、单项选择题：1-40题,每题20分共80分;在每个小题给出的四个选项中选正确答案;1、若元素a、b、c、d、e、f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈工作,则不可能得到的出栈序列是A、dcebfaB、cbdaefC、bcaefdD、afedcb2、某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,则不可能得到的顺顺序是A、bacdeB、dbaceC、dbcaeD、ecbad3、下列线索二叉树中用虚线表示线索,符合后序线索树定义的是4、在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树,在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的关键字分别是A、13,48B、24,48C、24,53D、24,905、在一棵度数为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶结点个数是A、41B、82C、113D、1226、对nn>=2个权值均不相同的字符构成哈弗曼树,关于该树的叙述中,错误的是A、该树一定是一棵完全二交叉B、树中一定没有度为1的结点C、树中两个权值最小的结点一定是兄弟结点D、树中任一非叶结点的权值一定不小于下一层任一结点的权值7、若无向图G=中含7个顶点,则保证图G在任何情况下都是连通的,则需要的边数最少是A、6B、15C、16D、218、对下图进行拓扑排序,可以得到不同的拓扑序列的个数是A、4B、3C、2D、19、已知一个长度为16的顺序表L,其元素按关键字有序排列,若采用折半查找法查找一个不存在的元素,则比较次数最多的是A、4B、5C、6D、710、采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是A、递归次数于初始数据的排列次数无关B、每次划分后,先处理较长的分区可以减少递归次数勤思考研C、每次划分后,先处理较短的分区可以减少递归次数D、递归次数与每次划分后得到的分区处理顺序无关11、对一组数据2,12,16,88,5,10进行排序,若前三趟排序结果如下：第一趟：2,12,16,5,10,88第二趟：2,12,5,10,16,88第三趟：2,5,10,12,16,88则采用的排序方法可能是A.冒泡排序法B.希尔排序法C.归并排序法D.基数排序法12.下列选项中,能缩短程序执行时间的措施是1.提高CPU时钟频率2.优化通过数据结构3.优化通过程序A.仅1和2B.仅1和3C,仅2和3,2,313.假定有4个整数用8位补码分别表示r1=FEH,r2=F2H,r3=90H,r4=F8H,若将运算结果存放在一个8位寄存器中,则下列运算会发生益处的是A. r1 x r2B. r2 x r3C. r1 x r4D. r2 x r414.假定变量i,f,d数据类型分别为int, float, doubleint用补码表示,float 和double用IEEE754单精度和双精度浮点数据格式表示,已知i=785,f=,d=,若在32位机器中执行下列关系表达式,则结果为真的是I i==intfloatIIIf==floatintfIIIf==floatdoublefIVd+f-d==fA. 仅I和IIB. 仅I和IIIC. 仅II和IIID. 仅III和IV15.假定用若干个2K x 4位芯片组成一个8K x 8为存储器,则0B1FH所在芯片的最小地址是16.下列有关RAM和ROM得叙述中正确的是I RAM是易失性存储器,ROM是非易失性存储器II RAM和ROM都是采用随机存取方式进行信息访问III RAM和ROM都可用做CacheIV RAM和ROM都需要进行刷新A. 仅I和IIB. 仅II和IIIC. 仅I ,II, IIID. 仅II,III,IV17.下列命令组合情况,一次访存过程中,不可能发生的是未命中,Cache未命中,Page未命中未命中,Cache命中,Page命中命中,Cache未命中,Page命中命中,Cache命中,Page未命中18.下列寄存器中,反汇编语言程序员可见的是A.存储器地址寄存器MARB.程序计数器PCC.存储区数据寄存器MDRD.指令寄存器IR19.下列不会引起指令流水阻塞的是A.数据旁路B.数据相关C.条件转移D.资源冲突20.下列选项中的英文缩写均为总线规范的是A. PCI、CRT、USB、EISAB. ISA、CPI、VESA、EISAC. ISA、SCSI、RAM、MIPSD. ISA、EISA、PCI、PCI-Express21、单级中断系统中,中断服务程序执行顺序是I保护现场II开中断III关中断IV保存断点V中断事件处理VI恢复现场VII中断返回A、I->V->VI->II->VIIB、III->I->V->VIIC、III->IV->V->VI->VIID、IV->I->V->VI->VII22、假定一台计算机的显示存储器用DRAM芯片实现,若要求显示分辨率为16001200,颜色深度为24位,帧频为85HZ,现实总带宽的50%用来刷新屏幕,则需要的显存总带宽至少约为A、245MbpsB、979MbpsC、1958MbpsD、7834Mbps23、下列选项中,操作S提供的给应程序的接口是A、系统调用B、中断C、库函数D、原语24、下列选项中,导制创进新进程的操作是I用户登陆成功 II设备分配 III启动程序执行A、仅I和IIB、仅II和IIIC、仅I和IIID、I、II、III25、设与某资源相关联的信号量初值为3,当前值为1,若M表示该资源的可用个数,N表示等待该资源的进程数,则M,N分别是A、0,1B、1,0C、1,2D、2,026、下列选项中,降低进程优先权级的合理时机是A、进程的时间片用完B、进程刚完成I/O,进入就绪列队C、进程长期处于就绪列队D、进程从就绪状态转为运行状态27、进行PO和P1的共享变量定义及其初值为booleam flag2;int turn=0;flag0=false; flag1=false;若进行P0和P1访问临界资源的类C代码实现如下：void p0 33KBB. 519KBC. 1057KBD. 16513KB31. 设当前工作目录的主要目的是A. 节省外存空间B. 节省内存空间C. 加快文件的检索速度D. 加快文件的读写速度32.本地用户通过键盘登陆系统是,首先获得键盘输入信息的程序时A. 命令解释程序B. 中断处理程序C. 系统调用程序D. 用户登录程序33. 下列选项中,不属于网络体系结构中所描述的内容是A.网络的层次B.每一层使用的协议C.协议的内部实现细节D.每一层必须完成的功能34.在下图所表示的采用”存储-转发”方式分组的交换网络中所有的链路的数据传输速度为100Mbps,分组大小为1000B,其中分组头大小为20B若主机H1向主机H2发送一个大小为980000的文件,则在不考虑分组拆装时间和传播延迟的情况下,从H1发送到H2接受完为止,需要的时间至少是B.C.D.35.某自治系统采用RIP协议,若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量中包含的信息<net1,16>,则可能得出的结论是A. R2可以经过R1到达net1,跳数为17B. R2可以到达net1,跳数为16C. R1可以经过R2到达net1,跳数为17不能经过R2到达net136.若路由器R因为拥塞丢弃IP分组,则此时R可向发出该IP分组的源主机的ICMP报文件的类型是A. 路由重定向B. 目的不可达C. 源抑制D. 超时37、某网络的IP地址空间为/24采用长子网划分,子网掩码为,则该网络的最大子网个数、每个子网内的最大可分配地址个数为A、32,8B、32,6C、8,32D、8,3038、下列网络设备中,能够抑制网络风暴的是I中断器II集线器III网桥IV路由器A、仅I和IIB、仅IIIC、仅III和IVD、仅IV39、主机甲和主机乙之间建立一个TCP连接,TCP最大段长度为1000字节,勤思考研若主机甲的当前拥塞窗口为4000字节,在主机甲向主机乙连续发送2个最大段后,成功收到主机乙发送的第一段的确认段,确认段中通告的接收窗口大小为2000字节,则此时主机甲还可以向主机乙发送的最大字节数是A、1000B、2000C、3000D、400040、如果本地域名服务无缓存,当采用递归方法解读另一网络某主机域名时,用户主机本地域名服务器发送的域名请求条数分别为A、1条,1条B、1条,多条C、多条,1条D、多条,多条二、综合应用题：41-47小题,共70分41.10分将关键字序列7、8、30、11、18、9、14散列存储到散列表中,勤思考研散列表的存储空间是一个下标从0开始的一个一维数组散列,函数为：Hkey=key x 3MODT,处理冲突采用线性探测再散列法,要求装载因子为问题：1.请画出所构造的散列表;2.分别计算等概率情况下,查找成功和查找不成功的平均查找长度;42.13分设将nn>1个整数存放到一维数组R中;设计一个在时间和空间两方面尽可能高效的算法;将R中的序列循环左移P0<P<n个位置,即将R中的数据由X0, X1, ……Xn-1变换为Xp, Xp-1 …Xn-1,X0, X1……Xp-1要求：1、给出算法的基本设计思想;2、根据设计思想,采用C或C++或JAVA语言描述算法,关键之处给出注释;3、说明你所设计算法的时间复杂度和空间复杂度;43、11分某计算机字节长为16位,主存地址空间大小为128KB,按字编址;采用字长指令格式,指令名字段定义如下：1512 116 50源操作数目的操作数转移指令采用相对寻址,相对偏移是用补码表示,寻址方式定义如下：注：X表示有存储地址X或寄存器X的内容,请回答下列问题：1、该指令系统最多可有多少指令该计算机最多有多少个通用寄存器勤思教育存储地址寄存器MAR和存储数据寄存器MDR至少各需多少位2、转移指令的目标地址范围是多少3、若操作码0010B表示加法操作助记符为add,寄存器R4和R5得编号分别为100B 何101B,R4的内容为1234H,R5的内容为5678H,地址1234H中的内容为5678H,5678H中的内容为1234H,则汇编语言为addR4,R5 逗号前为源操作符,逗号后目的操作数对应的机器码是什么用十六进制该指令执行后,勤思教育哪些寄存器和存储单元的内容会改变改变后的内容是什么44、12分某计算机的主存地址空间大小为256M,按字节编址;指令Cache分离,均有8个Cache行,每个Cache行大小为64MB,数据Cache采用直接映射方式,勤思教育现有两个功能相同的程序A和B,其伪代码如下：程序A:int a256256; ......int sum_array1{int i, j, sum = 0;for i = 0; i < 256; i++ for j= 0; j < 256; j++ sum += aij;return sum;}程序B:int a256256; ......int sum_array2{int i, j, sum = 0;for j = 0; j < 256; j++ for i= 0; i < 256; i++ sum += aij;return sum;}假定int类型数据用32位补码表示,程序编译时i,j,sum均分配在寄存器中,数组a按行优先方式存放,其地址为320十进制;请回答,要求说明理由或给出计算过程;1、若不考虑用于Cache一致维护和替换算法的控制位,则数据Cache的总容量为多少2、数组元素a031和a11各自所在的主存块对应的Cache行号分别是多少Cache 行号从0开始3、程序A和B得数据访问命中率各是多少哪个程序的执行时间短45、7分假设计算机系统采用CSCAN循环扫描磁盘调度策略,使用2KB的内存空间记录16384个磁盘的空闲状态1、请说明在上述条件如何进行磁盘块空闲状态的经管;2、设某单面磁盘的旋转速度为每分钟6000转,勤思教育每个磁道有100个扇区,相临磁道间的平均移动的时间为1ms.若在某时刻,磁头位于100号磁道处,并沿着磁道号增大的方向移动如下图所示,磁道号的请求队列为50,90,30,120对请求队列中的每个磁道需读取1个随机分布的扇区,则读完这个扇区点共需要多少时间需要给出计算过程;46.8分设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址;勤思教育某进程最多需要6页数据存储空间,页的大小为1KB,操作系统采用固定分配局部置换策略为此进程分配4个页框;页号页框号装入时间访问位0 7 130 11 4 230 12 2 200 13 9 160 1当该进程执行到时刻260时,要访问逻辑地址为17CAH的数据;请回答下列问题：1、该逻辑地址对应的页号时多少2、若采用先进先出FIFO置换算法,该逻辑地址对应的物理地址要求给出计算过程;3、采用时钟Clock置换算法,该逻辑地址对应的物理地址是多少要求给出计算过程;设搜索下一页的指针按顺时针方向移动,且指向当前2号页框,示意图如下47、9分某局域网采用CSMA/CD协议实现介质访问控制,数据传输率为100M/S,主机甲和主机已的距离为2KM,信号传播速速时200000M/S请回答下列问题,并给出计算过程;1、若主机甲和主机已发送数据时发生冲突,则从开始发送数据时刻起,到两台主机均检测到冲突时刻为止,最短经过多长时间最长经过多长时间假设主机甲和主机已发送数据时,其它主机不发送数据2、若网络不存在任何冲突与差错,主机甲总是以规范的最长以太数据帧1518字节向主机已发送数据,主机已每成功收到一个数据帧后,立即发送下一个数据帧,勤思教育此时主机甲的有效数据传输速率是多少不考虑以太网帧的前导码答案1-5 D C B C B6-10 A A B A D11-15 A D C B D16-20 A D B A D21-25 A D A C B26-30 A A B B C31-35 C B C A A36-40 C B C A A41、1因为装填因子为,数据总数为7,所以存储空间长度为L = 7/ = 10因此可选T=10,构造的散列函数为Hkey = key3 MOD 10线性探测再散列函数为：Hi = Hkey+ di MOD 10 , di = 1,2,3 (9)因此,各数据的下标为H7 = 73 MOD 10 = 1H8 = 83 MOD 10 = 4H30 = 303 MOD 10 = 0H11 = 113 MOD 10 = 3H18 = 183 MOD 10 = 4H1 = H18 +1 MOD 10 = 5H9 = 93 MOD 10 = 7H14 = 143 MOD 10 = 2所构造的散列表如下：2查找成功的平均查找长度为：ASL1 = 1+1+1+1+2+1+1/7 = 8/7查找不成功的平均查找长度为：ASL2 =7+6+5+4+3+2+1+2+1+1 =42、1建立一个可以放下p个整数的辅助队列,将数组R中的前p个整数依次进入辅助队列,将R中后面的n-p个整数依次前移p个位置,将辅助队列中的数据依次出队,依次放入R中第n-p个整数开始的位置;2使用c语言描述算法如下：void Shiftint pR, int n, int p 题思路：1cache总容量等于cache每一行的容量乘以cache的行数;大家需要注意的是,本题cache总容量分别等于数据cache和指令cache的总和;2分别计算出A031A11的地址的值,然后根据直接映射方式除以cache行的大小,与cache行数求余,所得的余数就是所映射的cache块;3cache的命中率等于访问cache的次数除以cache的次数加上访问内存的次数;本题通过计算得知,命中率高的计算速度快;45、12KB = 210248bit = 16384bit;因此可以使用位图法进行磁盘块空闲状态经管,每1bit表示一个磁盘块是否空闲;2每分钟6000转,转一圈的时间为,通过一个扇区的时间为;根据CSCAN算法,被访问的磁道号顺序为100 à120 à 30à 50 à 90,因此,寻道用去的总时间为：20 + 90 + 20 + 40 1ms = 170ms总共要随机读取四个扇区,用去的时间为： + 4 = = 所以,读完这个扇区点共需要 170ms + = ;46、117CAH 转换为二进制为：0001 0111 1100 1010, 页的大小为1KB,所以页内偏移为10位,于是前6位是页号,所以其页号为0001 01,转换为10进制为5,所以,17CA对应的页号为5;2若采用先进先出置换算法,则被置换出的页号对应的页框号是7,因此对应的二进制物理地址为：0001 1111 1100 1010,转换为16进制位的物理地址为1FCAH;3若采用时钟算法,且当前指针指向2号页框,则第一次循环时,访问位都被置为0,在第二次循环时,将选择置换2号页框对应的页,因此对应的二进制物理地址为：0000 1011 1100 1010,转换为16进制物理地址为0BCAH;47、1当甲乙两台主机同时向对方发送数据时,两台主机均检测到冲突的时间最短：Tmin = 1KM/200000KM/S2 = 10us当一台主机发送的数据就要到达另一台主机时,另一台主机才发送数据,两台主机均检测到冲突的时间最长：Tmax = 2KM/200000KM/S2 = 20us2主机甲发送一帧数据所需的时间为：T1 = 1518B/10Mbps =数据在传输过程中所需的时间：T2 = 2KM/200000KM/S =因此,主机甲的有效数据传输速率为：V= 10MbpsT1/T1+T2 = 10Mbps+ =。
数据结构试卷（一）王彬一、单选题（每题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(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
cA．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：____ ____、________、________和_______。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
