数据结构与所有练习和作业 .pptVIP

* 第一章练习 1.数据结构就是研究（ ）。 A．数据的逻辑结构 B．数据的存储结构 C．数据的逻辑结构和存储结构 D．数据的逻辑结构、存储结构及其数据在运算上的实现 2.一个算法的好坏取决于该算法的（ ）和（ ）。 3.下面程序的时间复杂度为（ ）。 For(i=0;im;i++) For(j=0;jn;j++) A[i][j]=i*j; A.O(m2) B. O(n2) C. O(n*m) D.O(n+m) 4.下面程序的时间复杂度为（ ）。 i=1; while(i=n) i=i*3; 假设代码执行次数是k，则i=3k-1 因为i=n，i=3k-1=n,k=log3n+1,所以O(logn) 第二章 练习 1.线性表L=（a1，a2 ，……an，）下列说法正确的是（ ）。 A．每个元素都有一个直接前驱和一个直接后继 B．线性表中至少要有一个元素 C．表中所有元素的排列顺序必须是由小到大或由大到小 D．除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继 2.线性表采用链式存储时，其地址（ ）。 A．必须连续 B．部分地址必须连续 C．必须连续 D．连续与否均可 3．下面关于线性表叙述错误的是（ ）。 A．线性表采用顺序存储，必须占用一段地址连续的单元 B．线性表采用顺序存储，便于进行插入和删除操作 C．线性表采用链式存储，不必占用一段地址连续的单元 D．线性表采用链式存储，便于进行插入和删除操作 4．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ 　）存储方式最节省运算时间。 A．单链表　 B．双链表　 C．带头结点的双循环链表　 D．容量足够大的顺序表 第二章作业 2.22 试写一算法,对单链表实现就地逆置,即利用原表的存储空间将线性表 （a1,a2,…,an）逆置为（an,an-1,…,a1） 提示：将原链表中的头结点和第一个元素结点断开（令其指针域为空），先构成一个空表，然后将原链表中各结点从第一个结点起依次插入这个新表的头部。 2.11设顺序表Va中的数据元素递增有序（非递减有序）。试写一算法， 将x插入到顺序表的适当位置上，以保持该表的有序性。 补充作业： 写出按正位序建立一个单链表的算法。 for (i = 1; i =n; i++) { p = (LinkList) malloc (sizeof (LNode)); scanf(p-data); // 输入元素值 p-next = NULL; if (head-next == NULL) //如果链表只有头结点 { head-next = p; q = p;}else //如果头结点next不为空 { q-next = p; q = p;} } 第三章练习 1.假定一个顺序循环队列存储于长度为n的一维数组中，其队头和队尾指针分别用front和rear表示，则判断队满的条件是（） A．（rear+1）%n==front B．front+1==rear C．rear==（front-1）%n D．rear==（front+1）%n 2.假定一个顺序循环队列的队头和队尾指针分别用front和rear表示，则判队空的条件是（）。 A．front+1= =rear B．front= =rear+1 C．front= =0 D．front= =rear 练习 3.三个元素按照A,B,C的顺序入栈，下列哪一个是不合法的出栈序列？（?） ?A. ABC??????????B. CAB?????C. ACB???????????D. BAC? 4.堆栈的逻辑特点是（ ），队列的逻辑特点是（ ）。二者的共同点是只允许在它们的（ ）处插入和删除数据元素。 5. 设输入元素的顺序为1,2,3,4,5，要在栈的输出端得到43521，则应进行栈的基本运算表示应为：Push（S,1），Push(S,2)，Push(S,3)，Push(S,4)，Pop(S)，（ ），（ ），Pop(S)，Pop(S)，Pop(S)。 练习 6. 队列的插入操作是在队列的（ ）进行，删除操作是在队列的（ ）进行。 7．堆栈的逻辑特点是（ ），队列的逻辑特点是（ ）。 第三章作业 3.1 设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次