北航 1999-2002 程序设计与数据结构考研试题

一、选择题1. 算法的计算量的大小称为计算的（B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C ）【中科院计算所1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（C），它必须具备（B）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列D. 调度方法(2) A．可执行性、可移植性、可扩充性B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（B ）。

【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.5. 下面关于算法说法错误的是（ D ）【南京理工大学2000 一、1（分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（ C ）【南京理工大学2000 一、2 （分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低4 A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（ C ）两大类。

【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（ D ）。

【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D.栈9．以下数据结构中，哪一个是线性结构（D ）【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关（ A ）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（C ）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A．O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（ D ）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（ D ）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（ A ）是非线性数据结构【中山大学1999 一、4】A．树B．字符串C．队D．栈15. 下列数据中，（C）是非线性数据结构。

北京工业大学1999年硕士研究生入学考试试题考试科目：数据结构一、（26分）填空、选择（一个或多个）题，1-6题每小题2分：1下面的叙述中，不正确的是（）A关键活动不按期完成就会影响整个工程的完工时间。

B任何一个关键工程提前完成，将使整个工程提前完成。

C所有关键活动都提前完成，则使整个工程提前完成。

D提些关键活动若提前完成，则将使整个工程提前完成。

2 下面的排序算法中，不稳定得是（）A 起泡排序B 折半插入排序C简单选择排序D希尔排序E基数排序F堆排序。

3包含结点A，B，C的二叉树有-----------种不同的状态，---------种不同的二叉树。

4包含结点A，B，C的树有------种不同形态，------种不同的树。

5分块检索中，若索引表和各块内存均用顺序查找，则有900各元素的线性表分成-----块最好：若分成25块；其平均查找长度为--------。

6下面的程序段中，对ｘ的赋值语句的频度为------------（表示为n的函数）ＦＯＲ Ｉ：＝ １ＴＯ Ｎ ＤＯＦＯＲ Ｊ：＝１ ＴＯＩ ＤＯＦＯＲ Ｋ：＝Ｉ ＴＯ Ｊ ＤＯ ｘ：＝ｘ＋ＤＥＬＴＡ；７（８分）设有字符序列Ｑ Ｈ Ｃ Ｙ Ｐ Ａ Ｍ Ｓ Ｒ Ｄ Ｆ Ｘ要求按字符升列排序：采用初是长为４的希尔（３ｂｅｌｌ）排序，一趟扫描的结果是――――――――― 采用以元素为分界元素的快速排序，一躺扫描的结果是------------。

8（6分）已知广义表：A-（0），B-（），C-（a，b，c，d），D-（A，B，C）它们的存储结构图为（接两种结构种的任一种即可）：二（6分）编写递归程序将二叉树逆时针旋转90度打印出来。

如右图：（要求用类PASCAL 语言，并描述结构）。

三 （8分）用依次输入的关键字13，29，41，19，5，1，7和6建一棵三阶B-树，画出建该树的变化过程示意图（每插入一个结点至少用一张图）。

四（共20分）已知顶点1——6和输入边与权值的序列（如右框中）： 2 4 6 每行三个数表示一条边的两个端点和其权值，共11行。

20XX年“数据结构与C程序设计”(代码991)试题一、单项选择题（本题共20分，每小题各2分）1．对于长度为n的线性表，建立其对应的单链表的时间复杂度为( )。

A．O(1)；B．O(log2n)；．O(n)；D．O(n2)。

2．一般情况下，在一个双向链表中插入一个新的链结点，( )。

A．需要修改4个指针域内的指针；B．需要修改3个指针域内的指针；C．需要修改2个指针域内的指针；D．只需要修改1个指针域内的指针。

3．假设用单个字母表示中缀表达式中的一个运算数(或称运算对象)，并利用堆栈产生中缀表达式对应的后缀表达式。

对于中缀表达式A+B*(C/D-E)，当从左至右扫描到运算数E时，堆栈中的运算符依次是( )。

(注：不包含表达式的分界符)A．+*/-；B．+*(/-；C．+*-；．+*(-。

4．若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70，则后序遍历序列为( )。

A．30,40,20,50,70,60,80；B．30,40,20,70,60,80,50；C．70,60,80,50,30,40,20；D．70,60,80,30,40,20,50。

5．分别以6, 3, 8, 12, 5, 7对应叶结点的权值构造的哈夫曼(Huffman) 树的深度为( )。

A．6；B．5；C．4；D．3。

6．下列关于图的叙述中，错误的是( )。

A．根据图的定义，图中至少有一个顶点；B．根据图的定义，图中至少有一个顶点和一条边(弧)；C．具有n个顶点的无向图最多有n(n-1)/2条边；D．具有n个顶点的有向图最多有n(n-1)条边(弧)。

7．若在有向图G的拓扑序列中，顶点vi在顶点vj之前，则下列4种情形中不可能出现的是( )。

A．G中有弧<vi,vj>；B．G中没有弧<vi,vj>；C．G中有一条从顶点vi到顶点vj的路径；D．G中有一条从顶点vj到顶点vi的路径。

北京航空航天大学程序设计与数据结构专业考研真题(2000年)一、选择题(2’x10)1.在非空双向循环链表中q所指的结点前插入一个由p所指的链接点的过程依次为：rlink(p)←q；llink(p)←llink(q)；llink(q)←p；_________。

(A)rlink(q)←p(B)rlink(llink(q))←p(C)rlink(llink(p))←p(D)rlink(rlink(p))←p2.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B(1)1:2n n+⎡⎤⎢⎥⎣⎦中，则在B中确定a ij(i<j)的位置k的关系为_________。

(A)(1)2i ij*-+(B)(1)2j ji*-+(C)(1)2i ij*++(D)(1)2j ji*++3.某堆栈的输入序列为a，b，c，d，下面的四个序列中，_________不可能是它的输出序列。

(A)a，c，b，d(B)b，c，d，a(C)c，d，b，a(D)d，c，a，b4.深度为h的满m叉数的第k层有_________个结点。

(1≤k≤h)(A)m k-1(B)m k-1 (C)m h-1(D)m h-15.具有10个叶结点的二叉树中有_________个度为2的结点。

(A)8 (B)9 (C)10 (D)116.要连通具有n个顶点的有向图，至少需要_________条边。

(A)n-1 (B)n(C)n+1 (D)2n7.已知有向图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的拓扑序列是_________。

2013年''数据结构与C程序设计〃（代码991）试题一、单项选择题（本题共20分，每小题各2分）1.对于长度为n的线性表，建立其对应的収链表的时间复朵度为（）。

A.0（1）： B・ O（log2n）：・ O（n）： D・ O（n2）n2.一般情况下，在一个双向链表中插入一个新的链结点，（）。

A.需耍修改4个抬针域内的指针：B・需要修改3个指针域内的抬针：C.需要修改2个抬针域内的抬针：D.只需要修改1个指针域内的抬针。

3.假设用单个字母表示中缀表达式中的一个运算数（或称运算对彖）.并利用堆栈产生中缀表达式对应的后缀表达式。

对于中缀表达式A+B^C/D-E）,十从左至右扫描到运算数E时，堆栈中的运算符依次是（）。

（注：不包含表达式的分界符）A.+*/-：B. +*（/-： C・ +*-：・ +*（-o4.若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70,则后序遍历序列为（）。

A. 30,40,20,50,70,60,80：B. 30,40,20,70,60,80,50：C. 70,60,80,50,30,40,20：D. 70,60,80,30,40,20,50.5.分别以6, 3, 8, 12, 5, 7对应叶结点的权值构造的哈夫曼（Huffman）树的深度为（）。

A. 6： B・ 5： C・ 4： D・ 3。

&下列关于图的叙述中，错误的是（）0A.根据图的定义，图中至少有一个顶点：B.根据图的定义.图中至少有一个顶点和一条边（弧）：C.具有n个顶点的无向图最多有n&#61620;（n-l）/2条边:D.具有n个顶点的有向图最多有n&#61620;（n-l）条边（弧）。

7.若在有向图G的拓扑序列中.顶点W在顶点vj之前，则下列4种情形中不可能岀现的是（）。

A.G 中有弧vvi,vj＞：B.G 中没有3ft＜vi r vj＞；c. G中有一条从顶点W到顶点vj的路径：D・G中有一条从顶点vj到顶点vi的路径。

2017年北京航空航天大学991数据 结构与C语言程序设计考研真题
2018年北京航空航天大学991数据 结构与C语言程序设计考研真题
目 录
2010年北京航空航天大学993数据结构与C语言程序设计考研真题 2011年北京航空航天大学991数据结构与C语言程序设计考研真题 2012年北京航空航天大学991数据结构与C语言程序设计考研真题 2013年北京航空航天大学991数据结构与C语言程序设计考研真题 2014年北京航空航天大学991数据结构与C语言程序设计考研真题 2015年北京航空航天大学991数据结构与C语言程序设计考研真题 2016年北京航空航天大学991数据结构与C语言程序设计考研真题 2017年北京航空航天大学991数据结构与C语言程序设计考研真题 2018年北京航空航天大学991数据结构与C语言程序设计考研真题
2014年北京航空航天大学991数据 结构与C语言程序设计考研真题
2015年北京航空航天大学991数据 结构与C语言程序设计考研真题
2016年北京航空航天大学991数据 结构与C语言程序设计考研真题
2010年北京航空航天大学993数据 结构与C语言程序设计考研真题
2011年北京航空航天大学991数据 结构与C语言程序设数据 结构与C语言程序设计考研真题
2013年北京航空航天大学991数据 结构与C语言程序设计考研真题

第10章 排序排序排序一、选择题 1．某内排序方法的稳定性是指．某内排序方法的稳定性是指( )( )( )。

【南京理工大学【南京理工大学 1997 1997 1997 一、一、一、101010（（2分）】 A ．该排序算法不允许有相同的关键字记录该排序算法不允许有相同的关键字记录 B B B．．该排序算法允许有相同的关键字记录记录C ．平均时间为0（n log n n log n）的排序方法）的排序方法）的排序方法D D D．以上都不对．以上都不对．以上都不对2．下面给出的四种排序法中下面给出的四种排序法中( )( )( )排序法是不稳定性排序法。

排序法是不稳定性排序法。

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

）是稳定的。

）是稳定的。

【福州大学【福州大学 1998 1998 1998 一、一、一、3 (23 (2分)】A. A. 堆排序，冒泡排序堆排序，冒泡排序堆排序，冒泡排序B. B. B. 快速排序，堆排序快速排序，堆排序快速排序，堆排序C. C. 直接选择排序，归并排序直接选择排序，归并排序直接选择排序，归并排序D. D. D. 归并排序，冒泡排序归并排序，冒泡排序归并排序，冒泡排序4．稳定的排序方法是（．稳定的排序方法是（ ）） 【北方交通大学【北方交通大学【北方交通大学 2000 2000 2000 二、二、二、33（2分）】 A ．直接插入排序和快速排序．直接插入排序和快速排序 B B B．折半插入排序和起泡排序．折半插入排序和起泡排序．折半插入排序和起泡排序C ．简单选择排序和四路归并排序．简单选择排序和四路归并排序D D D．树形选择排序和．树形选择排序和shell 排序排序5．下列排序方法中，哪一个是稳定的排序方法？（．下列排序方法中，哪一个是稳定的排序方法？（ ） 【北方交通大学【北方交通大学【北方交通大学 2001 2001 2001 一、一、一、88（2分）】A ．直接选择排序．直接选择排序B B B．二分法插入排序．二分法插入排序．二分法插入排序C C C．希尔排序．希尔排序．希尔排序D D D．快速排序．快速排序．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（．若要求尽可能快地对序列进行稳定的排序，则应选（A A ．快速排序．快速排序 B B B．归并排序．归并排序．归并排序 C C C．冒．冒泡排序）。

北京航天航空大学2000年数据结构试题
一、选择题(2’x10)
1. 在非空双向循环链表中q所指的结点前插入一个由p所指的链接点的过程依次为：rlink(p)←q；llink(p)←llink(q)；llink(q)←p；_________。

(A)rlink(q)←p (B)rlink(llink(q))←p
(C)rlink(llink(p))←p (D)rlink(rlink(p))←p
2. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B 中，则在B中确定aij(i<j)的位置k的关系为_________。

(A) (B)
(C) (D)
3. 某堆栈的输入序列为a，b，c，d，下面的四个序列中，_________不可能是它的输出序列。

(A)a，c，b，d (B)b，c，d，a
(C)c，d，b，a (D)d，c，a，b
4. 深度为h的满m叉数的第k层有_________个结点。

(1≤k≤h)
(A)mk-1 (B)mk-1 (C)mh-1 (D)mh-1
5. 具有10个叶结点的二叉树中有_________个度为2的结点。

(A)8 (B)9 (C)10 (D)11
6. 要连通具有n个顶点的有向图，至少需要_________条边。

(A)n-1 (B)n (C)n+1 (D)2n。

计算机考研考试题目及答案计算机考研考试是广大计算机专业毕业生追求深造的重要途径之一。

通过考研，学生有机会进入优质的学术研究机构或者深入实践的科研岗位。

在这篇文章中，我们将为大家提供一些常见的计算机考研题目及其答案，希望能对正在备战考研的同学们有所帮助。

第一部分：数据结构1. 什么是数据结构？答案：数据结构是计算机存储、组织和管理数据的方式。

它涉及到各种数据类型，如数组、链表、栈、队列、树、图等，并提供了一系列操作这些数据类型的操作方法。

2. 请说明数组和链表的区别。

答案：数组是一种线性数据结构，其中的元素在内存中是连续存储的，可以通过索引访问。

链表是通过指针连接起来的节点构成的，节点在内存中可以是离散的，每个节点都包含了下一个节点的指针。

3. 请解释一下栈和队列的特点。

答案：栈是一种后进先出（LIFO）的数据结构，只允许从栈顶进行插入和删除操作。

队列是一种先进先出（FIFO）的数据结构，允许在队尾插入元素，在队首删除元素。

第二部分：操作系统1. 什么是进程和线程？答案：进程是指在计算机上运行的程序的实例，每个进程都有自己的内存空间和资源。

线程是进程中的执行单元，一个进程可以包含多个线程，共享进程的资源。

2. 解释一下死锁。

答案：死锁是指两个或多个进程在互斥、占有、等待和不可剥夺资源等条件下，无法向前推进的状态。

在死锁中，每个进程都在等待其他进程释放资源，因此无法继续执行。

3. 什么是虚拟内存？答案：虚拟内存是操作系统提供给应用程序的一种抽象概念，它使得应用程序认为自己拥有连续的可用内存空间，而实际上这个空间可能是分散存储于物理内存和硬盘上的。

第三部分：数据库1. 请解释关系数据库和非关系数据库的区别。

答案：关系数据库使用表格的形式组织数据，表格由行和列组成，通过事先定义的模式进行数据管理。

非关系数据库通常不使用表格，而是使用键值对、文档、图等方式组织数据。

2. 什么是SQL？答案：SQL（Structured Query Language）是一种用于管理关系数据库的编程语言。

B. 无向图；
C. AOV网；
D. AOE网。
,； ．
7令下列关千带权连通图的最小生成树的叙述中 令 正确的是一。 A. 最小生成树的代价不一定比该图其他任何一棵生成树的代价小；
B. 若图中出现权值相同的边时，则该图的最小生成树不是惟一的；
c. 若图中边上的权值各不相同，则该图的最小生成树是惟一的；
北京航空航天大学2016 年
硕士研究生招生考试初试试题科目代码991
数据结构与 C 语言程序设计（共 8页）
考生注意：所有答题务必书写在考场提供的答题纸上，写在本试题单上的 答题一律无效（本题单不参与阅卷）。
一、单项选择题（本题共20分，每小题各2分）
L若listl和list2分别为一个指向单向链表与指向双向链表的指针变量则下列叙述中， 正确的是—°
A. list2比listl占用更多的存储单元； B. Iistl与list2占用相同多的存储单元； C. listl和list2应该是相同类型的指针变量； D. 双向链表比单向链表占用更多的存储单元。
Байду номын сангаас
2. 下列关于队列的叙述中，错误的是 '0 A. 队列是一种插入和删除位置受到限制的特殊线性表； B. 做删除操作时要先判断队列是否为空，做插入操作时要先判断队列是否已满； C. 采用循环链表作为存储结构的队列称为循环队列； D. 通常情况下，循环队列比非循环的队列的空间使用率要高。
s. 若采用快速排序法对序列(49, 38, 65, 97, 76, 13, 27. 49')的元素按值从小到大进行排
D. push, pop, push, pop, push, pop。
4. 若某完全二叉树的第6层有24个叶结点，则该完全二叉树的结点总数最大为-一°

1.北京航空航天大学 1998年数理逻辑与编译技术试题资料下载2.北京航空航天大学 1998年数字与模拟电路试题资料下载3.北京航空航天大学 1991，1999、2001-2002综合考试试题资料下载4.北京航空航天大学 2000年信号与系统试题资料下载5.北京航空航天大学 1999年信号与系统试题资料下载6.北京航空航天大学 2000年数字与模拟电路试题资料下载7.北京航空航天大学 1999年数字与模拟电路试题资料下载8.北京航空航天大学 1999年微波技术试题资料下载9.北京航空航天大学 1999年电路分析试题资料下载10.北京航空航天大学 2000年微波技术试题资料下载11.北京航空航天大学 2001年数据结构试题资料下载12.北京航空航天大学 2002年数据结构试题资料下载13.北京航空航天大学 2002行政管理学试题资料下载14.北京航空航天大学 2002金融联考试题资料下载15.北京航空航天大学 2000年程序设计数据结构试题资料下载16.北京航空航天大学 2000年数理逻辑与编译技术试题资料下载17.北京航空航天大学 2000年电路分析试题资料下载18.北京航空航天大学 2001年程序设计与数据结构试题资料下载19.北京航空航天大学 2002年程序设计与数据结构试题资料下载20.北京航空航天大学 2003企业管理基础试题资料下载21.北京航空航天大学 2003-2005年日语（图片格式）试题资料下载22.北京航空航天大学 2003国际贸易基础试题资料下载23.北京航空航天大学 2003年行政管理综合知识试题资料下载24.北京航空航天大学 2003金融联考试题资料下载25.北京航空航天大学 2003证券投资学试题资料下载26.北京航空航天大学 2004年经济管理基础试题资料下载27.北京航空航天大学 2004年行政管理综合知识)试题资料下载28.北京航空航天大学 2004年证券投资学试题资料下载29.北京航空航天大学 2005企业管理基础试题资料下载30.北京航空航天大学 2004金融联考试题资料下载31.北京航空航天大学传热学2001试题资料下载32.北京航空航天大学 2005年金融联考试题资料下载33.北京航空航天大学信号与系统2001试题资料下载34.北京航空航天大学信号与系统2002试题资料下载35.北京航空航天大学信息类专业综合2004试题资料下载36.北京航空航天大学交通信息类专业综合2005试题资料下载37.北京航空航天大学信号与系统2003试题资料下载38.北京航空航天大学企业管理基础2004（7.22邓力文补充整理）（许明波绿色部分7。

北京航空航天大学程序设计与数据结构试题(2002年)一、简答题1. “数据结构”课程是计算机专业的基础课还是专业课，或者专业基础课？(2’)2. 学习“数据结构”课程需要哪些课程作为它的基础(举例两门课程)？若没有这些知识，对学习“数据结构”课程可能会产生哪些影响？请举例说明(不超过100字)。

(4’)3. “数据结构”课程将为那些课程学习奠定必要的基础？请举例说明哪些课程(举例两门课程)用到了“数据结构”课程的哪些知识(不超过100字)。

(4’)二、(5’)请推导出结论：具有n0个叶结点的哈夫曼树(Huffman)的分支总数为2(n0-1)。

三、单项选择题(2’x15)1. 线性链表中各链接点之间的地址__________。

A)必须连续B)部分地址必须连续C)不一定连续D)连续与否无所谓2. 在非空线性链表中由p所指的链接点后面插入一个由q所致的链接点的过程是依次执行动作__________。

A) link(q)←p; link(p)←q; B) link(q)←link(p); link(p)←q;C) link(q)←link(p); p←q; D) link(p)←q; link(q)←p;3. 在非空双向循环链表中由q所指的那个链接点前插入一个p指的链接点的动作对应的语句依次为rlink(p)←q, llink(p)←llink(q), llink(q)←p, __________。

(空白处为一条赋值语句)A) rlink(q)←p B) rlink(llink(q))←pC) rlink(llink(p))←p D) rlink(rlink(p))←p4. 在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了三次删除操作，此时栈顶元素是__________。

A) c B) d C) b D) e5. 若某堆栈的输入序列为1，2，3，……，n，输出序列的第1个元素为n，则第i个输出元素为__________。

1.如:
.即一有向树外加一个有向环所构成的所有有向图都不是一棵有向
树. 2.将 Kn+1 插入数组的第 n+1 个位置(即作为一树叶插入),然后将其与双亲比较.若是大于等 于 其双亲则终止调整,否则将 Kn+1 与其父亲交换.重复的将 Kn+1 与新的双亲比较,算法终止 于 Kn+1 大于等于其双亲或 Kn+1 本身已上升为根为止. 四.程序输出 1,2,3,......100.本题主要考察学生对函数中修改指针的理解 五. 1.略. 2.思想:若已知ห้องสมุดไป่ตู้b[0..i-1]的最长平台的长度为 p,且 b[i]是下一平台的开始位置,即 b[i]!=b[i-1], 则从 位置 i 开始计算下一平台的长度.若 p<q,则更新最长平台的长度 p.当 i=N 时,p 即为所求: i:=0; p:=0;//初始化 while i<N do{ q:=1;//b[i]构成长度为 1 的平台 i:=i+1;//改查下一元素 while i<N and b[i-1]=b[i] do{ q:=q+1;//当前平台长度加 1 i:=i+1 }
if q>p then p:=q; } 3.求树的直径的时间复杂度可为 O(n),O(n^2)和 O(n^3),若时间为 O(n^3) 适当扣分 解法一:先调用求所有点对见最短路径算法(每边权数为 1)如 FLOYD 算法,然后对指代矩阵 求最大的 COST[i,j]作为直径. 解法二:修改 Bfs 算法,使之遍历时,记录当前访问结点的深度(离根的边数),用存在度为 1 的 结 点作起点调用 Bfs,求出其他非根结点的深度,在各次调用 Bps 算法中求最大深度,即为树的 直径.时间 O(n(n+e))=O(n^2+ne)这里 O(ne)是一次外部调用 Bfs 的运行时间,最多调用 Bfs 次 数(指外部调用)不超过 O(n)(存储结构为邻接表时) 解法三:用邻接表作为存储结构 依次删去树叶(度为一的结点),将与树叶相连的结点度数减 1.设在第一轮删去原树 T 的所有 树叶后,所得树为 T1;再依次做第二轮删除,即删除所有 T1 的叶子;为此反复,若最后剩下一个 结点,则树直径应为删除的轮数*2.具体算法如下: m:=0; for i:=1 to n do if (du(v[i])=1)then{ enqueue(Q,v[i]);//叶子 vi 入队 m:=m+1;//m 记录当前一轮叶子数 } r:==0;//表示删除叶子轮数 while m>=2 do {//当前叶子轮数 j:=0;//j 计算新一轮叶子数目 for i:=1 to m do{ dequeue(Q,v);//出队,表示删去叶子 v 将与 v 相邻的结点 w 的度数减 1 if du(w)=1 then {//w 是新一轮的叶子 j:=j+1; enqueue(Q,w);//w 入队 } } r:=r+1;//轮数加 1 m:=j;//新一轮叶子总数 } if m=0 then return 2*r-1//m=0,直径为轮数*2-1 else return 2*r;// m=1,直径为轮数*2 NOTE:假定 T 结点数>1,否则在算法首部判定处理之.

单项选择题第1题一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。

如果按层次顺序从1开始对全部结点编号，问编号为n的结点的父结点（若存在）的编号是多少？（）A、2n-1B、Kn-1C、KD、1+2+3+…+K答案：B第2题下一段程序实现的功能是打印以h为头节点的单链表中的所有节点，哪一段程序是正确的：（）。

A、p = h while ( p != NULL ) {printf(p->data) p = p->next}B、while ( h != NULL ) {printf(h->data)h = h->next}C、p = h while ( p!= NULL ) {p = p->next printf(p->data)}D、p = h while ( p－>next!= NULL ) {p = p->next printf(p->data)}答案：A第3题文件的基本组织方式有：（）。

A、顺序组织、索引组织、散列组织和链接方式B、磁盘组织、磁带组织C、数据库组织D、关键字与非关键字答案：A第4题设n为正整数。

试确定下列程序段中带标号@的语句的频度。

X=91; Y=100; While(y>0) @If(x>100){ X=x–10; Y=y–1; }else x=x+1; ：（）。

A、无穷多次B、1100C、9100D、100答案：B多项选择题第5题下述陈述中哪一项是正确的():A、文件是由记录组成的集合B、记录是文件存取的基本单位C、文件是由数据项组成的D、数据项有时也被称之为字段答案：B|D第6题下列排序算法中哪些是不稳定的():A、昌泡排序B、选择排序C、快速排序D、堆排序答案：B|C|D判断题第7题在单向链表中，在X指向的结点后插入结点，对应的方法与X是否是头指针无关。

} } }
while (signal.availablePermits() > 0) { try { Thread.sleep(50); } catch (Exception e) { e.printStackTrace(); } System.out.println("一名顾客理完发"); if (signal.availablePermits() < 10) { signal.release();//V操作 } }
import java.util.concurrent.Semaphore; public class SleepBarber { public static void main(String[] args) { Semaphore signal = new Semaphore(10);//初始座位数为10 Semaphore sleep = new Semaphore(0);//初始为睡觉状态 Thread barber = new Thread(new Barber(signal, sleep)); barber.start(); try { Thread.sleep(1000); while (true) { Thread customer = new Thread(new Customer(signal, sleep)); customer.start(); Thread.sleep(100); } } catch (Exception e) { e.printStackTrace(); }
public Barber(Semaphore signal, Semaphore sleep) { this.signal = signal; this.sleep = sleep; } } }

北京航空航天大学数据结构与C语言程序设计2005-2008、2010-2012年（12年带
答案）
Tao：彩虹真题（考研考博）出售真题价格如下：
所有真题价格如下：
2000年之前真题试卷均可免费赠送（前提：购买其它年份真题，如此校只有1999-2000年，均为2元每年每份。

）
2001-2008年真题试卷均为1元每年每份
2009-2011年真题试卷均为2元每年每份
2012年真题试卷均为5元每年每份（若有）
2013年真题试卷均为10元每年每份（若有）
注：回忆版本价格从优，个别比较难得的专业课真题价格再定，如有附带答案的可免费附赠，个别特殊答案价格再定（会标注）。

恭祝大家考试成功，金榜题名！。

第10章排序一、选择题1．某内排序方法的稳定性是指( )。

【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对2．下面给出的四种排序法中( )排序法是不稳定性排序法。

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

【福州大学 1998 一、3 (2分)】A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序4．稳定的排序方法是（）【北方交通大学 2000 二、3（2分）】A．直接插入排序和快速排序 B．折半插入排序和起泡排序C．简单选择排序和四路归并排序 D．树形选择排序和shell排序5．下列排序方法中，哪一个是稳定的排序方法？（）【北方交通大学 2001 一、8（2分）】A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。

【北京邮电大学 2001 一、5（2分）】7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

（）就是不稳定的排序方法。

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

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

A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】10．下面的排序算法中，不稳定的是（）【北京工业大学 1999 一、2 (2分)】A.起泡排序B.折半插入排序C.简单选择排序D.希尔排序E.基数排序F.堆排序。