安工大数据结构试卷(带完整答案).doc
- 格式：doc
- 大小：199.50 KB
- 文档页数：6
2.设一棵完全二叉树中有500个结点，则该二叉W的深度为9；若用二叉链表作为该完全二叉树的存储结构，则共有501___
个空指针域。
3.设输入序列为1、2、3,则经过栈的作用后可以得到__5种不同的输出序列。
4.设哈夫曼树中共有99个结点，则该树中有50个若采用二叉链表作为存储结构，则该树中有__100___个空指针域。
答：见三、4图
5.设一棵二叉树的先序序列为ABDGECFH,中序序列为：DGBAECHF。试画出该二叉树。（6分）
答：见三、5图
四、判断题（1*10'=10分）
1、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（错）
2、两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。。（对）
{
r=q;
r->next=p->next; p->next=r; q=q->next;
}
else
{
p=p->next; q=q->next;
}
if (!p&&q)
P=q;
return A;
}
2、试编写算法计算二叉树中度为1的结点数。(9分)
int count (bintree t) /*求二叉链表结构二叉树t度为1的结点数*/
答：int count (bintree t)
{
int count=0;
PSeqStack S; bintree p=t;
5.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的中序遍历序列为DBEAFCo
课程班级姓名学号
工 业 大 学 试 题 纸（二）
6.设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为F=R。
7.设二叉树中结点的两个指针域分别为lchild和rchild,则判断指针变量p所指向的结点为叶子结点的条件是
7.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列(B)方法可以达到此目的。
(A)快速排序(B)堆排序(C)归并排序(D)插入排序
8.若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用(D)存储方式最节省时间。
(A)单链表(B)双链表(C)单向循环(D)顺序表
答：希尔排序：12
24
30
91
47
53
36
85（步长为5）
快速排序：24
36
30
12
47
53
91
85
小堆排序：12
36
53
85
47
30
24
91
2.假定有字符al, a2,
a3,
a4, a5在一篇文章中出现的次数分别为{{3,2,4,5,1}}试以它们为叶子结点构造哈夫曼树，并计算WPL（8分）
答：见三、2图
课程班级姓名学号
工 业 大 学 试 题 纸(一)
题号
—*
二
三
四
五
六
七
八
九
十
十
十
十
十
四
十
五
十
六
十
七ห้องสมุดไป่ตู้
十
八
十
九
十
总分
得分
安徽工业大学
一、单项选择题(1x10=10分)
1.在数据结构中，从逻辑上可以把数据结构分为(C)。
(A)动态结构和静态结构(B)紧凑结构和非紧凑结构
(C)线性结构和非线性结构(D)内部结构和外部结构
9.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为(D)。
(A) n(B) e(C) 2n(D) 2e
10.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较(B)次。
(A)25⑻ 10(C)7(D)1
二、填空题(每空格1分，共17分)
1.数据的物理结构主要包括__连续存储结构和___非连续存储结构两种情况。
p-〉lchi Id二NULL&&p-〉rchi Id二NULLo
8.择排序和直接插入排序算法的平均时间复0G<2）。
9.快速排序算法的空间复杂度平均情况下为__0（log2n），最兄下为____0（rf2）。
10.散列表中解决冲突的两种方法是开iii址法链地址法◊
11.平衡因子是指____左子树的深）去i子树的深度o
12.数组A[0..6,0..8]的每个元素占4个字节，将其按行优先次序存储在起始地址为2000的内存单元中，元素A[5,6]
的地址是2204o
三、应用题。（共35分）
1.己知8个待排序的记录，其关键码分别为53, 36, 3（），91, 47, 12, 24, 85,用希尔排序、快速排序和堆排序对其进行排序，写出第一趟排 序后结果。（9分）
(A) R-F(B) F-R(C) (R-F+M)%M(D) (F-R+M) %M
5.设某棵三叉树中有40个结点，则该三叉树的最小高度为(B)。
(A)3(B)4(C)5(D)6
6.设某强连通图中有n个顶点，则该强连通图中至少有(C)条边。
(A) n (n~l)(B) n+1(C) n(D) n(n+l)
3、一个栈的输入序列是12345,则栈的输出序列不可能是12345。（错）
4、串是一种数据对象和操作都特殊的线性表。（对）
5、数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（错）
6、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有之1-!个结点。（错）
2.设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD，则后序遍历该二叉树得到序列为(A)。
(A) BADC(B) BCDA(C) CDAB (D) CBDA
3.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为(C)。
(A)100(B)40(C)55(D)80
4.设顺序循环队列Q[0: M-1]的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位 置，则该循环队列中的元素个数为(C)。
WPL:（3+4+5）*2+（1+2）*3=33
3.己知广义表L=（a, （b, c）,（d，e）），试画出其存储结构图并利用取头函数head和取尾函数tail求出原子e。（（6分） 答：见三、3图
e=head（tail（head（tail（tai 1（L））））
4.（共6分）设有下列带权无向图：
请用PRIM求该图的一棵最小生成树。
7、最小代价生成树是唯一的。（错）
8、归并排序的空间复杂度为0（n）（对）
9、为了方便操作，一般在二叉树排序树中插入一个新结点，总是作为叶结点。（对）
10、在初始数据表已经有序时，快速排序算法的时间复杂度为0（nlog2n）。（错）
五、编写算法（28分）
1、试编写算法将两个有序的单链表归并成一个新的有序单链表。（10分）
linklist Merge（linklist A, linklist B） /*将有序单链表合并后由函数带回*/
答：LinkList Merge (LinkList A, LinkList B)
{
LinkList p, q, r;
P:A;
q=B->next; while (p)
{
if (q->next->dtat<p->data)
个空指针域。
3.设输入序列为1、2、3,则经过栈的作用后可以得到__5种不同的输出序列。
4.设哈夫曼树中共有99个结点，则该树中有50个若采用二叉链表作为存储结构，则该树中有__100___个空指针域。
答：见三、4图
5.设一棵二叉树的先序序列为ABDGECFH,中序序列为：DGBAECHF。试画出该二叉树。（6分）
答：见三、5图
四、判断题（1*10'=10分）
1、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（错）
2、两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。。（对）
{
r=q;
r->next=p->next; p->next=r; q=q->next;
}
else
{
p=p->next; q=q->next;
}
if (!p&&q)
P=q;
return A;
}
2、试编写算法计算二叉树中度为1的结点数。(9分)
int count (bintree t) /*求二叉链表结构二叉树t度为1的结点数*/
答：int count (bintree t)
{
int count=0;
PSeqStack S; bintree p=t;
5.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的中序遍历序列为DBEAFCo
课程班级姓名学号
工 业 大 学 试 题 纸（二）
6.设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为F=R。
7.设二叉树中结点的两个指针域分别为lchild和rchild,则判断指针变量p所指向的结点为叶子结点的条件是
7.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列(B)方法可以达到此目的。
(A)快速排序(B)堆排序(C)归并排序(D)插入排序
8.若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用(D)存储方式最节省时间。
(A)单链表(B)双链表(C)单向循环(D)顺序表
答：希尔排序：12
24
30
91
47
53
36
85（步长为5）
快速排序：24
36
30
12
47
53
91
85
小堆排序：12
36
53
85
47
30
24
91
2.假定有字符al, a2,
a3,
a4, a5在一篇文章中出现的次数分别为{{3,2,4,5,1}}试以它们为叶子结点构造哈夫曼树，并计算WPL（8分）
答：见三、2图
课程班级姓名学号
工 业 大 学 试 题 纸(一)
题号
—*
二
三
四
五
六
七
八
九
十
十
十
十
十
四
十
五
十
六
十
七ห้องสมุดไป่ตู้
十
八
十
九
十
总分
得分
安徽工业大学
一、单项选择题(1x10=10分)
1.在数据结构中，从逻辑上可以把数据结构分为(C)。
(A)动态结构和静态结构(B)紧凑结构和非紧凑结构
(C)线性结构和非线性结构(D)内部结构和外部结构
9.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为(D)。
(A) n(B) e(C) 2n(D) 2e
10.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较(B)次。
(A)25⑻ 10(C)7(D)1
二、填空题(每空格1分，共17分)
1.数据的物理结构主要包括__连续存储结构和___非连续存储结构两种情况。
p-〉lchi Id二NULL&&p-〉rchi Id二NULLo
8.择排序和直接插入排序算法的平均时间复0G<2）。
9.快速排序算法的空间复杂度平均情况下为__0（log2n），最兄下为____0（rf2）。
10.散列表中解决冲突的两种方法是开iii址法链地址法◊
11.平衡因子是指____左子树的深）去i子树的深度o
12.数组A[0..6,0..8]的每个元素占4个字节，将其按行优先次序存储在起始地址为2000的内存单元中，元素A[5,6]
的地址是2204o
三、应用题。（共35分）
1.己知8个待排序的记录，其关键码分别为53, 36, 3（），91, 47, 12, 24, 85,用希尔排序、快速排序和堆排序对其进行排序，写出第一趟排 序后结果。（9分）
(A) R-F(B) F-R(C) (R-F+M)%M(D) (F-R+M) %M
5.设某棵三叉树中有40个结点，则该三叉树的最小高度为(B)。
(A)3(B)4(C)5(D)6
6.设某强连通图中有n个顶点，则该强连通图中至少有(C)条边。
(A) n (n~l)(B) n+1(C) n(D) n(n+l)
3、一个栈的输入序列是12345,则栈的输出序列不可能是12345。（错）
4、串是一种数据对象和操作都特殊的线性表。（对）
5、数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（错）
6、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有之1-!个结点。（错）
2.设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD，则后序遍历该二叉树得到序列为(A)。
(A) BADC(B) BCDA(C) CDAB (D) CBDA
3.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为(C)。
(A)100(B)40(C)55(D)80
4.设顺序循环队列Q[0: M-1]的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位 置，则该循环队列中的元素个数为(C)。
WPL:（3+4+5）*2+（1+2）*3=33
3.己知广义表L=（a, （b, c）,（d，e）），试画出其存储结构图并利用取头函数head和取尾函数tail求出原子e。（（6分） 答：见三、3图
e=head（tail（head（tail（tai 1（L））））
4.（共6分）设有下列带权无向图：
请用PRIM求该图的一棵最小生成树。
7、最小代价生成树是唯一的。（错）
8、归并排序的空间复杂度为0（n）（对）
9、为了方便操作，一般在二叉树排序树中插入一个新结点，总是作为叶结点。（对）
10、在初始数据表已经有序时，快速排序算法的时间复杂度为0（nlog2n）。（错）
五、编写算法（28分）
1、试编写算法将两个有序的单链表归并成一个新的有序单链表。（10分）
linklist Merge（linklist A, linklist B） /*将有序单链表合并后由函数带回*/
答：LinkList Merge (LinkList A, LinkList B)
{
LinkList p, q, r;
P:A;
q=B->next; while (p)
{
if (q->next->dtat<p->data)
