数据结构高手进,安徽电大数据结构期末试题一一、单选题(每小题3分,共30分)1、对于单链表形式的队列,队空的条件是（）A、F=R=NULLB、F=RC、F≠NULL且R=NULLD、R-F=12、下述排序算法中,稳定的

　　数据结构高手进,

　　安徽电大数据结构期末试题一

　　一、单选题(每小题3分,共30分)

　　1、对于单链表形式的队列,队空的条件是（）

　　A、F=R=NULLB、F=RC、F≠NULL且R=NULLD、R-F=1

　　2、下述排序算法中,稳定的是（）.

　　A、直接选择排序B、表插入排序C、快速排序D、堆排序

　　3、四组含C1～C7的结点序列中,哪一种是下列有向图的拓扑序列（）.

　　A、C1,C2,C6,C7,C5,C4,C3B、C1,C2,C6,C3,C4,C5,C7

　　C、C1,C4,C2,C3,C5,C6,C7D、C5,C7,C4,C1,C2,C6,C3

　　4、下列广义表中,深度为2的有（）.

　　A、(a,b)B、((c,(a,b)),d)

　　C、(c,(a,b))D、((a,b),(c,(a,b)))

　　5、从一个顺序队列删除元素时,首先要（）.

　　A、前移一位队首指针

　　B、后移一位队首指针

　　C、取出队首指针所指位置上的元素

　　D、取出队尾指针所指位置上的元素

　　6、设一个广义表中结点的个数为n,则广义表深度算法的时间复杂度为.

　　A、O(1)

　　B、O(n)

　　C、O(n2)

　　D、O(Log2N)

　　7、度为h的满二叉树（仅含根结点的二叉树高度为零）的结点最少是多少（）

　　A、h＋1

　　B、2h＋1

　　C、2h+1－1

　　D、2h

　　8、5个不同的数据元素进行直接插入排序,最多需要进行（）次比较.

　　A、8B、10C、15D、25

　　9、链表表示线性表的优点是（）

　　A、便于随机存取

　　B、花费的存储空间比顺序表少

　　C、便于插入与删除

　　10、一棵具有5层满二叉树中节点总数为（）.

　　A、31B、32C、33D、16

　　二、填空题(每题2分,共30分)

　　1.从逻辑结构看,线性表是典型的,树是典型的.

　　2.设有二维数组A[0..9,0..19],其每个元素占两个字节,第一个元素的存储地址为100,若按行优先顺序存储,则元素A[6,6]的存储地址为,按列优顺序存储,元素A[6,6]的存储地址为.

　　3.若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号,那么当i为且小于n时,结点I的右兄弟是结点,否则结点i没有右兄弟.

　　4、含有2n个结点的二叉树高度至少是,至多是（仅含根结点的二叉树高度为零）.

　　5、起泡法对n个关键码排序,在最好情况下,只需做次比较和次移动；在最坏的情况下要做次比较.

　　6、栈是一种表.队列又称为表.

　　7、一个广义表的元素分为和两类.

　　三、判断题（每小题2分,

　　1、栈是一种线性结构.（）

　　2、顺序表中所有结点的类型必须相同.（）

　　3、链接表中所有灵活利用存储空间,所以链表都是紧凑结构.（）

　　4、任何无环的有向图,其结点都可以排在一个拓扑序列里.（）

　　5、用Ch1,Ch2表示两个字符,若Ord(Ch1)＜Ord(Ch2),则称Ch1＜Ch2.（）

　　四、简答、应用题(每题10分,共30分)

　　1、某二叉树的节点数据采用顺序存储表示如下：

　　012345678910111213141516171819

　　E

　　A

　　F

　　D

　　H

　　C

　　G

　　B

　　（1）试画出此二叉树的图形表示；

　　（2）写出节点d的双亲节点及左、右子女

　　（3）将此二叉树看作森林的二叉树表示,试将它还原为森林

　　2、请简述散列函数在散列法存储中的作用,并举出一个散列函数的例子.

　　3、请画出下面广义表相应的加入表头结点的单链表表示,D(A(x,y,L(a,b)),B(z,