中国人民公安大学硕士研究生招生考试

823《物理与数据结构》考试大纲

（本大纲适用于公安技术一级学科刑事科学技术二级学科招生初试）

目 录

I.考查目标3

II.考试形式和试卷结构3

III.考查内容4

第一部分 物理4

第二部分 数据结构6

IV.参考试题8

V.参考 答案13

I. 考 查 目 标

物理与数据结构包括物理和数据结构两部分内容，要求考生具有扎实的物理基础以及数据的组织、存储、处理等能力。

一、物理学主要考查学生对物理学基础知识的掌握程度以及运用物理学基础知识分析问题和解决问题的能力，要求学生能够比较系统地掌握刑事技术中比较常用的物理学基础知识，理解力学光学基本定理和定律，掌握现代检验检测技术、仪器的基本原理， 能够熟练应用物理学相关知识解决刑事技术应用过程中的有关问题。

二、数据结构主要考查学生对数据的组织、存储、处理等能力，算法设计以及对算 法的分析和评价的掌握程度。要求考生理解数据结构的逻辑结构和物理结构的基本概念， 熟练掌握各种数据结构以及有关算法，并具有综合运用所学知识分析和解决刑事科学技 术实际应用问题的能力。

II. 考试形式和试卷结构

一、试卷满分及考试时间

本试卷满分为 150 分，考试时间为 180 分钟。二、答题方式

答题方式为闭卷、笔试。三、试卷内容结构

四、试卷题型结构

（一）第一部分：物理（75 分）

1. 选择题共 10 小题，每题 3 分，共 30 分

2. 填空题共 5 小题，每题 3 分，共 15 分

3. 计算题共 3 小题，每题 10 分，共 30 分

（二）第二部分：数据结构（75 分）

1. 单项选择题 10 小题，每小题 1 分，共 10 分

2. 填空题 10 小题，每小题 1 分，共 10 分

3. 应用题 5 小题，每小题 7 分，共 35 分

4. 算法设计题 2 小题，每小题 10 分，共 20 分

III. 考 查 内 容

第一部分 物理

一、力学部分（30%）

（一）质点运动学

1. 质点运动的描述

（1） 参考系、质点

（2） 位置矢量、运动方程、位移

（3） 速度、加速度

2. 圆周运动

（1） 平面极坐标

（2） 圆周运动的角速度

（3） 圆周运动的切向加速度和法向加速度、角加速度

（4） 匀速率圆周运动和匀变速率圆周运动

（二）牛顿定律

1. 牛顿定律

（1） 牛顿第一定律

（2） 牛顿第二定律

（3） 牛顿第三定律

2. 牛顿定律的应用

（三）动量守恒定律和能量守恒定律

1. 质点和质点系的动量定理

（1） 冲量、质点的动量定理

（2） 质点系的动量定理

2. 动量守恒定律

3. 动能定理

（1） 功

（2） 质点的动能定理

4. 保守力与非保守力、势能

（1） 万有引力和弹性力做功的特点

（2） 保守力做功的数学表达式

（3） 势能

5. 功能原理、机械能守恒定律

（1） 质点系的动能定理

（2） 质点系的功能原理

（3） 机械能守恒定律

6. 完全弹性碰撞、完全非弹性碰撞

7. 能量守恒定律 二、光学部分（70%）

（一）相干光

（二）杨氏双缝干涉

（三）光程、薄膜干涉

（四）劈尖、牛顿环

（五）光的衍射

1. 光的衍射现象

2. 惠更斯菲涅耳原理

3. 菲涅耳衍射和夫琅禾费衍射

（六）单缝衍射

（七）圆孔衍射、光学仪器的分辨本领

（八）衍射光栅

1. 光栅衍射条纹的形成

2. 衍射光谱

（九）光的偏振性和马吕斯定律

1. 自然光、偏振光

2. 偏振片、起偏与检偏

3. 马吕斯定律

（十）反射光和折射光的偏振

（十一）几何光学

1. 几何光学基本定律

2. 光在平面上的反射和折射成像

3. 光在球面上的反射和折射成像

4. 薄透镜

5. 显微镜、望远镜和照相机

第二部分 数据结构

（一）数据结构的基本概念

1. 什么是数据结构

2. 逻辑结构

3. 存储结构

4. 算法和算法分析

（二）线性表

1. 线性表的基本概念

2. 线性表的顺序表示和实现

3. 线性链表

4. 循环链表

5. 双向链表

6. 链表的应用

（三）栈和队列

1. 栈和队列的基本概念

2. 栈的顺序实现

3. 栈的链式实现

4. 栈的应用

5. 栈与递归的实现

6. 队列的顺序实现

7. 队列的链式实现

（四）串

1. 串的定义、性质和特点；

2. 串的设计、实现方法和基本操作；

3. 串的朴素模式匹配算法

4. KMP模式匹配算法

（五）数组和广义表

1. 数组的顺序表示和实现

2. 特殊矩阵

3. 稀疏矩阵

4. 广义表的定义

5. 广义表的存储结构

6. 广义表的运算

（六）树和二叉树

1. 树的定义和基本术语

2. 二叉树的定义和性质

3. 二叉树的顺序存储

4. 二叉树的链式存储

5. 遍历二叉树

6. 线索二叉树

7. 树的存储结构

8. 森林与二叉树的转换

9. 树和森林的遍历

10. 树与等价问题

11. 哈夫曼树及其应用

（七）图

1. 图的定义和基本术语

2. 图的数组表示法

3. 邻接表

4. 十字链表

5. 邻接多重表

6. 图的深度优先搜索

7. 图的广度优先搜索

8. 无向图的连通分量和生成树

9. 有向图的强连通分量

10. 最小生成树

11. 拓扑排序

12. 关键路径

（八）查找

1. 查找的基本概念

2. 顺序查找

3. 二分查找

4. 分块查找

5. 二叉排序树

6. 平衡二叉树

7. 散列查找

（九）内部排序

1. 直接插入排序

2. 希尔排序

3. 冒泡排序

4. 快速排序

5. 简单选择排序

6. 树形选择排序

7. 堆排序

8. 归并排序

9. 基数排序

10. 各种内部排序方法的比较

IV. 参 考 试 题

第一部 分物理一、单项选择题（共 30 分，每题 3 分）

1. 圆锥摆系统哪些量不守恒( )

A. 角速度 B.  动量 C.  机械能 D. 角动量

2. 真空当中以下哪种光的波长最短？( )

A. 红光 B.  蓝光 C.  黄光 D. 紫光

3. 真空当中以下哪种光的波长最长？( )

A. 红光 B.  蓝光 C.  黄光 D. 紫光

4. 光的相干条件是光矢量振动的(     )

A.频率相同，振幅相同，相位差恒定； B.方向相同，振幅相同，相位差恒定； C.方向相同，频率相同，相位差恒定； D.方向相同，频率相同，振幅相同。

5. 在相同的时间内，一束波长为λ的单色光在空气中和在玻璃中：(  ) A.传播的路程相等，走过的光程相等；

B.传播的路程相等，走过的光程不相等； C.传播的路程不相等，走过的光程相等； D.传播的路程不相等，走过的光程不相等。

6. 双缝干涉试验中下列光的条纹间距最宽的是？（ ）

A 红光 B  蓝光 C  黄光 D 紫光

7. 双缝间距 0.5 mm，当用波长为 500 nm 的单色光垂直照射时，在缝后 1.20m 处的屏上测得相邻两条干涉明条纹间距为 ( )

(A) 1.2 mm(B) 2.4 mm(C) 8.3 mm(D) 0.83 mm

8. 牛顿环的干涉条纹中心为( )

A. 暗纹 B.  明纹 C.  不一定 D.明或暗与牛顿环半径有关

9. 在双缝干涉实验中，用单色自然光，在屏上形成干涉条纹，若在两缝后放一个偏振片，则( )

A.干涉条纹的间距不变，但明纹的亮度加强； B.干涉条纹的间距不变，但明纹的亮度减弱； C.干涉条纹的间距变窄，且明纹的亮度减弱；D.无干涉条纹。

10. 系统机械能守恒的条件是( ) A.外力和内力都不做功；

B. 外力和非保守内力必须为零；

C. 只要外力和非保守内力做功之和为零； D.外力和非保守内力都不做功。

二、填空题（共 15 分，每空 3 分）

1. 牛顿第三定律:  。

2. 一物体从静止开始做圆周运动，切向加速度为3m / s2 ，圆半径 300m.  经过  s，加速度恰巧与半径成 450 角。

3. 光程是 

4. 空气，油，海水三种介质折射率分别为 1、1.2、1.3，海水上漂浮的油层厚度为d，则从海面上空看干涉光的光程差为 I=   从海底看干涉光的光程差为 I=  。

5. 劈尖干涉条纹的顶端是明文还是暗纹？ 

三、计算题（共 30 分，每题 10 分）

1. 某种光的波长为 λ =500nm,分别垂直照射到一单缝和一光栅上。分别求它们在屏上形成的第二和第三级相邻明条纹间距。(1) 单缝宽度 b=2.0×10-2cm, 缝到屏距离 f=50cm;(2)光栅的光栅常量 b+b′=2.0×10-3cm,缝到屏距离 f=50cm。

2. 用细线将一质量为m 的大圆环悬挂起来，两质量为 M 的小圆环套在大圆环上， 可无摩擦滑动。若小圆环沿相反方向从大圆环顶部自静止下落，求下滑过程中q 取什么值大圆环刚能升起？(大圆顶端设为零势能面)

3. 杨氏双缝的间距为 0.2mm，距离屏幕为 1m，求：（1）若第一级明纹距离为 2.5mm，求入射光波长。（2）若入射光的波长为 6000Å，求相邻两明纹的间距。

第二部分 数据结构一、单项选择题（共10分，每题1分）

1. 栈和队列的共同特点是（ ）。

A.只允许在端点处插入和删除元素 B.都是先进后出C.都是先进先出 D.没有共同点

2. 线性表采用链式存储时，节点的存储的地址（ ）。

A.必须是不连续的 B.连续与否均可

C.必须是连续的 D.和头节点的存储地址相连续3．以下数据结构中哪一个是非线性结构？（ ）

A.队列 B.栈 C.线性表 D.二叉树

4. 二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且A[0][0]地址为150，则元素A[9][7]的地址为( )。

A.42 B.432 C.435 D.438

5. 树最适合用来表示( )。

A.有序数据元素 B.无序数据元素

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据

6. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( ）的二叉树。

A.空或只有一个结点 B.高度等于其节点数C.任一结点无左孩子 D.任一结点无右孩子

7. 对稀疏矩阵进行压缩存储目的是（ ）。

A.便于进行矩阵运算 B.便于输入和输出

C.节省存储空间 D.降低运算的时间复杂度

8. 若采用邻接矩阵翻存储一个n个顶点的无向图，则该邻接矩阵是一个（ ）。

A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵9．图的广度优先搜索类似于树的（ ）次序遍历。

A.先根 B.中根 C.后根 D. 层 次 10．快速排序在最坏情况下的时间复杂度是（ ）

A.O(n2log2n) B.O(n2) C.O(nlog2n) D.O(log2n)

二、填空题（共10分，每空1分）

1. 一个二叉树第5层节点最多有  。

2. 已知完全二叉树T的第5层只有7个结点，则该树共有  个叶子结点。

3. 在一棵二叉树中，度为零的结点的个数为N0，度为2的结点的个数为N2，则有N0=  。

4. 假设用于通信的电文由8个字母组成，其频率分别为7,19,2,6,32,3,27,10。设计哈夫曼编码，其中字母的编码长度最大是  。

5. 一棵具有257个结点的完全二叉树，它的深度为  。

6. 一个无向图有n个顶点，e条边，则所以顶点的度数之和为  。

7. 在图中，任何两个结点之间都可能存在关系，因此图的数据元素之间时一种 

的关系。

8. 在有向图中，以顶点v为终点的边的数目称为v的  。

9. 大多数排序算法都有两个基本的操作：  。

10. 在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为  。

三、应用题（共35分，每小题7分）

1．设散列函数为 H（K）=K MOD 13，给定的键值序列为 13,41,15,44,06,68,12,

25,38,64,19,49。(1)画出用链地址法处理冲突构造得的哈希表 (2)计算 ASL

2. 

3. 有一份电文中共使用 5 个字符：a,b,c,d,e，它们的出现频率依次为 0.15、0.3、0.25、0.1、0.2，试画出对应的 Huffman 树(约定，小的做左子树)，并求出每个字符的 Huffman编码

4. 用冒泡排序法对关键字序列 16 42 27 05 90 23 51 11 进行排序，写出每一趟的排序结果

5. 已知一棵二叉树的前序序列为：A,B,D,G,J,E,H,C,F,I,K,L；中序序列：D,J,G,B,E,H, A,C,K,I,L,F。

（1） 写出该二叉树的后序序列；

（2） 画出该二叉树；

（3） 求该二叉树的高度(假定空树的高度为-1)和度为2、度为1、及度为0的结点个数。

四、算法设计题（共20分，每小题10分）

1. 已知二叉树的二叉链表存储表示，写出中序遍历的递归算法。

2. 试写出把图的邻接矩阵表示转换为邻接表表示的算法。

V. 参 考 答 案

第一部分 物理一、单项选择题（共 30 分，每题 3 分）

二、填空题（共15分，每空3分）

1．两个物体之间作用力和反作用力，沿同一直线，大小相等，方向相反，分别作用在两个物体上

2．10

3．介质折射率与光的几何路程之积

2.4d + l

4．2.4d 2

5．暗纹

三、计算题（共 30 分，每题 10 分）

1. 解：（1）相邻明条纹间距l = l f  / b = 1.25mm

（２）相邻明条纹间距Dx » l f /(b + b ') = 12.5 mm

2. 解：对于小圆，只有重力做功机械能守恒

0 = 1 Mv2 - MgR(1- cosq )

2

v2 = 2gR(1- cosq )

向心力

2

F = = 2Mg(1- cosq )ñMg cosq

R

大圆对小环的支持力 N 指向圆心小环对大圆 N = N '

当 N ' 在竖直方向分量等于大圆mg 时大圆刚好升起

2N ' cosq = mg

2N cosq = mg

N = mg

2 cosq

= 2Mg(1- cosq ) - Mg cosq

cosq = 1 ±

3 6

q = arccos(1 +

4 - 6m

M )

3 6

3. 解：

（1）x =

L kλ

d

, d=0.2mm, L=1m, x1=2.5m, k=1 带入

λ=500nm

（2）∆x = Dλ

d

= 1×6×10−7 = 3mm

0.2×10−3

第二部分 数据结构一、单项选择题（共 10 分，每题 1 分）

二、填空题（共10分，每空1分）

1．16个 2．11

3．N2+1 4．5位

5．9 6．2e

7．多对多 8．入度

9．比较和移动 9．2

三、应用题（共35分，每小题7分）

（2）ASL 为：20/12 2．解：

（1） 画出最后所得的最小生成树如下

（2） 按生成顺序写出所选择的边

(A,C) , (C,B), (C,G), (G, D), (D,F), (C,E)

3. 解：

对应的 Huffman 树如下：

Huffman 编码：

a 001

b 01

c 11

d 000

e 10

4. 解：

5. 解：

（1） 该二叉树的后序序列为：J,G,D,H,E,B,K,L,I,F,C,A。

（2） 该二叉树的形式如图所示：

（3） 该二叉树高度为：5；度为2的结点的个数为：3；度为1的结点的个数为：5；度为0的结点个数为：4。

四、算法设计题（共20分，每小题10分）

1. 解：

typedef struct BiTNode

{ char data;

struct BiTNode *lchild,*rchild;

} BiTNode,*BiTree;

void inorder( BiTNode *p)

{

if (p!=NULL){

inorder(p–>lchild); printf(“%c”,p–>data) inorder(p–>rchild);

}

}

2. 解：

设图的邻接矩阵为g[n][n]（针对无向图），定义邻接表节点的类型为

struct edgenode

{ int adjvex; edgenode next;

}