09信管数据结构期中试题答案.doc

苏州大学 数据结构 课程期中考试（共6页） 学院 计算机 专业 信息管理与信息系统 成绩____________________ 班级 09信管 学号_____________姓名______________日期 2010.11 一、填空题(每2分，共分) 1. 线性 和 非线性 两类。 2.用大”O”记号表示下面程序段的时间复杂度 O(log2n) 。 while (i=m) i=i*2; 3. 对一个长度为n的无序线性表中的元素进行顺序查找，假设查找每个元素的概率相同，则在此线性表下的顺序查找的平均比较次数为 (n+1)/2 。．在一个长度为n的顺序表中第i(in)个元素，需移动的元素个数为 。 Evaluate the postfix expression: 2 4 3 1 + * - , where each number represents an operand and each symbol of + and * represents an operator,please give the result of the expression on the following line -14 。假设有个元素abcde依次进栈（进栈过程中可以出栈），出栈序列为dceba，则该栈容量必定不小于 。 空栈 。 ,在出栈算法中需要判断 队列是否为空 。 9.设在循环队列中用front和rear分别指示队头位置和队尾位置，为队列分配的空间个数为maxqsize，若用损失一个空间的方法来区分队空和队满，则当 时表示队空，当 时表示队满。 .在线性表和数组这两个概念中， 是一个逻辑概念， 数组 是一个存储实现时的概念。 .给定两个有序顺序表A和B，设A表的长度为m，B表的长度为n，将两个有序表合并成有序表C，最好情况下需进行 min(m,n) 次比较。 7 。 13.每个递归算法（的运行）都有两个阶段： 向前调用 阶段和 向后返回 阶段。一定能消除的递归是 尾递归 。 二、应用题(共分) ．public static T NodeT remove (NodeT f,T x) { if (f==null) return null; else if (f.data==x) return f.next; else{ f.next=remove (f.next,x); return f;} } 线性表L中存放若干整型元素，设其内容从前往后依次为：（0,0,1,0,2,3,5,6,0,0,7,9,1,0），L采用单向非循环链表表示，head为L中第一个结点的指针，L中结点类型为Node类型。 使用以下语句调用unknown算法： L.head=L.unknown(L.head,0); 说明unknown算法完成的功能，并写出上述语句执行之后L的内容。 答：Unknown算法的功能是在f为头结点的链表中删除第一次出现的值为x的元素。 删除后L表的内容为（0,1,0,2,3,5,6,0,0,7,9,1,0）。 3.简述循环队列中区分队空和队满的方法(至少给出3种方法)。 A circular array with front and rear indices and one position left vacant. A circular array with front and rear indices and a flag to indicate fullness (or emptiness). A circular array with front and rear indices and an integer variable counting entries. A circular array with front and rear indices taking special values to indicate emptiness. 4.在一个双向(非循环)链表中，设双向链表结点包含:data域存放数据，prior域指向前驱结点，next域指向后继结点。若要求在指针P所指结点前面插入一个值为item