宁波网站建设论坛,引流推广平台,西安市建设局官方网站,厦门微信网站数据结构试卷#xff08;五#xff09;
一、选择题 (20 分)
1#xff0e;数据的最小单位是#xff08; #xff09;。
(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量
2#xff0e;设一组初始记录关键字序列为 (50 #xff0c;40#xff0c; 95#xff0c;20…数据结构试卷五
一、选择题 (20 分)
1数据的最小单位是 。
(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量
2设一组初始记录关键字序列为 (50 40 952015706045) 则以增量 d4 的一趟希尔排序结
束后前 4 条记录关键字为 。
(A) 40 502095 (B) 15 4060 20
(C) 15 204045 (D) 45 4015 20
3设一组初始记录关键字序列为 (255015 35808520403670)其中含有 5 个长度为 2 的
有序子表则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为 。
(A) 15 253550 204080853670
(B) 15 25355080208540 7036
(C) 1525355080852036 4070
(D) 15 253550 802036407085
4函数 substr( “DATASTRUCTURE” 59) 的返回值为 。
(A) “STRUCTURE” (B) “DATA”
(C) “ASTRUCTUR” (D) “DATASTRUCTURE”
5设一个有序的单链表中有 n 个结点现要求插入一个新结点后使得单链表仍然保持有序则该操作的
时间复杂度为 。
(A) O(log 2n) (B) O(1) (C) O(n 2
) (D) O(n)
6设一棵 m叉树中度数为 0 的结点数为 N0度数为 1 的结点数为 Nl ,, 度数为 m的结点数为 Nm则
N0 。
(A) N l N2,, Nm (B) lN 22N33N4,, (m-1)Nm
(C) N 22N33N4,, (m-1)Nm (D) 2N l 3N2,, (m1)Nm
7设有序表中有 1000 个元素则用二分查找查找元素 X最多需要比较 次。
(A) 25 (B) 10 (C) 7 (D) 1
8设连通图 G 中的边集 E{(a b)(ae)(ac)(b e) (e d)(df) (f c)}则从顶点 a 出发可
以得到一种深度优先遍历的顶点序列为 。
(A) abedfc (B) acfebd (C) aebdfc (D) aedfcb
9设输入序列是 1、 2、3、,, 、 n经过栈的作用后输出序列的第一个元素是 n则输出序列中第 i 个
输出元素是 。
(A) n-i (B) n-1-i (C) n1-i (D) 不能确定
10 设一组初始记录关键字序列为 (45 8055404285) 则以第一个记录关键字 45 为基准而得到一
趟快速排序的结果是 。
(A) 40 4245558083 (B) 42 4045 808588
(C) 42 4045558085 (D) 42 4045 855580
二、填空题 ( 共 20 分)
1. 设有一个顺序共享栈 S[0 n-1] 其中第一个栈项指针 top1 的初值为 -1 第二个栈顶指针 top2 的初
值为 n则判断共享栈满的条件是 ____________________。
2. 在图的邻接表中用顺序存储结构存储表头结点的优点是 ____________________。
3. 设有一个 n 阶的下三角矩阵 A如果按照行的顺序将下三角矩阵中的元素包括对角线上元素存放
在 n(n1) 个连续的存储单元中则 A[i][j] 与 A[0][0] 之间有 _______个数据元素。
4. 栈的插入和删除只能在栈的栈顶进行后进栈的元素必定先出栈所以又把栈称为 __________表队
列的插入和删除运算分别在队列的两端进行先进队列的元素必定先出队列所以又把队列称为
_________表。
5. 设一棵完全二叉树的顺序存储结构中存储数据元素为 ABCDEF则该二叉树的前序遍历序列为
___________中序遍历序列为 ___________后序遍历序列为 ___________。
6. 设一棵完全二叉树有 128 个结点则该完全二叉树的深度为 ________有 __________个叶子结点。
7. 设有向图 G的存储结构用邻接矩阵 A 来表示则 A 中第 i 行中所有非零元素个数之和等于顶点 i 的
________第 i 列中所有非零元素个数之和等于顶点 i 的__________。
8. 设一组初始记录关键字序列 (k 1k 2,, k n) 是堆则对 i1 2, n/2 而言满足的条件为
_______________________________ 。
9. 下面程序段的功能是实现冒泡排序算法请在下划线处填上正确的语句。
void bubble(int r[n])
{
for(i1;in-1; i)
{
for(exchange0,j0; j_____________;j)
if (r[j]r[j1]){tempr[j1];______________;r[j]temp;exchange1;}
if (exchange0) return
}
}
10. 下面程序段的功能是实现二分查找算法请在下划线处填上正确的语句。
struct record{int key; int others;};
int bisearch(struct record r[ ], int k)
{
int low0,mid,highn-1;
while(lowhigh)
{
________________________________;
if(r[mid].keyk) return(mid1); else if(____________) highmid-1;else lowmid1;
}
return(0);
}
三、应用题 (32 分)
1. 设某棵二叉树的中序遍历序列为 DBEAC前序遍历序列为 ABDEC要求给出该二
叉树的的后序遍历序列。
2. 设无向图 G如右图所示 给出该图的最小生成树上边的集合并计算最小生成
树各边上的权值之和。
3. 设一组初始记录关键字序列为 (15 171822355160)要求计算出成功
查找时的平均查找长度。
4. 设散列表的长度为 8散列函数 H(k)k mod 7初始记录关键字序列为 (25 318271368) 要
求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。
四、算法设计题 (28 分)
1 设计判断两个二叉树是否相同的算法。
2 设计两个有序单链表的合并排序算法。
一、选择题
1A 2B 3A 4A 5D
6B 7B 8B 9C 10 C
二、填空题
1. top11top2
2. 可以随机访问到任一个顶点的简单链表
3. i(i1)/2j-1
4. FILO FIFO
5. ABDECF DBEAFC DEBFCA
6. 864
7. 出度入度
8. kik 2i k ik 2i1
9. n-ir[j1]r[j]
10. mid(lowhigh)/2 r[mid].keyk
三、应用题
1. DEBCA
2. E{(1,5),(5,2),(5,3),(3,4)},W10
3. ASL(1*12*23*4)/717/7
4. ASL17/6 ASL24/3
四、算法设计题
1. 设计判断两个二叉树是否相同的算法。
typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;
int judgebitree(bitree *bt1,bitree *bt2)
{
if (bt10 bt20) return(1);
else if (bt10 || bt20 ||bt1-data!bt2-data) return(0);
else return(judgebitree(bt1-lchild,bt2-lchild)*judgebitree(bt1-rchild,bt2-rchild));
}
2. 设计两个有序单链表的合并排序算法。
void mergelklist(lklist *ha,lklist *hb,lklist *hc)
{
lklist *shc0;
while(ha!0 hb!0)
if(ha-datahb-data){if(s0) hcsha; else {s-nextha; sha;};haha-next;}
else {if(s0) hcshb; else {s-nexthb; shb;};hbhb-next;}
if(ha0) s-nexthb; else s-nextha;
}
