北京大学1997硕士入学数据结构试题

名校操作系统考研试题与解答10.1北京大学1997年考研操作系统试题(一)名词术语解释(每小题5分,共30分)1.进程状态2.快表3.目录项4.系统调用5.设备驱动程序6.微内核(二)填空(每小题1分,共10分)1.如果系统中有n个进程,则在等待队列中进程的个数最多为________个。

2.在操作系统中,不可中断执行的操作称为_________。

3.如果系统中的所有作业是同时到达的,则使作业平均周转时间最短的作业调度是_________。

4.如果信号量的当前值为-4,则表示系统中在该信号量上有________个等待进程。

5.在有m个进程的系统中出现死锁时,死锁进程的个数k应该满足的条件是_________。

6.不让死锁发生的策略可以分为静态和动态两种,死锁避免属于_________。

7.在操作系统中,一种用空间换取时间的资源转换技术是_________。

8.为实现CPU与外部设备的并行工作,系统引入了__________硬件机制。

9.中断优先级是由硬件规定的,若要调整中断的响应次序可通过_________。

10.若使当前运行的进程总是优先级最高的进程,应选择________进程调度算法。

(三)问答题(每小题15分,共30分)1.消息缓冲通信技术是一种高级通信机制,由Hansen首先提出。

(1)试述高级通信机制与低级通信机制P、V原语操作的主要区别。

(2)请给出消息缓冲机制(有界缓冲)的基本原理。

(3)消息缓冲通信机制(有界缓冲)中提供发送原语Send(receiver,a),调用参数a表示发送消息的内存区首地址,试设计相应的数据结构,并用P、V原语操作实现Send原语。

2.在虚拟段式存储系统中,引入了段的动态链接。

(1)试说明为什么引入段的动态链接。

(2)请给出动态链接的一种实现方法。

(四)(共10分)在实现文件系统时,为加快文件目录的检索速度,可利用"文件控制块分解法"。

假设目录文件存放在磁盘上,每个盘块为512字节。

计算机专业基础综合数据结构（排序）历年真题试卷汇编3(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：36.00)1.下面给出的四种排序法中，( )排序法是不稳定性排序法。

【北京航空航天大学1999一、10(2分)】A.插入B.冒泡C.二路归并D.堆√2.下列排序算法中，其中( )是稳定的。

【福州大学1998一、3(2分)】A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序√3.稳定的排序方法是( )。

【北方交通大学2000二、3(2分)】A.直接插入排序和快速排序B.折半插入排序和起泡排序√C.简单选择排序和四路归并排序D.树形选择排序和Shell排序4.下列排序方法中，哪一个是稳定的排序方法?( )。

【北方交通大学2001一、8(2分)】A.直接选择排序B.二分法插入排序√C.希尔排序D.快速排序5.下列排序算法中，( )是稳定排序。

【北京理工大学2007一、10(1分)】A.希尔排序B.快速排序C.堆排序D.直接插入排序√6.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

( )就是不稳定的排序方法。

【清华大学1998一、3(2分)】A.起泡排序B.归并排序C.Shell排序√D.直接插入排序E.简单选择排序√7.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选( )排序为宜。

【中科院计算所2000一、5(2分)】A.直接插入√B.直接选择C.堆D.快速E.基数8.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )。

【中国科技大学1998二、4(2分)】【中科院计算所1998二、4(2分)】A.快速排序B.堆排序C.归并排序√D.直接插入排序9.下面的排序算法中，不稳定的是( )。

【北京工业大学1999一、2(2分)】A.起泡排序B.折半插入排序C.简单选择排序√D.希尔排序√E.基数排序下列内部排序算法中：【北京工业大学2000一、1(10分每问2分)】A．快速排序B．直接插入排序C．二路归并排序D．简单选择排序E．起泡排序（分数：8.00）(1).其比较次数与序列初态无关的算法是( )A.B.C. √D. √E.(2).不稳定的排序算法是( )A. √B.C.D. √E.(3).在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序，k<A.B. √C.D.E.(4).排序的平均时间复杂度为O(n*10gn)的算法是( )，为O(n*n)的算法是( )A. √B. √C. √D. √E. √10.排序趟数与序列的原始状态有关的排序方法是( )排序法。

2022年北京大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并2、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。

A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ8、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间9、有n（n>0）个分支结点的满二叉树的深度是（）。

A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）10、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为l，则应作（）型调整以使其平衡A.LLB.LRC.RLD.RR二、填空题11、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。

北京大学信息科学技术学院考试试卷 考试科目：数据结构与算法A 姓名： 学号： 考试时间：2017年 11月 15日 任课教师: 以下以下为答题纸，共 页注意事项：1． 全部题目都在空白答题纸上解答。

2． 试卷对算法设计都有质量要求，请尽量按照试题中的要求来写算法。

否则将酌情扣分。

3． 请申明所写算法的基本思想，并在算法段加以恰当的注释。

以下为试题和答题纸，共5页，请把答案写在答题纸。

题号 一 二 三 四 五 总分 分数 阅卷人 北京大学考场纪律 1、考生进入考场后，按照监考老师安排隔位就座，将学生证放在桌面上。

无学生证者不能参加考试；迟到超过15分钟不得入场。

在考试开始30分钟后方可交卷出场。

2、除必要的文具和主考教师允许的工具书、参考书、计算器以外，其它所有物品（包括空白纸张、手机等）不得带入座位，已经带入考场的必须放在监考人员指定的位置，并关闭手机等一切电子设备。

3、考试使用的试题、答卷、草稿纸由监考人员统一发放，考试结束时收回，一律不准带出考场。

若有试题印制问题请向监考教师提出，不得向其他考生询问。

提前答完试卷，应举手示意请监考人员收卷后方可离开；交卷后不得在考场内逗留或在附近高声交谈。

未交卷擅自离开考场，不得重新进入考场答卷。

考试结束监考人员宣布收卷时，考生立即停止答卷，在座位上等待监考人员收卷清点后，方可离场。

4、考生要严格遵守考场规则，在规定时间内独立完成答卷。

不准旁窥、交头接耳、打暗号，不准携带与考试内容相关的材料参加考试，不准抄袭或者有意让他人抄袭答题内容，不准接传答案或者试卷等。

凡有严重违纪或作弊者，一经发现，当场取消其考试资格，并根据《北京大学本科考试工作与学习纪律管理规定》及其他相关规定严肃处理。

5、考生须确认自己填写的个人信息真实、准确，并承担信息填写错误带来的一切责任与后果。

学校倡议所有考生以北京大学学生的荣誉与诚信答卷，共同维护北京大学的学术声誉。

装订线内不要答题一、选择与填空（每空2分，共24分）得分1.下面函数的时间复杂度是（）void recursive(int n, int m, int k){if (n <= 0)printf("%d, %d\n", m, k);else {recursive(n-1, m+1, k);recursive(n-1, m, k+1);}}A.O(n*m*k)B. O(n^2*m^2)B.O(2^n) D. O(n!)2.完成在双循环链表结点p之后插入s的操作为( ):A. p->next->prev=s; s->prev=p; s->next=p->next; p->next=s;B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;C. s->next=p->next; s->prev=p; p->next->prev=s; p->next=s;D. s->prev=p; s->next=p->next; s->prev->next=s; s->next->prev=s;3.设栈S和队列Q初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈S，一个元素出栈后即进队列Q，若6 个元素出队序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少是( )A.2;B.3;C.4;D.64.设循环队列的容量为40 （序号从0到39），现经过一系列的入队和出队运算后：1）front=12，rear=19；2）front=19，rear=12；在这两种情况下，循环队列中的元素个数分别为和。

√
13. 关于杂凑查找说法不正确的有几个 ) 【南京 关于杂凑查找说法不正确的有几个( 理工大学 2000 一、16 （1.5分）】 分 （1）采用链地址法解决冲突时，查找一个元素的 ）采用链地址法解决冲突时， 时间是相同的 （2）采用链地址法解决冲突时，若插入规定总是 ）采用链地址法解决冲突时， 在链首， 在链首，则插入任一个元素的时间是相同的 （3）用链地址法解决冲突易引起聚集现象 ） （4）再哈希法不易产生聚集 ） A. 1 B. 2 C. 3 D. 4
√
14. 设哈希表长为 ，哈希函数是 设哈希表长为14， H(key)=key%11,表中已有数据的关键字为 ， 表中已有数据的关键字为15， 表中已有数据的关键字为 38，61，84共四个，现要将关键字为 的结点加 共四个， ， ， 共四个 现要将关键字为49的结点加 到表中，用二次探测再散列法解决冲突， 到表中，用二次探测再散列法解决冲突，则放入 的位置是( 的位置是 ) 【南京理工大学 2001 一、15 （1.5分）】 分 A．8 B．3 C．5 D．9 ． ． ． ．
第九章 习题
一、 选择题 1.若查找每个记录的概率均等，则在具有 个记录 若查找每个记录的概率均等， 若查找每个记录的概率均等 则在具有n个记录 的连续顺序文件中采用顺序查找法查找一个记录， 的连续顺序文件中采用顺序查找法查找一个记录， 其平均查找长度ASL为( )。【北京航空航天大学 其平均查找长度 为 。 2000 一、8 （2分）】 分 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n ．
5．分别以下列序列构造二叉排序树，与用其它 ．分别以下列序列构造二叉排序树， 三个序列所构造的结果不同的是( 三个序列所构造的结果不同的是 ) 【合肥工业 大学2000一、4（2分）】 大学 一 （ 分 A.（100，80， 90， 60， 120，110，130） （ ， ， ， ， ， ， ） B.（100，120，110，130，80， 60， 90） （ ， ， ， ， ， ， ） C.（100，60， 80， 90， 120，110，130） （ ， ， ， ， ， ， ） D. (100，80， 60， 90， 120，130，110) ， ， ， ， ， ，

北京大学计算机试题及答案一、选择题1. 下列哪个选项是计算机的基本组成部分？a) 中央处理器 (CPU)b) 显卡 (GPU)c) 声卡 (Sound Card)d) 字符串 (String)答案：a) 中央处理器 (CPU)2. 在计算机内部，信息的传输是通过什么形式进行的？a) 电流b) 磁力c) 光线d) 电子信号答案：d) 电子信号3. 下列哪个选项是一种计算机编程语言？a) HTMLb) JPEGc) USBd) HTTP答案：a) HTML4. 在计算机科学中，什么是算法？a) 一种计算机程序b) 一种数据结构c) 一种解决问题的方法或步骤d) 一种计算机硬件设备答案：c) 一种解决问题的方法或步骤二、填空题1. 在二进制表示中，8个二进制位表示一个_____________。

答案：字节2. 操作系统是一种_____________软件。

答案：系统3. HTML是一种用于_____________的标记语言。

答案：网页4. TCP/IP是一种用于互联网通信的_____________。

答案：协议三、简答题1. 请简要解释什么是计算机网络。

答：计算机网络是通过通信链路将多台计算机连接在一起，使它们能够相互传输数据和共享资源的系统。

计算机网络可以是局域网、广域网或互联网，通过使用各种协议和技术实现数据的传输和通信。

2. 请说明计算机内存的作用。

答：计算机内存是计算机的主要存储介质之一，用于暂时存储和快速访问计算机程序和数据。

它被用来存储正在运行的程序代码、变量、输入/输出数据以及临时计算结果等。

计算机内存的大小直接影响计算机的运行速度和性能。

3. 阐述计算机硬件和软件之间的区别和联系。

答：计算机硬件是指计算机的物理组成部分，包括主机、显示器、键盘、鼠标、内存、硬盘等。

它们是构成计算机系统的实体，可以被看到和触摸到。

而计算机软件是指指挥硬件工作的指令、程序和数据，它们是以二进制形式存储在硬件中的。

北京大学1997年全国硕士研究生招生考试数学分析试题及解答微信公众号：数学十五少2019.05.21一、(10分)将函数f(x)=arctan2x1−x2在x=0点展开为幂级数,并指出收敛区间.二、(10分)判断广义积分的收敛性:∫+∞0ln(1+x)x pd x.三、(15分)设f(x)在(−∞,+∞)上有任意阶导数f(n)(x),且对任意有限闭区间[a,b],f(n)(x)在[a,b]上一致收敛于ϕ(x)(n→+∞),求证:ϕ(x)=c e x,c为常数.四、(15分)设xn >0(n=1,2,…)及limn→+∞x n=a,用ε−N语言证明:limn→+∞√x n=√a.五、(15分)求第二型曲面积分∯S(x d y d z+cos y d z d x+d x d y),其中S为x2+y2+z2=1的外侧.六、(20分)设x=f(u,v),y=g(u,v),w=w(x,y)有二阶连续偏导数,满足ðfðu=ðgðv,ðfðv=−ðgðu,ð2wðx2+ð2wðy2=0,证明:(1)ð2(fg)ðu2+ð2(fg)ðv2=0,(2)w(u,v)=w(f(u,v),g(u,v))满足ð2wðu2+ð2wðv2=0.七、(15分)计算三重积分∭Ω∶x2+y2+z2≤2z(x2+y2+z2)5/2d x d y d z.一、f(x)=2∞∑n=0(−1)n2n+1x2n+1(|x|<1).详细过程见林源渠、方企勤编的《数学分析解题指南》第241页例5.二、当1<p<2时,原广义积分收敛.详细过程见林源渠、方企勤编的《数学分析解题指南》第203页例3的(1).三、此题为林源渠、方企勤编的《数学分析解题指南》第235页练习题4.2.16.证明过程可参考裴礼文的《数学分析中的典型问题与方法》第二版第538页练习题5.2.28.四、因为limn→+∞x n=a,故有∀ε>0,∃N>0,当n>N时,|x n−a|<√aε.于是∣√x n−√a∣=|x n−a|√x n+√a<|x n−a|√a<ε.五、先由对称性知:所求的积分I=∯S x d y d z,再用Gauss公式得I=∭Vd x d y d z=4π3.六、此题为林源渠、方企勤编的《数学分析解题指南》第283页练习题5.2.23.证明过程可参考裴礼文的《数学分析中的典型问题与方法》第二版第670页练习题6.2.12.七、通过做极坐标变换可以算出结果为64π9.此题为林源渠、方企勤编的《数学分析解题指南》第336页练习题5.2.9的(2).。

2. 已知一组关键码为（26，36，41，38，44，15，68，12，06，51，25），散 列表长度为 15，用线性探查法解决冲突构造这组关键码的散列表。散列函 数为：h(k)= k %13。请回答： 1) 构造顺序插入上述关键码集合后的散列表；
2) 下一记录放到第 11 个槽和第 7 个槽中的概率分别是多少？ 下一条记录放在第 11 个槽中的概率是 2/13 放到第 7 个槽中的概率是 9/13
学校倡议所有考生以北京大学学生的荣誉与诚信答卷，共同维护北京大 学的学术声誉。
以下为试题和答题纸，共 页。
得分 一、选择填空题（每空 1 分，共 11 分）（答案写在答题纸上）
1. G 是一个非连通无向图，共有 21 条边，则图 G 至少有 8 个顶点。 2. 对于一个包含 N（N>1）个顶点的图，假定任意两点间最多只有一条边，
7. A[N][N]是对称矩阵，现将下三角矩阵按行存储到一维数组 T[N(N+1)/2]中
（包括对角线），则对任一上三角元素 A[i][j]其对应值（0 <= i <= j < N）在
T[k]中的下标 k 是 j(j+1)/2+i
。
8. 在一棵空 AVL 树中，顺序插入如下关键码：{5, 9, 4, 2, 1, 3, 8}，请问全部 插入后，在等概率下查找成功的平均检索长度为 17/7 。
9. 已知广义表 C=(c, (d, A), B, e)，则广义表 C 的深度为 2
，
tail(head(tail(C)))的运算结果为 (A) 。
得分 二、简答辨析题（每题 3 分，共 15 分）
1. 如果要找出一个具有 n 个元素集合中的第 k (1≤k≤n)个最小元素，所学过的 排序方法中哪种最适合？给出实现的基本思想。 答案：在具有 n 个元素的集合中找第 k 个最小元素，应使用快速排序算法。 其基本思想如下：设 n 个元素的集合用一维数组表示，其第一个元素的下 标为 1，最后一个元素下标为 n。以第一个元素为“枢轴”，经过快速排序的 一次划分，找到“枢轴”的位置 i，若 i = k，则该位置的元素下标为 n；若 i > k 则在 1 至 i-1 间继续进行快速排序的划分；若 i < k 则在 i+1 至 n 间继续 进行快速排序的划分。这种划分一直进行到 i = k 为止，第 i 位置上的元素 就是第 k 个最小元素。

数据结构绪论练习题题目1. 数据结构是一门研究什么内容的学科？【燕山大学 1999 二、1 （4分）】2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？【燕山大学1999 二、2（4分）】3. 数据类型和抽象数据类型是如何定义的。

二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？【北京邮电大学 1994 一（8分）】4. 回答问题（每题2分）【山东工业大学 1997 一（8分）】（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。

这样的说法对吗？举例说明之。

（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。

这样说法对吗？举例说明之。

（4）评价各种不同数据结构的标准是什么？5．评价一个好的算法，您是从哪几方面来考虑的？【大连海事大学 1996 二、3 （2分）】【中山大学 1998 三、1 （5分）】6．解释和比较以下各组概念【华南师范大学 2000 一（10分）】（1）抽象数据类型及数据类型（2）数据结构、逻辑结构、存储结构（3）抽象数据类型【哈尔滨工业大学 2000 一、1（3分）】（4）算法的时间复杂性【河海大学 1998 一、2（3分）】（5）算法【吉林工业大学1999 一、1（2分）】（6）频度【吉林工业大学 1999 一、2（2分）】7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？【北京科技大学 1998 一、1】【同济大学 1998】8．对于一个数据结构，一般包括哪三个方面的讨论？【北京科技大学 1999 一、1（2分）】9. 当你为解决某一问题而选择数据结构时，应从哪些方面考虑？【西安电子北京科技大学2000】10. 若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？【北京科技大学 2001 一、1（2分）】11．数据结构与数据类型有什么区别？【哈尔滨工业大学 2001 三、1（3分）】12．数据的存储结构由哪四种基本的存储方法实现？【山东科技大学2001 一、1（4分）】13．若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？【山东师范大学 1996 二、2（2分）】14. 运算是数据结构的一个重要方面。

2005-2006年北京大学数据结构期末考试试题(答案写在答题纸上)一、简答（10分）（1）什么是数据结构？它主要研究的问题是什么？答：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构研究的问题是数据的物理结构和逻辑结构，以及在此结构上定义并实现相关的运算，计算算法的效率。

（2）阅读以下程序，写出带@ 语句的频度（运行次数）。

X=91；Y=100；While(Y>=0)If (X>100) ……………@{X - =10;Y- -}ElseX++；答：频度为1111次二、编程（10分）编制一个程序就地实现单链表的逆置算法。

说明：1.算法中不能再另外增加结点空间(即不能在算法中使用malloc()函数分配新的结点空间)，但可以增加几个必要的指针变量。

2.该单链表具有头结点。

例如：L答案：invert(Linklist &L){ p=L;q=L->next;while(q){r=q->next;q->next=p;p=q;q=r;}L->next=NULL;L=p;}评分标准：总分为10分。

程序不同，但思路正确者也可酌情给分。

三、编程（10分）用循环队列将序列a0 a1 a2 a3┉┉ak-1 ak┉an循环右移k位。

（序列变为ak┉┉an a0 a1 a2 a3┉ak-1）。

答案：Right(SqQueue &Q,int k){ for(I=1;I<=k;I++){ Q.base[Q.rear]=Q.base[Q.front];Q.rear=(Q.rear+1)%Maxsize;ront=(Q.front+1)%Maxsize;}}评分标准：总分为10分。

出队为8分，入队为2分。

程序不同，但思路正确也可酌情给分。

四、树（10分）已知一棵二叉书树的先序序列为ABDHECFGI，中序序列为DHBEAFCIG，画出该二叉树。

五、画图（10分）画出下图的最小生成树。

北京大学1997年研究生入学考试离散数学试题（共50分）1 (7分)在一阶逻辑自然推理系统F中，构造下面推理的证明。

个体域是人的集合。

“每位科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功。

存在着身体健康的科学家。

所以，存在着事业获得成功的人或事业半途而废的人。

”2 (8分)在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。

乙说：王教授不是上海人，是苏州人。

丙说：王教授既不是上海人，也不是杭州人。

王教授听后，笑曰：你们3人中有一人全说对了，有一人全说错了，还有一人对错各半。

试用逻辑演算法判断王教授是哪里人？3 (3分)设根树T有17条边，12片树叶，4个4度内点，1个3度内点。

求T的树根的度数。

4 (7分)设无向图G是n(n≥3)个顶点的极大平面图，证明G的对偶图G*的边连通度l(G)≥2，并且G*是3-正则图(Δ(G)=d(G)=k的无向图G称作k-正则图)。

5 (4分)设R={| x,yÎnÙx+3y=12}，求R2。

6 (6分)设A为集合，B=P(A)-{Æ}-{A}，且B≠Æ。

求偏序集<B,&IACUTE;>的极大元，极小元，最大元和最小元。

7 (4分)设A={1,2,3}，fÎAA，且f(1)=f(2)=1，f(3)=2，定义G：A→P(A)，G(x)=f-1(x)。

说明G有什么性质(单射、满射和双射)，计算值域ranG。

8 (4分)设I是格L的非空子集，如果(1) "a,bÎI，有aÚbÎI，(2) "aÎI，"xÎL，有x≤aÞxÎI。

则称I是格L的理想。

证明：格L的理想是一个子格。

9 (7分)设G为n阶群，aÎG。

令H={xax-1|xÎG}，N(a)={x|xÎGÙax=xa}。

数据结构题库及答案Excel1. 单链表的插入操作- 问题：请描述在单链表中插入一个新节点的步骤。

- 答案：首先确定插入位置，然后创建一个新节点。

将新节点的next指针指向原链表中该位置的节点。

接着，更新前一个节点的next指针指向新节点。

最后，如果插入位置是链表头部，则更新头指针。

2. 二叉树的遍历方法- 问题：请列举二叉树的三种基本遍历方法。

- 答案：前序遍历（根-左-右）、中序遍历（左-根-右）、后序遍历（左-右-根）。

3. 哈希表的冲突解决方法- 问题：在哈希表中，如何解决冲突？- 答案：常见的冲突解决方法有开放地址法（线性探测、二次探测、双重哈希）和链地址法。

4. 堆排序的基本原理- 问题：堆排序的基本原理是什么？- 答案：堆排序基于二叉堆数据结构，通过构建最大堆或最小堆，然后逐步将堆顶元素与堆尾元素交换，缩小堆的范围，最后得到有序序列。

5. 图的深度优先搜索（DFS）- 问题：请简述图的深度优先搜索（DFS）的基本思想。

- 答案：DFS从图的某个顶点开始，沿着邻接表的边尽可能深地搜索，直到无法继续为止，然后回溯到上一个顶点，继续搜索其他邻接顶点。

6. 快速排序算法的时间复杂度- 问题：快速排序算法的平均时间复杂度是多少？- 答案：快速排序算法的平均时间复杂度为O(n log n)。

7. 栈的后进先出（LIFO）特性- 问题：栈的后进先出特性是如何体现的？- 答案：栈的LIFO特性体现在元素的添加和删除操作都发生在栈顶，即最后添加的元素最先被删除。

8. 队列的先进先出（FIFO）特性- 问题：队列的先进先出特性是如何体现的？- 答案：队列的FIFO特性体现在元素的添加操作在队尾进行，而删除操作在队首进行，即最先添加的元素最先被删除。

9. 最小生成树的构造方法- 问题：请列举两种最小生成树的构造方法。

- 答案：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。

10. 动态规划的适用场景- 问题：动态规划适用于解决哪些类型的问题？- 答案：动态规划适用于具有重叠子问题和最优子结构特性的问题，如斐波那契数列、背包问题、最长公共子序列等。

北京市考研计算机科学专业数据结构常考题数据结构是计算机科学专业中的基础课程之一，对于考研的学生来说，掌握数据结构常考题是非常重要的。

本文将介绍一些北京市考研计算机科学专业数据结构常考题，并附上详细的解答过程。

1. 栈和队列相关题目题目一：编写一个函数，判断输入的括号序列是否合法。

括号序列由"( )"、"[ ]"和"{ }"组成，要求括号必须按照正确的顺序闭合。

解答一：我们可以利用栈来解决这个问题。

遍历输入的括号序列，当遇到左括号时，将其压入栈中；当遇到右括号时，判断栈顶的括号是否与之匹配，如果匹配，则将栈顶的左括号弹出，继续检查下一个字符；如果不匹配，则返回false。

最后，如果栈中没有元素，表示所有的括号都匹配，返回true；否则，返回false。

题目二：给定一个字符串，判断其是否为回文字符串。

解答二：同样可以利用栈来解决。

将字符串的每个字符依次压入栈中，然后依次弹出栈顶元素与字符串的字符比较，如果全部相等，则说明是回文字符串；否则，不是回文字符串。

2. 链表相关题目题目三：给定一个链表，判断是否存在环。

解答三：可以使用快慢指针来解决。

定义两个指针，一个慢指针每次移动一步，一个快指针每次移动两步。

如果链表中存在环，那么两个指针最终会相遇；如果链表中不存在环，那么快指针会先到达链表的末尾。

题目四：给定一个链表和一个目标值，删除链表中所有等于给定值的节点。

解答四：遍历链表，如果节点的值等于目标值，删除该节点。

需要注意的是，删除节点时需要更新链表的指针，使得前一个节点指向后一个节点。

3. 树相关题目题目五：给定一个二叉树，求其前序遍历。

解答五：可以使用递归或者非递归的方式实现前序遍历。

递归实现时，先输出当前节点的值，然后递归遍历左子树，最后递归遍历右子树。

非递归实现时，使用栈来辅助遍历，先将根节点压入栈中，在栈不为空的情况下进行循环，每次循环弹出栈顶元素，并输出其值，然后将右子节点压入栈中，最后将左子节点压入栈中。

目录线性表 (1)栈和队列 (6)串 (8)数组和广义表 (10)树和二叉树 (13)图 (21)集合 (26)排序 (29)1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。

请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

【北京大学 1998 三、1 （5分）】类似本题的另外叙述有：（1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。

【南京理工大学1997 四、3（15分）】PROCEDURE merge(ha,hb);（2）已知头指针分别为la和lb 的带头结点的单链表中，结点按元素值非递减有序排列。

写出将la 和 lb 两链表归并成一个结点按元素值非递减有序排列的单链表（其头指针为 lc），并计算算法的时间复杂度。

【燕山大学 1998 五（20分）】2. 图（编者略）中带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。

两表中的元素皆为递增有序。

请写一算法求A和B的并集AUB。

要求该并集中的元素仍保持递增有序。

且要利用A和B的原有结点空间。

【北京邮电大学 1992 二（15分）】类似本题的另外叙述有：(1) 已知递增有序的两个单链表A，B分别存储了一个集合。

设计算法实现求两个集合的并集的运算A:=A∪B 【合肥工业大学 1999 五、1（8分）】（2）已知两个链表A和B分别表示两个集合，其元素递增排列。

编一函数，求A与B的交集，并存放于A链表中。

【南京航空航天大学 2001 六（10分）】（3）设有两个从小到大排序的带头结点的有序链表。

试编写求这两个链表交运算的算法（即L1∩L2）。

要求结果链表仍是从小到大排序，但无重复元素。

北京大学硕士研究生入学考试试题 1997～2009（缺2005、2006）===================================================================== 北京大学·1997年1997年1月25日上午社会学方法一、名词解释（每题4分，共24分）1、深度访问2、间接观察法3、同期群研究4、深度效度5、层次谬误6、理想类型法二、简答题（每题10分，共20分）1、分导体抽样与整群抽样的分类原则有何不同，为什么？2、试说明研究课题具体化与操作化的主要内容。

三、论述题（16分）试比较详析模式中，条件关系分析与变量关系检验的异同。

四、（20分）为了解某地今年人民的生活比去年是否有所改善，随机抽查8户人家。

结果有7户生活有改善，1户生活下降了。

试用符号检验法，推论该地人民的生活是否比去年有所提高（X=0.05）。

写出：1）原假设 2）备择假设 3）检验过程 4）推论结果（2=0.05）五、（20分）若根据列联表1：n11 n21 n31n12 n22 n32计算出用于检验的统计量∑∑(n_{ij}-E_{ij})^2x^2 = ------------------------------E_{ij} （注：x^2表示x的平方；E_{ij}表示ij为E的下标）那么，根据列联表2：Kn11 Kn21 Kn31kn12 kn22 Kn32计算出用于检验的统计量X2应等于什么？（注意：表2中所有格值都是表1相应格值的K倍）。

*******************************************************************************************北京大学·1998年1998年1月17日上午社会学方法一、名词解释（每个4分，共20分）1、命题和假设2、社群图3、抑制度量4、典型实验设计5、客观陈述法二、简答题（每个8分，共16分）1、简述科学研究的一般程序。

1997年细胞生物学
一,名词解释
stem sell, 衰老小体, tonoplast, cell coat, G protein linked receptor, part icle gun bombardment
gap junction, Hayflick limit
二,实验设计(选一个)
1,已知细胞内某一蛋白质的cDNA及其抗体,研究它在细胞内的合成,转运及修饰
2,已知一高等植物某一基因的cDNA,研究此基因在机体内的功能
三,问答
1,生命体内蛋白质,脂类,核酸装配的方式,你认为有几种,各举一例说明
2,细胞周期(分裂)与细胞程序性死亡在多细胞发育过程中有何作用?最近发现有些周期调控因子对细胞程序性死亡有诱发作用,对此你有何看法
3,图示细胞内蛋白质合成,转运的不同途径
4,植物初生壁与真菌细胞壁的区别
5,涉及叶绿体。

北京邮电大学97考研题注意事项：1、解答试卷应字迹清楚，语以确切画图工整；2、算法题应写明算法思想并对主要数据的类型、变量加以说明，算法力求结构清晰简明易懂，并加必要的注释；3、算法用类PASCAL语言编写，也可用你熟悉的语言编写，但要注明语种；4、答题纸上。

一、有递归算法如下：（10分）FUNCION sum (n:integer):intger;BEGINIF n=0 THEN sum:=0ELSE BEGINREAD (x);sum:=sum(n-1)+xEND;END;设初值n=4，读入 x=4,9,6,2问：1 若为局部变量时；该函数递归结束后返回调用程序的并画出在递归过程中栈状态的变化过程；2 若x为全程变量递归结束时返回调用程序的sum=?二、写出下面算法中带标号语句的频度。

（10分）TYPE AR=ARRY[1…n] OF datatype;PROCEDURE perm ( a: AR; k, n: integer);var x: datatype; i:integer;begin① if k=nthen begin②for i:=1 to n do③ write (a[i])writeln;end;else begin④for i:=k to n do’⑤ a[i]:=a[i]+i*i;⑥perm (a, k+1, n);endend;设k的初值等于1。

三、已知模式串t=’a b c a a b b a b c a b’写出用KMP法求得的每个字符对应的next和nextval函数值。

（10分）四、写出或画出下面两题的结果：（10分）1．归并段长度为9，4，7，3，8，6，15试画出3路平衡最佳归并树。

2．有二叉树中序序列为：A B C E F G H D后序序列为：A B F H G E D C请画出此二叉树。

五、求解下面有向图的有关问题：（15分）1 判断此有向图是否有强连通分量？若有请画出；2 画出此有向图的十字链表存储结构；其顶点表结点为：data firstin firstoutdata ------顶点的有关信息；firstin------指向一该顶点为弧头的第一条边的指针；firstout-------指向一该顶点为弧尾的第一条边的指针，其表结点的结构为：tailvex headvex weight hlink tlinktailvex,headvex-------分别为弧尾和弧头在图中的序号；weight---------弧上的权值；hlink,tlink--------分别为指向弧头相同和弧尾相同的下一条边的指针。