广东商学院试题纸.doc

1、广东商学院试题纸2006-2007 学年第二学期课程名称： 数据结构（B 卷） 课程代码：110104课程班号：05级12个班共_4_页-说明：本试卷用于闭卷考试，考试时间120 分钟。一、 单选题（每小题1 分，共 20 分）1、计算机内部数据处理的基本单位是【】。A、数据B 、数据项C、数据元素D、数据库2、线性表的顺序存储结构中，数据元素的逻辑位置和物理位置的关系是【】。A、不一致的B、一致的C、大致相同D 、个别元素相同3、顺序表的首地址是100，每个数据元素的长度为4，则第 6 个元素的地址是【】。A 、 106B、 104C、 120D、 1244、在一个具有n 个结点的单链表中删

2、除一个结点的时间复杂度是【】。A、 O(1)B 、O(n)C、 O(n2)D 、O(nlog 2n)5、插入和删除元素在同一端进行的线性表，称为【】。A、栈B、队列C、有序表D、循环链表6、判断一个顺序循环队列Q（元素个数为m）是否为满的条件是【】。A、 Q.front= =Q.rearB 、 Q.front= = （ Q.rear+1） % mC、 Q.front ！ =Q.rearD 、 Q.front ！=（ Q.rear+1 ）% m7、在一个链队列中，假设f 和 r 分别为队首和队尾指针，则插入s 所指结点的运算为【A 、f-next=s ； f=s；B 、 s-next=f ； f

3、=s；C、s-next=r ； r=s；D 、 r-next=s ； r=s；8、已知完全二叉树的第5 层共有 9 个结点，则其叶结点数是【】。A、 16B、32C、9D、12】。9、二叉树的第6 层至多有【】个结点。A 、12B 、32C、 63D、 6410、具有 5 层结点的平衡二叉树至少有【A 、12B、15】个结点C、 7D、 1711、下述哪一组编码是前缀编码【】。A 、0 ，11，011， 101C、0 ， 10， 11， 101B 、 00 ， 01， 11， 101D、 1 ，10， 011， 10012、具有 10 个顶点的无向完全图有【A、20B、90】条边。C、 45D

4、、 7213、求任意两个顶点之间的最短路径用【A 、 PrimB 、Dijkstra】算法。C、KruskalD、 Floyd14、对包含 A 、 5625 个元素的查找表进行索引顺序查找，每个分块为【B、 15C、25】个元素时D、45ASL最小。15、关键字的比较次数与记录的初始排列次序无关的内部排序方法是【A 、选择排序B、起泡排序C、插入排序16、每一趟排序都能确定一个元素的最终位置的排序方式是【A 、 起泡排序B、快速排序C、插入排序17、以下几种排序方法中，关键字比较次数最少的是【】。A 、快速排序B、基数排序C、起泡排序】。】。D 、希尔排序D 、基数排序D 、归并排序18、快速

5、排序在【】情况下最不利于发挥其长处。2006-2007 学年第二学期数据结构期末试卷BA、待排记录太多B、使用次关键字C、待排记录基本有序D、都不对19、堆排序的两个主要操作是【】。A 、比较和移动B、初建和筛选C、分配和收集D、选择和插入20、稳定的排序方法是【】。A 、堆排序B、快速排序C、希尔排序D、插入排序二、 填空题（每空1 分，共 20 分）1、线性结构反映结点间的逻辑关系是一对一的，而非线性结构反映结点间的逻辑关系是或的。2、链表相对于顺序表的优点有和操作方便。3、从逻辑结构上看，栈是操作受限的结构，遵循原则。4、图的存储结构有四种：、十字链表和邻接多重表表示法。5、如果已知二叉

6、树的和遍历序列，可以唯一确定该二叉树。6、构造稀疏图的最小生成树适合用算法，构造稠密图的最小生成树适合用算法。7、对二叉排序树进行处理，可以使平均查找长度ASL 最小。8、一棵 m 阶的 B_树中具有 k 个子树的非叶子结点含有个关键字。9、假设记录R1 和 R2 的关键字相同且R1 在 R2 的前面，如果排序后 R1 仍在 R2 的前面则称排序方法是的，一般情况下基于关键字比较的排序算法是稳定的。10、在插入排序和选择排序中，若初始关键字基本正序则选用，若基本逆序则选用。11、在堆排序、快速排序和归并排序中，稳定的排序方法是，平均情形下最快的排序方法是。三、 简答题（每小题5 分，共 20

7、分）1、 求下列程序段的时间复杂度，要求简明扼要的写出推导过程和结果。i=s=0;while (sdatadata);if(T-lchild) Print_NLT(T-rchild,x)if(T-rchild) Print_NLT(T-lchild,x);/Print_NLT注：上题涉及的类型定义如下：二叉排序树采用二叉链表存储，其存储结构定义语句如下：typedefstructBitNode TElemType data;StructBiTNode*lchild, *rchild;BiTNode, *BiTree;TElemType 的定义如下：typedefstruct TElemTypeintkey;/关键字InfoTypeotherinfo;/ 其它数据项 TElemType;六、 算法设计题（共12 分）有一表长不小于2 的单链表，试写一算法对其实现就地逆置，即利用原表的存储空间将线性表（a1，a2 ， ， a