中央广播电视大学2007-2008学年度第二学期"开放专科"期末考试
数据结构 试题
2008年7月
一、单选题(每小题2分，共20分)
1．若需要利用形参直接访问实参，则应把形参变量说明为( )参数。
A．指针 B．引用
C. 值 D．函数
2．假定利用数组aLN引顷序存储一个栈，用top表示栈顶指针，top＝＝一1表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作为( )。
A．returna[--top]； B．returna[top--]；
C. returna[++top]； D．returna[top++];
3．假定一个链队的队首和队尾指针分别为f和r，则判断队空的条件为( )。
A．f＝=r B．f!＝NULL
C. r!＝NULL D. f＝＝NULL
4．在一棵具有n个结点的二叉树中，所有结点的空指针数等于( )。
A．n B．n一1
C． n+1 D． 2 * n
5．从堆中删除一个元素的时间复杂度为( )。
A．O(1) B．O(n)
C O(10g2n) D． O(nlog2n)
6．利用n个值作为叶子结点的权生成的哈夫曼树中共有( )个分支结点。
A．n B．n+l
C．n一1 D．2 * n
7．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。
A．最小 B．一般
C. 广度优先 D．深度优先
8．一个具有n个顶点和小于n-l条边的图一定是( )。
A．连通的 B．不连通的
C. 无回路 D．有回路
9．对于长度为n的顺序存储的有序表，若采用二分查找，则对任一元素的查找长度为 ( )数量级。
A．n2 B．n
C. log2n D．
lo．若根据一个数据集合建立对应的散列表，假定采用h(K)＝K％7计算散列地址，则 元素48的散列地址为( )。
A．3 B．4
C．5 D．6
二、填空题(每小题2分，共20分)
1．对于一个长度为n的顺序存储的线性表，在表尾插入元素的时间复杂度为 。
2．在稀疏矩阵所对应的三元组线性表中，线性表的长度等于稀疏矩阵中(0／非0)
元素的个数。
3．当用长度为N的数组顺序存储一个栈时，假定用top＝＝N表示栈空，则表示栈满的条件为--。
4．队列的插入操作在队尾进行，而删除操作在 进行。
5．由20个元素构成的二叉树中，其最小深度为 。
6．在任一棵二叉树中，除树根结点外，其余的每个结点均有 个父亲结点。
7．对于一棵二叉树，若一个结点的编号为i，它的左孩子结点的编号为2i，则右孩子结点的编号为 。
8．向一棵二叉搜索树中插入一个元素时，若元素的值大于树根结点的值，则应把它插入到该树根结点的 子树上。
9．对于一个具有n个顶点和c条边的无向图，在其对应的邻接表中，所含边结点的总数为 个。
10．以 查找的方法查找一个元素时，首先需要查找索引表，然后再查找主表。
三、运算题(每小题6分，共24分)
1．假定一棵普通树的广义表表示为a(b(e)，c(f，g)，d)，试分别写出先根、后根和按层遍
历的结果。
先根：
后根：
按层：
2．已知一个带权图的顶点集V和边集G分别为：
V＝{0，1，2，3，4}；
E＝{(0，1)8，(0，2)5，(0，3)2，(2，3)10，(2，4)13，(3，4)16}；
按照权值从小到大的次序写出该图的最小生成树中的每条边。
最小生成树中的每条边：
3．假定对线性表(18，25，63，50，41，22)进行散列存储，若选用H(K)＝K％7作为散列函数，并采用链接法处理冲突，则查找长度为1的元素个数有--个。
4．假定-组记录的排序码为(40，80，50，62，46，79，56，38，73，38，64)，写出对其进行归并排序的过程中，第二趟归并后的结果。
第二趟归并后的结果：
四、阅读算法，回答问题(每小题8分，共16分)
1．写出下面算法被调用后得到的输出结果。
voidAE(Stack& S) ／／S为一个顺序存储的栈
{
InitStack(S)；
Push(S，30)；Push(S，40)；
inti，a[4]＝{12，15，5，8}；
for(i＝0；i<4；id-+)Push(S，a[i])；
Pop(S)；
while(!StackEmpty(S))cout<
输出结果为：
2．指出下面算法的功能，假定BST指向一棵二叉搜索树。
bool Find(BTreeNode* BST，ElemType& item)
{
while(BST!＝NULL){
if(item＝＝BST一>data)return true；
else if(item
else BST＝BST一->right；
)
return false；
}
算法功能：
五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分)
1．此算法为求出并返回一个用邻接表表示的无向图GL中序号为numb的顶点的度数。
int degree(adjlist GL，int numb，int n)
{
int d＝0；
edgenode* p＝GL[numb]；
while(p!＝NULL){
；
p=p一>next；
}
return d；
}
2．下面算法的功能是统计出二叉树BT中值为x的结点个数并返回。
int BTCl(BTreeNode* BT，ElemType x)
{
if(BT＝＝NULL)return 0；
else if(BT一>data＝＝x)
return BTCl(BT一>left，x)+BTCl(BT一>right，x)+1；
else
return BTCl(BT一>left，x)+ ；
}
六、编写算法(8分)
根据下面函数原型编写出从二叉搜索树BST中查找并返回所有结点的最大值的算法，若为空树则退出运行。
ElemType FM(BTreeNode* BST)；
试卷代号：2075
中央广播电视大学2007-2008学年度第二学期"开放专科"期末考试
数据结构 试题答案及评分标准
(供参考)
2008年7月
一、单选题(每小题2分，共20分)
1．B 2．B 3．D 4．C 5．C
6．C 7．A 8．B 9．C 10．D
二、填空题(每小题2分，共20分)
1．O(1)
2. 非 0
3．top＝＝0
4．队首(队头)
5． 5
6． 1
7．2i+1
8．右
9． 2e
10．索引
三、运算题(每小题6分，共24分)
1．先根：a，b，e，c，f，g，d； ／／2分
后根：e，b，f，g，c，d，a； ／／2分
按层：a，b，c，d，e，f，g ／／2分
2．最小生成树中的每条边：(0，3)2，(0，2)5，(0，1)8，(2，4)13
3． 4
4．[40 50 62 80][38 46 56 79][38 64 73] ／／酌情给分
四、阅读算法，回答问题(每小题8分，共16分)
评分标准：根据每小题所答完整程度酌情给分。
1． 5 15 12 40 30
2．从BST所指向的二叉搜索树中查找出值为item的元素，若查找成功返回真，否则返回假。
五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分)
1．d++
2．BTCl(BT一>right，x)
六、编写算法(8分)
评分标准：根据编程完整程度酌情给分。
注：可以不设指针t，而直接使用值参BST。
ElemType FM(BTreeNode* BST){
if(BST＝＝NULL){cerr<<"此树为空"<
while(t一>right!＝NULL)t＝t一>right； ／／6分
returnt->data； ／／8分
}
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
2045电大《金融企业会计》试题和答案20060704-27
2045电大《金融企业会计》试题和答案20050104-27
2045电大《金融企业会计》试题和答案20060104-27
2045电大《金融企业会计》试题和答案20040104-27
2045电大《金融企业会计》试题和答案20040704-27
电大金融学专业《公司财务》试题04-27
电大网上中考《西方经济学》试题（专科）04-27
电大计算机专业《英语》中考试题04-27