08年南大金陵学院数据结构期末考试陈Word文档格式.docx
《08年南大金陵学院数据结构期末考试陈Word文档格式.docx》由会员分享，可在线阅读，更多相关《08年南大金陵学院数据结构期末考试陈Word文档格式.docx（10页珍藏版）》请在冰点文库上搜索。
a'
）;
（3）下列每组代码利用标准容器list建立一个表，然后逐个删除表中的元素。
其中那组代码是正确的？
（）
A）list<
int>
lst;
B）list<
for（inti=0;
i<
5;
i++）lst.push_back（i）;
list<
:
iteratorp;
iteratorp=lst.begin（）;
for（p=lst.begin（）;
p!
=lst.end（）;
p++）lst.erase（p）;
while（!
lst.empty（））lst.erase（p）;
C）list<
D）list<
while（p!
=lst.end（））lst.erase（p）;
=lst.end（））p=lst.erase（p）;
（4）字符a、b、c、d依次进入一个栈，按所有可能的次序出栈后组成一个长度是4的字符串，至多可以组成多少个不同的字符串？
A）4B）14C）24D）16
（5）设有如下定义的数组Q：
constintm=20；
TQ[m]；
//T为队列元素的类型
Q存储一个环形队列。
quelen是队列中元素的个数，back是实际队尾元素的位置，队列中第一个元素的实际位置是（）
A）back+m-quelenB）back–quelen
C）（back+m–quelen+1）%mD）（m–back+quelen）%m
（6）C++标准模板库的“表”容器（list）是用双向链表实现的，对这种实现，下列叙述正确的是（）
A）元素的物理顺序与元素的逻辑顺序一定相同
B）一个表元素所占用的存储空间只用来存储表元素的值，不含其他附加信息
C）可以随机地访问元素
D）可以高效地进行插入和删除操作
（7）设一个长度为10的排好序的序列存储在数组intarr[10]中。
对一个给定的值k，用二分法查找与k相等的元素，若查找不成功，至少需要比较多少次？
（）。
A）3B）4C）5D）6
（8）设一棵树的度是4，其中度为0、1、2、3和4的结点个数分别是8、4、2、1和x，x是（）。
A）4B）3C）2D）1
（9）下面关于二叉树的叙述正确的是（）。
A）任何二叉树至少有一个结点
B）二叉树的度是2
C）在二叉树中，度为0的结点个数等于度为2的结点个数加1。
D）在任何一棵完全二叉树中，没有度为1的结点。
（10）一棵二叉树含有25个结点，这些结点要么是叶，要么是有两棵非空子的子树，此二叉树中有（）个非叶结点。
A）11B）12C）13D）14
（11）设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度的完全二叉树分别有f个结点和c个结点，下列关系式错误的是（）
A）f≥cB）c>
fC）f=2k+1－1D）c≤2k+1－1
（12）下列关于二叉搜索树的叙述，错误的是（）。
A）二叉搜索树可以是空二叉树
B）向二叉搜索树中插入一个结点，该结点的度一定是0。
C）对二叉搜索树进行中序遍历，将得到结点键值的递增序列。
D）向二叉搜索树中插入一个结点，树的高度一定增加1。
（13）考虑一棵二叉树结点的先序、中序和后序序列，所有叶结点的先后顺序关系是（）
A）都不相同B）完全相同
C）先序和中序相同，而与后序不同D）中序和后序相同，而与先序不同
（14）设有森林F，与F对应的二叉树是B。
若已知F有m个非叶结点，B中有n个结点的右
子树是空二叉树，对m和n，下列等式成立的是（）
A）m=nB）m=n-1C）m=n+1D）m=n-2
（15）考虑下列4种排序方法，不稳定的方法是（）
A）直接插入排序B）二分法插入排序
C）归并排序D）快速排序
二、填空题（共10题，每题3分，计30分）请将下列各题的答案填写在横线上
（1）一个抽象数据类型由一组值的集合以及定义在这组值上的一组组成。
（2）利用STL的向量容器vector定义二维向量vv如下：
vector<
>
vv;
//二维向量vv
执行循环语句：
for（inti=1;
i<
=3;
i++）vv.push_back（vector<
（i,2*i））;
后，向量vv的元素vv[1]是_______________________
（3）对下列函数mystery（intn），参数n是2的正整数幂（n=2k,k=1,2,3,…），用参数n表示函数执行结束时的count值：
count=___________________________。
intmystery（intn）
{
intx=2,count=0;
while（x<
n）
x*=2;
count++;
}
returncount;
}
（4）设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后立即进入队列，若6个元素出队列顺序是e2，e5，e6，e4，e3，e1，在操作过程中，栈S的最大长度（size）是多少?
______________
（5）可以高效地在两端进行插入和删除操作的队列称为_____________队列。
（6）广义表D=（（），（e），（a，（b，c，d））），则：
D的长度是_________,D的表头Head（D）是________,
D的表尾Tail（D）是_______________
（7）设森林F有3棵树，第一、第二和第三棵树的结点个数分别是t1、t2和t3，与森林对应的二叉树根结点的左子树有___________个结点。
（8）在一棵中序线索树中，一个结点p有两棵非空的子树，它的中序前驱结点的度至多是____________。
（9）在n个结点的完全二叉树中，叶结点的个数是。
（10）对一棵二叉树进行先序和中序遍历的结果分别是
先序序列：
ADBGEFC
中序序列：
BGDAFEC
则这棵二叉树根结点的左子女和右子女分别是_________和___________。
三、解答题（共5题，每题5分，计25分）请按照题意解答下列各题。
（1）函数func（）对表alist进行什么操作？
template<
typenameT>
voidfunc（list<
T>
&
alist）
{
iteratoriter=alist.begin（）;
while（iter!
=alist.end（））
alist.push_front（*iter）;
alist.erase（iter++）;
//本句也可改用p=alist.erase（iter）;
}
（2）设整型数组arr[]的长度为n，元素已按值递增的顺序排好序，函数Bsearch（）在数组中查找与给定值target相等的元素，若查找成功，返回元素在数组中的位置，否则返回-1。
实现代码如下：
intBsearch（intconst*arr,intn,constint&
target）
boolfound=false;
intfirst=0,last=n-1,m;
while（first<
=last&
!
found）
m=（first+last）/2;
//二等分
intmid=arr[m];
if（target==mid）found=true;
else
if（target>
mid）first=m;
elselast=m;
if（found）returnm;
//查找成功，返回元素在数组中的位置
elsereturn-1;
//查找失败，返回-1
无任是查找成功或查找失败，函数是否总能正确地工作？
如果不能，请举例说明。
（3）删除一棵二叉搜索树中的一个结点，然后再插入这个结点，所得的结果二叉树是否与原先的二叉树一定相同？
举例说明你的结论。
（4）设被排序的初始序列为{26,28,41,57,14,10,35,22}，用快速排序方法进行排序，以第一个元素26作为划分的基准，写成第一次划分后所得到的两个序列。
//本题不宜作为考题，因为划分的具体算法不同会得到不同结果。
（5）假设一则电文中仅出现6个不同的字母a，b，c，d，e和f，每个字母在电文中出现的频率分别是3，10，12，7，4和20。
试为这6个字母设计哈夫曼编码。
四．编程题（共2题，第
（1）题5分，第
（2）题10分，计15分）
（1）对下列单链表
写一个递归函数，反向输出单链表中的结点，即依次输出an，an-1，……，a2，a1
单链表的结点类型定义如下：
structnode
intdata;
node*next;
};
函数的原型:
voidPrint（Node*head）;
//函数写在下面
（2）若序列{h0,h1,h2,......,hn-1}中的元素满足下列关系：
hi≥h2i+1并且hi≥h2i+2（i=0,1,2,....,
）
则该序列是一个堆（heap）。
设向量A有n个元素，若它的前n-1个元素组成的序列
{a0,a1,a2,......,an-2}
已经是一个堆，编写函数push_heap（），它将向量A的n个元素组成的序列
{a0,a1,a2,......,an-2，an-1}
变成堆。
函数原型是voidpush_heap（vector<
A）;
2008.1.2.考试
A卷答案：
一、选择题（每题2分）
（2）C
（2）C（3）D（4）B（5）C
（2）D（7）A（8）D（9）C（10）B
（11）B（12）D（13）B（14）B（15）D
二、填空题（每题3分）
（11）操作
（2）4,4（3）count=long2n-1（4）4
（5）双端（或双向）队列（6）3，Head（D）=（），Tail（D）=（（e），（a，（b，c，d）））
（7）t1-1（8）1（9）
或
（10）D和E
三、解答题（每题5分）
（1）逆转一个表
（2）函数有时不能正确地工作，例如：
序列{1,5,8,10}，若要查找元素10，
（3）不一定相同。
例如：
删除10，然后再插入10，将得到下列不同的二叉查找树：
（4）【22，10，14】【57，41，28，35，26】
（5）构造哈夫曼树如下：
6个字母的哈夫曼编码分别是：
a=1010b=00c=01d=100d=100e=1011f=11
（4）编程题
（1）
voidPrint（node*head）
if（head）
Print（head->
next）;
cout<
<
head->
data;
（2）
voidpush_heap（vector<
A）
intn=A.size（）-1,currPos=n;
intparentPos=（currPos-1）/2;
while（currPos!
=0）
if（A[currPos]<
A[parentPos]）break;
inttemp=A[currPos];
A[currPos]=A[parentPos];
A[parentPos]=temp;
currPos=parentPos;
parentPos=（currPos-1）/2;
升级会员 