文档介绍：试卷代号: 1 0 1 0 座位号CD
中央广播电视大学 2 0 11一 2 0 1 2学年度第一学期"开放本科"期末考试
数据结构试题
2012 年1 月
|题号 I - I 二| 三| 四| 五| 六l 总分|
|分数 I I I I I I I I
|得分|评卷人|
一、单项选择题{在括号内填写所选捧的标号。每小题 2分,共 1 8
I I I 分)
, 5语句的执行次数为( )。
for (int i=l; i<=n; i+ 十)
for (int j=l; j<=i; j++) S;
A. n 2 B. n2 / 2
C. n(n 十1) D. n(n 十 1) / 2
2. 多维数组实际上是由嵌套的( )实现的。
儿一维数组
D . 简单变量
3. 对于表头指针为 fi r s t 的单链表, 为空表的判定条件是( )。
A. first==NULL; B. first->link==NULL;
C. first- > link = = first; D. first! =NULL;
4. 若让元素1 ,2 ,3 依次进钱, 则出钱次序不可能出现( )种情况。
A. 3 ,2,1 B. 2,1,3
C. 3,1,2 D. 1 ,3,2
5. 在一棵具有 n 个结点的满二叉树中, 共包含有( )个分支结点。
A. n-l B. n/2
C. n几+ 1 D. n/2-1
74
6. 若搜索每个元素的概率相等, 则在长度为 n 的顺序表上搜索任一元素的平均搜索长
度为( )。
A. n B. n+1
C. (n 一 1) / 2 D. (n+1)/2
7. 向一棵AVL 树插入元素时, 可能引起对最小不平衡子树的调整过程, 此调整分为
( )种旋转类型。
A. 2 B. 3
C. 4 D. 5
8. 为了实现图的广度优先搜索遍历, 其算法使用的一个辅助数据结构是( )。
A. 枝B. 队列
C. 二叉树D. 树
9. 在一棵5 阶B 树中, 每个结点最多允许有( )个关键码。
A. 2 B. 3
C. 4 D. 5
|得分|评卷人 l
二、填空题{在横线处填写合适的内容。每小题 2分,共 1 4分)
I I I
,类中的每个对象又称为该类的一一一一
2. 队列的删除操作在进行。
3. 在一棵三叉树中, 若度为3 的结点数有2 个, 度为2 的结点数有1 个, 度为1 的结点数
有 2个,则度为 O的结点数有一一一一-个。
4. 在一个最小堆中, 堆顶结点的值是所有结点中的
5. 在一棵具有 n 个结点的AVL 树上进行插入或删除元素的时间复杂度大致为
6. 在对 n 个元素进行直接选择排序的算法中, 记录比较总次数的时间复杂度为
7. 在堆排序中, 如果n 个对象的初始堆已经建好, 则在堆排序阶段, 需要进行
次对堆顶结点的调整(筛)运算。
75
|得分|评卷人|
三、判断题(在每小题后面的括号内打对号"~"表示叙述正确或打叉
I I I 号" X "表示叙述错误。