数据结构c语言版试题大全（含答案）

q->prior=p;p->next=q;p->next->prior=q;q->next=p->next;|q->next=p->next;p->next->prior=q;p->next=q;q->prior=p;|p->next=q;q->prior=p;q->next=p->next;p->next->prior=q;|p->next->prior=q;q->next=p->next;q->prior=p;p->next=q; B 36、

p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;|q->prior=p->prior;p->prior->next=q;q->next=p;p->prior=q->next;|q->next=p;p->next=q;q->prior->next=q;q->next=p;|p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q; D 37、

p->prior->nexxt=p->next;p->next->prior=p->prior;|p->prior=p->prior->prior;p->prior->prior=p;|p->next->prior=p;p->next=p->next->next;|p->next=p->prior->prior;p->prior=p->rprior->prior A

38、

p->next=p->next->next;p->next->next->prior=p;|p->next->prior=p;p->next=p->next->next;|p->next=p->next->next;p->next->prior=p;|p->next->next=p->next;p->next->pror=p; C

39、p->next==NULL|p==NULL|p->next==L|p==L C 40、L->==NULL|L->next->prior==NULL|L->prior==NULL|L->next==L D 41、单链表|给出表头指针的循环单链表|双链表|带头结点的循环双链表 D 42、只有尾结点指针没有头结点指针的循环单链表|只有尾结点指针没有头结点指针的非循环单链表|只有头结点指针没有尾结点指针的循环双链表|既有头结点指针也有尾结点指针的循环单链表 C

43、单链表|仅有头结点的单循环链表|双链表|仅有尾结点指针的单循环链表 D

44、对于两个链表来说，删除第一个结点的操作，其时间复杂度都是O(1)|对于两个链表来说，删除最后一个结点的操作，其时间复杂度都是O(n)|循环链表要比非循环链表占用更多的内在空间|h1和h2是不同类型的变量 B

45、只有首结点指针h的不带头结点的循环单链表|只有尾结点指针r的不带头结点的循环单链表|只有尾结点指针r的带头结点h的循环单链表|只有头结点h的循环单链表 A

46、A|B|C|D D|A 47、a|b|1|0 A 48、a|b|1|0 C 49、A、B、C、D|D、C、B、A|A、C、D、B|D、A、B、C D 50、单链表|双链表|单循环链表|顺序表 D

51、可随机访问任一结点|插入删除不需要移动元素|不必事先估计存储空间|所需空间与其长度成正比 A

52、n-i|n-i+1|n-i-1|I B 53、n-1|n-i+1|n-i-1|I A 54、n|n/2|(n+1)/2|(n-1)/2 C 57、

p=q->next;p->next=q->next;|p=q->next;q->next=p;|p=q->next;q-next=p->next;|q->next=q->next->next;q->next=q; C

- 17 -

数据结构复习题：线性表 判断题

1、顺序存储的线性表可以随机存取。

2、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性， 因此，是属于同一数据对象。

3、在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素。 4、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 5、链表的每个结点中，都恰好包含一个指针。

6、线性表中每个元素都有一个直接前驱和直接后继。

7、线性表中所有元素的排列顺序必须由小到大或由大到小。 8、静态链表的存储空间在运算中可以改变大小。

9、静态链表既有顺序存储结构的优点，又有动态链表的优点。所以，它存取表中的第i个元素的时间与i无关。

10、静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加。 11、静态链表与动态链表的插入、删除操作类似，不需做元素的移动。 12、线性表的顺序存储结构优于链式存储结构。

15、在双链表中，可以从任一结点开始沿同一方向查找任何其他结点。

数据结构复习题答案：线性表 判断题 1、True 2、True 3、False 4、False 5、False 6、False 7、False 8、False 9、False 10、True 11、True 12、False 15、False

数据结构复习题：线性表 算法分析题

1、己知一个顺序表L,其中的元素按值非递减有序排列,设计一个算法插入一个元素x后保持该顺序表仍按递减有序排列。要求算法的空间复杂度为O(1)。

2、设计一个算法从顺序表L中删除所有值为X的元素。要求算法的空间复杂度为O(1)。

3、从顺序表L中删除重复的元素,并使剩余元素间的相应次序保持不变.要求本算法的空间复杂记度为O(1)。 4、有一个单链表(不同结点的数据域值可能相同),其头指针为head,设计一个算法计算数据域为x的结点个数。

- 18 -

5、己知线性表元素递增有序,并以带头结点的单链表作存储结构,设计一个高效算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素)。并分析所写算法的时间复杂度。 6、设计一个在带头结点的单链表中删除一个最小值结点的高效算法。

7、有一个不带头结点的单链表L(至少有1人结点),其头指针为head,设计一个算法将L逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等。

8、用单链表表示集合,设计一个算法求两个集合的差。要求不破坏原有的结点。 9、用单链表表示集合,设计一个算法求两个集合的并。要求不破坏原有的结点。

10、设计一个算法,将一个头结点指针为a的单链表A分解成两个单链表A和B,其头结点指针分别为a和b,使得A链表中含有原链表A中序号为奇数的元素,而B链表中含有原链表A中序号为倒数的元素,且保持原来的相对顺序。 11、有一个单链表,其结点的元素值以递增有序排列,设计一个算法删除该单链表中多余的元素值相同的结点。 12、己知两个存放整数的有序单链表(己按整数从小至大的顺序排序),指针L1和L2分别指向这两个单链表的头结点。设计一个算法,将L1和L2合并成一个单链表,且新的链表仍按整数由小到大的顺序排列,新的单链表的结点由L1和L2的结点构成。要求合并后的单链表利用原来单链表的存储空间。

13、设计一个算法,将线性表lb连接到la之后,要求其时间复杂度为O(1),占用的辅助空间尽量小。描述所用的结构。

14、设指针p指向双链表中的结点X,指针f指向将要插入的新结点Y,Y要插入在结点X之后,写出指针需要修改的有关步骤。

15、有一个循环双链表,每个结点由两个指针(prior和next)以及关键字(data)构成,p指向其中某一结点,设计一个算法从该循环双链表中删除p所指的结点。

16、设有一个循环双链表,其中有一结点的指针为p,设计一个算法将p与其后续结点进行交换。

19、设A和B是两个单链表(带头结点)，其表中元素递增有序。设计一个算法将A和B归并成一个按元素值递增有序的单链表C，要求辅助空晨为O(1)，并分析算法的时间复杂度。

数据结构复习题答案：线性表 算法分析题 1、答：

void insert(sqlist &L,ElemType x) {

int i=0,j;

while(i

for (j=L.Length-1;j>=i;j--) L.data[j+1]=L.data[j]; L.data[i]=x; L.Length++; }

2、void delnode(SqList &A,ElemType item ) {

int k=0,i=0;

while (i

if(A.data[i]==item)

- 19 -

k++; else

A.data[i-k]=A.data[i]; i++; }

A.length=A.length-k }

3、

4、int Listlant (Salist &L,ElemType e) {/*带有头结点*/ p=head; int n=0;

while (p!=NULL) {

if(p->next->data==x) n++; p=p-.next; }

return n; }

5、void Delnodes(LinkList *&L,ElemType mink,ElemType maxk) {

LinkList *p=head->next;

While(p!=null&&p->data

r=p;

p=p->next; }

q=p; //求值域刚好>min while(q!=null&&q->data>maxk) //求值域刚好next; r->next=q->next; while(r!=q) {

r=p->next; free(p); p=r; }

free(q); }

- 20 -