14. 下面程序段的时间复杂度是 O(mn) 。
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
a[i][j]=0;
。
43. 数据结构的三个方面：数据的 逻辑结构、物理结构、 运算。
====================线性表 栈 队列===========================
线性表
一
6．若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中数据元素的个数是（n-i）。
22. 线性表的长度是指（表中的元素个数）。
26. 若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应该是（ C. 1≤i≤n）。
28. 若某线性表中最常用的操作是取第i个元素和删除最后一个元素，则采用什么存储方式最节省时间（顺序表）。
40. 带头结点的单链表head为空的判断条件是(head->next==NULL)。
43．在一个单链表中，若删除(*p)结点的后继结点，则执行(p->next=p->next->next)。
字符串是什么数据结构49. 若频繁地对线性表进行插入和删除操作，该线性表应该采用的存储结构是（链式）。
53．若要在O(1) 的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向(各自的尾结点 )。
77. 若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，需要移动表中元素的个数是（n-i+1）。
95. 若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向( 各自的尾结点)。
102. 将长度为m的单链表连接在长度为n的单链表之后的算法的时间复杂度为( O(n) )。
107. 单链表中，增加头结点的目的是为了（方便运算的实现）。
121. 在顺序表（n足够大）中进行顺序查，其查不成功的平均长度是（n+1 ）。
2222222222222222222222222222222222222
二
4. 在 循环 链表中，从任何一结点出发都能访问到表中的所有结点。
44. 每个结点只有 一个 链接域的链表叫做单链表。
33333333333333333333333333333333333333333333333333
三
11．线性表有两种存储结构：一是顺序表，二是链表。试问：如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？
答：选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O（1）。
12．试述顺序存储和链式存储的区别及各自的优缺点。
答：数组占用连续的内存空间，链表不要求结点的空间连续。
1）插入与删除操作：由于数组在插入与删除数据时需移动大量的数据元素，而链表只需要改变一些指针的链接，因此，链表比数组易于实现数据的插入和删除操作。
2）内存空间的占用情况：因链表多了一个指针域，故较浪费空间，因此，在空间占用方面，数组优于链表。
3）数据的存取操作：访问链表中的结点必须从表头开始，是顺序的存取方式，而数组元素
的访问是通过数组下标来实现的，是随机存取方式，因此，在数据存取方面，数组优于链表。
数据的合并与分离：链表优于数组，因为只需要改变指针的指向
44444444444444444444444444444444444444444444444444444444
四
1.写出计算单链表head（head为单链表的表头）中数据域data值为m的结点个数的算法。
int count (Node *head)
//计算单链表head中数据域data值为m的结点个数
{ Node *p=head->next;
int n=0;
while (p!=NULL)
{if (p->data==m)
n++；
p=p->next;
}
return n;
}// count
2.已知非空单链表head，试设计一个算法，交换p所指结点与其后继结点在链表中的位置。
解答：
int revers(listnode *head, listnode *p)
/*交换p所指结点与其后继结点在链表中的位置*/
{ if (p->next==NULL) return 0 ;
listnode *q=head;
while (q->next!=p) q=q->next;
{r=p->next；q->next=r;
p->next =r->next ; r->next=p;
return 1;
}// revers
3.线性表用带头结点的单向链表示，试写出删除表中所有data域为零的元素的算法。
解答：
解：int DeleteItem(Node * head)
{ Node *p=head;
//声明指针p，并令其指向链表头结点
while (p->next!=NULL)
{if(p->nex->data==0)
p->next=p->next->next.
else p=p->next; //指针下移
}
}
4．试设计一算法，计算带头结点的单链表head(head指向表头)的结点个数。
解答：
int Length( )
//计算带表头结点的单链表head的长度
{Node *p=head->next;
int count=0;
while (p!=NULL)
{p=p->next; count ++;}
return count;
}
5．判断单链表head(head指向表头) 是否是递增的。
解答：【编者注： 链表无头结点】
int order(Node *head)
{Node *p=head;
while(p->next!=NULL)
if(p->data<p->next->data)
p=p->next;
else
break;
if(p->next==NULL)
return 1;
else
return 0;
}
6. 设计一个算法，在一个单链表head中出值最小的元素。
解答：【编者注： 链表无头结点】
int Min(Node * head )
//在单链表head中出值最小的元素
{ Node *p=head;
int min=p->data;
while (p->next!=NULL)
{ if(p->next->data<min) min=p->next->data;
p=p->next;
}
return min;
}
7设有两个单链表L和L1,其结点结构为(data,next),试编写算法判断链表L1中的各元素是否都是单链表L中的元素。
解答：
int SubLnk(Node *L, Node *L1)
{Node *p1=L1;
while(p1!=NULL)
{Node *p=L;
while((p!=NULL)&&(p1->data!=p->data))
p=p->next;
if (p==NULL) return 0; //【编者注：L1中元素未在L中】
else p1=p1->next;
}
return 1;
}
9.设有一个正整数序列组成带头结点的单链表head，试编写算法确定在序列中比正整数x 大的数有几个。（8分）
解答：
int count（Node * head，int x）
∥在带头结点的单链表head中，确定序列中比正整数x大的数有几个
{
Node *p=head->next;
int count=0;
while (p!=NULL)
{ if (p->data>x) count ++;
p=p->next;
}
return count;
}∥算法count结束
五
33333333333333333333333333333333333333333333333333333333333333333
一
5. 对于栈操作数据的原则是（后进先出 ）。
13．对于栈操作数据的原则是（后进先出 ）
14. 设输入序列为A,B,C,D,借助一个栈不可以得到的输出序列是(D,A,B,C )。
19.因此在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是 (d ).
20. 一般情况下，将递归算法转换成等价的非递归算法应该设置（堆栈）。
25. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ cabdef）。
37. 因此在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是 (d )。
41．栈和队列的主要区别在于（插入删除运算的限定不一样）
48. 链栈和顺序栈相比，有一个较明显的优点是(通常不会出现栈满的情况)。
50. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（3 2 1 5 4）。
72.单链表表示的链式队列的队头在链表的什么位置（链头 ）。
101.链栈和顺序栈相比，有一个较明显的优点是(通常不会出现栈满的情况 )。
110. 设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为(O(n) )。
113. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是(ZXY )。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论