山东师范大学-数据结构与算法-期中考试试题

第1页共4页1学号姓名院（部）专业考试时间：年月日------------------------------------------------密--------------------封----------------------线-----------------------------------------------------------------山东师范大学数据结构与算法期中考试试题（时间：120分钟共100分）课程编号：4082203课程名称：数据结构与算法适用年级：2015学制:四适用专业：信息与计算科学试题类别：A(A/B/C)题号一二三四五六总分阅卷人复核人得分一、得分阅卷人单项选择题：下面每题的选项中，只有一个是正确的，请将答案填在题后的括号内。（本题共10小题，每小题1分，共10分）1．研究数据结构就是研究___D______。A数据的逻辑结构B数据的存储结构C数据的逻辑和存储结构D数据逻辑结构、存储结构及其数据在运算上的实现2．链表不具有的特点是____A____。A可随机访问任一元素B插入删除不需要移动元素C不必事先估计存储空间D所需空间与线性表长度成正比3．设一个栈的输入序列为1，2，3，4，则借助一个栈所得到的输出序列不可能是__C___。A1，2，3，4B2，4，3，1C3，1，4，2D3，2，4，14．队列的操作原则是__A______。A先进先出B后进先出C只能进行插入D只能进行删除5．表达式a*(b+c)-d的后缀表达式是__B_____。Aabcd*+-Babc+*d-Cabc*+d-D-+*abcd6．将一棵有100个结点的完全二叉树从根为一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左子结点编号为_A_____A.98B.99C.50D.487．设计一个判别表达式中左、右括号是否配对出现的算法，采用__D_____数据结构最佳。A线性表的顺序存储结构B队列C线性表的链式存储结构D栈8．判断带头结点的单链表llist为空的条件是___C_______Allist-link==llistBllist==NULLCllist-link==NULLDllist!=NULL9．在以下时间复杂度的数量级中，数量级最大的是_D_____A.n2logB.2nC.n2D.!n10.在一非空二叉树的中根周游序列中，根结点的右边___A_______。A）只有右子树上的所有结点B）只有右子树上的部分结点C）只有左子树上的部分结点D）只有左子树上所有结点二、得分阅卷人填空题（每小题2分，共20分）1、下列程序段的时间复杂性是____O(m*n)_______。for(i=1;i=n;i++)for(j=1;j=m;j++)A[i][j]=0;2、已知二叉树有50个叶子结点，则该二叉树的总结点数至少是____99_______。3、在一个长度为n的线性表的第i个元素（1≦i≦n）之前插入一个元素时，需向后移动_n-i+1_______个元素。4、一个串中包括的字符个数称作这个串的___长度_______。5、后缀表达式6124+*3-的值为___93_____。6、若某线性表采用顺序存储结构，每个元素占2个存储单元，首地址为是100，则第5个元素的地址是__108______7、在一棵二叉树中，度为零的结点的个数为n0,度为2的结点个数为n2，则有n0=__n2+1___8、向一个顺序栈插入一个元素时，首先使栈顶指针后移一个位置，然后把待插入元素到这个位置上。9、若结点y是结点x的一棵子树的根，则x称作y的__父结点_________。10、具有n个结点的完全二叉树的深度k为__[log2n]_________。第2页共4页2学号姓名院（部）专业考试时间：年月日------------------------------------------------密--------------------封----------------------线-----------------------------------------------------------------学号姓名院（部）专业考试时间：2007年月日------------------------------------------------密--------------------封----------------------线-----------------------------------------------------------------三、得分阅卷人判断题（每小题1分，共10分）1．线性表中的每个结点最多只有一个前驱和一个后继（√）2．栈和队列逻辑都是线性表（√）3．广义表的元素可以是广义表（√）4．在顺序表中取出第i个元素所花费的时间与i成正比（X）5．在带头结点的单循环链表中，任一结点的后继指针均不空（√）6．如果一个串中的所有字符均在另一个串中出现，则说前者是后者的子串（X）7．如果两个子串含有相同的字符，则说它们相等（X）8．在栈满情况下，不能做进栈运算，否则产生“上溢”（√）9．线性表的逻辑顺序与存储顺序总是一致的（X）10．若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树（√）四、得分阅卷人简答题（每小题6分，共30分）1、编号为1，2，3，4的四辆列车，顺序开进一个栈式结构的站台，请写出开出车站的所有顺序。123412431324134214322134214323142341243132143241342143212、一棵二叉树如图所示：写出对此树的先根、中根和后根序列。先根序列:ABDEFC中根序列:DEFBAC后根序列:FEDBCA3、判断下列序列是否为堆，（1）23、12、15、11（2）23、12、15、13、11（3）23、13、15、12、11(1)(3)是堆，（2）不是堆4、写出字符串“babbaba”的next数组i0123456pibabbabak001123pi=pj≠=≠==≠Next[i]-10-110-135、以{5、6、7、8、9、10、15、18、22}作为叶子结点的权值构造一棵哈夫曼树，并计算出其带权路径长度。ABC第3页共4页3100415919263311152291065871815WPL=22*2+(9+10+15+18)*3+(5+6+7+8)*4=304五、得分阅卷人程序填空题（每空2分，共12分）1.无回溯的模式匹配算法intpMatch(PSeqStringt,PSeqStringp,int*next){inti=0,j=0;while(ip-n&&jt-n)if(i==-1||p-c[i]==t-c[j]){j++;__i++_______________;}elsei=_next[i]_______________;if(i=p-n)return(j-p-n+1);elsereturn(0);}2.链接表示的进栈算法strucNode;typedefstructNode*PNode;structNode{DataTypeinfo;PNodelink;}structLinkStack{PNodetop;};typedefstructLinkStack*PLinkStack;voidpush_link(PlinkStackplstack,DataTypex)/*在栈中压入一元素x*/{PNodep;p=(Pnode)malloc(sizeof(structNode));if(p==NULL)printf(“Outofspace!\n”);else{___p-info___________=x;p-link=__plstack-top_____;plstack-top=p;}}3.按中根次序周游二叉树的递归算法voidinOrder(BinTreet){if(t==NULL)__return___________;inOrder(leftChild(t);visit(root(t));_inOrder(rightChild(t)______;}六、得分阅卷人算法设计题（每小题9分，共18分）1、设有一线性表e=(e1,e2,...,en-1,en),其逆线性表定义为e’=(en,en-1,...e2,e1),请设计一个算法，将线性表置逆，要求逆线性表仍占用原线性表的空间，顺序表存储方式。voidReverseList(SeqList*L){DataTypetemp;inti,j;第4页共4页4学号姓名院（部）专业考试时间：年月日------------------------------------------------密--------------------封----------------------线-----------------------------------------------------------------for(i=0,j=L-n-1;ij;i++,j--){temp=L-element[i];L-element[i]=L-element[j];L-element[j]=temp;}}2.请设计一个算法，求出循环表中结点的个数。intCountnode(ClinkListclist){intn;PNodep;p=clist-link;n=0;while(p!=clist){n++;p=p-link;}return(++n);}