数据结构与算法考试试卷

《数据结构与算法考试试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、江西财经大学－第学期期末考试试卷试卷代码：03266A授课课时：112课程名称：数据结构与算法适用对象：本科一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。)1.数据结构被形式地定义为(K,R)，其中K是数据元素的有限集，R是K上的___有限集。A.操作B.映像C.存储D.关系2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址____。A.必须连续的B.部分地址必须连续的C.一定是不续的D.连续不连续都可以3.一个栈的入栈序列是a、b、c、d、e，则栈的不可能输出序列是____。A.e

2、dcbaB.decbaC.dceabD.abcde4.一个队列的入队序列是1、2、3、4，则队列输出序列是____。A.4、3、2、1B.1、2、3、4C.1、4、3、2D.3、2、4、15.栈和队列的共同点是____。A.都是先进后出B.都是先进先出C.只允许在端点处插入、删除元素D.没有共同点6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->next=s;s->next=

3、q;7.设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con(x,y)返回x与y串的连接串，函数subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，函数len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是____。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF8.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。A.2hB.2h-1C.2h+1D.h+19.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访问顺序是

4、dgbaechf，则其后序遍历结点访问顺序是____。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca10.具有6个顶点的无向图至少应有____条边才能确保是一个连通图。A.5B.6C.7D.811.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为–。A.nB.n/2C.(n+1)/2D.(n-1)/2【第9页共9页】12.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(注：初始时为空)的一端的方法，称为____。A.希尔排序B.归并排序C.插入排序D.选择排序二、填空题(请在每小题的横线上填入正确内容，每空1分，共7分。

5、)1.在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点。2.对n个元素的序列进行起泡排序时，最少的比较次数是。3.空串是，其长度等于0。4.一棵有n个结点的满二叉树共有个叶子结点。5.在散列函数H(key)=key%p中，p应取。6.已知模式串t=‘abcaabbabc’，其用KMP法求得的每个字符对应的next函数值为。三、简答题(本大题共3小题，每小题5分，共15分)1.在对线性表的处理中一般使用两种存储结构，顺序存储结构和链式存储结构。试叙述在什么情况下使用顺序表比链表好？2.简述什么是稳定的排序，什么是不稳定的排序。3.下列中缀表达式对应的后缀形式是什么？(1)(A

6、+B)*D+E/(F+A*D)+C(2)A&&B

7、

8、!(E>F){注：按C的优先级)四、判断题(本大题共10小题，命题正确的在题后括号内写“T”，错误的在题后括号内写“F”，每小题1分，共10分)1.数据元素不是数据的最小单位()。2.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。()3.AOE网是一种带权的无环连通图。()4.对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的()。5.一棵树中的叶子数一定等于与其对应的二叉树的叶子数。()6.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。()7.折半插入排序是稳定的

9、。()8.在散列法中，使用双散列函数可保证绝对不产生冲突。()9.消除递归不一定需要使用栈()10.堆排序是交换排序的一种。()五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）1．阅读后分析下面程序段的功能是什么?（6分）SeqStackS1,S2,tmp;DataTypex;//设栈tmp和S2已做过初始化while(!StackEmpty(S1)){x=Pop(S1);Push(tmp,x);}while(!S