中央广播电视大学2005-2006学年度第二学期"开放专科"期末考试
计算机专业 数据结构 试题
2006年7月
一、单选题(每小题2分，共16分)
1．若一个数据具有集合结构，则元素之间为( )。
A. 线性关系 B．层次关系
C. 网状关系 D．无任何关系
2．在一个顺序表的表尾插人一个元素的时间复杂度为( )。
A．O(n) B. O(1)
C．O(n*n) D．O(log2n)
3．在一个长度为n的顺序表中向第i个元素(o≤i≤n)位置插入一个新元素时，需要从后向前依次后移( )个元素。
A．n-i B．n-i+1
C．n-i-l D．i
4．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行( )操作。
5．在一个顺序队列中，队首指针指向队首元素的( )位置。
A. 后一个 B．前一个
C．当前 D．任何
6．向二叉搜索树中插入一个元素时，其时间复杂度大致为( )。
7．一个记录r理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空间的大小即记录长度为( )。
A．所有域长度之和 B．最大域所占字节长度
C．任意一个域长度 D．sizeof(r)的值
8．对于长度为9的顺序存储的有序表，若采用二分查找，则平均查找长度为( )除以9。
A．20 D．18
C．25 D．22
二、填空题(每空1分，共28分)
1．数据的逻辑结构被分为--、--、--和--四种。
2．对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度和空间复杂度分别为--和--
3．在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的--、--和--三项。
4．在一棵高度为5的理想平衡树中，最少含有--个结点，最多含有----个结点。
5．在一个小根堆中，堆顶结点的值是所有结点中的--，在一个大根堆中，堆顶结点的值是所有结点中的--·
6．在一个具有n个(n>=3)顶点的无向图中，要连通所有顶点则至少需要--条边，要使每对顶点之间都存在回路，则至少需要--条边。
7．在一个具有5个顶点的无向完全图中，包含有--条边，在一个具有5个顶点的有向完全图中，包含有----朱边。
8．对于一个具有n个顶点和e条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为--和--条'
9．假定一个线性表为(12，23，?4，55，63，40，80，37)，若按Key％3条件进行划分，使得同一余数的元素成为一个子表，则得到的余数为0、l、2三个子表的长度依次为--、
10．在一棵4阶B_树上，每个非树根结点的关键字数目最少允许为--个，最多允许为--个，其子树数目最少允许为--个，最多允许为---个.
11．在对具有n个元素的顺序表进行堆排序时，对任一分支结点进行筛：亏算的时间复杂度为--，整个堆排序过程的时间复杂度为--。
三、运算题(每小题6分，共24分)
1．假定一棵'-X树广义表表示为A(B(，D)，C(E(G)，F))，分别写出对它进行先序、中序、按层遍历的结果。
先序：
中序：
按层：
2．已知一个有向图的顶点集V和边集G分别为：
假定该图采用邻接矩阵表示，并假定顶点a，b，c，d，e，f对应的编号依次为0，1，2，3，4，5，则分别写出从顶点a出发进行深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。此序列可按字符，也可按序号写出。
深度优先搜索序列：
广度优先搜索序列：
3．假定对线性表(38，25，74，52，48，65，36)进行散列存储，采用HCK)＝K％9作为散列函数，若采用链接法处理冲突，则求出每个元素对应的查找长度(38，25，74，52，48，65，36)对应的查找长度依次为--。
4．有5个带权结点，其权值分别为3，7，2，6，14，以它们为叶子结点生成一棵霍夫曼树，求出该树的带权路径长度和树的高度。
带权路径长度：
高度：
四、阅读算法，回答问题(每小题6分，共12分)
五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分)
1．该函数的功能是统计出BT所指向的二叉树中大于给定值x的结点个数并返回
2．下面函数的功能是从二叉树BT中查找值为x的结点，若查找成功则返回结点地址，否则返回空。
六、编写算法(8分)
根据下面函数声明编写算法，向类型为List的线性表L中第i个元素位置(0≤i≤L．size)
插入一个元素的算法，假定不需要对i的值进行有效性检查，同时不需要检查存储空间是否用完。
试卷代号：2075
中央广播电视大学2005-2006学年度第二学期"开放专科"期末考试
计算机专业 数据结构 试题答案及评分标准
(供参考)
2006年?月
一、单选题(每小题2分，共16分)
评分标准：选对者得2分，否则不得分。
1．D 2，B 3．A 4．D
5．B 6．A 7．D 8．C
二、填空题{每空1分，共28分)
1．集合结构 线性结构 树结构 图结构 (次序无先后)
2．O(n) O(1)
3．行号 列号 元素值 (次序无先后)
4． 16 31
5．最小值 最大值
6．n一1 n
7． 10 20
8． e e
9． 2 3 3
10． 1 3 2 4
11． O(log2n) O(nlog2n)
三、运算题(每小题6分，共24分)
1．先序：A，B，D，C，E，G，F；
中序；B，D，A，G，E，C，F；
按层：A，B，C，D，E，F，G
2．深度优先搜索序列：a，b，f，c，d，e(或0，1，5，2，3，4)
广度优先搜索序列：a，b，c，f，d，e(或0，1，2，5，3，4)
3．(38，25，74，52，48，65，36)对应的查找长度(1，l，2，1，2，3，1)
4．带权路径长度：66
高度：5 ·
四、阅读箅法，回答问题(每小题2分，共12分)
评分标准：根据情况酌情给分。
1．(36，15，12，8，50，25)
2． 5 15 8 6 20 28 ·
五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分)
六、编写算法(8分)
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
2045电大《金融企业会计》试题和答案20050104-27
2045电大《金融企业会计》试题和答案20040104-27
2045电大《金融企业会计》试题和答案20040704-27
电大金融学专业《公司财务》试题04-27
电大网上中考《西方经济学》试题（专科）04-27
电大计算机专业《英语》中考试题04-27
2058电大《C++语言程序设计》试题和答案20040104-27
2056电大《证券投资分析》试题和答案20070104-27