当前位置：首页> 安全验证

安全验证

时间：2023-11-15 05:38:02 下载该word文档

第2部分习题解析第1章绪论
1.1选择题
1.算法的时间复杂度取决于（c）
A）问题的规模B）待处理数据的初态C）A和B2.计算机算法指的是解决问题的步骤序列，它必须具备（B）这三个特性。
A）可执行性、可移植性、可扩充性B）可执行性、确定性、有穷性C）确定性、有穷性、稳定性D）易读性、稳定性、安全性5．从逻辑上可以把数据结构分为（C）两大类。
A）动态结构、静态结构B）顺序结构、链式结构C）线性结构、非线性结构D）初等结构、构造型结构6．在下面的程序段中，对x的赋值的语句频度为（C）
for(i=0;ifor(j=0;jA）O(2nB）O(nC．O(n2D．O(log2n
7．下面的程序段中，n为正整数，则最后一行的语句频度在最坏情况下是（D）
for(i=n-1;i>=1;i--for(j=1;j<=i;j++if(A[j]>A[j+1]A[j]与A[j+1]对换；
A.O（n）B）O(nlog2nC）O(n3D）O(n21.2填空题
2.对于给定的n个元素,可以构造出的逻辑结构有集合、线性结构、树形结构、图状结构或网状结构四种。4．数据结构中评价算法的两个重要指标是：算法的时间复杂度和空间复杂度。
5.数据结构是研讨数据的__逻辑结构_和_物理结构_以及它们之间的相互关系，并对与这种结构定义相应的_操作（运算）_设计出相应的_算法_。
6．一个算法具有5个特性：有穷性_、确定性、可行性，有零个或多个输入、有一个或多个输出。9．已知如下程序段
for(i=n;i>0;i--{语句1}{x=x+1;{语句2}for(j=n;j>=i;j--{语句3}y=y+1;{语句4}}语句1执行的频度为_n+1_;语句2执行的频度为_n__；语句3执行的频度为_n(n+3/2_；语句4执行的频度为_n(n+1/2_。10．在下面的程序段中，对ｘ的赋值语句的频度为_____________（表示为n的函数）for(i=0;i>n;i++
for(j=0;j>i;j++
for(k=0;k>j;k++ｘ=ｘ+delta;【答案】1+（1+2）+（1+2+3）+…+（1+2+…+n）=n(n+1(n+2/6，O(n311.下面程序段中带下划线的语句的执行次数的数量级是_____________。i=1;while(i【答案】log2n12.计算机执行下面的语句时，语句s的执行次数为_____________。
for(i=l;ifor(j=n;j>=i;j--s;【答案】(n+3(n-2/213.下面程序段的时间复杂度为_____________。(n>1sum=1;for(i=0;sum【答案】O(n第2章线性表
2.1选择题
1．对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（A）最节省时间A）顺序表B）带头结点的双循环链表C）单链表D）带尾结点的单循环链表2．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（C）(1≤i≤n+1。A）O(0B）O(1C）O(nD）O(n23．双向链表中有两个指针域，prior和next，分别指向前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（D）A）p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;B）q->prior=p->prior;p->prior->next=q;q->next=p;p->prior=q->next;C）q->next=p;p->next=q;p->prior->next=q;q->next=p;D）p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q;4．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（C）A）O(nlog2n）B）O(1）C）O(n）D）O(n2）
5．在一个以h为头指针的单循环链中，p指针指向链尾结点的条件是（B）A）p->next==NULLB）p->next==hC）p->next->next==hD）p->data==-16．对于一个具有n个结点的线性表，建立其单链表的时间复杂度是（