电子科技历年真题-天勤2004-2011试题

号码分别填在题干的括号内，多选、少选、错选，均五分。每小题2分10分） ① ⑤ ⑤共享 ①口 ②③ ⑤将有关参数填到PCB 三、简答题（共15分）3、6；产生多少次缺页中段？并给出他们的概率。（7分） MOD (b)双向链 (d)顺序数组A[1:5，1:6]的每个元素各占5个单元，将其按行优先次序在起始地址为的连续的内存单元中，则元素A[5,5]的地址为 (c) (d) (a)， (c) (d)用孩子兄弟链表表示一棵树，若要找到结点X的第5个孩子，则只要先找到X的第1个 (a)不发生改 (b)发生改 (c)不能确定(d)以上都不 (b)直接后继结点的地(c)链表首结点的地 (d)链表 (b)求最短路径的弗洛伊德算(c)广度优先搜索算 (d)深度优先搜索算 (a) (b) (c) (d) 4，，7，2，13，6六、综合应用题（6分电子科技大学2004年攻读入学试题注意：全部答案要求写在答题纸上，写在本试卷上无效。（75分如果从无向图G的任何一个顶点出发进行一次深度优先搜索可以图的每 B.连通C.有回路的 D. 2k+1- 2k- 2k-1- B.中序遍C.后序遍 D.层次遍 B.BFS算C.最短路径Dijkstra算 D.DFS算 B.直接选择排C.归并排 D.快速排对包含N个元素的散列表进行查找，平均查找长度 2为 B.为2C.不直接依赖于 D.上述三者都不 B.快速排C.选择排 D.归并排 B.中序遍历算C.后序遍历算 D.层次遍历算 B.克鲁斯（Kruskal）算C.弗洛伊德（Floyed）算法 D.拓扑排序（Topologicalsort）算法二、填空题（每空1分，共12分） 结构，可以性表的位置插入和删除元素而栈只能在 插入和删除元素对于列队只能在 入元素、在 n个值构造哈夫曼树，经过 设图中顶点数为n，则其生成树有 条边；若图的边数大于n-1，则一定 图。若图的边数小于n-1，则一定是 DFSBFS遍历各采用什么样的数据结构来暂存顶点？当要求连通图的生成树的线性表有哪两种结构？在这两种结构中元间的逻辑关系分别是通过栈图11任意两个顶点ij四、算法题：（共19分）有相同结构的链表AC，其中C的结点是原A中结点值为偶数的结点。要求利ODD(p↑.data)pdata是否为奇数，是则返回true（9分）PROC 利用两个栈S1和S2模拟一个队列，该队列如下图所示，试写出队空和队满 并编写出队列的插入add和删除delete运算（10分）- PROCENDP；PROCdelete(var第二部分作系统（75分设有n个进程共用一个相同的程序段（临界区如果每次最多允许m个进程（m≤n） A. B. D.– B.宏观上并C.微观上和宏观上并 D.微观上和宏观上串 A.程序设计语 B.编译系 D.标准库程 B.执行完一条指令C.执行P操作 D.由用户态转入态 A.页式地址转 B.段式地址转 C.静态重定 D.动态重定 A.复 B.可重定位分区管 C.页 D.分区方 A.界地址保 B.程序状态保 D.存取控制表保 A.计算型作 B.终端型作 D.脱机作 B.分层结C.微内核结 D.面向对象的程序设E.客户/ B.使软件的容C.避免了编程的随意 D.仅为数据库软件开E. 时间片轮转 B.多级反馈队列调度算 C.抢占式调度算 E.高响应比优先调度算 通道能大大减少CPU对I/O的干 B.建立独立的I/O操C.在CPU和设备控制器之间才能增设通 E.I/O任务后，才向CPU B.文 C.文件描述信D.i结 E.文件物理结 ）UNIX的S 八、填空题（每小题2分，共10分）通道程序解决了I/O操作的独立性和各部件工作的 能实现CPU与通道的 其中的每一个各实现单独的一种 一个进程分配给4个页帧（下面的所有数字均为十进制数，每一项都是从0开始计数的。最页号以及每个页帧的位（R）和修改位（M）如下表所示（时间均为从进程开始到该事件之间的时钟值，而不是从事件发生到当前的时钟值（9分）RMClock一台计算机有一个cache、主器和用作虚拟器的磁盘，假设cache中的字需要20ns的定位时间；如果该字在主器中而不在cache中，则需要60ns的时间载入器中率是0.6，在该系统中一个被定位的字所需要的平均时间为多少（单位：ns）？（7分）期。假设使用简单的循环法调度，并且I/O操作可以与处理器操作。定义以下量：使用率。（9分）电子科技大学2005年攻读入学试题 ③AVL 度为3的结点数为n3，则n0与n1，n2，n3满足关系（ ③ 完全二叉树的第h层的从左到右第k个结点的编号为（ ①2h+k- ②2h- ③ ④2h-k-设T2是由树T转换得到的二叉树，则T中结点额后序序列是T2结点的 ③后序序 ③图的深度优先搜 ③双向链表 三、填空题（每空1分，共10分） 广义表A(b，A)的长度 棵设二叉排序树T中各结点关键字互不相同，x↑是T的叶结点且是双亲y↑的右孩子，试y↑.keyTx↑.key的所以关键字的最大者。23时，表示相应2i的右a1，a2，a3a1<a2a36中不同的输入顺序，问其中哪几种输入顺序可以构成高度为3的二叉排序树。WHILEj<=nCANDadj[i，j]=0 IFj=n+1THENRETURN(0)ELSE函数ABC不属于DMA控制器的寄存器是 B.内存地址寄存C.数据寄存 D.堆栈指针寄存 A B C D. C.抢占式调度算 B.文C.文件物理结 D.i结下面关于UNIX系统中用户接口的描述正确的是 A 命令是用户与UNIX终端用户通过trap指令可以取得UNIX A.0 B.1 C.4 D.5 C.最先适应算 D.循环扫描 A.硬 C.应用软 D.虚拟 B.提高了系统的可扩展C.提高了操作系统的可靠 D.可运行于分布式系E. B.父进程请C.负荷调节的需 D.操作系统的需E. B.处理机利用率 C.周转时间D.各类资源的平横使 E.响应时间 5.（）UNIX系统中将空闲盘块分成组，每组用一块来记录本组的空闲盘块号，这样 主器有多种管理方式，对不同的管理方式有不同的实现保护的方法，在每个程序占 、分 操统用 来模拟 实现虚拟备必须有一定的 条件为基操系统实虚拟设的功能模块是计算机制下通过 来其的此它为 。位01104111172000-310024000-51010Request(P，Q，R)=1R22P43Q24P25R16Q27R38P29R3电子科技大学2006年攻读入学试题科目：413计算机专业基础 ① ③递 排序算法为（。 F>，<C，G>，<C，H>，<E，I>，<E，J>，<A，B>，<A，C>}，T所表示的最准确的数据结构是（） ④用行主顺序存放一维数组A，若A的下限为1，元素长度为L，则A的第i个元素的存放地址loc(Ai)为（ ③loc(A1)+i*L ④设H为结点单链表的头指针，则该表为空的条件为 ④H↑.next=设m=16，Hash函数为H(key)=(keymod13，现采用再哈希法Hi=RHi(key)处理，RHi分别为：H(key)+1，平方取中法，移位叠加法，……，问key=55的第二次地址RH2为（） ④关键字序列为为 ④ ④堆排 二、填空题（每空2分，共22分）设网中的顶点数为n，边的条数为e，则普里姆（Prim）最小生成树算法的时间复杂度 3.4.和。5.广义表难以用 算法时间复杂度，Ak[i,j]的含义和如何用该算法来判断图是否有回路.╳╳╳╳ 试分别写出哈夫曼树、完全二叉树和单枝二叉树n1的取值。四、算法题：（共13分）左孩子，2为只有右孩子，3为有左右。如下图的二叉树的结点度表示为：PROCi)入栈操作，pop(s)出栈操作函数和EMPTY(s)判栈空函数。} B.进程总共需要运行时间多C.进程自身和进程调度策 D.进程完成什么功 B.进程状态转C.进程调 D.程序被创建为进 B.索引文C.流式文 D.索引顺序文 ）UNIX系统中采用成组法便于管理一个文件占有地址空间和提高检索速度。八、填空题（每小题2分，共10分）在引入线程的O.S系统中，则把 UNIX系统，使文件描述信息单独形成一个数据结构叫 项，仅由文件名和 九、简答题（3个小题，共25分）间和平均带权周转时间（按十进制计算（8分）1234（8分MN个进程共享，进程一次只能保留或释放一个单元。如≤M说明该系统不会发生死锁。（9分）电子科技大学2007年攻读入学试题科目：413计算机专业基础(75分 ① ②队 ③十字链 ④三元在有向图G的邻接矩阵中，顶点Vi的度是 ①邻接矩阵中第i行元②邻接矩阵中第j行元 二、填空题（每空2分，共8分） 二叉树结点数n与边数e的关系 在各种查找算法中，平均查找长度与关键字个数n无关的方法 遍历算法三、判断题（212分 给定结点xm，又如何根据该编号断定x设L是不结点单链表的头指针，P是指向链表中某个结点的指针，该结点既不是第一个结点，也不是最后一个结点，S是指向待插入新结点的指针，用下面①——⑦选项完成A、B功能。在P所指结点前插入S所指结点的语句序列是 在第一个结点前面插入S所指结点的语句序列是 ①P↑.next②③④⑤WHILE（P↑.next<>Q）DO⑥S↑.next：=L↑.next；五、算法题（共15分）pp和q两者data域值较小的结点。（5分）PROCxyz（pq指针域next}m]，初始时S.rear=S.front=1.（10分）PROCRootoLeaf（bt：bitreptr（75分在UNIX中的索引结点可以看成 ③Hash文 在采用SPOOLing技术的系统中，用户的打印数据首先被送到 ④如果I/O设备与设备间的数据交换不经过CPU来完成，这种数据交换方式是 ③DMA方 分别填在题干的括号内，多选，少选，错选均无分。每小题2分，共10分） 时间，给定8位缓冲则放宽8个单位的中断响应时间。 能保证CPU的正常执行。 九、简答题（25分8.012 8.0128.20.618.40.518.6139.00.52（8分）假设一个文件系统基于索引分配策略来管理块，假设每个文件有一个项，该项可给出文件名字、第一个索引块以及文件的长度。第一个索引块最多依次指向下一个操作将逻辑块308，那么必须从磁盘中多少个物理块？解释一下您的答电子科技大学2007年攻读入学试题科目：413计算机专业基础1.②2.①3.②4.③5.④1.中序序列2.n-e=1 3.哈希查找方法4.BFS广度优先搜索1.×2. 3.×4. 5. 6.0的实际含义是不存在由顶点b：11c：1010d1011e1000000hA.在P所指结点前插入S所指结点的语句序列是（②④⑤⑥ B.在第一个结点前面插入S所指结点的语句序列是（ ⑦③ 1.②2.④3.②4.①5.③6.③7.②8.①9.③10.④1.①④ 2.①③④ 3.④⑤ 4.③⑤ 5.②④191M物理空2K10位表示位移量，所以19-10=9.8.08918.298.48.639.08-1=7电子科技大学2008年攻读入学试题科目：820计算机专业基础数据结 在具有n个顶点的图G中，若最小生成树不唯一，则 ①front= ②front=③front+1= ④rear= ①② ③④ ①L↑.next↑.next= ②L↑.next↑.next=③L↑.next= ④L↑.next= 二、填空题（每空1分，共11分） Dijkstra最短路径算法是求

在AOE网中，从源点到汇点所经过的边的权值之和的最小路径，称为 （2）对待排序关键字序列46 pak，，，，，x 结点数为T的宽度。修改下面层次遍历算法，使其能得到T的宽度。（10分） LayerOrder（bt：bitreptr[INIQUEUE(Q)；WHILENOT [p：=IFp↑.lchild≠NILTHENENQUEUE(Q，p↑.lchild)；IFp↑.rchild≠NILTHEN]]阅读下面函数ABC，该函数的功能是从顺序结构的线性表A中，删除第i个元素到确和高效。（10分）{A.length存放表长，A.elem[l..A.length]存放数据元素}IF(i＜1ORk＜0 FORcount：=1TOk[FORj：=A.lengthDOWNOTi+1DOA.elem[j-1]：=A.elem[j]；]RETURN(1)操作系统部 B.可变式管C.固定分区式管 D.段页式管 A.加 B.重定 C.置 D.程序连 文 B.文 C.文 D.索引结点中有文件的控制信 B.该程序的大小不应超过实际的内存容C.该程序应具有较好的局部 D.该程序的指令相关不应过 A.文件信 B.与主存交换信 C.地址变 D.通道程 A.顺序文 B.文 C.索引文 文 B.实现虚拟C.提高外存的读写速 D.用于系统文 A.磁盘固定区 B.内存固定区 C.终 D.支持多道程序设计的操作系统在运行过程中，不断地选择新进程来实现CPU的共享，不 B.运行进程出C.运行进程要等待某一事件的发 D.有新进程进入就绪状（则的互斥信号量的取值范围为（ A.–(N-1)~ B.–(N-M)~ C.–(N-M)~ D.–(N-1)~分别填在题干的括号内，多选、少选、错选，均无分。每小题2分，共10分） D.命令控制方E. B.顺序结 C.层次结D.索引结 E.记录结 B.减少了人工干C.提高了单位时间的处理能 D.提高了系统的吞吐 B.分层结 C.微内核结D.面向对象的程序设 E.客户/服务器模 B.多级反馈队列调度算 C.抢占式调度算D.FCFS（先来先去）调度算法 E.高响应比优先调度算法七、填空题（每空1分，共13分） 当一个进程独占处理器顺序执行时，具有两个特性：性和UNIX的s有两层含义，一层指由s命令组成的 语言；二是八、简答题（32分（10分）在一个采用页式虚拟管理的系统中，有一用户作业，它依次要的字地址序列是：115，228，120，88，446，102，321，432，260，167，若该作业的第0300100字，请回答下列86400个逻辑记录的文件，逻辑记录的大小与扇区大小不一（00KB（100KB（300KB（150KB（30KB（40KB，申请（60KB（30KBFit电子科技大学2008年攻读入学试题科目：820计算机专业基础数据结构参考答操作系统部分参考答1. 2. 3. 4. 5. 6. 7. 8. 9. 1. 2. 3. 4. 5.1.前台，2.–程序，命 3.系统，用 4.5.短， 6.封闭，可再现 7.S命令，指该命令的解八、简答题（32分ODOD或

电子科技大学2010年入学试题 B.索引文C.流式文 D.索引顺序文 A.文件是文件逻辑组织的 B.文件是以空间交换时C.文件不适合随机存 D.文件是索引结 B.联机用C.操作系 D.目标程 B.按记录关键字顺序查 A.文件信 B.实现虚拟管C.地址变 D.通道程 B.分区管C.页式管 D.可重定位管 B.实现虚拟C.提高外存的读写速 D.用于系统文 B.提高CPU的利用C.充分利用O/I设 D.充分利用磁 A.结 B.顺序结C.层次结 D.树型结分别填在题干的括号内，多选、少选、错选，均无分。每小题2分，共10分） B.用户不知道，系统也不知C.虚拟设备与物理设备有 D.用户不知道，系统知E.SPOOLING LRU算 B.中断请求调 C.预调页技D.clock算 E.FIFO算）A.C.B.D.E. B.系统调 C.作业控制语D.软中 E.通过应用软件提供服 B.多级反馈队列调度算 C.抢占式调度算D.FCFS（先来先服务）调度算法 E.高响应比优先调度算法三、判断并改错（每小题2分，共14分） ）通道接到CPU令后，通过执行通道程序便可完成CPU指定的I/O任务。四、简答题（共31分）1.（10分）在虚拟管理系统中，假设快表中的页需要20ns的定位时间；如果该页在主器中不在快表中，则需要60ns的时间载入快表，然后再开始重新定位；如果该到快表中，然后才开始定位。快表中率是0.9，主器中率是0.6，在该系15234239数据结构（75分 ①有限序列，可以为 ②有限序列，不能为③无限序列，可以为 ④无序序列，不能为 ①快速排 ②冒泡排③希尔排 ④堆排 ①必须连 ②一定不连③部分地址必须连 ④连续与否无所能正确完成删除单链表中p所指结点的后继操作是 ①p=p->next ③p- ④p=p->next- ①哈希函数是否均 ②处理范围的方③哈希表的装填因 ④缩小查找范围的大 ① ③ ④ ①非叶结点的度均为 ②查找性能为顺序查③顺序时占用空间最 ④数的深度与等于结点个 ①满二叉树 ②完全二叉③哈夫曼 ④二叉排序 ②从源点到汇点的最短路③最长的回路 ④最短的回路二、填空题（每空1分，共10分） 广义表L=（a，（b，c），e，（d），（））的长度是、深度是 三、简答题（每小题5分，共35分）对通网，用迪杰斯特拉算法求得指定顶点到其他n-1个顶点之间的最短路径，由四、算题（每小题10分，共20分）度大于1，结点指针域为next，试编写算法，完成删除p所指结点的前趋结点。n电子科技大学2010年入学试题 1. 数据结构参考答 1.取值赋 2. 3.极 4.队 5.动态查找 6.取尾7.链队 8. 2：将二叉排序树的所有左右子树交换，然后用中序遍历算法遍历，所输出的结答：013510∞∞3∞045∞40{（V1，V2（V1，V3（V3，V4）}代价为1+3+4=8，所以说说法是错误的。即所谓无向图G的最小生成树T就是将G中各结点间的最短路径作为边所构造出来的G的子图是不对的。关键在定位，必须是p的前趋的前趋；DelPrior(LinkListp){ }1：073592：704263：340264：522045：966406：99674村庄1、2、5、6均为9，村庄47.初始化Maxmin=极大值；Node=V1；Fori=1ton{Vi为源点求到其他顶点的最短路径（调迪杰斯特拉算法将Vi置为被处理；S置为空；ifMax>MaxMin将S集中的顶点置为被处理；}}电子科技大学2011年入学试题 B.链式结C.索引结 D.散列结 B.单链C.单向循环链 D.双向链 A. B. C. D.(n+1)（1，2，3（1，6，1（3，1，5（3，2，-5，4（，1，- A. B. C.（3，2，- D.（2，3，- A.n- C.2n- D. B Cn- Dn+1 B.二叉排序 C.二叉平衡 B.希尔排序 C.归并排序 二、填空题（每小题1分，共8分）（n=3720n+4nlogn 在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数 广义表A=(a，(b)，()，(c，d，e))的长度 已知某二叉树的先序序列为ABDECF，中序序列为DBEAFC，则其后序序列为。 在以{4,5,6,7,8}作为叶子结点权值构造的二叉树中，其带权路径长度最小的 用DijkstraV1到其余各顶点的最短路径，按求解过程依次写出各已知图G的结构如下。假设对其时每行元素必须从右到左，请写出从V1开始 选取散列函数H(key)=(key)%11，用线性探测法处理，对下列关键码序四、算法题（23分1.（6分）阅读算法test01，说明其功能。inttest01(inta[],intlow,inthigh,intx){intI,j,t;while(i<j&&a[j]>=x)j--;}elsereturni-1;} structcharstructnode*root){if(root){}}75 B.多道批处理系C.计算机网 D.实时信息处理系 B.处理器C.计算机硬件和用 D.计算机硬件和软件之 I进程与进 III处理机与通 IV设备与设A.I、II和 B.I、II和C.I、III和 进程具有3中基本状态：就绪状态、执行状态和阻塞状态。进程在执行过程中，其状态 B.比自己级别高的中断事C.与中断标志相对应的事 D.比自己级别低的中断事 B.物理映C.地址映 D.逻辑地址映 B.成反C.无 D.