算法与数据结构(c语言) 2006数据结构期中试卷参考答案.pdf

《算法与数据结构(c语言) 2006数据结构期中试卷参考答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、山东师范大学2007-2008学年第二学期期中考试试题　　　　　　　　　　　　（时间：120分钟共100分）课程编号：4082203课程名称：数据结构与算法适用年级：2006学制:四适用专业：信息与计算科学试题类别：A(A/B/C)题号一二三四五六总分阅卷人复核人得分一、得分阅卷人单项选择题：下面每题的选项中，只有一个是正确的，请将答案填在题后的括号内。（本题共10小题，每小题1分，共10分）1．研究数据结构就是研究___D______。A数据的逻辑结构B数据的存储结构C数据的逻辑和存储结构D数据逻辑结构、存储结构及

2、其数据在运算上的实现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-+*ab

3、cd6．将一棵有100个结点的完全二叉树从根为一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左子结点编号为_A_____A.98B.99C.50D.487．设计一个判别表达式中左、右括号是否配对出现的算法，采用__D_____数据结构最佳。A线性表的顺序存储结构B队列C线性表的链式存储结构D栈8．判断带头结点的单链表llist为空的条件是___C_______Allist->link==llistBllist==NULLCllist->link==NULLDllist!=NULL　

4、　9．在以下时间复杂度的数量级中，数量级最大的是_D_____　　A.B.C.D.10.在一非空二叉树的中根周游序列中，根结点的右边___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个叶子结点，则该二叉树的总结点数至少是____9

5、9_______。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、向一个顺序栈插入一个元素时，首先使栈顶指针后移一

6、个位置，然后把待插入元素到这个位置上。9、若结点y是结点x的一棵子树的根，则x称作y的__父结点_________。10、具有n个结点的完全二叉树的深度k为__[log2n]_________。三、得分阅卷人判断题（每小题1分，共10分）　1．线性表中的每个结点最多只有一个前驱和一个后继（√）2．栈和队列逻辑都是线性表（√）3．广义表的元素可以是广义表（√）4．在顺序表中取出第i个元素所花费的时间与i成正比（X）5．在带头结点的单循环链表中，任一结点的后继指针均不空（√）6．如果一个串中的所有字符均在另一个串中出现，

7、则说前者是后者的子串（X）7．如果两个子串含有相同的字符，则说它们相等（X）8．在栈满情况下，不能做进栈运算，否则产生"上溢"（√）9．线性表的逻辑顺序与存储顺序总是一致的（X）10．若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树（√）四、得分阅卷人简答题（每小题6分，共30分）1、编号为1，2，3，4的四辆列车，顺序开进一个栈式结构的站台，请写出开出车站的所有顺序。12341243132413421432213421432314234124313214324134214321　　2、一棵二叉树如图所示：

8、写出对此树的先根、中根和后根序列。先根序列: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数组i0123456pibabbabak001123