………………………………密………………………………封…………………………………线………………………………
6．设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_______F==R______________。
7．设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_______p->lchild==NULL&&p->rchild==NULL______________________________________。
5.设某棵三叉树中有40个结点，则该三叉树的最小高度为（B）。
(A) 3(B) 4(C) 5(D) 6
6.设某强连通图中有n个顶点，则该强连通图中至少有（C）条边。
(A) n(n-1)(B) n+1(C) n(D) n(n+1)
7.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（B）方法可以达到此目的。
{
LinkList p,q,r;
p=A;
q=B->next;
while(p)
{
if(q->next->dtat<p->data)
{
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;
1、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（错）
2、两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。。（对）
3、一个栈的输入序列是12345，则栈的输出序列不可能是12345。（错）
4、串是一种数据对象和操作都特殊的线性表。（对）
2．假定有字符a1，a2，a3，a4，a5在一篇文章中出现的次数分别为{{3, 2, 4, 5, 1}}试以它们为叶子结点构造哈夫曼树，并计算WPL (8分)
答：见三、2图
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(tail(L))))
4．（共6分）设有下列带权无向图：
请用PRIM求该图的一棵最小生成树。
答：见三、4图
5.设一棵二叉树的先序序列为ABDGECFH，中序序列为：DGBAECHF。试画出该二叉树。(6分)
答：见三、5图
四、判断题（1*10`=10分）
10、在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。（错）
五、编写算法（28分）
1、试编写算法将两个有序的单链表归并成一个新的有序单链表。（10分）
linklist Merge(linklist A, linklist B) /*将有序单链表合并后由函数带回*/
答：LinkList Merge(LinkList A,LinkList B)
(A)动态结构和静态结构(B)紧凑结构和非紧凑结构
(C)线性结构和非线性结构(D)内部结构和外部结构
2.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。
() BADC(B) BCDA(C) CDAB(D) CBDA
3.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C）。
}
2、试编写算法计算二叉树中度为1的结点数。（9分）
int count(bintree t) /*求二叉链表结构二叉树t度为1的结点数*/
答:int count(bintree t)
{
int count=0;
PSeqStack S;
bintree p=t;
S=Init_SeqStack();
while(p||Empty_SeqStack(S))
1．已知8个待排序的记录，其关键码分别为53，36，30，91，47，12，24，85，用希尔排序、快速排序和堆排序对其进行排序，写出第一趟排序后结果。(9分)
答：希尔排序：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
{
while(t)
{
if(t->key==X)
return t;
if(t->key<X)t=t->lchild;
else t=t->rchild;
}
return NULL;
}
三、2图
三、3图
三、4图
三、5图
11．平衡因子是指____左子树的深度减去右子树的深度____________________________________。
12．数组A[0..6,0..8]的每个元素占4个字节，将其按行优先次序存储在起始地址为2000的内存单元中，元素A[5,6]
的地址是_____2204________。
三、应用题。（共35分）
(A)快速排序(B)堆排序(C)归并排序(D)插入排序
8.若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用（D）存储方式最节省时间。
（A）单链表(B)双链表（C）单向循环(D)顺序表
9.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（D）。
(A) n(B) e(C) 2n(D) 2e
………………………………装………………………………订…………………………………线………………………………
课程________________________班级________________________姓名__________________________学号________________________
{
if(p)
{
Push_SeqStack(S,p);
p=p->lichild;
}
else
{
Pop_SeqStack(S,&p);
if(((p->lchild!=NULL)&&(p->rchild==NULL))||((p->lchild==NULL)&&(p->rchild!=NULL)))
count++;
(A) 100(B) 40(C) 55(D) 80
4.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。
(A) R-F(B) F-R(C) (R-F+M)％M(D) (F-R+M)％M
………………………………密………………………………封…………………………………线………………………………
题号
一
二
三
四
五
六
七
八
九
十
十一
十二
十三
十四
十五
十六
十七
十八
十九
二十
总分
得分
安徽工业大学2012~2013学年第二学期期末考试《数据结构》试卷(A)
一、单项选择题（110=10分）
1、在数据结构中，从逻辑上可以把数据结构分为（C）。
5、数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（错）
6、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。（错）
7、最小代价生成树是唯一的。（错）
8、归并排序的空间复杂度为O(n)（对）
9、为了方便操作，一般在二叉树排序树中插入一个新结点，总是作为叶结点。（对）
3.设输入序列为1、2、3，则经过栈的作用后可以得到____5_______种不同的输出序列。
4.设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。
5.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的中序遍历序列为_____DBEAFC______。
8．简单选择排序和直接插入排序算法的平均时间复杂度为_____O(n^2)______。
9．快速排序算法的空间复杂度平均情况下为____O(log2n)______，最坏的情况下为____O(n^2)______。
10.散列表中解决冲突的两种方法是______开放地址法_______和___链地址法__________。
10.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（B）次。
(A) 25(B) 10(C) 7(D) 1
二、填空题（每空格1分，共17分）
1.数据的物理结构主要包括__连续存储结构____和___非连续存储结构____两种情况。
2.设一棵完全二叉树中有500个结点，则该二叉树的深度为_____9_____；若用二叉链表作为该完全二叉树的存储结构，则共有______501_____个空指针域。
p=p->rchild;
}
}
return count;
}
3、试编写算法在二叉排序树T中查找值为X的算法。（9分）
BinSTree BSTSearch (BinSTree t , KeyType X ,)/*二叉排序树T中查找值为X的算法*/