中央广播电视大学2007-2008学年度第二学期"开放本科"期末考试
计算机科学技术专业 数据结构(本) 试题
2008年7月
一、单项选择题(每小题2分，共30分)
1．非空的单向循环链表的尾结点满足( )(设头指针为head，指针p指向尾结点)。
A．p->next＝＝NULL B．p=＝NULL
C．p->next＝＝head D．p＝＝head
2．一种逻辑结构( )。
A．可以有不同的存储结构
B．只能有唯一的存储结构
C. 是指某一种数据元素之间的存储关系
n以上三种说法均不正确
3．把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为( )。
A．物理结构 B．逻辑结构
C. 算法的具体实现 D．给相关变量分配存储单元
4．在一个单链表中p所指结点之后插入一个s所指的结点时，可执行( )。
A．p->next＝s；s->next=p->next B．p->next＝s->next
C．p＝s->next D．s->next＝p->next；p->next＝S
5．在一个链队中，假设f和r分别为队头和队尾指针，则插人s所指结点的运算为( )。
A．f->next＝S；f＝S B．r->next＝s；r＝S
C．s->next＝r；r＝S D。s->next＝f；f＝S
6．元素l，3，5，7按顺序依次进栈，则该栈的不可能输出序列是( )(进栈出栈可以交替进行)。
A．7，5，3，1 B．1，3，5，7
C．7，5，1，3 D．3，l，7，5
7．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素a。，2在一维数组B中的下标是( )。
A．41 B．32
C．18 D．38
8．设有两个串p和q，求q在p中首次出现的位置的运算称作( )。
A．连接 B．求子串
C．求串长 D．模式匹配
9．在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为( )。
A．2i B．2i一1
C．2i+1 D．2i+2
10．设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有( )
个结点。
A．2n B．2n+l
C．2n+2 D．2n一1
11，已知如图l所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。
A．abecdf B．acfebd
C．aebcfd D．acdfrb
12．线性表以( )方式存储，能进行折半查找。
A．关键字有序的顺序
B．顺序
C. 链接
D．二插树
13．有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为( )。
A．35／12
B．39／12
C．41／12
D．37／12
14．设已有m个元素有序，在未排好序的序列中挑选第m+1个元素，并且只经过一次元素的交换就使第m+1个元素排序到位，该方法是( )。
A．折半排序
B．冒泡排序
C. 归并排序
D．简单选择排序
15．一组记录的关键字序列为(47，80，57，39，41，46)，利用堆排序(堆顶元素是最小元素) 的方法建立的初始堆为( )。
A．39，41，46，80，47，57
B．39，47，46，80，4l，57
C．41，39，46，47，57，80
D．39，80，46，47，41，57
二、填空题(每小题2分，共24分)
1．结构中的数据元素存在一对多的关系称为--结构。
2．求两个n阶矩阵的乘积，算法的基本操作和时间复杂度分别为 和--。
3．在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作--。
4．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行--和h＝s；操作。(结点的指针域为next)
5．串的两种最基本的存储方式分别是--和--。
6．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的 --、--和--三项信息。
7．设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有--个结点。
(根所在结点为第1层)
8．一棵--y．树中有2n一2条边(结点间的连线)，其中每一个非叶结点的度数都为2，则该树共有--个非叶结点。
9．如图2所示的二叉树，其中序遍历序列为--。
10．哈希函数是记录关键字值与该记录--之间所构造的对应关系。
11．在对一组记录(55，39，97，22，16，73，65，47，88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较--次。
12．n个元素进行冒泡法排序，通常需要进行----趟冒泡，第j趟冒泡要进行
--次元素间的比较。
三、综合题(每小题10分，共30分)
1．设查找表为(7，15，21，22，40，58，68，80，88，89，120)，元素的下标依次为1，2，3，．．．．11。
(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)
(2)说明成功查找到元素40需要经过多少次比较?
(3)求在等概率条件下，成功查找的平均比较次数?
2．(1)如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二叉排序树，这种说法是否正确?若认为正确，则回答正确，若认为不正确，则举例说明。
(2)设有数据集合{40，29，7，73，101，4，55，2，81，92，39}，依次取集合中各数据，构造-棵二叉排序树。
3．(1)以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树，给出相应权重值叶结点的哈夫曼编码。
(2)一棵哈夫曼树有n个叶结点，它一共有多少个结点?简述理由?
四、程序填空题(每空2分，共16分)
1．设线性表为(6，10，16，4)，以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。
#define NULL 0
void main()
{NODE a，b，c，d，*head，*p；
a．data＝6；
b，data＝10；
C．data＝16；
d．data＝4；／*d是尾结点*／
head=(1) ；
a．next＝&b；
b．next＝&c；
c．next＝&d；
(2) ；／*以上结束建表过程*／
p=head；／*p为工作指针，准备输出链表*／
dO
{printf("％d＼n"，(3)--)；
(4)-- ；
}while((5)--)；
}
2．以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点)。
void lnorder(struct BTreeNode *BT)
{if(BT!：NULL){
(1)-- ；
(2)-- ；
Inorder(BT->right)；}
)
利用上述程序对右图进行遍历，结果是(3)--；
试卷代号：1252
中央广播电视大学2007-2008学年度第二学期"开放本科"期末考试
计算机科学技术专业 数据结构(本)
试题答案及评分标准
(供参考)
2008年7月
一、单项选择题(每小题2分，共30分)
1．C 2．A 3．A 4．D 5．B
6．C 7．D 8．D 9．A 10．D
11．D 12．A 13．D 14．D 15．A
二、填空题(每小题2分，共24分)
1．树形
2．乘法，0(n3)
3．q->next＝p->next；
4．S->next＝h；
5．顺序存储 链式存储
6．行下标 列下标 非零元素值
7． 12
8．n一1
9．dgbaechif
10．存储地址
11．3
12．n一1 n-j
三、综合题(每小题10分，共30分)
1．
(1)
(2)4次
(3)ASL＝(1+2x 2+3*4+4*4)／11＝3
2．
(1)不正确，例
（2）
2；0000
3 0001
4 001
7 10
8 ll
9 0l
(2)2n一1个，因为非叶结点数比叶结点数少一个。
四、程序填空题(每空2分，共16分)
1．(1)&a
(2)d->next＝=NULL
(3)p->data
(4)p=p->next
(5)p!＝NULL
2．(1)Inorder(BT->leh)
(2)printf("％c"，BT->data)
(3)dbeafc
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
1201电大《英语综合实践》试题和答案20090704-27
1201电大《英语综合实践》试题和答案20070704-27
1201电大《英语综合实践》试题和答案20080104-27
1197电大《组织行为学(教育)》试题和答案20070704-27
1198电大《中外政治思想史》试题和答案20050704-27
1197电大《组织行为学(教育)》试题和答案20050704-27
1196电大《桥梁工程(本)》试题和答案20070704-27
1196电大《桥梁工程(本)》试题和答案20080104-27