数据结构试卷（五）
一、 选择题（每题2分，共20分）
1. 数据的最小单位是( A )。
A. 数据项
B. 数据类型
C. 数据元素
D. 数据变量
2. 设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为( B )。
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)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为( A )。
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)的返回值为( 快速排序python实现A)。
A. "STRUCTURE"
B. "DATA"
C. "ASTRUCTUR"
D. "DATASTRUCTURE"
5. 设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为( D )。
A. O(log2n)
B. O(1)
C. O(n2)
D. O(n)
6. 设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为N1，…，度数为m的结点数为Nm，则N0=(B)。
A. N1+N2+…+Nm
B. 1+N2+2N3+3N4+…+(m-1)Nm
C. N2+2N3+3N4+…+(m-1)Nm
D. 2N1+3N2+…+(m+1)Nm
7. 设有序表中有1000个元素，则用二分查法查元素X最多需要比较(B)次。
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出发可以得到一种深度优先遍历的顶点序列为(B)。
A. abedfc
B. acfebd
C. aebdfc
D. aedfcb
9. 设输入序列是（1，2，3，…，n），经过栈的作用后输出序列的第一个元素是n，则输出序列中的第i个输出元素是(C)。
A. n-I
B. n-1-I
C. n+1-I
D. 不能确定
10. 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45
为基准得到的一趟快速排序的结果是(C)。
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
二、 填空题（除第1、2、8题2分外每空1分，共20分）
1. 设有一个顺序共享栈S[0： n-1]，其中第一个栈顶指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是__top1+1 = top2__。
2. 在图的邻接表中用顺序存储结构存储表头结点的优点是_可以随机访问到任一个顶点的简单链表_。
3. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素(包括对角线上的
元素)存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_i*（i+1)/2 +j-1__个数据元素。
4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为FILO表； 队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_FIFO表。
5. 设一棵完全二叉树的顺序存储结构中的存储数据元素为ABCDEF，则该二叉树的前序遍历序列为_ABDECF_、中序遍历序列为_DBEAFC_、后序遍历序列为_DEBFCA_。
6. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为_8_，有_64_个叶子结点。
7. 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中的所有非零元素个数之和等于顶点i的_出度_，第i列中的所有非零元素个数之和等于顶点i的_入度_。
8. 设一组初始记录关键字序列(k1，k2，…，kn)是堆，则对i=1、2、…、n/2而言满足的条件为_ki<=k2i and k<=k2i+1_。
9. 下面程序段的功能是实现冒泡排序算法，请在下画线处填上正确的语句。
1 | def bubbleSort(sqlist): |
2 | flag = True |
3 | i = 1 |
4 | while i<sqlist.len and flag: |
5 | flag = False |
6 | for j in range(_n-i_): |
7 | if sqlist.list[j+1].key < sqlist.list[j].key: |
8 | p = sqlist.list[j] |
9 | r[j+1]=r[j] |
10 | sqlist.list[j+1] = p |
11 | flag = True |
12 | i += 1 |
10. 下面程序段的功能是实现二分查算法，请在下画线处填上正确的语句。
1 | class record(object): |
2 | def __init__(self,key=None,other=None): |
3 | self.key = key |
4 | her = other |
5 | |
6 | def bisearch(r,k): |
7 | low = 0 |
8 | high = len(r)-1 |
9 | while low<=high: |
10 | _mid=(low+high)/2_ |
11 | if r[mid].key == k: |
12 | return mid+1 |
13 | elif r[mid].key>k: |
14 | high = mid-1 |
15 | else: |
16 | low = mid+1 |
17 | return -1 |
三、 应用题（每题8分，共32分）
1. 设某棵二叉树的中序遍历序列为DBEAC、前序遍历序列为ABDEC，要求给出该二叉树的后序遍历序列。
答：DEBCA
2. 设有无向图G(如图A.7所示)，给出该图的最小生成树上边的集合，并计算最小生成树各边上的权值之和。
图A.7无向图G
答：E={(1,5),(5,2),(5,3),(3,4)},W=10
3. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查时的平均查长度。
答：ASL=(1*1+2*2+3*4)/7=17/7;
4. 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查长度。
答：ASL1=7/6,ASL2=4/3
四、 算法设计题（每题14分，共28分）
1. 设计判断两个二叉树是否相同的算法。
1 | Def judge(node nod1,node nod2): |
2 | If nod1 == NULL and nod2 == NULL: |
3 | return True; |
4 | Elif nod1 == NULL or nod2 == NULL or nod1.data!=nod2.data: |
5 | return False; |
4 | Else: |
5 | If judge(nod1.lchild,nod2.lchild) and hild): |
6 | Return True; |
7 | Else: |
8 | Return False |
2. 设计两个有序单链表的合并排序算法。
1 | Def merge(lklist l1,lklist l2): |
2 | lklist out = lklist() |
3 | While !l1.isempty() and !l2.isempty(): |
4 | If l1.front() < l2.front(): |
5 | out.append(l1.front()) |
4 | l1.pop_front() |
5 | Else: |
6 | out.append(l2.front()) |
7 | l2.pop_front() |
8 | If !l1.isempty(): |
9 | For item in l1: |
10 | out.append(item) |
11 | If !l2.isempty(): |
12 | For item in l2: |
13 | out.append(item) |
14 | Return out |
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论