数据结构复习题.doc

复习题一、选择题： 1、线性表采用链式存储时，其地址 。A必须是连续的 B一定是不连续的C部分地址必须是连续的 D连续与否均可以2、设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需用修改指针的操作为 。Apnext= pnext next； Bp= pnext；Cp= pnext next； Dpnext= p；3、设有一个栈，元素的进栈次序为A、B、C、D、E，下列 是不可能的出栈序列。AA、B、C、D、E BB、C、D、E、ACE、A、B、C、D DE、D、C、B、A4、在一个具有n个单元的顺序存储循环队列中，假定front和rear分别为队首和队尾指针，则判断队列为满的条件是 。Arear%n=front B(front+1)%n=rear Crear%n -1 = front Drear%n+1=front5、串是一种特殊的线性表，其特殊性体现在 。A 可以顺序存储 B数据元素是一个字符C可以链接存储 D数据元素可以是多个字符6、广义表(a, b, c, d)的表头是 ，表尾是 。Aa B( ) C( a, b ,c, d ) D( a, b, c, d )7、一棵高为K的完全二叉树，至少有多少个结点？( ) A. 2k-1 B. 2k-1-1 C. 2k-1 D. 2k 8、若给定的关键字集合为20，15，14，18，21，36，40，10，一趟快速排序结束时，键值的排列为 。A10，15，14，18，20，36，40，21 B10，15，14，18，20，40，36，21 C10，15，14，20，18，40，36，21 D15，10，14，18，20，36，40，219、在有n个结点的二叉链表中，值为非空的链域的个数为 。An-1 B2n-1 Cn+1 D2n+110、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中 。A第i行非无穷元素之和 B第i列非无穷元素之和 C第i行非零且非无穷元素个数 D第i列非零且非无穷元素个数二、填空题： 1下面程序段的时间复杂度是 。for (i=0;in;i+) for (j=0;jnext ) Q=L; L=L-next; P=L; While ( P-next ) P=P-next; P-next=Q; Q-next=NULL;return OK; /A2简述以下算法的功能。 status algo2 (Stack S，int e) Stack T； int d；InitStack (T)；while ( !StackEmpty (S) ) Pop ( S，d)； if (d!=e) Push (T，d )； while ( !StackEmpty (T) ) Pop ( T,d)； Push ( S，d)； 六、设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。(va.length 顺序表现有元素个数，va.listsize 为顺序表容量，va.elemi为数据元素)七、直接插入排序、冒泡排序、简单选择排序、归并排序、基数排序书上例子，要自己能写出每一趟的结果。八、根据图的数组表示法或者邻接矩阵表示法，画出图的结构，且能够根据表示结构进行深度/广度遍历。九、拓扑排序，huffman树的构造，WPL计算，根据树进行编解码。十、哈希表，书上的