数据结构(50分） 一。（15分）
回答下列各题，并简要说明理由，每题3分
1。 什么是线形表？线形表的各元素类型是否必须是同一类型？为什么？ 2。线形表有两种不同的继承形式，顺序的和链接的存储结构， 在使用时，如何确定使用哪种存储结构？
3。给出一个二叉树的前序和中序遍历序列，要求写出后序遍历序列。 4。（记不清楚具体数字了，大概的数字把）
一个文件用B+树做索引，给定文件大小2000000 B，每个页块大小为4000 B, 每个指针大小为5 B。每个记录是200 B,其中关键码为5 B. 问:
1）应采用多少阶B+树? 2)该文件索引块数目。
5。下列哪些可以做Hash函数？哪些效果不好？哪些效果好？
其中，n为Hash表的表长；Random(n)可以产生一个0---n=1 的随机数； p(n)为小于n的最大素数。 1）Hash(key) = key/n; 2) Hash(key) = 1;
3) Hash(key) = (key + Random(n)) % n; 4) Hash(key) = key % p(n); 二。（5分）
证明:一棵二叉树的前序，中序，后序遍历序列中，叶结点的相对位置是不变的 三。（15分）
1） 给定一组关键码，要求依次插入建立一棵AVL树，大约12个关键码左右， （和03年那个真题只是关键码的不同）
需要旋转的时候，要求标出旋转的类型:左单旋，右单旋，先左后右双旋，先右后 左双旋。
2）在建成的这棵AVL树上，依次删除关键码****（四个），要求: 如果需要旋转，那要标出旋转类型；用中序的直接前驱代替关键码 四。（15分）
1）将书上284页的Dijkstra算法挖去5个空，让添。（5分） 具体字母有差别，但是确实就是那个算法，我按照书上的来了。 void ShortestPath(Graph for (int i = 0; i < n; i++){ //n为图的顶点数目 dist = Edge[v]; s = 0; if (i != v && dist < MaxNum) 1空; else path = -1; } s[v] = 1; dist[v] = 0; for (int i = 0; i < n - 1; i++){ float min = MaxNum; int u = v; for (int j = 0; j < n; j++){ if( 2空 && dist[j] < min){ u = j; min = dist[j]; } } } 3空； for (int w = 0; w < n; w++){ if( 4空 && Edge[w] < MaxNum && dist + Edge[w] < dist [w]){ dist[w] = dist + Edge[w]; 5空； } } } 2）（10分） 定义了一个Max{***********}，即顶点i到其余各顶点的最短路径的最大值， 让写一个算法求 这个Max{***********}的最小值。 操作系统 1.反置页表原理,同样的逻辑地址空间,主存空间,用一般的页表和反置页表各需要多少项. (反置的表项是以主存空间来分的;比一般页表项少得多.) 2.UNIX的文件组织方式,磁块地址4BYTE,索引结点前10个直接,一个一级,二个二级的最大文 件长度. 3.快表的作用和原理. 4.学生选课最多可以选3们，但是如果王同学选了3门C1C2C3后，想把C3换成C4，王同 学就得先退选C3再申请选修C4.但是这个时候可能C4已经选满了,而王同学想再选回 C3的时候可能已经被人选满,不能再选了.为了解决这个问题,使用一个函数 TradeCourse(user,course1,course2)将课程course1换成course2.下面给出一种实 现.如果有不正确,给出所有错误的执行情况,并给出你认为正确的实现.要有适当注 释.15分. TradeCourse（user，course1，course2）{ course1->p(); //申请课程course1数据结构的互斥信号量 course1->drop(user); //退选课程course1 course2->p(); //申请课程course2数据结构的互斥信号量 if(course2->isFull()==false){//课程course2没有选满 course2->add(user);//申请选修课程course2 course2->v(); //释放课程course2数据结构的互斥信号量 course1->v(); //释放课程course1数据结构的互斥信号量 } } (答案是错误.若课程2选满,即c2-full==1,会死锁) 组成原理: 第一题:填空，每空1.5分，共18分 1、多处理机存储的两种组织类型是_____和_____ 2、写出3种多处理机高性能通信网络________________________ 3。硬盘的接口的两种类型____________________ 4。举例应用局部性原理的两种系统_________________和________________ 5。显卡的两种总线接口___________和_________ 6。IA32机的最大主存空间是__________ 第二题:20分 1。什么叫disk array,它的作用。3分 2。什么叫cache，它的原理和作用。6分 3。什么叫SMP,它个cluster（集群系统）比较有什么区别和联系。3分 4。写出RISC、CISC、VLIW的基本思想。5分 5。嵌入式cpu和普通 cpu比较有哪些特点？3分 第三题:选择，每个3分，共12分。选择题基本上都是历年出过的真题，去核对一 下就知道了。 1。浮点数的尾数3位，符号为1位，用补码表示；阶数2位，符号1位。x的尾数是 -0.875，阶数为1。y的尾数是0.625，阶数是2。则z=x-y规格化后的结果是: A、1011011 B、******* C、******* D以上均不对 2。cache用组相联映射，一块大小为128字节，cache共64块，4块分一组。主存有 4096块。地址共需多少位: A、19 B、18 C、17 D、**** 3。指令的执行分为取指令用时△t，译址用时2△t，执行用时3△t。当流水执行的 时，时间接近: A 1n△t B、2n△t C、3n△t D、6n△t 4。总线分同步总线和异步总线，其中同步总线具备的性质是: ①成本高、②成本低、③逻辑复杂、④逻辑简单、⑤⑥后两个想不起来了。 A、2、3、6 B、1、3、5 C、1、4、5 D、2、4、6 ※ 来源：考研论坛 bbs.kaoyan.com 中科院辅导班笔记： OS 基本概念部分 一． 对OS的认识 1． 外部： 模型：OS本身是个层次模型。在计算机中起承上启下的作用。层次：硬件，硬件抽象层，OS内核，OS外部程序，应用软件等。层次模型从两个方面认识：OS在计算机的层次模型中；OS本身也是分层的。OS层次见笔记。 类型（分类）：批处理，分时，时事，单用户多用户，单机网络等。 功能：定义：1资源管理，2进程角度：安排计算机工作流程，3方便用户。 内部组成：进程，存储，设备，文件，磁盘管理等。也可以看成是进程存储，设备文件两个子系统。 现代OS特征：动态性等（不会直接考）。 2．内部：子系统：进程控制：进程＋处理机 文件管理：设备＋文件 3．对典型OS的认识 特点：UNIX,LINUX,NT各有什么特点？WHY? 对应的设计思想：为什么NT有多用户的特点？ 一般的设计思想（OS几大模块的设计过程） A.设计模型（层次模型，面向对象） 例如：给定条件，设计当中某个管理模块。 B.模块设计 一． 进程管理模块：（对进程的认识及控制） 并发的含义，条件，与顺序，并行之间的区别：给定条件，能否实现并发（保证读集写集）？如果不能为什么？什么情况下可以并发？什么情况下可以？ 进程的特征，状态：在特定OS设计中各个状态之间的转换。如：LINUX下进程状态转换过程。 进程控制，原语，运行状态：原语的含义。 运行状态：1核心态：哪些进程运行在核心态，在什么情况下它们之间会相互转换？注意中断，系统调用。通过中断进入核心态。中断的处理过程。如NT下给出系统调用，给出函数名，问它在OS中的运行过程，在此过程中他要做的关键性的不走：参数检查，类型匹配，形参的个数处理，如果实参个数超过形参个数，如何处理？参考第10章OS接口。 2用户态：哪些进程运行在用户态。 线程的特征，与进程的比较：进程定义与线程定义＋线程好处＋线程缺点。 注意：比较题的答法：定义＋各自优点＋各自缺点。 1． 进程通信：（不会出编程题） 临界区与临界资源的含义： 进程的通信方式：低级，高级（消息，共享存储区等） 进程调度模型：分三层：进程调度，中间调度，作业调度。特定OS从属于哪一类？一般来说，UNIX无作业调度，而其他有3种调度。 常用进程调度算法： 1每种算法的思想：优先权调度，对动态优先权感兴趣；UNIX多级队列反馈轮转。 2各自特点：好？坏？ 3实现时的支持：如动态优先权需要什么数据结构，硬件。 4实际OS中，采用的是什么？ 二． 存储管理模块（内存＋外存＋CACHE＋TLB） 1． 内存（尤其是分区式） （1） 几种典型的内存分配方案：基本思想；设计方案，如何实现动态分区；特点（优缺）。 （2） 虚拟存储思想： （3） 请求分页式：思想： 硬件支持：页表，地址转换，缺页中断 页面分配策略： 页面置换算法：OBT，LRU,LFU等。注意各自思想；软（数据结构）硬件（存储区，寄存器等）实现。 实例： 2． 外存（尤其是连续分配） （1） 磁盘调度算法：1思想： 2实例：对特定例子，最好的磁盘调度算法是什么 （2） 外存分配方式：1连续：过程，如何做，分配不好出现的情况。 2链接：显式，隐式的含义特点：思想，大概做法。 3索引：常见的，所以不一定考。 3． 抖动（请求分页式）：外存空间分配会不会出现抖动？从空间分配方法，内外存分配的区别表现在哪些方面？抖动是否可以看成一个方面？ 4． 碎片：不同的分配方案要分别考虑这4个问题 （1） 含义： （2） 引起原因：分区式的区内碎片，分页式的页内碎片，外存分配的连续分配。 （3） 解决方法：紧凑。什么时候用？分页式一般不谈紧凑 （4） 分类：1内碎片（内存中的）和外碎片（外存中） 2内碎片是页内碎片等已经分配给进程但不会被使用的空间。 5． 实例设计：尽量选用速度快价格可以接受的。EG：全用CACHE不用磁盘。 三．设备与文件管理模块（目前出题比较少） 1．I/O控制方式，做法：重点是中断方式。如：中断的处理过程，它所运行的状态（可以在核心态也可以在用户态）。 2．缓冲区：类型，作用（缓冲速度）。 注意：从设计角度出题。 实际OS 一． 她们体现出的特点及如何体现：如LINUX在完成一个任务花的时间比较短，WHY？从调度算法等多方面说明。 二． 进程/线程调度算法及算法流程，数据结构，特点。（优先权定义，如何改变，调度 的标准） 三． 请求分页方案的实现细节：数据结构，页面置换，淘汰等。 死锁不会考，UNIX估计也不会考，分区是重点，考LINUX和NT的可能性比较大。 1.1.3 1.2.5 2.1.2 2.1.3 2.1.4 2.2.1 2.2.2 2.3.1 2.3.2 2.4.1 2.4.2 2.4.3 3.1.1 3.1.2 3.5 4.1 4.2 5.2.2 5.2.3 5.2.4 5.4 5.5.1 5.5.2 6.1 6.2 6.3 6.4.3 7.2.2 7.3 8.2 9.1 9.2 10.2 DS 1． 数据结构的概念：数据之间的内在联系。要了解3种数据结构的概念：逻辑结构；物理结构；基本操作。 例如：栈和队的逻辑结构都是线性的，但她们的基本操作不同，就是不同的数据结构。 2． 常见的数据结构的分类：线性关系；集合关系；一对多；多对多（图）； 3． 什么事物理结构（应该有印象）。 4． 算法设计时要用类PASCAL,类C，不要用C++. 5． 算法分析的常用方法：事前分析；事后统计。 6． 时间/空间复杂度的概念。空间是算法运行时资源占用情况。 时间复杂度：最坏，最好，平均。 例如：归并排序都是O（n*logn），最好，最怀，平均都是一样的 插入排序：最好为O(n) ,最坏为O（n2） 7． 线性表：逻辑关系，各种基本操作，两个有序表的归并。 线性表的顺序存储：线性表的操作在顺序表中的实现。 例如：1。插入与删除和插入的位置与表长有关。 2．在一个长为n的表中插入一个元素的平均复杂度，要有插入位置的概率分布表达式，即给出此表达式，算平均复杂度。 8． 线性表的链式存储：链表的基本操作：2个有序表的归并。 例如：1。把链表就地逆置：一个指针P指向当前逆置好的一系列节点的最后一个节点，取P的NEXT插入队头。 2．三色问题：节点红黄蓝在链表上无序排列，把他们按红黄蓝的顺序排好。要求只能从头到尾搜索一遍。设当前指针P，头指针S，S.NEXT为Q，S后接红节点。若P为红，插入S后。若P为黄，插入Q后。若P为兰，不动。然后P向后移，求下个。 注：要了解单链表的插入，删除在什么位置操作。 9． 静态链表（数组表示）：不能象单链表那样不受限增加节点。 10． 循环链表：如果表示队列，用它最好。P指向队尾。好处：用于优先队列中。 11． 双向链表：单链表中只有P指向当前节点，不能删除P。因为无法找到P 的前驱。而双向链表可以。注意指针变化情况。 12． 栈：后进先出。基本操作：出入栈，取栈顶。在顺序表和链表上的实现；出栈序列是否合理？ 例如：入栈序列是1，2，，，n，则出栈序列有几种？（即n个节点的二叉树的个数。因为树的先序是1，2，，，n）。 13． 栈与递归：见我给你寄过去的手写体。 14． 队列：先进现出。链队列，循环队列。 例如：1。把从队头开始的第i个元素删除：队列 只有出队入队，不能直接删除。要先将前i-1个出队，入队尾；i出队；i+1以后的出队入队尾。 2．队列逆置（队头与队尾交互）：出队入栈；后出栈入队。 注意：这些结构的基本操作有什么，不能混。 15． 循环队列：队头指针和队尾指针。记住队空和满的标志。见手写版。 16． 串：1。KMP算法，求NEXT函数值等。时间：O(n+m)。其中，模式匹配为O（n）；预处理为O（m）,要会证明她们。简略证明见手写版。 2．求两串的最长公共子串，时间为O（n）是不行的，至少要O（n2）。具体证明估计不会考。 17．数组：存储位置与下标对应。特殊数组（对称，上三角等）。 三元组，稀疏矩阵（求逆）。计数技术，在设计算法中的应用。 十字链表不考。 广义表：基本概念，存储结构（二叉链表）。应用不考。 广义表递归算法了解。 18． 二叉树的性质（熟）。 存储结构：二叉链表，三叉链表。 遍历：中，先，后。 按层遍历：用辅助队列。例如求K层有多少节点。 19． 线索二叉树：中序（先后序不考）。线索中的插入删除不考。 20． 树与森林的遍历：树的先根与后根（分别对应相应二叉树的先序，中序）。森林的先序和后序（分别对应相应二叉树的先序，中序）。 树与二叉树一一对应。 由先序中序可以唯一确定二叉树。而由先序后序不能。例子见手写版。 二叉树可以为空，树不能为空（树为有根有序树）。 21． 树与等价：例如：判断一个元素是否属于一个特定的集合，可看这个节点是否在此树上。看两个节点是否在一个强联通分量，看他们是否在一棵树上。求KRUSCAL算法（最小生成树集合）。 22． 哈夫曼：前缀码。它是加权外部路径长度最小的二叉树。它是严格二叉树，无度为1的点。节点个数＝2×叶节点－1。 构造，编码。 扩展：用0，1，2三进制编码：元素个数为奇。N个元素K进制：K-1整除N-1。否则增加概率为零的元素。 注意11。6节的最佳归并。 23． 树的计数：记结论。 1． N个操作符或N个括号，为操作符加括号的情况数目。 2． N＋2个顶点的凸多边形，他的不同三角剖分的个数。 3． a1,a2,,,an, ai=1/-1,任意前k个ai之和大于等于0，求不同组合数。 4． 见手写版。 24． 图：存储结构（针对有向图和无向图）。邻接表中边节点中存储的信息不是顶点内容而是顶点序号。 25． 图的遍历：深度优先借助于栈；广度优先借助于队列。 26． 图的连通：深度优先搜索一次。 27． 有向图的强联通分量（不重要）。 28． 最小生成树：PRIM算法，KRUSCAL算法。写算法，要用到树与等价类。（SEL-UNION算法）。她们的时间复杂度。若用优先队列，时间复杂度降低。 29． 关节点，关键路径：深度优先数。 30． 有向无环图：拓扑排序。用邻接矩阵保存它，则入度为0的列全为0。去掉该节点，必还有节点入度为0，所以调整矩阵，可得上三角矩阵。 DAG图等价为拓扑有序。拓扑排序算法：2个共享链栈，利用空间。 若得逆拓扑序，不用栈而用队列；也可以增加一个栈。也可以用深度优先搜索，找最深得那个节点最先把它输出。 31． 最短路径：单源（有向图，且权值>=0是DIJISTRU算法的适应范围）。对无向图，可看成2个方向权值一样。例子见手写版。 问：DIJISTRU算法能否求图的最小生成树？不能。 打印最短路径，时间O（n2），空间O（n），可以用DIJISTRU算法得到集合的同时，记录每个节点前面那个元素，一个一个向前找。 32． 二部图：一个图是否是二部图？时间是O（n）。用等价类：一个边的两点分属于不用等价类（估计不会考太深）。 33． 伙伴系统，边界标识（要看）。无用单元收集不考。 34． 顺序查找时间（最坏，平均）。有序表查找，二分查找，折半查找（判定树，树的高度，平均检索长度（在成功和不成功时的不同情况））。 静态树表不考，静态次优不考。 索引顺序表：概念。 动态查找：二叉排序树：中序遍历有序，先序无序。给出先（或后）序的次序，写出此树（因为中序是顺序的，已知）。他的插入和删除（删除不一定考）。给定树，求平均查找长度。 查找长度的量级。 平衡二叉树：一定是二叉排序树。树的所有子树都是平衡二叉树。反之不成立。若要执行4种旋转，至少7个节点。 M阶B树：关键字个数的上下限。N个关键字构成树的节点数目层数。 B＋树的概念。 键树。 35． 哈希表：解决冲突的方法。只有链地址法可以解决二次聚集。不是同义词不会竞争同一位置。链地址法是顺 序结构和链结构的完美结合。 36． 查找长度：1。探测次数（包括最后一次比较为空的次数）。 2．关键字比较次数（不包括最后一次为空的）。 37．内部排序：简单插入排序（稳定）；折半（不稳定）；希尔（不稳定）；冒泡（稳定）；快速（不稳定）；选择（不稳定）；堆（不稳定）；归并（稳定）。要记住她们的时间复杂度（最好，平均，最坏）。 基数排序：给定N个数，范围在（0，n2-1），以O(n)时间排序。记ni=ai*n+bi，按(ai,bi)先以bi为基数排序，再以ai 排。 基数排序利用关键字本身的值，而其他基于比较。 37． 找最大和最小值的时间[3/2n]-2。见手写版。两两比较，小的方一个数组，大的放一个数组，再找。 找最大和次大值：可以调整堆，也可以记下比较路径。 中科院计算所1999 一. 选择题. 1.____的遍历仍需要栈的支持. (1) 前续线索树(2)中序线索树 (3)后序线索树 2.若度为m的哈夫曼树中，其叶结点个数为n,则非叶结点的个数为＿＿＿． （１）n-1 (2)|_n/m_|-1 (3)上取整 (n-1)/(m-1)4)[上取整n/(m-1)]-1 (5)[上取整(n+1)/(m+1 )]-1 3.最优二叉树（哈夫曼树），最优查找树均为平均查找路径长度 wihi最小的树,其中对最优二叉树,n表示___,对最优查找树,n表示 ____;构造这两种树均为——。*（1）结点数（2）叶结点数 （3）非叶结点数 （4）度为2的结点数 （5）需要一张N个关键字的有序表 （6）需要对N个关键字进行动态插入（7）需要N个关键字的查找概率表（8）不需要任何前提。 4.对于前序遍历与中序遍历结果相同的二叉树为_____;对于前遍历和后序遍历 结果相同的二叉为_____. (1) 一般二叉树 (2) 只有根结点的二叉树 (3)根结点无左孩子的二叉树 (4)根结点无右孩子的二叉树 (5)所有结点只有左子数的二叉树 (6)所有结点只有右子树的二叉树. 5.M路B+树是一棵_____,其结点中关键字最多为___个,最少为___个.. (1) M路平衡查找树 (2)M路平衡索引树 (3) M路TRIE 树 (4)M路键树(5)M-1 (6)M (7)M+1 (8)上取整(M/2)-1 (9) 上取整(M/2) (10) 上取整(M/2)+1 二. 填空题 1. 对于给定的N个元素,可以构造出的逻辑结构有___._____. _____.. ____四种. 2. 具有N个关键字的B-树的查找路径长度不会大于________., 3. 克鲁司卡尔算法的时间复杂度为_____,它对_____图较为适合. 4. 深度为可（设根的层数为一）的完全二叉树至少有______个结点,至多有_____个结点,K和结点数N之间的关系是_____. 三. 问答题 1.一棵非空的有向数中恰有一个顶点入度为0, 其他顶点入度为一, 但一个恰有一个顶点入度为0, 其他顶点入度为一的有向图却不一定是一棵有向数,请举例说明. 2.若有N个元素已构成一个小根堆, 那么如果增加一个元素为Kn+1,请用文字简要说明你如何在LG(N)/LG(2) 的时间内将其重新调整为一个堆? 四. 指出程序输出 void g(int**); main() { int line[100],i; int *p=line; for (i=0; i<100;i++) { *p=i; g(&p); } for(i=0; i<100;i+1) printf(“%d/n”,line); } void g(int**p) { (**p)++; (**p)++; } 五 .编程题 1. 设一单向链表的 头指针为HEAD,链表的记录中包含着整数类型的KEY 域,试设计算法,将此链表的记录按照KEY递增的次序进行就地排序. 2. 给定一个整数叔数组b[0..n-1].,b中连续的相等元素构成的子序列称为平台.试设计算法,求出B中最长平台的长度.[ 3. 自由树(即无环连通图)T=(V,E)的直径是树中所有点对间最短路径长度的最大值,即T的 直径定义为MAX D(u,v) ,这里D(u,v)表示顶点U到顶点V的最短 u,v∈V 路径长度(路径长度为路径中所包含的边数). 写一算法求T的直径,并分析算法的时间复杂度(时间复杂度越小得分越高). 中国科学院计算所 一九九二年招收硕士学位研究生入学考试试题 试题名称：离散数学 （供计算所用） 代数结构部分（共32分） 一． 判断对错（18分） 1．A，B是集合，命题 和 不可能同时成立。 2．若R 是集合A上的传递关系，则 也是集合A 上的传递关系。 3．四阶群中必有四阶元。 4．非循环群的每一个子群必是非循环群。 5．f 是G1 到G2的群同态映射，若G1是交换群，则G2 也是交换群。 6．分配格必是模格。 二． （14分） 是D={1,2,……n}上所有置换（双射）组成的集合。 对置换乘法（函数复合）运算构成群，G是 的子群。 1. 在 上定义关系R, , 存在 证明：R是 上的等价关系。 2. 取n=3，列出 的所有元素，找出 的一个二元阶子群G，求上述等价关系所确定的 一个划分。 图论部分（共33分） 一. (8分) 下面列出了一些关于简单图的结论,它们的哪些组合可以作为树的定义,写出所有可能,但不允许在组合中有多余的结论: a. 无圈. b. 连通. c. 边数=结点数-1; d. 每队结点间有且仅有一条通路(轨); e. 连通图的每一条边均为割边; f. 在原图中增加任一条边恰好得到一个圈; 二. (15分) 1. 右图是否是平面图,为什么? 2. 如何从一连通图的关联距阵中判断一边是否割边? 3. 一个简单图的七个结点的次数分别为6,6,5,4,3,3,1,问这样的图是否存在?若存在,请画出相应的图 ,否则,说明理由. 三. (10分) 证明:连通图的任意两条最长的通路(轨)有公共结点. 数理逻辑部分(共29分) 一. 判断对错(9分) 1. 为重言式. 2. 联结词 的定义是 .{ }是最小的联结词组. 3. 的前束范式为 . 二. (10分) 利用谓词E(x, y)(表示x与y 相同”)来构造命题函数(谓词演算的合式公式),使得该命题函数具有性质:”在个体域 D中可满足:当且仅当D只含有两个个体.”论述你构造的正确性. 三. (10分) 1. 用真值表证明: 为重言式 2. 用推理规则证明: . (不准使用规则 ). 中国科学院计算所 一九九三年招收硕士学位研究生入学考试试题 试题名称：离散数学 数理逻辑部分(共34分) 一.(12分)下列推理是否成立?证明你的结论. a) 前提: 结论: b) 前提: 结论: 二.(10分) 是否最小联结词组?即能否仅用联结词组 和 表示所有的命题公式?证明你的结论. 三.(12分) 三个前提为: 两个结论为: 写出推导过程. 代数结构部分(共34分) 一.(10分) 和 是集合S中的等价关系, 和 是它们产生的划分.证明: 当且仅当 的每一个划分都包含在 的每一个分块中. 五.(10分) 设 是n阶有限群,e为单位元, 是G 的任意几个元素,不一定两两不同.试证:存在整数p和q, ,使得 . 六.(14分) 设 是环,其乘法单位元记为1,加法单位元记为0,对于任意 ,定义 , .求证: 也是环,并且与环 同构 图论部分(共32分) 七.(11分) 设连通单图G有n个结点(或称作顶点), ,m条边 ,定义矩阵 , ,分别如下: 1) 2) 3) 证明: (其中 为结点 的次数(或称为度数), 为矩阵B 的转置). 八.(11分) 设G是连通单图,但不是完全图,则存在三个结点u,v,w,使uv,vw E(G),但uw E(G). 九(10分) 连通图G 的树图是一个图,它的结点 为G的生成树, 与 相连的充要条件是它们恰好有v-2条公共边(其中v为G的结点数).证明:连通图的树图是连通图. 软件所： 1996年试题 一九九六年招收硕士学位研究生入学考试试题 试题名称：软件基础 一．（10分） 1．给出下列表达式的逆波兰表示（后缀式）：（各1分） a+b*c； a≦b+c∧a>d∨a+b≠e 2．写出下列语句的逆波兰式表示（后缀式）：（各1分） ﹤变量﹥：=﹤表达式﹥ IF ﹤表达式﹥ THEN ﹤语句1﹥ ELSE ﹤语句2﹥ 3．写出算术表达式 A+B*（C-D）+E/（C-D）**N 的四元式、三元式和间接三元式序列。（各2分） 二．（10分）写一文法，使其语言是偶数的集合，但不允许有以0居首的偶 整数。 三．（10分）LRU算法的基本思想是什么？有什么缺点？给出该算法的流程图。 四．（10分）设有一个具有n个信息元素的环形缓冲区，A进程顺序地把信息写 入缓冲区，B进程依次地从缓冲区读出信息，回答下列问题： 1． 叙述A、B两进程的相互制约关系； 2． 判别下列用P、V操作表示的同步算法是否正确？如果不正确，试说明 理由，并修改成正确算法。 var buffer：array 0..N-1 of T; in,out: 0..N-1; var S1,S2:Semaphore; S1:==0; s2:=N; in:=out:=0; Procedure A: begin repeat 生产数据m; P(S2); buffer(in):=m; in:=(in+1) mod N; V(S1); forever end Procedure B: begin repeat V(S2); m:=buffer(out); 消费m; out:=(out+1) mod N; P(S1); forever end 五．（10分）试简述UNIX的文件读写过程。 六．（10分）试给出运算变量均为整数的简单算术表达式所需最少临时单元个 数的算法（假定不许用代数规则变更表达式的计值顺序）。 例如：A+B*C需要一个临时单元为（B*C）；（A+B）*（C+D）+E则 需要两个临时单元，一个为C+D，另一个既为A+B又为（A+B）*（C+D）。 七．（10分）已知三维空间（直角坐标系）有n个点，请编写一个函数过程， 求通过某一特定平面的点数。 八．（13分）编写一过程，对一个n×n矩阵，通过行变换，使其每行元素的平 均值按递增顺序排列。 九．（17分）请编写一过程，对具有n个整数的序列进行二叉树排序。 1997试题 一九九七年招收硕士学位研究生入学考试试题 试题名称：软件基础 第一部分：数据结构和程序设计 一． 是非题（正确填√，错误填×）（1分×10） （ ）1．稀疏矩阵压缩存储后，必会失去随机存取功能。 （ ）2．完全二叉树的某结点若无左孩子，则它必是叶结点。 （ ）3．由一棵二叉树的前序序列和后序序列可以唯一确定它。 （ ）4．在n个结点的无向图中,若边数>n-1，则该图必是连通图。 （ ）5．若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑 有序序列必定存在。 （ ）6．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速 度。 （ ）7．在任意一棵非空二叉排序树，删除某结点后又将其插入，则所得二 叉排序树与删除前原二叉排序树相同。 （ ）8．若一个广义表的表头为空表，则此广义表亦为空表。 （ ）9．二叉树是度数为二的有序树。 （ ）10．对磁带机而言，ISAM是一种方便的文件组织方法。 二． 程序阅读题（共18分） 1． 设m，n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。例f(5,3)=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。 ①以下是该函数的程序段，请将未完成部分填入，使之完整。 int f(m,n) int m,n; { if (m==1) return ; if (n==1) { return ; } if (m return 1+ ; } return f(m,n-1)+f(m-n, ); } ②执行程序，f(6,4)= ; 2． 设输入为整数数组A[1..n]，其中1≦A ≦k（1≦i≦n）；输出数组为B[1..n]；C[1..k]是临时工作空间；阅读下述算法后，回答下列问题： Proc Demo(A,B,k) { ⑴ for i:=1 to k do C:=0; ⑵ for j:=1 to n do C[A[j]]:=C[A[j]]+1; ⑶ for i:=2 to k do C:=C+C[i-1]; ⑷ for j:=n downto 1 do { ⑸ B[C[A[j]]]:=A[j]; ⑹ C[A[j]]:=C[A[j]]-1; } } (a) 当标号⑵行的循环执行完后，C（1≦i≦n）的值有何意义？ (b) 当标号⑶行的循环执行完后，C（1≦i≦n）的值有何意义？ (c) 算法执行后，B的内容有何特点？ (d) 当k=O(n)时，算法的时间复杂度是多少？ 三． （10分）设大根堆（即堆顶元素最大）的存储结构为： type HEAP=record keys：array[1..max] of keystype; /*存放堆元素的空间*/ size : int ; /*当前堆中已有的元素个数*/ end; 写一算法HeapInsert(var heap:HEAP;key:keystype)将关键字key插入到堆heap中且不破坏堆性质。（提示：先将key插入到数组的size+1位置上，然后自底向上调整）。 四． （12分）设二叉排序树的存储结构为： type TREE=↑node； node = record key ：keytype； size ：int； lchild，rchild，parents：TREE； end； 一个结点x↑的size域的值是以该结点为根的子树中结点的总数（包括x ↑ 本身）。例如，下图中x所指结点的size值为4。设树高为h，试写一时间 为O(h)的算法Rank（T：TREE；x：↑node）返回x所指结点在二叉排序树 T的中序序列里的排列序号，即： 求x结点是根为T的二叉排序树中 第几个最小元素。例如，下图x所 指结点是树T中第11个最小元素。 （提示：你可利用size值和双亲 指针parents）。 第二部分：操作系统和编译技术 五． 填空题（1分×9） 1． 实现虚拟存储器，应有以下几种物质基础来支持：① ② ③ 。 2． 页面淘汰算法选得不好会引起 现象。 3． 从资源管理的角度看，I/O设备分为 设备、 设备和 设备三类。 4． 引入缓冲的原因在于： 和 。 六． 简答题（共16分） 1． 一个分层结构操作系统有下列部分组成：裸机、用户、CPU调度和PV操作、文件管理、作业管理、内存管理、设备管理、命令管理等。试按层次结构的原则从内到外将各部分重新排列。 2． 产生死锁的必要条件是什么？解决死锁问题常用哪几种措施？ 3． UNIX进程映像由哪几部分组成？简述各部分的内容。 七． （10分）为正规式 构造一个确定的有限自动机。 八． （15分）试画出如下中间代码序列的程序流图，并求出： (1) 各结点的必经结点集合D（n）； (2) 流图中的回边与循环。 J:=0; L1: I:=0; if I<8 goto L3; L2: A:=B+C; B:=D*C; L3: if B=0 goto L4; write B; goto L5; L4: I:=I+1; if I<8 goto L2; L5: J:=J+1; if J<=3 goto L1; HALT 1998年试题一九九八年招收硕士学位研究生入学考试试题 试题名称：软件基础 第一部分：程序设计和数据结构 要求：算法设计题目要求写注解，否则扣分。写出正确的设计思想和伪代码给分。 一. 选择合适的答案填空（1分×20） 1． 程序的三种基本控制结构是 ， 和 。 （a）顺序 （b）转移 （c）I/O （d）选择 （e）重复 （f）递归 2． 过程或函数的副作用是指在过程或函数体内 。 （a）．对局部量的修改 （b）．对非局部量的修改 3． 在C语言的函数void f（）{static int I=0；……}说明中，静态变量I的作用域是 ，生命期是 ，I的初始化是在 时进行的。（第一、二个空从（a）~（c）中选择，第三个空从（d），（e）中选择） （a）整个程序 （b）函数f（）所在的文件 （c）函数f（）内部 （d）编译 （e）程序运行 4． 将递归程序转换成非递归程序，一般都要使用栈，但是消除 可以不使用栈。 （a）直接递归 （b）间接递归 （c）尾递归 5． 没有提供指针类型的语言，无法构造链式结构，该说法 。 （a）正确 （b）错误 6． 若广义表A满足head（A）=tail（A）=（），则A为 。 （a）（） （b）（（）） （c）（（），（）） （d）（（），（），（）） 7． 假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行 次探测。 （a）K-1次 （b）K次 （c）K+1次 （d）K（K+1）/2次 8． 若要尽可能快的完成对实数数组的排序，且要求排序是稳定的，则应选 。 （a）快速排序 （b）堆排序 （c）归并排序 （d）基数排序 9． 一个具有n个顶点的强连通图，至少有 条边，至多有 条边。 （a）n-1 （b）n （c）n（n-1） （d）n（n-1）/2 10. 用ISAM组织文件适合于 。 （a）磁带 （b）磁盘 11. 对外部排序的K路平衡归并，采用败者树，归并效率与K 。 （a）有关 （b）无关 12. 若一个具有n个顶点，k条边的无向图是一个森林（n>k），则该森林中必有 棵树。 （a）k （b）n （c）n-k （d）1 13. 已知待排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素并小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为 。 （a）O（nlog2n） （b）O（nlog2k） （c）O（klog2n） （d）O（klog2k） 14. 若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是 。 （a）二叉排序树 （b）哈夫曼树 （c）堆 15. 用dfs遍历一个无环有向图，并在dfs算法退栈返回时，打印出相应的顶点，则输出的顶点序列是 。 （a）逆拓扑有序的 （b）拓扑有序的 （c）无序的 二. （共15分）设A[0..k-1]是一个整数数组，各分量的初值为0，即A=0（0≦i≦k-1），设n为连续调用Demo过程的次数，请回答下述问题： (1) 给出调用次数n=4时，数组A中各分量的结果。（4分） (2) 若 ，数组A中各分量的结果是什么？（4分） (3) Demo过程的功能是什么？数组A起何作用？（4分） (4) 显然Demo过程的最坏时间是o（k），故连续调用Demo过程n次的总时间为O（kn）。但是这个界偏大，请详细分析求出一个更小的n次连续调用Demo的总时间的上界。（3分） Procedure Demo（Var A：arraytype；k：integer） { i：=0； while （i 写一算法从给定的G求出 ，并分析算法的时间复杂度，要求使用以下 邻接表作为存储结构： Type arcptr = ^arcnode; arcnode = RECORD //边表结点 arjvex : 1..n; //邻接点序号 nextarc: arcptr; //指向下一个边表结点 END; vexnode = RECORD vexdata : vextype; //顶点信息 firstarc : arcptr; //指向边表的第1个结点 END; adjlist = ARRAY[1..n] OF vexnode; 第二部分：操作系统和编译原理 四. 简答题（3分×5） (1) 操作系统的作用是什么？其主要特征是什么？ (2) 什么是系统调用？它与一般的程序过程调用有什么区别？ (3) 引起系统抖动的原因是什么？ (4) 什么是虚拟设备？如何实现虚拟设备？ (5) UNIX系统中有哪些磁盘读写方式？ 五. （10分）分析下面用信号量解决哲学家进餐问题的同步算法是否满足同步机制的四条准则。若不满足，说明为什么，并给出满足同步机制四条准则的同步算法。 var fork：array[0..4] of semaphore; fork[0] := fork[1] := fork[2] := fork[3] := fork[4] := 1; parbegin Pi : repeat /*第i个哲学家的生活过程*/ ThinkForWhile; P(fork); P(fork[(i+1) mod 5]); EatForWhile; V(fork); V(fork[(i+1) mod 5]); until false parend 六. （10分）下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。 S S and S | S or S | not S | p | q | (S) 七. （15分）下面程序的结果是120。但是如果把第10行的abs（1）改成1的话，则程序结果是1。试分析为什么会有这样不同的结果。 int fact（） { static int i = 5； if （i == 0） { return （1）； } else { i = i –1； return （（i+abs（1））*fact（））； /*第10行*/ } } main（） { printf（“factor of 5 = %d\\n”，fact（））； } 因篇幅问题不能全部显示，请点此查看更多更全内容