中国人民公安大学硕士研究生招生考试 823 物理与数据结构 考试大纲 （本大纲适用于公安技术一级学科刑事科学技术二级学科招生初试） 目 录 I. 考 查 目 标 . 3 II. 考试形式和试卷结构 . 3 III. 考 查 内 容 . 4 第一部分 物理 . 4 第二部分 数据结构 . 6 IV. 参 考 试 题 . 8 V. 参 考 答 案 . 13 I. 考 查 目 标 物理与数据结构 包括物理和 数据结构 两部分内容，要求考生具有扎实的物理基础 以 及数据的组织、存储、处理等能力 。 一、 物理学主要考查学生对物理学基础知识的掌握程度以及运用物理学基础知识分 析问题和解决问题的能力，要求学生能够比较系统地掌握刑事技术中比较常用的物理学 基础知识，理解力学光学基本定理和定律，掌握现代检验检测技术、仪器的基本原理， 能够熟练应用物理学相关知识解决刑事技术应用过程中的有关问题 。 二、数据结构主要考查 学生对数据的组织、存储、处理等能力，算法设计以及对算 法的分析和评价的掌握程度。要求考生理解数据结构的 逻辑结构和物理结构的基本概念， 熟练掌握各种数据结构以及有关算法，并具有综合运用所学知识分析和解决刑事科学技 术实际应用问题的能力。 II. 考试形式和试卷结构 一、试卷满分及考试时间 本试卷满分为 150分，考试时间为 180分钟。 二、答题方式 答题方式为闭卷、笔试。 三、试卷内容结构 第一部分 物理 75分 第二部分 数据结构 75分 四、试卷题型结构 （一）第一部分：物理（ 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.010-2cm,缝到屏距离 f=50cm;(2)光栅的光栅常量 b+b=2.010-3cm,缝到屏距离 f=50cm。 2 用细线将一质量为 m 的大圆环悬挂起来，两质量为 M 的小圆环套在大圆环上， 可无摩擦滑动。若小圆环沿相反方向从大圆环顶部 自静止下落，求下滑过程中 取什么 值大圆环刚能升起？ (大圆顶端设为零势能面 ) 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 二维数组 A1218采用列优先的存储方法，若每个元素各占 3个存储单元，且 A00地址为 150，则元素 A97的地址为 ( )。 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用 Prim方法对下图构造最小生成树，要求从顶点 A出发。（ 1）画出最后所得的 树，（ 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分） 1 B 2 D 3 A 4 C 5 C 6 B 7 C 8 D 9 B 10 B 二、填空题（共 15分，每空 3分） 1两个物体之间作用力和反作用力，沿同一直线，大小相等，方向相反，分别作用在两 个物体上 2 10 3 介质折射率与光的几何路程之积 4 2.4d 2.4 2d + 5 暗纹 三、计算题（共 30分，每题 10分） 1解：（ 1）相邻明条纹间距 / 1.25 m ml f b= （）相邻明条纹间距 /( ) 1 2 .5 m mx f b b + = 2解：对于小圆，只有重力做功机械能守恒 2 2 10 (1 c o s ) 2 2 (1 c o s ) M v M g R v g R = = 向心力 2 2 (1 c os ) c osMvF M g M gR = = 大圆对小环的支持力 N 指向圆心 小环对大圆 NN= 当 N 在竖直方向分量等于大圆 mg 时大圆刚好升起 2 c os 2 c os 2 ( 1 c os ) c os 2 c os 6 4 1 c os 36 6 4 1 a r c c os ( ) 36 N mg N mg mg N Mg Mg m M m M = = = = = =+ 3解： （ 1） x = Ldk, d=0.2mm, L=1m, x1=2.5m, k=1带入 =500nm （ 2） x = D d = 161070.2103 = 3mm 第二部分 数据结构 一、单项选择题（共 10分，每题 1分） 1 A 2 B 3 D 4 A 5 C 6 A 7 A 8 A 9 B 10 D 二、填空题（共 10分，每空 1分） 1 16个 2 11 3 N2+1 4 5位 5 9 6 2e 7多对多 8入度 9比较和移动 9 2 三、应用题 （共 35分，每小题 7分） 1解：（ 1）用链地址法处理冲突构造得的哈希表为 （ 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 解： (1) 16 27 05 42 23 51 11 90 (2) 16 05 27 23 42 11 51 90 (3) 05 16 23 27 11 42 51 90 (4) 05 16 23 11 27 42 51 90 (5) 05 16 11 23 27 42 51 90 (6) 05 11 16 23 27 42 51 90 (7) 05 11 16 23 27 42 51 90 5解： （ 1）该二叉树的后序序列为： J,G,D,H,E,B,K,L,I,F,C,A。 （ 2）该二叉树的形式如图所示： A B C D E F G H I J K L （ 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(plchild); printf(“%c”,pdata) inorder(prchild); 2解： 设图的邻接矩阵为 gnn（针对无向图），定义邻接表节点的类型为 struct edgenode int adjvex; edgenode next; typedef edgenode *adjlistn; void matritolist (int g, adjlist gl, int n ) edgenode *p, *q; for (int i=0 in; i+) gli=null; for (int i=0; in; i+) for ( int j=0; jadjvex=j; p-next=null; if(gli=null) gli=p; q=p; else q-next=p; q=p;