数构半期考数据结构2011-20121

1、福建师范大学学院卷数学与计算机科学20112012学年第1 学期 半期专业：年级：课程名称:数据结构任课教师：用时：试卷类别：开卷（ ）闭卷（）分钟时间:年月日午点分考生信息栏学院系专业 年级学号装订线题号一二三四五总得分评卷人得分题号六七十得分一、选择：(每题 2 分，共 20 分)1、已知二叉树的前、中根序列分别是 abdefcg和 defbagc，则该二叉树的后根遍历序列是( )。A. defbgcaB. fedbgcaC. abcdefgD. gfedcba2、数据在计算机器内表示时,物理地址与逻辑地址相同并且是连续的,称为()A.结构B.逻辑结构C.顺序D.链式结构结构3、一个栈的输

2、入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 24、在具有n 个结点的单链表中,实现( )的操作,其算法的时间复杂度是 O(n).A.遍历链表和求链表的第 i 个结点.B.在地址为p 的结点之后C.删除开始结点一个结点.D.删除地址为 p 的结点的后继结点.5、数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为A.rf;C.nrf;B.（nfr）% n;D.（nrf）% n6、判定一个栈 ST（最多元素为

3、 m0）为空的条件是()AST-top0BST-top= =0CST-topm0，将其下三角部分（DST-top= =m0）按行序存放在一维数7、设矩阵 A 是一个对称矩阵，为了节省组 B 1, n(n-1)/2 中，对下三角部分中任一元素 ai,j(ij), 在一维数组 B 中下标k 的值是：i(i-1)/2+j-1i(i+1)/2+j-1i(i-1)/2+ji(i+1)/2+j8、线性表在情况下适用于使用链式结构实现。A.需经常修改中的结点值B.需不断对进行删除D.中结点结构复杂C.中9、单链表的A.大于 1；的结点密度（B. 小于 1；）等于 1； D.不能确定C.a,1aaA 2,12

4、,2an,1an,2an,n 考生信专业 年级息栏学院系学号装订线10、设串 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)的结果串是：BCDEFBCDEFGBCPQRSTBCDEFEF二、填空题：(每空 1.5 分，共 30 分)1 、 数 据 的结 构 可 用 四 种 基 本 的方 法 表 示 , 分 别 是,索引与散列。2、在顺序表中或删除一个

5、元素，需要平均移动元素，具体移动的元素个数与有关。3、链表相对于顺序表的优点有和操作方便。4、在 n 个结点的单链表中要删除已知结点*p,需找到,其时间复杂度为.5、设循环向量有 m 个元素，循环向量中有一个循环队列，在循环队列中设队头指针 front 指向队头元素，队尾无名指是针指向队尾元素后的一个空闲元素。.在循环队列中，队空标志为队满标志为.当 rear=front 时，队列长度为；当 rearFRONT 时，队列长度是。6 、向一个长度为 n 的向量中删除第 i 个元素(1 i n) 时， 需向前移动个元素。7、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分

6、别表示该元素的、和。8、设目标 T=”abccdcdccbaa”，模式 P=“cdcc”，用朴素匹配算法时，第次匹配成功。9、子串的定位运算称为串的模式匹配；称为目标串，称为模式。10、设数组 a160, 170的址为 2000，每个元素占 2 个单元，若以列a32,58。三、解答题：(每题 5 分，共 30 分)1、写出下列算法的语句频度和时间复杂度。x=0;for(i=1;in;i+) for(j=i+1;j=2)叉树的 K 叉链表表示中，有多少个空指针。3、已知一棵二叉树的前序序列和中序序列分别为 abdghcefi 和 gdhbaecif,请画出该二叉树。4、画出下列广义表的图形表示和

7、它们的(1) D(A(c), B(e), C(a, L(b, c, d)(2) J1(J2(J1, a, J3(J1), J3(J1)表示：5、设长度为 n 的链队列用单循环链表表示，若只设头指针，则入队，出队操作的时间是什么？如果只设尾指针呢？6、利用广义表的 head 和tail 操作写出函数表达式，把以下各题中的单元素 banana 从广义表中分离出来：(1) L1(apple, pear, banana, orange)(2) L2(apple, pear), (banana, orange)(3) L3(apple), (pear), (banana), (orange) (4) L

8、4(apple), (pear), (banana), orange)(5) L5(apple), pear), banana), orange)(6) L6(apple, (pear, (banana), orange)四、算法题：(每题 10 分，共 20 分)1、 描述二叉树的二叉链表表示的结构，并给出中序遍历二叉树的算法。2、 设栈 S=(1,2,3,4,5,6,7) ，其中 7 为栈顶元素。简述函数 f31 中第一个循环语句的功能；写出调用 f31(&s)后的 s。(stack 表示栈，queue 表示队列) void f31(stack *s) queue q;stack t;initqueue(&q);i=0;initstack(&s);while(!stackempty(s)