计算机科学与技术、网络工程本科
《数据结构》期末考试试卷
一、选择题〔单选题，每小题3分，共33分〕
1．已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为。
A．BCDEAF B．ABDCEF C．DBACEF D．DABECF 2．在11个元素的有序表A[1…11]中进行折半查〔⎣⎦2/)
low+〕，查元素
(high
A[11]时，被比较的元素的下标依次是。
A．6，8，10，11 B．6，9，10，11 C．6，7，9，11 D．6，8，9，
11
3．由元素序列〔27，16，75，38，51〕构造平衡二叉树，则首次出现的最小不平衡子树的根〔即离插入结点最近且平衡因子的绝对值为2的结点〕为。
A．27 B．38 C．51 D．75
4．利用逐点插入法建立序列〔50，72，43，85，75，20，35，45，65，30〕对应的二叉排序树以后，查元素30要进行次元素间的比较。
A．4 B．5 C．6 D．7
5．循环链表的主要优点是。
A．不再需要头指针了B．已知某个结点的位置后，很容易到它的直接前驱结点
C．在进行删除后，能保证链表不断开D．从表中任一结点出发都能遍历整个链表
6．已知一个线性表〔38，25，74，63，52，48〕，假定采用散列函数h〔key〕=key%7计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率查时查成功的平均查长度为。
A．1．5 B．1．7 C．2．0 D．2．3
7．由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为。
A．23 B．37 C．44 D．46
8．在最好和最坏情况下的时间复杂度均为O〔nlogn〕且稳定的排序方法是。
A．基数排序B．快速排序C．堆排序D．归并排序
9．无向图G=(V，E)，其中V={a，b，c，d，e，f}，E={(a，b)，〔a，e〕，(a，c)，〔b，e〕，〔c，f〕，(f，d)，〔e，d〕}。对该图进行深度优先遍历，下面不能得到的序列是。
A．aebdcf B．abedfc C．aedfcb D．acfdeb
10．置换-选择排序的功能是。
A．产生初始归并段B．选出最大的元素C．产生有序文件D．置换某个记录
11．ISAM和VSAM文件属于。
A．索引顺序文件B．索引非顺序文件C．顺序文件D．散列文件二、填空题(1~8每空2分，9~12每空1分，共20分〕
1．下面程序段的时间复杂度为[1]。
Sum=1; For (i=0; sum<n; i++) sum+=i;
2．稀疏矩阵快速转置算法(见第三题第1小题)的时间复杂度为[2]，空间复杂度为[3]。
3．对广义表A=(a，(b，c，d))的运算head(rail(A))的结果是[4]。
4．将n个数据元素依次按a1，a2，…，an的顺序压入栈中，共有[5]种出栈序列。
5．含有4个结点的不相似的二叉树有[6] 棵。
6．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，则A[3][3](10)存放的位置为[7]。(脚注(10)表示用10进制表示)
7．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总的结点数是[8]。
8．给定一组关键字{49，38，65，97，76，13，27，49’}，以下用了4种不同的排序
三、算法填空题(每空3分，共18分〕
1．稀疏矩阵快速转置算法
//稀疏矩阵的三元组顺序表存储表示
#define MAXSIZE 12500 //非零元个数最大为12500
typedef struct
{int i,j; //行号，列号
ElemType e; //非零元
}Triple;
typedef struct
{Triple data[MAXSIZE+1]; //三元组表．0号不用
int mu,nu,tu; //总行数，总列数，非零元总个数
}TSMatrix;
#define MAXCOL 50
status FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
{//采用三元组表存储表示，求稀疏矩阵M的转置矩阵T．
int num[MAXCOL], cpot[MAXCOL], col, t, p, q;
T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if (T.tu)
{for (col=1;col<=M.nu;++col) num[col]=0;
for (t=1;t<=M.tu;++t) ++num[①]; //求M中每一列含非零元个数
cpot[1]=1;//求第col列中第一个非零元在T.data中的序号
for (col=2;col<=M.nu;++col) //后一列第一个非零元在T．data中的序号等于
cpot[col]=cpot[col-1]+②; // 前一列的序号+前一列非零元个数for (p=1;p<=M.tu;++p)
{col=M.data[p].j; //M中第p行的列号域值赋给col
q=cpot[col]; //M中的第col列非零元在T.data中的恰当位置赋给q
T.data[q].i=M.data[p].j; //M中的第p行复制到T中的第q行
T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e;
③; //M中第col列下一个非零元在T．data中的位置应增1
}
}
return OK;
}
2．后序遍历二叉树非递归算法
Status PostOrderTraverse1(BiTree t,Status (*Visit)(TElemType e))
{//后序遍历二叉树T非递归算法，对每个数据元素调用函数Visit一次且仅一次.
BiTree p;  SqStack S;  int tag;
InitStack(S);
do
{while (t) {Push(S,t);④;}
p=NULL;                      //p指向当前结点的前一个已访问的结点
tag=1;                      //设置t的访问标记为已访问过
while (!StackEmpty(S)&&tag)
{t=GetTop(S);              //取栈顶元素
if (t->rchild==p)        //右子树不存在或已被访问，访问之
{⑤;      //访问根结点
Pop(S,p);            //退栈
p=t;}                //p指向已被访问的结点
else {t=t->rchild;        //t指向右子树
tag=0;}            //设置未被访问的标记
}
}while(⑥ );
return OK;
}
四、解答题〔共20分〕
1．〔6分〕已知模式串p=’cbcaacbcbc’，求出p的next数组值和nextval数组值。
j    1    2    3    4    5    6 7 8 9 10 模式串p    c    b    c    a    a    c    b    c    b    c Next[j]
Nextval[j]
2．〔6分〕已知一组关键字为{21，33，12，40，68，59，25，51}，
(1) 试依次插入关键字生成一棵3阶的B-树；
(2) 在生成的3阶B-树中依次删除40和12，画出每一步执行后B-树的状态。
3．〔8分〕试对右图所示的AOE网络，解答下列问题。
(1) 求每个事件的最早开始时间Ve[i]和最迟开始时间
Vl[i]。
1①2③3②4④5⑤6⑥
Ve
Vl
(2) 求每个活动的最早开始时间e( )和最迟开始时间l( )。
<1, 2> <1, 3> <3, 2> <2, 4> <2, 5> <3, 5> <4, 6> <5, 6> e
l
(3)
个工程提前完成。
(4) 这个工程最早可能在什么时间结束。
五、算法设计题〔9分〕
完成以下算法，对单链表实现就地逆置。
void LinkList_reverse(Linklist &L)
{//链表的就地逆置；为简化算法，假设表长大于2
Linklist p,q,s;
p=L->next;q=p->next;s=q->next;p->next=NULL;
试题答案与评分标准
一、选择题〔单选题，每小题3分，共33分〕
二、填空题(1~8每空2分，9~12每空1分，共20分〕
三、算法填空题(每空3分，共18分〕
1．①M.data[t].j ②num[col-1] ③++cpot[col]
2．④t=t->lchild ⑤Visit(t->data) ⑥!StackEmpty(S)
四、解答题〔共20分〕
1．(6分)
2．(共6分) (1) (2分) 3阶B-树为：
(2) 〔4分〕
删除40后B-树的状态删除12后B-树的状态 3．(8分) 按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve 和最迟允许开始时间Vl 。然后再计算各个活动的最早可能开始时间e 和最迟允许开始时间l ，根据l - e = 0? 来确定关键活动，从而确定关键路径。
①  2③  3②  4④  5⑤  6⑥  Ve  0
15  19  29  38  43  Vl  0  15  19  37  38  43      <1, 2> <1, 3> <3, 2> <2, 4> <2, 5> <3, 5> <4, 6> <5, 6>  e  0  0  15  19  19  15  29  38  l  17  0  15  27  19  27  37  38 l -e
17
8
12
8
(3) 关键活动为：<1, 3>，<3, 2>，<2, 5>，<5, 6>； 加速这些活动可使整个工程提前完成； 由所有关键活动构成的图：〔关键路径为：<1, 3><3, 2><2, 5><5, 6>〕
(4) 此工程最早完成时间为43。
五、算法设计题〔9分〕
试写一算法，对单链表实现就地逆置。
void LinkList_reverse(Linklist &L)
{//链表的就地逆置；为简化算法，假设表长大于2  Linklist p,q,s;
二叉树中序遍历非递归算法p=L->next;  q=p->next;  s=q->next;  p->next=NULL; 解：
while  (s->next)
{q->next=p;  p=q;
1
3
2
6
5
15
4
19
5

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。