Question

数据结构复习题！求救，高分！

一、选择题（每题2分，共20分）
1、二分查找，要求被查找的表是（ ）
A 顺序表 B 分块有序表 C 链表 D 无限制
2、一完二叉树有30个接点，则该树有（ ） 层。(根为0层)
A 3 B 4 C 5 D 6
3、下列排序算法中，第一趟排序后，其最大的或最小的数一定在最终的位置上的是（ ）
A 归并排序 B 直接插入排序 C 快速排序 D 冒泡排序
4、设八栈序列为A,B,C,D,则栈可能产生的出栈序列是（ ）
A、 A C D B B、 C A D B
C、 D C A B D、 D A B C
5、如有一颗二叉树按先序遍历所得结果为（ ）
A A、C G B E F D A
B D B、A B C G D E F
C E F C、C G B A E D F
G D、G C B E F D A
6、下面哪个结构属于线形结构 （ ）
A 二叉排序树 B 线索树 C 队列 D 图
7、栈和队列都是 （ ）
A 没有限制的线形表 B 没有限制的非线形表
CD
8、在线性表操作中，常对某元素插入或删除。则采用什么存贮结构最节省运算时间（ ）
A、单链表 B、散列表 C、二叉链表 D、顺序表
9、设H为带头结点单向循环链表的头指针，P为移动指针，指针域为link，则表尾的判断条件是（ ）
A、H->link = H B、P = H C、P->link = nil D、P->link = H
10、先序遍历能得到A，B，C序列的不同二叉树，最多有几种（ ）
A、4 B、5 C、6 D、7

二、填空题（每题2分，共20分）
1、在单链表中，欲删除某一指定结点时，必须找到该结点的 结点。
2、 和 是操作点受限的线性表。
3、二分查找的条件是 。
4、深度为K的二叉树中结点总数最多为 。
5、在有n（n>0）个结点的二叉链表中，空链域的个数为 个。
6、在对有15个数据的有序表中作二分查找时，有 个结点查找长度为3。
7、在单链表中，若要在指针P所指结点后插入指针S所指结点，则需执行下列语句： 。
8、举出插入排序的两种排序法： 。
9、快速排序的时间复杂度是 。
三、解答下列各题（每题10分，共30分）
1、简述基数排序的思想方法。
2、如图所示森林，请将其转化为二叉树，并写出其前，中，后序遍历序列。
A
B C
D E F G
H I J K
L M N
3、利用哈夫曼树进行编码。
请写出下列字符集的最佳前缀码：
字符集： a b c d
频率（万次）：2 3 4 8
编 码：
（给出详细编码过程）
四、算法设计题（每题10分，共30分）
1、有一数组，随机存贮一串关键字代码，请用快速排序法将关键字由小到大排列写出其算法描述。
2、设有一二叉树，用链式存贮，结点结构如下
lc data Kc
请写出后序遍历该二叉树的算法描述。（方法不限）

Answer 1

一、选择题
ACDAA C*ADB (第7题选C或D)

二、填空题

1、前驱
2、栈、队列
3、被查找的表是已经有序的顺序表
4、2的K次方-1
5、n＋1
6、4
7、s->next=p->next;p->next=s;
8、直接插入排序、折半插入排序
9、O(nlogn)

三、解答下列各题
1、基数排序的基本思想是：从低位到高位依次对Kj(j=d-1，d-2，…，0)进行箱排序。在d趟箱排序中，所需的箱子数就是基数rd，这就是"基数排序"名称的由来。
2、图看不清楚
3、哈夫曼树进行编码
a:110
b:111
c:10
d:0

四、算法设计题
略

Answer 2

不好意思 只能回答部分选择题了

1. A
2. C
3. D
4. A
5. 看不懂选项
6. C
7. C和D的内容是什么?
8. A
9. D
10. B

Answer 3

一、ACDADA*ADB
二、l略
三、基数排序的基本思想是：从低位到高位依次对Kj(j=d-1，d-2，…，0)进行箱排序。箱排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。
其他的不好写了

Answer 4

自己做把