北京理工大学-数据结构期末考试试题（五）
数据结构试卷（五）
一、选择题(20分)
1．数据的最小单位是（ ）。
(A)数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量
给定一组初始记录关键字序列(50, 40, 95, 20, 15, 70, 60, 45)，经过一次希尔排序使用步长d=4对上述序列进行处理后前四个元素分别为多少？
(A)40，50，20，95 (B)15，40，60，20
(C)15，20，40，45 (D)45，40，15，20
3．给定一个初始记录关键字序列为(25, 50, 15, 35, 80, 85, 20, 40, 36, 70)，其中包含五个长度为2的有序子序列，则采用归并排序方法对该序列表进行一次归并后的结果是什么？
(A) 15，25，35，50，20，40，80，85，36，70
(B) 15，25，35，50，80，20，85，40，70，36
(C) 15，25，35，50，80，85，20，36，40，70
(D) 15，25，35，50，80，20，36，40，70，85
4．函数substr(“DATASTRUCTURE”，5，9)的返回值为（ ）。
(A)“STRUCTURE” (B) “DATA”
(C)“ASTRUCTUR” (D) “DATASTRUCTURE”
设有长度为n的一个递增排列的单链表，在插入一个新节点之后仍能保持递增顺序，则该操作的时间复杂度是多少？
(A)O(log2n) (B) O(1) (C) O(n2) (D) O(n)
考虑一棵m元树，在该树中零度顶点的数量记作N₀、单度顶点的数量记作N₁、依此类推直至第m度顶点的数量记作Nₘ，则零度顶点的数量N₀等于（ ）。
(A)Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm
(C)N2+2N3+3N4+……+(m-1)Nm (D)2Nl+3N2+……+(m+1)Nm
7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ ）次。
(A)25 (B) 10 (C) 7 (D) 1
8．给定连通图G中的边集E=\{(a,b),\ (a,e),\ (a,c),\ (b,e),\ (e,d),\ (d,f),\ (f,c)\}，
则可以从顶点a出发进行深度优先遍历以获得相应的顶点序列。（ ）
(A)abedfc (B) acfebd (C) aebdfc (D) aedfcb
对于输入序列为1,2,3,…,n的情况，在经过栈操作后第一个输出元素为n，则第i个输出元素的位置是（ ）。
(A)n-i (B) n-1-i (C) n+1-i (D) 不能确定
给定一组初始记录关键字序列(45, 80, 55, 40, 42, 85)，基于第一个记录的关键字45完成一次快速排序后所得的结果是（ ）。
(A)40，42，45，55，80，83 (B) 42，40，45，80，85，88
(C)42，40，45，55，80，85 (D) 42，40，45，85，55，80
二、填空题(共20分)
考虑一个顺序共享栈S[0: n−1]（此处应保留数学公式S[0: n−1]），其中第一个栈顶指针top₁初始化设置为−1值域范围端点处（此处应保留数学公式top₁ = -1），第二个栈顶指针top₂初始化设置为n值域范围端点处（此处应保留数学公式top₂ = n）。则判断该共享栈满载时的状态判定依据是什么？
2. 在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。
3. 假设有一个n阶的下三角矩阵A。按照行顺序将下三角区域的所有元素（包括主对角线上的元素）连续存储在n(n+1)个存储单元中，则在该存储结构中，在索引位置上位于起始位置A[0][0]之后存在的数据元素数量为多少？
4. 栈的数据结构只能在其顶端执行插入和删除操作, 这意味着最新的元素总是第一个被移除. 因此, 栈常被称为遵循"先进后出"原则 的数据结构；类似地, 队列始终在其两端执行操作, 其中第一个加入的数据总是第一个被取出. 因此, 队列常被称为遵循"先进先出"原则 的数据结构
给定一棵完全二叉树的顺序存储结构存放着数据元素ABCDEF，则其前、中、后序遍历序列分别为__________。
6. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。
设有向图G的存储结构用邻接矩阵A来表示，则邻接矩阵A中第i行的所有非零元素数量总和等于顶点v_i的出度（或称作发散度），而邻接矩阵A中第j列的所有非零元素数量总和则等于对应顶点v_j的入度（或称作收敛度）。
8. 设一组初始记录关键字序列(k1，k2，……，kn)是堆，则对i=1，2，…，n/2而言满足的条件为_______________________________。
9. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。
void bubble(int r[n])
{
for(i=1;i<=n-1; i++)
{
for(exchange=0,j=0; j<_____________;j++)
if (r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}
if (exchange==0) return；
}
}
10. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。
struct record{int key;int others;};
int bisearch(structrecord r[ ], int k)
{
int low=0,mid,high=n-1;
while(low<=high)
{
________________________________;
if(r[mid].key==k) return(mid+1); else if(____________)high=mid-1;else low=mid+1;
}
return(0);
}
三、应用题(32分)
给定一棵二叉树的中根遍历序列DBEAC和先根遍历序列ABDEC，请提供该二叉树的后根遍历序列。
给定一个无向图G（如右图所示），请求取该无向图G的最小生成树的所有边组成的集合，并计算该最小生成树中各条边上所赋权值之总和。
3. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。
设定散列表的大小为8，并采用H(k)=k mod 7这一特定的散列函数。给定一组初始关键字序列（25、31、8、27、13、68），请分别计算使用线性探测策略和链表处理冲突方式时的平均查找时间。
四、算法设计题(28分)
1． 设计判断两个二叉树是否相同的算法。
2． 设计两个有序单链表的合并排序算法。
参考答案
一、选择题
1．A 2．B 3．A 4．A 5．D
6．B 7．B 8．B 9．C 10．C
二、填空题
1. top1+1=top2
2. 可以随机访问到任一个顶点的简单链表
3. i(i+1)/2+j-1
4. FILO，FIFO
5. ABDECF，DBEAFC，DEBFCA
6. 8，64
7. 出度，入度
8. ki<=k2i&& ki<=k2i+1
9. n-i，r[j+1]=r[j]
10. mid=(low+high)/2，r[mid].key>k
三、应用题
1. DEBCA
2. E={(1,5),(5,2),(5,3),(3,4)},W=10
3. ASL=(11+22+3*4)/7=17/7
4. ASL1=7/6，ASL2=4/3
四、算法设计题
1. 设计判断两个二叉树是否相同的算法。
typedefstruct node {datatype data; struct node *lchild,*rchild;} bitree;
intjudgebitree(bitree *bt1,bitree *bt2)
{
if (bt1==0 && bt2==0) return(1);
else if (bt1==0 || bt2==0||bt1->data!=bt2->data) return(0);
else\_return(\ judge\_bitree(bt1{\_}l\_child, bt2{\_}l\_child) \times \ judge\_bitree(bt1{\_}r\_child, bt2{\_}r\_child));
}
2. 设计两个有序单链表的合并排序算法。
voidmergelklist(lklist *ha,lklist *hb,lklist *&hc)
{
lklist *s=hc=0;
while(ha!=0 && hb!=0)
if(ha->data
else {if(s==0) hc=s=hb; else {s->next=hb;s=hb;};hb=hb->next;}
if(ha==0) s->next=hb; else s->next=ha;
}