西南财经大学电子商务学院

西南财经大学天府学院试卷(B卷)考试科目：数据构造

_本年级

层次

教课班

：

学号：记试题号一二三分考分表阅卷人注意：1、本次考试为A卷考试，考试时间120分钟。2、请将答案挨次写在专用答题纸上。3、全卷共一部分，满分为100分。

四

五

六

总分一、单项选择题（共15题，每题2分，合计30分）1、在数据构造学科中，伪代码是（）、描绘算法且简单理解的一种语言、能够方便描绘算法中的分支与循环等构造化语句、以上都正确2、若进栈序列为1、2、3、4，进栈过程中能够出栈，则以下不行能的出栈序列是（）A、1、4、3、2B、2、3、4、1C、3、1、4、2D、3、4、2、13、设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;B、O(n2)D、O(n3)A、O(1)C、O(n)4、假设一个链表行列的队首和队尾指针分别用front和rear表示，每个结点的构造为：datanext当出队时所进行的指针操作为（）A、front=front–>nextB、rear=rear–>nextC、front–>next=rear;rear=rear–>nextD、front=front–>next;front–>next=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}，若采纳折半查找，则查找元素26的比较次数为（）。A、2B、3C、4D、57、对一组数据（86，48，26，15，23）排序，数据的摆列序次在排序过程中的变化为：8648261523154826862315232686481523264886这个排序过程采纳的排序方法是（）。A、冒泡B、选择C、迅速8、若依据查找表（23，44，36，48，52，73，64，58）成立哈希表，采纳址，则哈希地点等于3的元素个数为（）。A、1B、2C、3

D、插入h(K)=K%7D、4

计算哈希地9、若一个元素序列基本有序，则采纳（）方法较快。A、直接插入排序B、简单项选择择排序C、堆排序D、迅速排序10、在一个长度为n的次序表中向第i个元素(0<i<n+1)以前插入一个新元素时，需要向后挪动（个元素。A、n-iB、n-i+1C、n-i-1D、i

）11、下边对于线性表的说确的是

(

).、每个元素都有一个直接前趋和一个直接后继、线性表中起码要有一个元素、除第一个和最后一个元素外，其他每个元素都有一个且仅有一个直接前趋和直接后继12、在数据构造中，从逻辑上能够把数据构造分为（）。A．动向构造和静态构造B.紧凑构造和非紧凑构造C.线性构造和非线性构造D.部构造和外面构造13、已知函数SubString(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数SCopy(s,t)的功能为复制串t到s。若字符串S=”SCIENCESTUDY”，则调用函数SCopy(P,Sub(S,1,7))后获得（）。A、P=”SCIENCE”B、P=”STUDY”C、S=”SCIENCE”D、S=”STUDY”14、若将一个10×10阶的对称矩阵压缩储存到一个一维数组中，则该一维数组的大小应当是（）。A、55B、56C、45D、4615、线索二叉树中，结点p没有左子数的充要条件是（）。A、p->lc=NULLB、p->ltag=1C、p->lc=NULL且p->ltag=1D、以上都不对二、是非题（以下表达正确的写上T，不然，写上F。共10题，每题1分，合计10分）1、在有向图G中，<V2,V1>和<V1,V2>是两条不一样的边。（）2、线性表中的每个结点最多只有一个前驱和一个后继。（）3、线性表简称为“次序表”。（）4、线性的数据构造能够次序储存，也能够链式储存。非线性的数据构造只好连结储存。（）5、从单链表的任一结点出发，都能接见到全部结点。（）6、在有序的次序表和有序的链表上，均可使用折半查找来提升查找效率。（）7、假如某种排序方法是不稳固的，那么该排序方法不拥有适用价值。（）8、满二叉树必定是完整二叉树。（）9、若二叉树的中序遍历序列与后序遍历序列同样，则该二叉树必定是任何结点都没有右子树。10、数据构造观点包含数据之间的逻辑构造、数据在计算机中的储存方式和数据的运算三个方面。

（

）（）三、填空题（共10空，每空1分，合计10分）1、行列和货仓最大的同样点在于，它们都同属于【1】;行列和栈最大的不一样点在于，行列元素的删除和插入按照【2】规则；而栈元素的删除和插入按照后进先出（LIFO）规则。2、假如常常对线性表进行插入和删除运算，则最好采纳【3】储存构造。3、已知二维数组A[5][3]，其每个元素占2个储存单元，而且A[0][0]的储存地点为1000。则元素A[3][2]的储存地点为【4】。4、假设一个次序循环行列的储存空间长度为QueueSize，队首和队尾指针分别用front和假如采纳少用一个储存空间的方式来划分循环行列是队空仍是队满，则判断队空的条件是判断队满的条件是【6】。5、数据构造按结点间的关系，可分为4中逻辑构造，它们分别是【7】、【8】【9】和【10】。

rear表示，【5】；、四、算法填空题（每空2分，共20分）1、已知二叉树中的结点种类BinTreeNode

定义为：structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;};此中data为结点值域，left和right分别为指向左、右儿女结点的指针域。下边函数的功能是返回二叉树BT中值为X的结点所在的层号，请在画有横线的地方填写适合容。intNodeLevel(BinTreeNode*BT,ElemTypeX){intc1,c2;if(BT==NULL)return0;elseif(BT->data==X)

return1;

/*空树的层号为/*根结点的层号为

0*/

1*/else{c1=NodeLevel(BT->left,X)if(c1>=1)returnc1+1;c2=【1】;if(【2】)returnelsereturn0;

【3】;/*若树中不存在

X结点则返回

0*/}}2、以下算法片段是矩阵迅速转置算法，请在划线的地点填入适合的容。#defineARRAYSIZE1024typedefstruct{introw,col;DataTypevalue;

/*非零元素的行号和列号/*非零元素的值*/

*/}TriType;typedefstruct{triTypeitems[ARRAYSIZE+1];introws,cols;intnums;

/*非零元三元组，item[0]未用*//*稀少矩阵的行数、列数*//*稀少矩阵的非零元素个数*/}TriArray;FastTransMatrix(TriArrayTA,TriArrayTB){/*TA

为转置前的三元组属性表，

TB

为转置后的三元组次序表

*/inti,j=0,k=0;intpos[ARRATSIZE+1],num[ARRATSIZE+1];if(TA.nums){for(i=1;i<=TA.cols;i++)

num[i]=0;for(i=1;i<=TA.nums;i++)

/*求

TA

中每一列非零元个数

*/【4】

;pos[1]=1;for(i=2;i<=TA.cols;i++)

/*计算第

i列第一个非零元的地点【5】

;for(i=1;i<=TA.nums;i++){j=TA.items[i].col;k=pos[j];TB.items[k].row=TA.items[i].col;TB.items[k].col=TA.item[i].row;TB.items[k].value=TA.items[i].value;【6】;}}TB.rows=TA.cols;TB.cols=TA.rows;}2、以下算法片段预实现的功能是：对有序表ST进行折半查找，成功时返回记录在表中的地点，失败时返回0。请在划线的地点填入适合的容。typedefstruct{keytypekey;}ElemType；typedefstruct{ElemType*elem;intlength;

/*数据元素储存空间基址，/*表长度*/

建表时按实质长度分派，

0号空间留空

*/}SSTable;intSearch_Bin(SSTableST,keytypekey){/*在表R中查找重点字k*/intlow=1,high=ST.length;while(【7】){mid=(low+high)/2;if(key=ST.elem[mid].key)returnelseif(key>ST.elem[mid].key)else【10】;

【8】【9】

;

;

/*找到待查元素*//*持续在前一半查找/*持续在后一半查找

*/*/}return0;

/*次序表中不存在待查元素

*/}五、算法应用题（共

15分）1、模式般配的KMP算法应用设目标为s=”abcaabbabcabaacbacba”，模式p=”abcabaa”。(1)计算模式p的next[j]函数值。（3分）(2)不写出KMP算法，只画出采纳next[j]函数进行模式般配时每一趟的般配过程。（2分）2、若一棵二叉树后序遍历为DHEBFIGCA，中序遍历序列为D