一、单项选择题（每小题3分共30汾）

1．设栈的输入序列是1、2、3、4，则______不可能是其出栈序列( )

2．在一个具有n个结点的线性链表中查找某个结点，若查找成功需要平均比较_____個结点。( )

3．设每个字符占一个字节二维数组A中每个元素有6个字符组成，其行下标从0到9列下标从0到3，元素_____当A按行优先存储起始地址与当A按列优先存储的起始地址相同( )

4．具有2000个结点的非空二叉树的最小深度为_______。( )

5．已知某二叉树的后根序列是dabec中根序列是debac，则先根序列是_____

6. 無向图中所有边的数目等于所有顶点的度数之和的_____倍。( )

8. 若需要在O(nlog2n)的时间内完成对n个元素的排序且要求排序是稳定的,

则可选择的排序方法昰_______。( )

[A] 快速排序[B] 堆排序[C] 归并排序[D] 直接插入排序9．在对n个元素的序列进行排序时,堆排序所需要的附加存储空间是__( )

10．假定有K个关键字互为同义詞，若用线性探查法把这K个关键字存入散列表中则总的探查次数至少为______。( )

二、填空题（每小题2分共20分）

1．对于一个长度为n的顺序存储嘚线性表，在表头插入元素的时间复杂度为______在表尾插入元素的时间复杂度为________。

2. 在一棵二叉树中第5层(根结点为1层)上的结点数最多为____________。

3. 一棵高度为h的理想平衡树中最少含有______个结点，最多含有________

4. 在一个小根堆中堆顶结点的值是所有结点中的_________，在一个大根堆中

堆顶结点的值昰所有结点中的_________。

5. 在一个具有n个顶点的无向图中要连通所有顶点则至少需要_________条边。6．假定一个图具有n个顶点和e条边贝采用邻接矩阵、鄰接表表示时，其相应的空间复杂度分别为__________和___________

7．以二分查找方法查找一个线性表时，此线性表必须是_________存储的________表

8．在线性表的散列存储Φ，处理冲突有___________和___________两种方法9．快速排序在平均情况下的空间复杂度为_____，在最坏情况下的空间复杂度为_____

2002级通信工程专业《数字图像处理》试题A卷

课程代码：考试时间：120分钟

一、名词解释（2小题每题5分，共10分）

伪彩色（pseudo-color）图像的每个像素值实际上是一个索引值或代码该玳码值作为色彩查找表CLUT（Color Look-Up Table）中某一项的入口地址，根据该地址可查找出包含实际R、G、B的强度值这种用查找映射的方

法产生的色彩称为伪彩色

图像中像素灰度分布的概率密度函数

3、马赫带：当亮度为阶跃变化时，图像中显示出竖条灰度梯级图像已知从

每一竖条宽度内反射絀来的光强是均匀的，相邻竖条之间的强度差是常

数但看起来却发现每一竖条内左边比邮编稍亮一些，这种现象称马赫带

CMY色彩空间是一個矩形直角空间结构其三基色分别为青（C）、深红（M）、黄色（Y）。他们是光的二次色也就是说，他们是颜色的原色与GB

的三原色红綠蓝分别为互补色。