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

Question

数据结构高手进,
安徽电大数据结构期末试题一
一、单选题(每小题3分,共30分)
1、对于单链表形式的队列,队空的条件是（ ）
A、F=R=NULL B、 F=R C、 F≠NULL且R=NULL D、 R-F=1
2、下述排序算法中,稳定的是（ ）.
A、直接选择排序 B、 表插入排序 C、快速排序 D、堆排序
3、四组含C1～C7的结点序列中,哪一种是下列有向图的拓扑序列（ ）.
A、 C1,C2,C6,C7,C5,C4,C3 B、 C1,C2,C6,C3,C4,C5,C7
C、 C1,C4,C2,C3,C5,C6,C7 D、 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、8 B、10 C、15 D、25
9、链表表示线性表的优点是（ ）
A、便于随机存取
B、花费的存储空间比顺序表少
C、便于插入与删除
10、一棵具有5层满二叉树中节点总数为（ ）.
A、31 B、32 C、33 D、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、某二叉树的节点数据采用顺序存储表示如下：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
E
A
F
D
H
C
G
B
（1） 试画出此二叉树的图形表示；
（2） 写出节点d的双亲节点及左、右子女
（3） 将此二叉树看作森林的二叉树表示,试将它还原为森林
2、请简述散列函数在散列法存储中的作用,并举出一个散列函数的例子.
3、 请画出下面广义表相应的加入表头结点的单链表表示,D(A(x,y,L(a,b)),B(z,A(x,y,L(a,b)))).
错的别发啊 求求各位大虾拉、、

Answer 1

一、
1、B
2、B
4、C 《 A的深度为1,B的深度为3,D的深度为3》
5、C
6、B?
7、C
8、B 直接插入排序 ：n个不同的数据元素,最多需要比较n*(n-1)/2
9、C
10、A
二、
1.线性结构 ,非线性结构 .
2.352 < 100+ (6*20+6)*2 > ,232 < 100+ (6*10+6)*2> .
3.i能被2整除,i+1
4、log2(2n+1) ,2n-1
5、n-1 0 n*(n-1)/2
6、只在栈顶进行操作 插入删除受限.
7、子表 数据元素
三、
1、对
2、错 数组中的元素必须 类型相同
3、错
4、错 拓扑序列不唯一
5、用Ch1,Ch2表示两个字符,若Ord(Ch1)＜Ord(Ch2),则称Ch1＜Ch2.（ ）
四