《数据结构教学资料》1-3章复习资料

《《数据结构教学资料》1-3章复习资料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、复习题选择题1.算法的吋间复杂度取决于(c)A)问题的规模B)待处理数据的初态C)A和B2.计算机算法指的是解决问题的步骤序列，它必须具备(B)这三个待性。A)可执行性、可移植性、可扩充性C)确定性、有穷性、稳定性3.从逻辑上可以把数据结构分为(CA)动态结构、静态结构C)线性结构、非线性结构B)可执行性、确定性、有穷性D)易读性、稳定性、安全性)两大类。B)顺序结构、链式结构D)初等结构、构造型结构4.在下面的程序段屮，对x的赋值的语句频度为(C)for(i=0;ivn;i++)for(j=0;jvn;j

2、++)x=x+l;A)0(2n)B)0(n)C)0(n2)D)O(log2n)5.下面的程序段中，n为正整数，则最后一行的语句频度在最坏情况下是(D)for(i=n-l;i>=l;i-)for(j=l;j<=i;j++)if(AU]>AU+1])A[j]与A[j+1]对换；A)0(n)B)O(nlog2n)C)0(n3)D)0(n2)1.对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择(A)最节省时间A)顺序表C)单链表B)帯头结点的双循环链表D)带尾结点的单循环链表2.若长度为n的线性表

3、采用顺序存储结构，在其第i(lWiWn+l)个位置插入一个新元素的算法时间复杂度为(C)。A)0(0)B)0(1)C)0(n)D)0(n2)3.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的吋间复杂度是(C)A)4.A)C)5.A)B)C)D)6.A)C)O(nlog2n)B)0(1)线性表采用链式存储时，必须是连续的部分地址是连续的在双向链表存储结构中，p->prior->next=p->nextp->prior=p->prior->priorp->next->prior=pp->next

4、=p->prior->priorC)0(n)其元素地址(D)B)一定是不连续的D)连续与否均可删除P所指的结点时须修改指针(A)p・>next->prior=p->prior;p->prior->next=p;p・>next=p->next->nextp->prior=p->next->next;D)0(n2)在一个以h为头指针的单循环链屮，p指针指向链尾结点的条件是(B)p->next==NULLB)p・>next==hp->next?>next==hD)p->data==-l1.一个栈的输入序列为123

5、・・・n,若输出序列的第一个元素是n,输出第i(lWiWn)个元素是(B)A)不确定B)n-j+1C)iD)n-i1.若一个栈以向量V[l..n]存储,初始栈顶指针top为n+1,则下面x进栈的正确操作是(C)A)top=top+l;V[top]=xB)V[top]=x;top=top+lC)top=top-l;V[top]=xD)V[top]=x;top=top-l2.如果我们用数组A[1..1OO]來实现一个大小为100的栈，并且用变量top來指示栈顶，top的初值为0,表示栈空。请问在top为100时

6、，再进行入栈操作，会产生(B)A)正常动作B)溢出C)下溢D)同步填空题1•对于给定的n个元素，可以构造出的逻辑结构有,,，四种。1.数据结构中评价算法的两个重要指标是和o2.计算机执行下面的语句时，语句s的执行次数为。for(i=l;i=i;j-)s;1.线性表L=(al,a2,…，an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是o2.在单链表中设置头结点的作用是o3.线性表的顺序存储是通过来反应元素之间的逻辑关系，而链式存储结

7、构是通过來反应元素之间的逻辑关系。【答案】(n-1)/2【答案】主要是使插入和删除等操作统一，在第一个元素Z前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表头指针不变。【答案】(1)数据元素的前后顺序(2)元素中的指针4.当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则釆用存储结构最节省时间，相反当经常进行插入和删除操作时，则采用存储结构最节省时间。5.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为，在给定值为x的结点后插入一个新结点的吋间

8、复杂度为o【答案】(1)顺序(2)链式【答案】(1)0(1)(2)0(n)6.某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100,则下标为11的(第12个)元素的存储地址为o7.循环单链表的最大优点是o【答案】144【答案】从任一结点出发都可访问到链表中每一个元素。1.栈是的线性表，其运算遵循的原则。2.当两个栈共享一存储区时，栈利用一维数组stack[l..n]表示,两栈顶指针为top⑴与top