中央广播电视大学2008-2009学年度第二学期"开放本科"期末考试
数据结构(本) 试题
一、单项选择题(每小题2分，共30分)
1．针对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则采用( )存储方式最节省时间。
A.单链表 且双链表
C.单循环链表 D．顺序表
2．数据结构中，与所使用的计算机无关的是数据的( )结构。
A．物理
B.存储
C.逻辑与物理
D．逻辑
3．以下特征中，( )不是算法的特性。
A.有穷性 B．确定性
C.可行性 D。有0个或多个输出
4．设有一个长度为n的顺序表，要在第i个元素之前(也就是插入元素作为新表的第i个元素)，则移动元素个数为( )。
A．n-i+1 B.n-i
C． n-i一1 D． i
5．栈的插入删除操作在( )进行。
A．栈底
B．任意位置
C.指定位置
D．栈顶
6．以下说法正确的是( )。
A.栈的特点是先进先出，队列的特点是先进后出
B．栈和队列的特点都是先进后出
C.栈的特点是先进后出，队列的特点是先进先出
D．栈和队列的特点都是先进先出
7．元素2，4，6，8按顺序依次进栈，则该栈的不可能输出序列是( )(进栈出栈可以交替进行)。
A．8，6，4，2 B．2，4，6，8
C．4，2，8，6 D．8，6，2，4
8．设有一个15阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素a，，，在一维数组B中的下标是( )。
A． 42 B． 13
C． 27 D． 32
9．串函数StrCmp("d"，"D")的值为( )。
A．0 B．1
C． 一1 D．3
10．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为( )。
A．2i B．2i一1
C．2iq-2 D．2i+1
11．设一棵有n个叶结点采用链式存储的二叉树，除叶结点外每个结点度数都为2，则该树共有( )个指针域为空。
A．2n B.2n+1
C．2n+2 D．n-t-l
12．已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。
13．在有序表｛l，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86时，经 ( )次比较后查找成功。
A．6 B.3
C. 8 D．4
14．有一个长度为l0的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为( )。
A．29／10
B． 31／10
C． 26／10
D． 29／9
15．一组记录的关键字序列为(37，70，47，29，31，85)，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为( )。
A．3l，29，37，47，70，85
B． 29，3l，37，47，70，85
C． 31，29，37，70，47，85
D． 31，29，37，85，47，?0
二、填空题(每小题2分，共24分)
1．把数据存储到计算机中，并具体体现数据之间的逻辑结构称为（ ） 结构。
2．结构中的数据元素存在一对一的关系称为 （ ） 结构。
3．在双向链表中，每个结点有两个指针域，一个指向 （ ），另一个指向 （ ） 。
4．设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next＝＝NULL，通过操作（ ） ，就可使该单向链表构造成单向循环链表。
5．从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行 x＝h->data；和（ ） 。(结点的指针域为next)
6．两个串相等的充分必要条件是（ ） 。
7．对二叉树的遍历可分为（ ）、（ ） 、（ ） 、 （ ） 四种不同的遍历次序。
8．一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2，则该树共有 （ ） 个结点。
9．一棵有14个结点的完全二叉树，则它的最高层上有 （ ） 个结点。
10．如图2所示的二叉树，其先序遍历序列为 （ ） 。
11．哈希函数是记录关键字值与该记录（ ）之间所构造的对应关系。
12．二叉树排序中任一棵子树都是二叉排序树，这种说法是（ ）的。(回答正确或不正确)
三、综合题(每小题10分，共30分)
1．设一组记录的关键字序列为(49，83，59，41，43，47)，采用堆排序算法完成以下操作：(要求小根堆，并画出中间过程)
(1)以二叉树描述6个元素的初始堆；
(2)以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆。
2．设有序表为(13，19，25，36，48，51，63，84，91，116，135，200)，元素的下标依次为1，2，．．．．，12。
(1)说出有哪几个元素需要经过4次元素间的比较才能成功查到；
(2)画出对上述有序表进行折半查找所对应的判定树(树结点用下标表示)；
(3)设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。
3．(1)对给定数列{7，16，4，8，20，9，6，18，5)，依次取数列中的数据，构造一棵二叉排序树。
(2)对一个给定的查找值，简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查找元素20共要进行多少次元素的比较?
试卷代号：1252
中央广播电视大学2008-2009学年度第二学期"开放本科"期末考试
数据结构(本) 试题答案及评分标准
(供参考)
2009年7月
一、单项选择题(每小题2分，共30分)
1．D 2．D 3．D 4．A 5．D
6．C 7．D 8．C 9．B 10．D
11．D 12．B 13．D 14．A 15．A
二、填空题(每小题2分，共24分)
1．物理(存储)
2．线性
3．结点的直接后继 结点的直接前驱
4．p->next＝head；
5．h＝h->next；
6．串长度相等且对应位置的字符相等
7．先序 中序 后序 层次
8．2n-l
9．7
10．abdgcefhi
11．存储地址
12．正确
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
1201电大《英语综合实践》试题和答案20090704-27
1201电大《英语综合实践》试题和答案20070704-27
1201电大《英语综合实践》试题和答案20080104-27
1197电大《组织行为学(教育)》试题和答案20070704-27
1198电大《中外政治思想史》试题和答案20050704-27
1197电大《组织行为学(教育)》试题和答案20050704-27
1196电大《桥梁工程(本)》试题和答案20070704-27
1196电大《桥梁工程(本)》试题和答案20080104-27