《(电子商务)西南财经大学电子商务学院_》由会员分享,可在线阅读,更多相关《(电子商务)西南财经大学电子商务学院_(6页珍藏版)》请在金锄头文库上搜索。
1、(电子商务)西南财经大学电子商务学院西南财经大学天府学院试卷(B卷)考试科目:数据结构_本年级层次教学班姓名:学号:记分表试题号壹二三四五六总分考分阅卷人注意:1、本次考试为A卷考试,考试时间120分钟。2、请将答案依次写在专用答题纸 上。3、全卷共壹部分,满分为100分。壹、单项选择题(共15题,每题2分,共计30分)1、在数据结构学科中,伪代码是()A、描述算法且容易理解的壹种语言B、能够方便描述算法中的分支和循环等结构化语句C、不能直接编译或解释执行D、之上都正确2、若进栈序列为1、2、3、4,进栈过程中能够出栈,则以下不可能的出栈序列是()A、1、4、3、2B、2、3、4、1C、3、1
2、、4、2D、3、4、2、13、设语句x+的时间是单位时间,则以下语句的时间复杂度为()。for(i=1;i=n;i+)for(j=1;jnextB、rear=rearnextC、frontnext=rear;rear=rearnextD、front=frontnext;frontnext=rear5、向壹个栈顶指针为hs的链栈中插入壹个s结点时,应执行()。A、hs-next=s;B、s-next=hs;hs=s;C、s-next=hs-next;hs-next=s;D、s-next=hs;hs=hs-next;6、对于顺序存储的有序表5,12,20,26,37,42,46,50,64,若采用
3、折半查找,则查找元素26的比较次数为()。A、2B、3C、4D、57、对壹组数据(86,48,26,15,23)排序,数据的排列次序在排序过程中的变化为:8648261523154826862315232686481523264886这个排序过程采用的排序方法是()。A、冒泡B、选择C、快速D、插入8、若根据查找表(23,44,36,48,52,73,64,58)建立哈希表,采用h(K)=K%7计算哈希地址,则哈希地址等于3的元素个数为()。A、1B、2C、3D、49、若壹个元素序列基本有序,则选用()方法较快。A、直接插入排序B、简单选择排序C、堆排序D、快速排序10、在壹个长度为n的顺序表
4、中向第i个元素(0ilc=NULLB、p-ltag=1C、p-lc=NULL且p-ltag=1D、之上都不对二、是非题(下列叙述正确的写上T,否则,写上F。共10题,每题1分,共计10分)1、在有向图G中,和是俩条不同的边。()2、线性表中的每个结点最多只有壹个前驱和壹个后继。()3、线性表简称为“顺序表”。()4、线性的数据结构能够顺序存储,也能够链式存储。非线性的数据结构只能连接存储。()5、从单链表的任壹结点出发,都能访问到所有结点。()6、在有序的顺序表和有序的链表上,均可使用折半查找来提高查找效率。()7、如果某种排序方法是不稳定的,那么该排序方法不具有实用价值。()8、满二叉树壹定
5、是完全二叉树。()9、若二叉树的中序遍历序列和后序遍历序列相同,则该二叉树壹定是任何结点都没有右子树。()10、数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。()三、填空题(共10空,每空1分,共计10分)1、队列和堆栈最大的相同点在于,它们都同属于【1】;队列和栈最大的不同点在于,队列元素的删除和插入遵循【2】规则;而栈元素的删除和插入遵循后进先出(LIFO)规则。2、如果经常对线性表进行插入和删除运算,则最好采用【3】存储结构。3、已知二维数组A53,其每个元素占2个存储单元,且且A00的存储地址为1000。则元素A32的存储地址为【4】。4、假定壹个顺
6、序循环队列的存储空间长度为QueueSize,队首和队尾指针分别用front和rear表示,如果采用少用壹个存储空间的方式来区分循环队列是队空仍是队满,则判断队空的条件是【5】;判断队满的条件是【6】。5、数据结构按结点间的关系,可分为4中逻辑结构,它们分别是【7】、【8】、【9】和【10】。四、算法填空题(每空2分,共20分)1、已知二叉树中的结点类型BinTreeNode定义为:structBinTreeNodeElemTypedata;BinTreeNode*left,*right;其中data为结点值域,left和right分别为指向左、右子女结点的指针域。下面函数的功能是返回二叉树B
7、T中值为X的结点所在的层号,请在画有横线的地方填写合适内容。intNodeLevel(BinTreeNode*BT,ElemTypeX)intc1,c2;if(BT=NULL)return0;/*空树的层号为0*/elseif(BT-data=X)return1;/*根结点的层号为1*/elsec1=NodeLevel(BT-left,X)if(c1=1)returnc1+1;c2= 【1】 ;if( 【2】 )return 【3】 ;elsereturn0;/*若树中不存在X结点则返回0*/2、下列算法片段是矩阵快速转置算法,请在划线的位置填入适当的内容。#defineARRAYSIZE10
8、24typedefstructintrow,col;/*非零元素的行号和列号*/DataTypevalue;/*非零元素的值*/TriType;typedefstructtriTypeitemsARRAYSIZE+1;/*非零元三元组,item0未用*/introws,cols;/*稀疏矩阵的行数、列数*/intnums;/*稀疏矩阵的非零元素个数*/TriArray;FastTransMatrix(TriArrayTA,TriArrayTB)/*TA为转置前的三元组属性表,TB为转置后的三元组顺序表*/inti,j=0,k=0;intposARRATSIZE+1,numARRATSIZE+1
9、;if(TA.nums)for(i=1;i=TA.cols;i+)numi=0;for(i=1;i=TA.nums;i+)/*求TA中每壹列非零元个数*/ 【4】 ;pos1=1;for(i=2;i=TA.cols;i+)/*计算第i列第壹个非零元的位置 【5】 ;for(i=1;iST.elemmid.key) 【9】 ;/*继续在前壹半查找*/else 【10】 ;/*继续在后壹半查找*/return0;/*顺序表中不存在待查元素*/五、算法应用题(共15分)1、模式匹配的KMP算法应用设目标为s=”abcaabbabcabaacbacba”,模式p=”abcabaa”。(1)计算模式p的nextj函数值。(3分)(2)不写出KMP算法,只画出采用nextj函数进行模式匹配时每壹趟的匹配过程。(2分)2、若壹棵二叉树后序遍历为DHEBFIGCA,中序遍历序列为DBEHAFCIG。试画出这棵二叉树。(5分)3、对于给定的壹组记录的关键字23,13,17,21,30,60,58,28,30,90。试写出采用冒泡排序和快速排序方法时,每壹趟排序后的结果。(10分)六、算法设计题(共10分)设线性表存放于顺序表A中,其中有n个整型元素,且递增有序,请设计壹算法,将整型元素x插入到线性表的适当位置,以保持线性表的有序性。给出该算法的时间复杂度,且用C语言表示出线性表L和顺序表A。