【学历类职业资格】数据结构-9及答案解析.doc
《【学历类职业资格】数据结构-9及答案解析.doc》由会员分享,可在线阅读,更多相关《【学历类职业资格】数据结构-9及答案解析.doc(9页珍藏版)》请在麦多课文档分享上搜索。
1、数据结构-9 及答案解析(总分:100.00,做题时间:90 分钟)一、B单项选择题/B(总题数:15,分数:30.00)1.如果待排序的记录的规模很大,则在下面的排序方式中,我们最好不要选择使用 ( )(分数:2.00)A.快速排序B.直接插入排序C.堆排序D.归并排序2.设数组 A0,m作为循环队列 sq的存储空间,front 为队头指针,rear 为队尾指针,则执行入队操作的语句是( )(分数:2.00)A.sfront=(sfront+1)%mB.sfront=(sfront+1)%(m+1)C.srear=(srear+1)%mD.srear=(srear+1)%(m+1)3.线性表
2、若采用链表存储结构时,要求内存中可用存储单元的地址( )(分数:2.00)A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以4.串是一种特殊的线性表,其特殊性体现在( )(分数:2.00)A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符5.对广义表(a),(b)进行下面的操作 head(head(a),(b)后的结果是( )(分数:2.00)A.aB.(C.( )D.不确定6.将含有 83个结点的完全二叉树从根结点开始编号,根为 1号,后面按从上到下、从左到右的顺序对结点编号,那么编号为 41的结点的双亲结点编号为( )(分数:2.0
3、0)A.42B.40C.21D.207.带头结点的单链表 Head为空的判定条件是( )(分数:2.00)A.Head=NULL;B.Head.next=NULL;C.Head.nextHead;D.Head.next=Head8.堆是一个键值序列(k 1,k 2,k,k 1,k 0),对 i=1,2,n/2,满足( )(分数:2.00)A.kik 2ik 2i+1B.kik 2ik 2i+1C.kik 2i且 kk 2i+1(2i+1D.kik 2i或 kik 2i+l(2i+19.链栈与顺序栈相比,有一个比较明显的优点即( )(分数:2.00)A.插入操作更加方便B.通常不会出现栈满的情况
4、C.不会出现栈空的情况D.删除操作更加方便10.判断一个有向图是否存在回路,除了可以利用拓扑排序方法,还可以利用( )(分数:2.00)A.求关键路径的方法B.求最短路径的 Dijkstra方法C.广度优先遍历方法D.深度优先遍历方法11.如果 T2是由有序树 T转换而来的二叉树,那么 T中结点的后序就是 T2中结点的( )(分数:2.00)A.前序B.中序C.后序D.层次序12.假设有一个数组,它的行号从 0到 8,列号从 0到 10,数组中每个元素所占的存储空间为 3个单元,则现在将此数组从某一个地址开始连续存放在一个存储器中,试问至少需要( )个存储单元才能完全将此数组存放进去。(分数:
5、2.00)A.240B.297C.270D.30013.串是任意有限个( )(分数:2.00)A.符号构成的集合B.符号构成的序列C.字符构成的集合D.字符构成的序列14.已知某二叉树的后序遍历序列是 dabec,中序遍历序列是 debac,则它的前序遍历序列是 ( )(分数:2.00)A.a c b e dB.d e c a bC.d e a b cD.c e d b a15.堆排序的最坏时间复杂度为( )(分数:2.00)A.O(B.O(10g2C.O(nlog2D.O(n2)二、B填空题/B(总题数:10,分数:20.00)16.设线性表(a 1,a 2,a 500)元素的值由小到大排列
6、。对一个给定的 k值,用二分法检索查找表中与 k相等的元素,在检索不成功的情况下,至多需比较 1 次。(分数:2.00)填空项 1:_17. 1与数据元素本身的内容和形式无关。(分数:2.00)填空项 1:_18.已知无向图 G的结点数为 n,边数为 e,其邻接表表示中的表结点数与表头结点数之和为 1。(分数:2.00)填空项 1:_19.对带有头结点的链队列 lq,判定队列中具有一个数据元素的条件是 1。(分数:2.00)填空项 1:_20.判断一个没有头结点的单链表 head为空的条件是 1。(分数:2.00)填空项 1:_21.就文件而言,按用户的观点所确定的基本存储单元称为_。按外设的
7、观点所确定的基本存储单元称为_。(分数:2.00)填空项 1:_22.对于一个具有 n条边和 e个顶点的图来说,如果采用邻接表表示,则其空间复杂度为_,若采用邻接矩阵表示,则其空间复杂度为_。(分数:2.00)填空项 1:_23.设有一元多项式 A(x)=7+3x+10x30-4X100+13x101,用单链表给出 A(x)的存储表示为 1。(分数:2.00)填空项 1:_24.在顺序表中,插入或者删除一个元素,需要平均移动_个元素,具体移动的元素个数与_有关。(分数:2.00)填空项 1:_25.一棵树中非叶子结点的个数为 n,与树对应的二叉树中右子树为空的结点的个数为 m,则 m= 1。(
8、分数:2.00)填空项 1:_三、B解答题/B(总题数:4,分数:20.00)26.已知有一关键字序列为(372,81,437,96,205,732,821,634,572,495,264),如果采用归并排序方法对此序列进行升序排列,请给出每一趟的排序结果。(分数:5.00)_27.假设一棵具有 12个结点的二叉树的存储结构如下图所示,其中 left和 right分别表示此结点左、右孩子的序号,data 表示此结点的数据,根结点为编号为 4的结点。请根据此存储结构画出对应的二叉树,然后回答下面的问题: (分数:5.00)_28.在一棵二叉树中,度为 O的结点个数与度为 2的结点个数和度数之间有
9、什么关系?在一棵完全二叉树中,如果共有 200个结点,则能判断出叶结点的个数吗?如果能,请指出会有多少个叶结点,多少个度为 2的结点?多少个度为 1的结点?如果有 201个结点呢?(分数:5.00)_29.已知有如右图所示的一棵树,请将其转化成二叉树。 (分数:5.00)_四、B算法阅读题/B(总题数:4,分数:20.00)30.以下为单链表按序号查找的运算,分析算法,请在_处填上正确的语句。 pointer find_lklist(1klist head,int i) p=head;j=0; while(_) p=pnext;j+; if(i=j)return(p); else return
10、(NULL); (分数:5.00)填空项 1:_31.以下算法实现若开散列表 HP中存在键值为 K的结点,则将其删除。请分析程序,并在_上填充合适的语句。 void delete_openhash(keytype K,openhash HP) i=H(K); if(HPi=NULL)return; /*空表则退出*/ p=HVi; if(pkey=K)_=pnext;free(p);return;) /*表首结点为待删除结点时的删除*/ while(pnext!=NULL) /*其他情况下的删除*/ q=p;p=pnext; if(pkey=K)_=pnext;delete(p);return
11、;) (分数:5.00)填空项 1:_32.以下运算实现在循环队上的出队列,请在_处用适当的语句予以填充。 int OutCycQueue(CycqueueTp*sq,DataType*x) if(sqfront=_)error(“队空“);return(0);) else_; _; return(1); (分数:5.00)填空项 1:_33.以下为求单链表表长的运算,分析算法,请在_处填上正确的语句。 int length_lklist(lklist head) /*求表的长度。 */ _; j=0; while(pnext!=NULL) _; j+; return(j); /*回传表长*/
12、(分数:5.00)填空项 1:_五、B算法设计题/B(总题数:1,分数:10.00)34.有两个磁盘文件 A、B,各存放一行字母,要求把这两个文件中的信息按字母顺序排列合并,输出到一个新文件 C中。(分数:10.00)_数据结构-9 答案解析(总分:100.00,做题时间:90 分钟)一、B单项选择题/B(总题数:15,分数:30.00)1.如果待排序的记录的规模很大,则在下面的排序方式中,我们最好不要选择使用 ( )(分数:2.00)A.快速排序B.直接插入排序 C.堆排序D.归并排序解析:2.设数组 A0,m作为循环队列 sq的存储空间,front 为队头指针,rear 为队尾指针,则执行
13、入队操作的语句是( )(分数:2.00)A.sfront=(sfront+1)%mB.sfront=(sfront+1)%(m+1)C.srear=(srear+1)%mD.srear=(srear+1)%(m+1) 解析:3.线性表若采用链表存储结构时,要求内存中可用存储单元的地址( )(分数:2.00)A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以 解析:4.串是一种特殊的线性表,其特殊性体现在( )(分数:2.00)A.可以顺序存储B.数据元素是一个字符 C.可以链接存储D.数据元素可以是多个字符解析:5.对广义表(a),(b)进行下面的操作 head(h
14、ead(a),(b)后的结果是( )(分数:2.00)A.a B.(C.( )D.不确定解析:6.将含有 83个结点的完全二叉树从根结点开始编号,根为 1号,后面按从上到下、从左到右的顺序对结点编号,那么编号为 41的结点的双亲结点编号为( )(分数:2.00)A.42B.40C.21D.20 解析:7.带头结点的单链表 Head为空的判定条件是( )(分数:2.00)A.Head=NULL;B.Head.next=NULL; C.Head.nextHead;D.Head.next=Head解析:8.堆是一个键值序列(k 1,k 2,k,k 1,k 0),对 i=1,2,n/2,满足( )(分
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
5000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 学历 职业资格 数据结构 答案 解析 DOC
