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

苏州大学 数据结构 课程期中考试（共6页） 学院 计算机 专业 信息管理与信息系统 成绩____________________ 班级 10信管 学号_____________姓名______________日期 2011.11 一、填空题(每2分，共分) 1. 、 。 2. 数据结构的常见存储结构有顺序结构和 ；选择不同存储方案的主要依据是： 。 3.用大”O”记号表示下面程序段的时间复杂度 。 while (i=m) i=i*2; 4. 对一个长度为n的无序线性表中的元素进行顺序查找，假设查找每个元素的概率相同，则在此线性表下的顺序查找的平均比较次数为 。．在一个长度为n的顺序表中第i(=i=n)个插入一个新元素时，需向后移动的元素个数为 。 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 。 。假设有个元素abcde依次进栈（进栈过程中可以出栈），出栈序列为dce 。 。 ,在出队算法中需要判断 。 11.设在循环队列中用front和rear分别指示队头位置和队尾位置，为队列分配的空间个数为maxqsize，若用损失一个空间的方法来区分队空和队满，则当 时表示队空，当 时表示队满。.在线性表和数组这两个概念中， 是一个逻辑概念。 .给定两个有序顺序表A和B，设A表的长度为m，B表的长度为n，将两个有序表合并成有序表C，最坏情况下需进行 次比较。二、应用题(共分) .试说明顺序表和链表的优缺点和适用场合。 3.在一个双向(非循环)链表中，设双向链表结点包含:data域存放数据，prior域指向前驱结点，next域指向后继结点。若要求在p所指结点前面插入一个值为item的结点，请写出对应的语句序列。(8分) 4.在关键字序列依次为（7，12，15，18，27，32，41，92）的顺序线性表下进行二分查找（采用查找过程中比较相等的二分查找算法）。(12分) （1）简述查找target=41时的查找过程。 （2）画出对8个元素进行二分查找的比较树，并计算出成功查找时的平均比较次数。 （3）用大O记号来表示二分查找的时间效率。 三、算法设计题*10分） 1. a reference to the head node of a linked list as follows: Figure 1 A linked list Write a method to quickly locate the middle element of the list, your method should return a reference to the middle node, make sure that your method have time complexity of O(n) when n represents the number of nodes. Note: if the list has 5 elements which are (1,2,3,4,5),thus the middle element is 3; and if the list is (1,2,3,4),the middle element is 2; You should start from the following declaration: T NodeT middle_point (NodeT head) 2.设stack类定义如下， class Stack T { Stack() ; void push(T item) ; T pop() ; int size(); boolean isEmpty() ; void clear() ; } 使用以栈的方法bottom()。