中央广播电视大学2003-2004学年度第二学期"开放专科"期末考试
计算机专业 数据结构 试题
2004年7月
一、单选题(每小题2分，共12分)
1．对于长度为9的顺序存储的有序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为( )除以9。
A．20 B．18
C．25 D．22
2．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行( )。
3．在--个顺序队列中，队首指针指向队首元素的( )位置。
A．后一个 B，前一个
C．当前 D。任何
5．一个记录r理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空间的大小即记录长度为( )
A．所有域长度之和 B。最大域所占字节长度
C．任意一个域长度 D。 sizeof(r)的值
6．在一个长度为n的顺序表中向第i个元素(o≤i《n)位置插入一个新元素时，需要从后向前依次后移( )个元素。
A．n-i B．n-i+1
C。n-i-l D。i
二、填空题(每空1分，共28分)
1．对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为--，在表尾插入元素的时间复杂度为--。
2．在稀疏矩阵所对应的三元组线性表中，每个三元组元素按--为主序、--为辅序的次序排列。
3．当用长度为N的数组顺序存储一个栈时，假定用top＝＝N表示栈空，则表示栈满的条件为--。
4．假定一棵三叉树的结点个数为50，则它的最小深度为--，最大深度为--。
5．在一棵---X树中，第5层上的结点数最多为--。
6．在进行函数调用时，需要把每个实参的值和凋用后的--传送给被调用的函数中。
7．对于一棵具有n个结点的二叉树，若一个结点的编号为i(O≤i≤n-1)，则它的左孩子结点的编号为--，右孩子结点的编号为--，双亲结点的编号为--。
8．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为--和--条。
9．以二分查找方法从长度为n的顺序存储的线性表中查找一个元素时，平均查找长度小于等于--，时间复杂度为--。
10．队列的删除操作在 -- 逃行。
11．对于一棵具有n个结点的树，该树中所有结点的度数之和为--。
12．在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为--个。
13．在一个小根堆中，堆顶结点的值是所有结点中的--；在一个大根堆中，堆顶结点的值是所有结点中的--。
14．向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的--上；若元素的值大于根结点的值，则应把它插入到根结点的--上。
15．进行图的广度优先搜索遍历时，其算法需要使用的一个辅助数据结构是--；进行图的深度优先搜索遍历时，其非递归算法需要使用的一个辅助数据结构是--。
16．对5个不同的数据元素进行直接插入排序，最多需要进行--次元素之间比较。
17．对存储有n个元素的表长度为m的散列表进行查找，平均查找长度与--的值
有关。
18．如果一个过程直接或间接地调用自己，则称这个过程是一个--过程。
三、运算题(每小题6分，共24分)
1．假定一棵二叉树广义表表示为a(b(c)，d(e，f(，g)))，分别写出对它进行先序、中序、后序、按层遍历的结果。
先序：
中序：
后序：
按层：
2．已知一个图的顶点集V和边集G分别为：
V={0，1，2，3，4，5，6，7}；
E={(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(3，6)10，(4，6)4，(5，7)20，(6，7)8)；
试写出按照普里姆算法从顶点1出发得到最小生成树的过程中，依次选取的各条边。(提示：先画出对应的图形，然后再运算)。
--，--，--，--，--，--，--。
3．已知一个图的顶点集V和边集G分别为：
V={0，1，2，3，4，5，6，7，8)
E={<0，2>，
<5，7>，<6，7>，<7，8>)；
若存储它采用邻接表，并且每个顶点邻按表中的边结点都是按照终点序号从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列(提示：先画出对应的图形，然后再运算)。
拓扑序列：
4。假定一组记录的排序码为(46，79，56，38，40，80，25，34，53，64)，则对其进行归并排序的第二趟结果为一。
四、阅读算法，回答问题(每小题8分，共16分)
假定调用该算法时线性表l为(35，19，12，15)，则调用返回后线性表L变为；
------。
。
五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分)
1． 1． 此为向以BST为树根指针的二叉搜索树上插入值为item的结点的非递归算法。
2． 2． 从表头指针为1a的按从小到大有序的单链表中删除所有值相同的多余元素，并释放被删结点空间。
六、编写算法(8分)
编写从类型为List的线性表L中删除其值等于给定值x的第一个元素的算法，假定该线性表不为空。要求若删除成功返向true，否则返回false。
Bool Delere (List &L，Elem Type x)
试卷代号：2075
中央广播电视大学2003-2004学年度第二学期"开放专科"期末考试
计算机专业 数据结构 试题答案及评分标准
(供参考)
2004年?月
一、单选题(每小题2分，共12分)
评分标准：选对者得2分，否则不得分。
1．C 2．D 3．B 4．A 5．D 6．A
二、填空题(每空1分，共28分)
三、运算题(每小题6分，共24分)
1．先序：a，b，c，d，e，{，g 1分
中序：c，b，a，e，d，f，g 2分
后序：c，b，c，g，f，d，a 2分
按层：a，b，d，c，e，f，g 1分
2． (1，5)6， (1，0)8， (0，3)2， (0，2)5， (3，6)10， (6，4)4， (6，7)8
评分标准：边和次序均正确得6分，否则酌情给分。
3．拓扑序列：1，3，6，o，2，5，4，7，8／／完全相同得6分，否则视情况酌情
4．[38 46 56 79][25 34 40 80][53 64]／／全对6分，否则酌情给分
四、阅读算法，回答问题(每小题8分，共16分)
1． (58，35，19，15，30)
评分标准：8分，有一处错8分全扣。
2．对B丁指针所指向的二义树进行中序遍历的非递归算法。
评分标准：8分，请根据叙述情况酌情给分。
五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分)。
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
2045电大《金融企业会计》试题和答案20040104-27
2045电大《金融企业会计》试题和答案20040704-27
电大金融学专业《公司财务》试题04-27
电大网上中考《西方经济学》试题（专科）04-27
电大计算机专业《英语》中考试题04-27
2058电大《C++语言程序设计》试题和答案20040104-27
2056电大《证券投资分析》试题和答案20070104-27
2056电大《证券投资分析》试题和答案20080704-27