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分，共10分）

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
3、 ?
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。（ ）
四