计算机科学与技术专业2011级《数据结构》期中考试
一、选择题（单号仅做单序号题目，双号仅做双序号题目；四个选项中只有一个是正确的，每小题3分，共30分）
1、数据在计算机内存中的表示是指（A）
A)数据的存储结构
B)数据结构
C)数据的逻辑结构
D)数据元素之间的关系
2、在数据结构中，与所使用的计算机无关的数据结构是（A）
A)逻辑结构
B)存储结构
C)逻辑和存储结构
D)物理结构
3、链表不具备的特点是（A）
A)可随机访问任意一个结点
B)插入和删除不需要移动任何元素
C)不必事先估计存储空间
D)所需空间与其长度成正比
4、对线性表，在下列情况下应当采用链表表示的是（B）
A)经常需要随机存取元素
B)经常需要进行插入和删除操作
C)表中元素需要占据一片连续的存储空间
D)表中的元素个数不变
5、若已知一个栈的进栈序列是1，2，3……n，其输出序列是p1，p2，p3，pn，若p1=n，则pi（1<i<n）为（C）
A)i
B)N-i
C)N-i+1
D)不确定
6、若已知一个栈的进栈序列是1，2，3……n，其输出序列是p1，p2，p3，pn，若p1=3，
则p2为（A）
A)可能是2
B)一定是2
C)可能是1
D)一定是1
7、不带头结点的单链表head为空的判定条件是（A）
A)head=NULL
B)head->next=NULL
C)head->next=head
D)head!=NULL
8、带头结点的单链表head为空的判定条件是（B）
A)head=NULL
B)head->next=NULL
C)head->next=head
D)head!=NULL
9、在一个链式队列中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是（B）
A)f->next=s;f=s;
B)r->next=s;r=s;
C)s->next=r;r=s;
D)s->next=f;f=s;
10、在一个链队列中，假设f和r分别为队头和队尾指针，则删除结点的运算是（C）
A)r=f->next;
B)r=r->next;
C)f=f->next;
D)f=r->next;
11、下列有关树的概念错误的是（B）
A)一棵树中只有一个无前驱的结点
B)一棵树的度为树中各个结点的度之和
C)一棵树中，每个结点的度数等于结点总数减一
D)一棵树中每个结点的度数之和与边的条数相等
12、下面关于二叉树的叙述正确的是（A）
A)一棵二叉树中叶子结点的个数等于度为2的结点个数加1
B)一棵二叉树中结点的个数大于0
C)二叉树中任何一个结点要么是叶，要么恰有两个孩子
D)二叉树中，任何一个结点的左子树和右子树的结点个数一定相等
13、已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC，则它的前序遍历序列是（D）
A)ACBED
B)DEABC
C)DECAB
D)EDBCA
14、一棵二叉树的前序遍历序列为ABDGCFK，中序遍历为DGBAFCK，则结点的后序遍历序列是（B）
A)ACFKDBG
B)GDBFKCA
C)kcfAGDB
D)ABCDFKG
15、算法指的是（D）
A)计算机程序
C)排序算法
D)解决问题的有限运算序列
16、算法能正确地实现预定功能的特性称为算法的（A）
A)正确性
B)易读性
C)健壮性
D)高效性
17、执行下面程序段时，执行S语句的次数为（D）
for(inti=1;i<=n;i++)
for(intj=1;j<=i;j++)
S;
A)n2
B)n2/2D
C)n(n+1)
D)n(n+1)/2
18、下面程序段的时间复杂度是（D）
for(inti=0;i<n;i++)
for(intj=1;j<m;j++)
A[i][j]=0;
A)O(n)
B)O(m+n+1)
C)O(m+n)
D)O(m*n)
19、某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第12个元素的存储地址为（A）
A)144
B)145
C)147
D)148
20、设线性表的顺序存储结构中，每个元素占用1个存储单元，表的第1个元素的存储地址为d，则第i个元素（1<=i<=n,n为表长）的存储地址为（A）
A)d+(i-1)*1
B)d+i*1
C)d+(i+1)*1
D)d+i*1-1
二、填空题（每小题4分，共32分）
1、在一个单链表中的p所指向结点之前插入一个s所指的结点时，可以执行如下操作：
（1）s->next=p->next;
（2）p->next=s;
（3）t=p->data;
（4）p->data=s->data;
（5）s->data=t;
2、设树T的度为4，其中度为1，2，3和4的结点的个数分别为4，2，1，1，则T中叶子结点的个数为（8）。
深度为k的完全二叉树至少有(2k-1)（2的k-1次方）个结点，至多有（2k-1）（2的k次方减1）个结点，若按自上而下，从左向右的次序编号（从1开始），则编号最小的叶子结点的编号是（2k-2+1）（2的k-2次方减1）
3、现有按中序遍历二叉树的结果为abc，问有（5）种不同形态的二叉树可以得到这一遍历结果。
4、对于一个长度为n的单链表，在表头插入元素的时间复杂度为（O(1)），在表尾插入元素的时间复杂度为（O(n)）。
5、用数组A[1…N]顺序存储完全二叉树的各结点，则当I<=(n-1)/2时，结点A[I]的右孩子是结点（A[2i+1]）。
6、若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为K，则左、右子树皆非空的结点个数是（k-1）。
7、设F是由T1,T2和T3三棵树组成的森林，与F对应的二叉树为B，已知T1,T2和T3的结点个数分别是n1,n2,n3，则二叉树B的根结点的左子树和右子树中的结点个数分别是(n1-1、n2+n3)。
三、综合题（共38分）
1、设计一个算法，通过一趟遍历确定单链表中值最大的结点。（7分）
LinkListmaxnode(LinkListL)
{//在带头结点的单链表L中通过一趟遍历，查找值最大的结点并返回其地址
LinkListp=L->next,q=p;
while(p)
{if(p->data>q->data)
q=p;
p=p->next;
}
returnq;
}
2、编写算法对非递减有序的顺序表进行元素唯一化（即：使顺序表中重复的元素只保留一个），要求算法的时间复杂度为O(n)。（14分）
voidUnique(sqlist&L)
{//对非递减有序的顺序表L进行元素唯一化
i=0;
for(j=1;j<L.length;j++)
if(L.elem[j]!=L.elem[i-1])
{if(j!=i)L.elem[i]=L.elem[j];
i++;
}
L.length=i;//更新表长
}
3、编写一个算法，输出一个二叉树的所有叶子结点。（7分）
voidfindLeaf(BinTreeT)
{
if(T)
{if(T->lchild==NULL&&T->rchild==NULL)
cout<<T->data;
else{findLeaf(T->lchild);
findLeaf(T->rchild);
}
}
}
4、以数据集{9,6,2,5,8,13,17}为权值构造一棵huffman树，并计算其带权路径长度。（10分）
WPL=（13+17）*2+（6+8+9）*3+（2+5）*4=157
