数据结构试卷3(含答案)
- 格式：doc
- 大小：57.00 KB
- 文档页数：3
／ ＼ ＼
(H) (D) (G)
／ ＼
(E) (F)
＼
(I)
3.图示的三棵二叉树中(c)为最优二叉树。
A)B)C)
ca
27
abcddb
7 5 2 445
abcd
7 52 4
三．填空题
1．对于一棵二叉排序树，通过按( 中序 )次序遍历，可以得到结点的有序序列。
2．设循环队列存于一维数组Ｑ[ｍ]中，尾指针rear指示队尾元素在队列中的当前位置， 头指针front指示队列中队头元素的前一个位置，
<1> 44,41,15,26,33,16,55,20,59,71,61,75
<2> 20,41,61,71,33,44,75,55,15,26,16,59
<3> 15,20,16,26,33,44,61,59,55,71,41,75
<4> 41,59,75,26,33,16,20,61,55,15,71,44
一、判断题
1．简单地说,数据结构是带有结构的数据元素的集合。(T)
2．线性表的顺序存储结构具有可直接存取表中任一元素的优点。（T）
3．二叉排序树的平均查找长度为O(logｎ)。（T）
4．邻接多重表可用来表示有向图。(F)
5。栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(F)
二．选择题
1．若要按升序对关键字序列（59,41,75,26,33,16,61,20,55,71,15,44）进行排序,则（3）是堆排序初始建堆的结果（小堆顶）。（1）是以第一个元素作为枢轴的快速排序一趟扫描的结果。（6）是希尔排序（初始步长为4）一趟扫描的结果。（5）是冒泡排序一趟扫描的结果。
return i;
}
2.写出一个将树中每个结点的左右孩子对换的算法（12分）
SWAPTREE(T) 即如:
原二叉树 转换后
TSWAPTREE(T)
↓ ↓
(A)(A)
/ \ / \
(B) (C) (C) (B)
/ \ / \ / \
(D) (E) (F) (F) (E) (D)
\ \ / /
(G) (H) (H) (G)
while (②j<n-i-1){
if (A[j].key > A[j+1].key) {
A[j]<-> A[j+1];
exchange := true ;
}
③j++
}
④i+
1.某二叉树的中序遍历次序为BEGFDAC，先序遍历次序为ABDEFGC。试画出该二叉树，并为之建立中序线索（图示之）。
KeyTYPE key;
TYPE otheritem;
};
void BubbleSort(RecordType A[], int n) //n为待排序的记录数
{
i = 0; exchange = true;
while (i< n-1 && exchange) {
j:= 0;
①exchange=false;
则队列长度＝((rear-front+m)mod m)。
3.一棵ｍ阶的Ｂ-树，第一层至少有一个结点；第二层至少有2个结点，除根之外的所有非终端结点至少有（┌m/2┐）棵子树，树中每个结点至多有（m）棵子树。
4.对任何一棵二叉树T,若其终端结点数为n0.度为2的结点为n2,则n0与n2的关系为(n0=n2+1)。
2.右图为一棵3阶B－树。 （20，25）
① 画出在该树上插入元素15 ／ │ ＼
后的B－树。 (10，14)（21）（35）
②接着，再删除元素35，画出删除后的B－树。
3．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为7, 19, 2, 6, 32, 3, 21, 10。 试为这8个字母设计哈夫曼编码。
<5> 41,59,26,33,16,61,20,55,71,15,44,75
<6> 33,16,15,20,55,41,61,26,59,71,75,44
2.先序遍历图示二叉树可得到（a）的序列。
a)A B H D E F I C G(A)
b)H B E D F I A CG／＼
c) H E I F D B G C A(B) (C)
5．折半插入排序是对直接插入排序算法的改进，它着眼于减少比较次数。
6.如果对完全二叉树中结点从1开始按层进行编号，设最大编号为n；那么，可以断定编号为i (i>1)的结点的父结点编号为i/2；所有编号（大于n/2）
的结点为叶子结点。
8．完成以下起泡排序算法。待排序记录的类型:
struct RecordType {
4．设有向图如下，试画出图的邻接表。并给出DFS及BFS次序。
10
24
3
5．序列(3，4，7，2，1，5，6，9，8)次序构造一棵平衡二叉树。
五．写算法
1．写出求单链表长度算法（12分）
int length(linklist L)
//L为带表头的单链表
{
i=0;
p=L->next;
while (p) {i++;p=p->next;}
(H) (D) (G)
／ ＼
(E) (F)
＼
(I)
3.图示的三棵二叉树中(c)为最优二叉树。
A)B)C)
ca
27
abcddb
7 5 2 445
abcd
7 52 4
三．填空题
1．对于一棵二叉排序树，通过按( 中序 )次序遍历，可以得到结点的有序序列。
2．设循环队列存于一维数组Ｑ[ｍ]中，尾指针rear指示队尾元素在队列中的当前位置， 头指针front指示队列中队头元素的前一个位置，
<1> 44,41,15,26,33,16,55,20,59,71,61,75
<2> 20,41,61,71,33,44,75,55,15,26,16,59
<3> 15,20,16,26,33,44,61,59,55,71,41,75
<4> 41,59,75,26,33,16,20,61,55,15,71,44
一、判断题
1．简单地说,数据结构是带有结构的数据元素的集合。(T)
2．线性表的顺序存储结构具有可直接存取表中任一元素的优点。（T）
3．二叉排序树的平均查找长度为O(logｎ)。（T）
4．邻接多重表可用来表示有向图。(F)
5。栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(F)
二．选择题
1．若要按升序对关键字序列（59,41,75,26,33,16,61,20,55,71,15,44）进行排序,则（3）是堆排序初始建堆的结果（小堆顶）。（1）是以第一个元素作为枢轴的快速排序一趟扫描的结果。（6）是希尔排序（初始步长为4）一趟扫描的结果。（5）是冒泡排序一趟扫描的结果。
return i;
}
2.写出一个将树中每个结点的左右孩子对换的算法（12分）
SWAPTREE(T) 即如:
原二叉树 转换后
TSWAPTREE(T)
↓ ↓
(A)(A)
/ \ / \
(B) (C) (C) (B)
/ \ / \ / \
(D) (E) (F) (F) (E) (D)
\ \ / /
(G) (H) (H) (G)
while (②j<n-i-1){
if (A[j].key > A[j+1].key) {
A[j]<-> A[j+1];
exchange := true ;
}
③j++
}
④i+
1.某二叉树的中序遍历次序为BEGFDAC，先序遍历次序为ABDEFGC。试画出该二叉树，并为之建立中序线索（图示之）。
KeyTYPE key;
TYPE otheritem;
};
void BubbleSort(RecordType A[], int n) //n为待排序的记录数
{
i = 0; exchange = true;
while (i< n-1 && exchange) {
j:= 0;
①exchange=false;
则队列长度＝((rear-front+m)mod m)。
3.一棵ｍ阶的Ｂ-树，第一层至少有一个结点；第二层至少有2个结点，除根之外的所有非终端结点至少有（┌m/2┐）棵子树，树中每个结点至多有（m）棵子树。
4.对任何一棵二叉树T,若其终端结点数为n0.度为2的结点为n2,则n0与n2的关系为(n0=n2+1)。
2.右图为一棵3阶B－树。 （20，25）
① 画出在该树上插入元素15 ／ │ ＼
后的B－树。 (10，14)（21）（35）
②接着，再删除元素35，画出删除后的B－树。
3．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为7, 19, 2, 6, 32, 3, 21, 10。 试为这8个字母设计哈夫曼编码。
<5> 41,59,26,33,16,61,20,55,71,15,44,75
<6> 33,16,15,20,55,41,61,26,59,71,75,44
2.先序遍历图示二叉树可得到（a）的序列。
a)A B H D E F I C G(A)
b)H B E D F I A CG／＼
c) H E I F D B G C A(B) (C)
5．折半插入排序是对直接插入排序算法的改进，它着眼于减少比较次数。
6.如果对完全二叉树中结点从1开始按层进行编号，设最大编号为n；那么，可以断定编号为i (i>1)的结点的父结点编号为i/2；所有编号（大于n/2）
的结点为叶子结点。
8．完成以下起泡排序算法。待排序记录的类型:
struct RecordType {
4．设有向图如下，试画出图的邻接表。并给出DFS及BFS次序。
10
24
3
5．序列(3，4，7，2，1，5，6，9，8)次序构造一棵平衡二叉树。
五．写算法
1．写出求单链表长度算法（12分）
int length(linklist L)
//L为带表头的单链表
{
i=0;
p=L->next;
while (p) {i++;p=p->next;}
