文档介绍：试卷代号: 1 0 1 0 座位号 I II
中央广播电视大学2 0 1 0 - 2 0 1 1学年度第二学期"开放本科"期末考试
数据结构试题
2011 年7 月
!题号 I - I 二| 三| 四! 五! 六| 总分|
|分数 I I I ·1 1- I ---1 I
得分|评卷人
一、单项选择题(在括号内填写所选择的标号。每小题 2分,共 1 8
分)
1. 一种抽象数据类型包括数据和( )两个部分。
A. 数据类型B. 操作
c. 数据抽象 D . 类型说明
2. 在一个长度为 n 的顺序表的表尾插入一个新元素的时间复杂度为( )。
f\. OC 1) B. O(n)
2
c. O(n ) D. O(log2n)
3. 已知L 是带表头附加结点的单链表, 删除第一个元素结点的语句是( )。
A. L = 1.,一> l i nk ; B. L->1ink = L 一>link 一>link;
c. L->link 一>link = L. D. L 一>link = L;
4. 在下列广义表中, ( )又是一个线性表。
A. E ( a , (b , c) ) B. E(a,E)
C. E(a,b) D. E(a, ( »
5. 在一棵深度为3 的三叉树中, 最多含有( )个结点 o假定树根结点的深度为 1。
A. 10 B. 11
c. 12 D. 13
75
6. 向一棵AVL 树插入元素时, 可能引起对最小不平衡子树的双向旋转的调整过程, 此
时需要修改相关( )个指针域的值。
A. 2 B. 3
c. 4 D. 5
7. 在一个具有 n 个顶点的有向图的邻接矩阵表示中, 删除一条边< i , j > 需要的时间复杂
度为( )。
(l) (i)
2
(n) D. 0(n )
8. 在一棵B 树中, 当插入一个元素时, 若最终引起树根结点的分裂, 则新树的高度比原
树的高度( )。
A. 减1 B. 减2
c. 增 1 D. 增2
9. 对存储有 n 个元素的长度为 m 的散列表进行搜索, 平均搜索长度与( )有关。
A. n B. m
c. n/m D. n 长m
得分|评卷人
二、填空题(在横线处填写合适的内容。每小题 2 分, 共 1 4 分)
1. 链表只适用于查找。
2. 归并排序算法的时间复杂度为
3. 在一个链式队列中, 若队头指针与队尾指针的值相同, 则表示该队列至多有
个结点 o
4. 假定一棵树的广义表表示为a 仙,c , d 怡, f ) , g (h) ) ,则结点 f的层数为。假定
树根结点的层数为 0 0
5. 从一棵二叉搜索树中搜索一个元素时, 若给定值大于根结点的值, 则需要向根的
继续搜索。
76
6. 每次从第 i 至第 n 个元素中顺序挑选出一个最小元素, 把它交换到第 i 个位置, 此种排
序方法叫做排序。
7. 快速排序在最坏情况下的时间复杂度为
得分|评卷入 1
三、判断题(在每小题后面的括号内打对号"飞I "表示叙述正确或打叉
号" x "表示叙述错误。每小题 2