数据结构期末复习题库.doc

1. 、选择题1) （无序或有序）顺序表中插入元素的时间复杂度：_O(n)_。2) 带头结点的链表，如何判断其是否为空链表：_head-data=0_。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针.3) 数组形式存放的队列，其大小为n，最多可存放多少个元素（即在具有n个单元的循环队列中，队满时共有多少个元素 ）：_n-1_。常用空闲单元法（人为浪费一个单元，则队满特征可改为front=(rear+1)%N）：即front和rear之一指向实元素，另一指向空闲元素。4) 栈操作的原则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。5) 树的前驱结点： 在一棵树中，每个结点称为它的每棵子树的根结点的前驱结点（即该结点的上层的那个结点(直接前驱)）。如孩子的前驱结点是双亲结点 6) 二叉树存储是用二叉链表，二叉树的空指针域与非空指针域的关系：具有n个结点的二叉链表中，共有2n个指针域。其中有n-1个非空链表，用来指示结点的左孩子和右孩子，其余的n+1个指针域为空。7) 折半（二分）查找的平均查找长度：当n很大时，ASL= log2(n+1)-1 可以作为二分查找成功时的平均查找长度。8) 有向图的度的计算：即顶点的度的计算。入度和出度：顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v)；顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)；在有向图中, 顶点的度等于该顶点的入度与出度之和。 9) 列出各种排序中，最坏的时间复杂度： 平均时间 最差 最佳 辅助空间 稳定性直接插入 O(n2) O(n2) O(n) O(1) 稳定起泡排序 O(n2) O(n2) O(n) O(1) 稳定直接选择 O(n2) O(n2) O(n2) O(1) 不稳定希尔排序 O(n1.5) O(1) 不稳定快速排序 O(nlog2n) O(n2) 同平均 O(log2n) 不稳定堆排序 O(nlog2n) 同平均 同平均 O(1) 不稳定归并排序 O(nlog2n) 同平均 同平均 O(n) 稳定基数排序 O(d(n+r) 同平均 同平均 O(n+r) 稳定在最坏情况下，快速排序法的时间复杂度为O(n2) ，变为排序最慢的方法。10) 顺序存储与链式存储的优缺点：2、 判断题1) 数组与元素之间的关系：若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组Vn的下标）。设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1) = LOC(ai)+L LOC(ai) = LOC(a1) + L *（i-1）2) 链式的物理结构与逻辑结构的相关判断：链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。 3) 循环单链表队列是否一定需要头指针和尾指针：一个队列需要两个分别指示队头和队尾的指针（头指针和尾指针）才能唯一确定；解决假溢出的途径采用循环队列。4) 递归法的优点是：递归可以代替循环，但是，不是所有的可计算问题都可由递归转换为循环。递归清晰易懂，易于设计算法，具有较高的开发效率，所设计的程序具有更好可读性和可维护性。5) 广义表：广义表是线性表的推广，也称为列表（lists） 记为： LS = ( a1 , a2 , ， an ) 在广义表中约定：1 第一个元素是表头，而其余元素组成的表称为表尾；2 用小写字母表示原子类型，用大写字母表示列表。3 ai 区别于线性表中只限于是单个元素，而在广义表中或者是单个元素或者是一个广义表，分别称为广义表的原子和子表。注意：a. 为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。b. 广义表是递归定义的。因为在描述广义表时又用到了广义表的概念。6) 堆排序（选择排序中的一种，考堆排序的操作）： 堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序.。 堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？ 第二个问题解决方法筛选方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。7) 二叉树遍历的时间复杂度：三种遍历具有相同的时间复杂度和空间复杂度。若二叉树的结点个数为n，则算法的时间复杂度为O（n）。8) 邻接矩阵的大小有什么决定：邻接矩阵 表示各个顶点之间关系，设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edgenn9) 判断某种排序是否稳定：参看选择题910) 什么是物理结构：数据结构在计算机中的表示（又称映射）称为数据的物理结构，或称存储结构。 3、填空题1 数组结构（与判断第1题类似）2 链表的插入删除操作： 插入：（先挖“坑”,后种“萝卜”！)x结点的生成方式： S= new node; S-data=x; Step1：S-next=p-next Step2： p-next=s （思考：Step1和2能互换么？）删除：要借助辅助指针变量q q = p-next; p-next=q-next delete q 3 链栈用链表实现栈的操作：插入，删除等（程序函数相互调用，将关键的值保存在栈，保证顺序返回） 链栈的构造方式以头指针为栈顶，在头指针处插入或删除.一个链栈由其栈顶指针唯一指定 设st指向栈顶元素，则 st = NULL 表示栈空链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成。顺序栈入栈函数PUSH（） 顺序栈出栈函数pop()status Push(ElemType e) status pop( ) if(topM)上溢 if(top=L) 下溢 else s+top=e; else e=s-top; return(e);4 树的后驱结点：在一棵树中，每棵子树的根结点称为该结点的后继结点。5 在广义表中，如何判断结点层次：有长度表中元素个数 有深度表中括号的重数E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E为递归表6 高度平衡二叉树，左子树，右子树高度最多相差多少：7 图中最多有多少条边，顶点最大会有几度：若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图 图任意两个顶点都有一条边相连接4、 分析题1) 树转化为二叉树，直接写出结果（孩子是有左右之分的）2) 二叉树的遍历（前，中，后）3) 哈夫曼编码（给你一串字符，自己统计每个字符出现的概率），要写过程的4) 图里面最小生成树：Prim算法和Kruskal算法，都要写过程，过程是画图5、 编程题1、冒泡排序（用主函数调用子函数，写一个完整程序）#include#define N 5void MAOPAO(int arryN) int j,k; int temp;for (j=0; jN-1; j+) for (k=0; karryk+1) temp=arryk; arryk=arryk+1; arryk+1=temp; main()int j;int aN;printf(请输入5个数:n);for (j=0 ;jN ; j+)scanf(%d,&aj);MAOPAO(a);printf(排序后的数字为:n);for (j=0;jN;j+)printf(%5d,aj); 2、顺序查找#includestdio.hint seek(int a10,int key)int i; for(i=0;i5;i+) if(key=ai) return i; return -1;main()int a5,i,key,loc;printf(enter 5 numbers:n);for(i=0;i5;i+)scanf(%d,&ai);printf(enter key:n);scanf(%d,&key);if(seek(a,key)=-1)printf(not find!);elseloc=seek(a,key);printf(find and loctiong is:%d,loc); 总复习第1章 视觉特性与计色制1. 视觉特性：（1）亮度感觉：人眼的明暗感觉是相对的，重现的图像亮度无需与景物的实际亮度相等，只需保持二者的对比度C不变。 （2）分辨率：眼睛分辨景色细节的能力有一个极限值；人眼对彩色细节的分辨能力较差，对黑白细节的分辨力较强。 （3）视觉暂留与闪烁：人眼的主观亮度感觉总是在时间上滞后于实际亮度的改变；人眼在周期性光脉冲的刺激下，当频率偏低时，人眼会产生一明一暗的感觉闪烁。2.描述彩色的三个基本参量：（1）亮度光的明暗程度； （与光通量有关）（2）色调颜色的类别； （与彩色光中各基色的比例有关）（3）色饱和度彩色的深浅。（与彩色光中白光的 比例有关）3. 三基色原理与相加混色：自然界中，绝大多数的彩色都可以由三种基色按不同的比例相加混合得到。 混色规律： 红绿黄 红兰紫 绿兰青 红绿兰白4. 配色方程 F=RR+GG+BB R、G、B为三色系数; R、G、B为基色单位。5. 亮度方程: Y=0.3R+0.59G+0.11B第2章 电视成像原理与视频信号的产生1. CCD图像传感器： 工作原理： （1）光电转换； （2）电荷转移； （3）自扫描。 基本结构： （1）帧转移型FTCCD； （2）行间转移型IT CCD； （3）帧行间转移型 FITCCD。 2. 逐行扫描与隔行扫描： （1）逐行扫描：一帧画面（图像）一次性完成扫描。 （2）隔行扫描：一帧画面（图像）分二场完成扫描。优点： 既保证了图像的清晰度，又压缩了视频信号频带宽度。 缺点： 行间闪烁效应。 并行现象。 垂直边沿锯齿化现象。 3.扫描参数: （1）行扫描：行频fH=15 625 Hz，行扫描周期 TH=64 s（2）场扫描：场频 fV50Hz，场周期TV=20ms（3）每帧扫描行数：Z625行，每帧有效扫描行数：575行；（4）清晰度与分解力：垂直分解力决定于图像的每帧有效扫描行数；水平分解力主要与视频信号带宽有关。4. 视频图像信号:黑白:（1）亮度信号：电平高低反映图像的亮度（2）同步信号：确保收发二端扫描同步（3）消隐信号：使行、场逆程期间不产生回扫（4）开槽脉冲：保证场同步期间行扫描的稳定 （5）均衡脉冲：保证隔行扫描的准确性彩色 （1）基色信号：R、G、B （2）亮度信号：Y=0.30R+0.59G+0.11B （3）色差信号： RY BY 第3章 彩色视频信号的处理与制式 1. 频谱交错与高频混合：根据频谱交错原理，采用调幅技术将色差信号的频谱搬移到亮度信号的频谱中间，使色度信号的频谱与亮度信号的频谱相互错开，实现共频带传送； 根据高频混合原理，亮度信号以06MHz宽带传输，色度信号以01.3MHz窄带传输，既节省频带又可以减少亮度信号和色度信号共带传输产生的相互干扰。 2. NTSC制：（1）正交平衡调幅与同步检波： 两路色差信号分别对相位差为900的载波进行调制，这样，色度信号所占的带宽就只有2.6 MHZ，减小色度对亮度的干扰。同步检波：色度信号的解调同步检波电路由模拟乘法器和低通滤波器组成 （2）色同步信号：作为接收机恢复副载波的频率和相位的基准，用于解调色度信号。（3）色度信号的幅度压缩：压缩后的色差信号：色度信号：色度信号的幅度表示彩色的饱和度，相位角表示色调。（5）微分增益和微分相位失真：微分相位失真：亮度电平的变化而引起的色度信号相位移的变化导致色调失真。微分增益失真：亮度电平变化而引起的色度信号增益的变化引起色饱和度失真。 3. PAL制： （1）技术特点：将色度信号 ec(t)=u(t)+v(t)中的 V分量 逐行倒相为 ec(t)=u(t)v(t) U(t)SinsctV(t)Cossct （2）PAL制编码：5个组成部分 矩阵变换：将R、G、B线性组合（信号变换和幅度压缩）形成Y、U和V信号。 亮度陷波及延迟：陷波在副载波fSC附近对亮度信号进行衰减，减少色度信号对亮度信号的干扰。延迟将亮度信号延迟0.6 s使亮度信号和色度信号在时间上一致，消除彩色镶边现象。 副载波形成：由同步芯片产生副载波信号fSC 、 P脉冲、 K脉冲、 复合同步和复合消隐信号， 供平衡调幅和信号合成使用。 sinsct cossct cossct 平衡调幅：将色差信号和K脉冲平衡调幅为色度信号和色同步信号。 ec(t)= U（t） sinSCt V (t)cosSCt eb(t)= Ksinsct Kcossct 信号混合：将Y、 ec(t) 、 eb(t)以及复合同步信号S脉冲混合， 组成彩色全电视信号CVBS 。 (3). PAL制解码：五步信号处理 亮度信号和色度信号的分离频带分离法；色同步信号和色度信号的分离时间分离法；色度信号的两个分量FU、FV的分离频谱分离法；（梳状滤波器） 同步检波； 从色度信号分量u和v中解调出色差信号U、V，用模拟乘法器和低通滤波器来实现。矩阵变换：将Y、 U、 V 信号还原为三基色信号。（4） PAL制色同步信号的两个功能：一是给接收机恢复副载波提供解调副载波的基准频率和相位（与N制相同）；二是给接收机提供逐行倒相的识别信息。给接收机提供一个极性切换信息，来识别哪一行是不倒相NTSC行， 哪一行是倒相PAL行。 第4章 电视广播与视频信号的传输1.地面电视广播:（1）图像信号采用调幅方式，伴音信号采用调频方式，调制后的图像信号和伴音信号统称为射频电视信号（RF）。 （2）残留边带调幅：对00.75MHz图像信号采用双边带发送，对0.75