福建师范大学试卷纸第 1 页 共 6 页福建师范大学数学与计算机科学学院 2011 — 2012 学年第 1 学期 半期考试卷考生信息栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿装订线专业：年级：课程名称 : 数据结构任课教师：试卷类别： 开卷（）闭卷（√）考试用时：分钟考试时间 : 年月日午点分题号一二三四五总得分评卷人得分题号六七八九十得分福建师范大学试卷纸第 2 页 共 6 页一、选择： (每题 2 分，共 20 分) 1、已知二叉树的前、中根序列分别是abdefcg 和 defbagc，则该二叉树的后根遍历序列是( )。A. defbgca B. fedbgca C. abcdefg D. gfedcba 2、数据在计算机存储器内表示时, 物理地址与逻辑地址相同并且是连续的, 称为 ( ) A. 存储结构B. 逻辑结构C.顺序存储结构D.链式存储结构3、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 24、在具有 n 个结点的单链表中, 实现 ( )的操作 , 其算法的时间复杂度是O(n). A. 遍历链表和求链表的第i 个结点 .B. 在地址为 p 的结点之后插入一个结点. C.删除开始结点D.删除地址为p 的结点的后继结点. 5、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为A. r －f; B. （n＋f －r ）% n; C. n＋r －f; D. （n＋r －f ）% n 6、判定一个栈ST（最多元素为m0）为空的条件是( ) A ．ST->top<>0 B ．ST->top= =0 C ．ST->top<>m0 D．ST->top= =m0 7、设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如图所示）按行序存放在一维数组 B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j), 在一维数组B 中下标 k 的值是：Ａ． i(i-1)/2+j-1 Ｂ． i(i-1)/2+j Ｃ． i(i+1)/2+j-1 Ｄ． i(i+1)/2+j nnnnaaaaaaA,2,1,2,21,21,18、线性表Ｌ在 ________________情况下适用于使用链式结构实现。A. 需经常修改Ｌ中的结点值B.需不断对Ｌ进行删除插入C.Ｌ中含有大量的结点D.Ｌ中结点结构复杂9、单链表的存储密度（）A. 大于 1； B. 小于 1；C. 等于 1； D.不能确定福建师范大学试卷纸第 3 页 共 6 页考生信息栏＿＿＿＿＿＿学院...
