数据结构考研精华1800题精选：算法与复杂度详解

需积分: 50 43 浏览量更新于2024-07-31 1 收藏 1.4MB PDF 举报

《数据结构1800题》是一份针对数据结构重要知识点的精选习题集，包含了大量考研题型，旨在帮助学习者深入理解和掌握数据结构的基础理论和实践应用。文档以PDF格式提供，内容涵盖了数据结构的多个方面，如算法的复杂性分析、计算机算法的基本特性、数据结构的分类、存储结构的理解以及常见数据结构的辨识等。 1. 算法的复杂性是衡量算法性能的关键因素，它指算法在解决特定问题时所需的计算量，选项B“复杂性”是正确答案。理解算法的复杂性有助于评估不同算法在实际运行中的效率。 2. 算法的时间复杂度主要取决于问题的规模和待处理数据的初态，两者共同决定了算法执行的效率，因此C选项“问题的规模和待处理数据的初态”是正确的。 3. 计算机算法是指解决问题的步骤序列，必须具有可执行性（能够被计算机理解和执行）、确定性（每个步骤都有明确的结果）和有穷性（算法将在有限步内结束），对应于B选项。 4. 算法应该清晰地描述问题求解步骤，并满足可执行性、确定性和有穷性等基本特性，D选项是正确答案。 5. 关于算法的表述，虽然算法最终需要通过程序实现，但算法本身与程序并不完全等同；算法的可行性并不涉及指令的二义性，因此D选项是错误的。 6. 算法原地工作确实意味着不使用额外空间，但时间复杂度比较只在相同规模下有意义；时间复杂度是对最坏情况的估计，与实现语言无关，语言级别不会决定执行效率。所以，错误的说法包括(1)和(4)，即C选项。 7. 数据结构按逻辑上可分为线性结构和非线性结构，线性结构如串、数组等元素之间存在一对一的线性关系，而非线性结构如树、图则更为复杂，C选项正确。 8. 循环队列、链表和哈希表都与数据的存储结构密切相关，而栈虽然是线性结构的一种，其操作方式（后进先出）也体现了存储结构，排除A、B、C，D项是与存储结构无关的术语。 9. 在给定选项中，串是线性结构，因为它由单个字符或元素组成，且元素之间有一对一的关系，D选项正确。 10. 同样，"循环队列"、"链表"和"哈希表"都是数据结构实现的具体方式，与存储结构紧密相关，"栈"虽然也是线性结构，但这里的提问可能是要求选出与存储结构无关的抽象概念，因此答案可能是A或D，具体要看上下文。但根据前面的信息，A可能更合适，因为哈希表涉及到哈希函数的存储实现。《数据结构1800题》提供了丰富的数据结构概念和习题，适合备考的学生和自我学习者系统地提升数据结构理解与应用能力。

《数据结构 1800 题》

郴州都市网 www.0735.cc 郴州人才网 www.CZHR.com www.989.org

BEGIN

FOR i:=1 TO m-1 DO p:=p^.link;

(E)_

__; write(q^.data:8); (F)__ ;

dispose(q); j:=j+1

END

END;【复旦大学 1997 四（12 分）】

27．对于给定的线性链表 head , 下面的程序过程实现了按结点值非降次序输出链表中的所有结点，在每

次输出一个结点时，就把刚输出的结点从链表中删去。请在划线处填上适当的内容，使之成为一个完整的

程序过程，每个空框只填一个语句。

TYPE nodeptr =^ nodetype；

nodetype = RECORD

data : integer；link : nodeptr

END;

VAR head : nodeptr；

PROCEDURE sort_output_delete (head : nodeptr);

VAR p,q,r,s: nodeptr;

BEGIN WHILE head <> NIL DO

BEGIN p:= NIL ；q:= head；r:= q ；s:=q^.link ；

WHILE s <> NIL DO

BEGIN IF s^.data < q^.data THEN BEGIN (1)__

; (2)___ END ；

r:= s ； (3)___

END；

write(q^.data : 5) ；

IF p=NIL THEN (4)_

__ ELSE (5)____ ；

dispose (q) ；

END；

writeln

END；【复旦大学 1996 七（20 分） 1995 一（12 分）与本题相似】

28．下面函数的功能是在一个按访问频度不增有序的，带头结点的双向链环上检索关键值为 x 的结点，对

该结点访问频度计数，并维护该链环有序。若未找到，则插入该结点。所有结点的频度域初值在建表时都

为零。请将程序中四处空缺补写完整。

TYPE

link=^node

node=RECORD

key:char; freq:integer; pre,next:link;

END;

VAR l:link;

FUNCTION loc(l:link;x:char):link;

VAR p,q:link;

BEGIN

p:=l^.next; （1）_

；

WHILE p^.key<>x DO p:=p^.next;

IF p=l THEN [ new(q); q^.key:=x; q^.freq:=0 ]

ELSE {找到}

《数据结构 1800 题》

郴州都市网 www.0735.cc 郴州人才网 www.CZHR.com www.989.org

{ (1) ; q->next=p；p=q；(2)___ ; }

(3)_____;

}【北京理工大学 2001 九、1 （6 分）】

32．下面程序段是逆转单向循环链表的方法，p

是原链表头指针，逆转后链表头指针仍为 p

。

（可以根据需要增加标识符）

p:= p

; q

:=NIL;

WHILE （1）_

_______ DO

BEGIN （2）_____

___; （3）________;（4）______;（5）________ END;

p^.next:= q

; p

^.next:=p; p

:=p;【中国人民大学 2000 二、1（4 分）】

33．一个无头结点的线性链表(不循环)有两个域。数据域 data，指针域 next，链首 head，下面算法用

read(num)读入数据，当 num 小于 0 时，输入结束。建立一个数据以递增序组成的链表。

PROC insert( head, x);

{在链首为 head 的表中按递增序插入 x}

new(r);r＾.data:=x;

IF head=NIL

THEN[ head:=(1) _

____; r＾.next:= (2)________ ]

ELSE IF (3)__

_ THEN [r＾ .next:=head; head:=r]

ELSE [p:=head;

WHILE (4)__

_ AND (p＾.next≠NIL ) DO[q:=p; (5)___ ];

IF (6)__

_ THEN [ q＾ .next:=(7)___; r＾.next:= (8)____; ]

ELSE [p＾.next:=(9)

____; r＾.next:= (10)___; ]

]

ENDP;

PROC creat(head);

head:= (11)_____

_; read(num);

WHILE num>0 DO

[ insert(head,num); read(num) ]

ENDP;【南京理工大学 1999 三、4（11 分）】

34. 一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域 coef ，指数域 exp 和指针域 next；

现对链表求一阶导数，链表的头指针为 ha，头结点的 exp 域为 –1。

derivative(ha)

{ q=ha ; pa=ha->next;

while( (1)___

____)

{ if ( (2)___

_) { ( (3)__); free(pa); pa= ( (4) _); }

else{ pa->coef ( (5) ___

); pa->exp( (6)___); q=( (7) __);}

pa=( (8)____

____);

}

} 【南京理工大学 2000 三、3（10 分）】

35.下面是删除单链表 L 中最大元素所在结点的类 PASCAL 语言算法，请在横线填上内容，完成其功能。

TYPE pointer =↑node；

node=RECORD

data:integer; next: pointer

END;

PROCEDURE delmax (L:pointer);

《数据结构 1800 题》

郴州都市网 www.0735.cc 郴州人才网 www.CZHR.com www.989.org

VAR p,q,r:pointer; m:integer;

BEGIN

r:=L； p:=L↑.next;

IF p<>NIL THEN

[ m:=p↑.data; (1)_____

___; p:=p↑.next;

WHILE p<>NIL DO

[ IF (2)_____

___THEN [ (3)________ ; m:=p↑.data; ]

(4)_______

_; p:=p↑.next;

]

q:=r↑.next; (5)______

; dispose(q);

]

END;【北京科技大学 1998 二】

36．对单链表中元素按插入方法排序的 C 语言描述算法如下，其中 L 为链表头结点指针。请填充算法中标

出的空白处，完成其功能。

typedef struct node

{int data; struct node *next;

}linknode,*link;

void Insertsort(link L)

{ link p,q,r,u;

p=L->next; (1)______

;

while((2)___

_____)

{ r=L; q=L->next;

while((3)___

_____&& q->data<=p->data) {r=q; q=q->next;}

u=p->next; (4)______

; (5)______; p=u;

}

}【北京科技大学 2001 二（10 分）】

37．下面是一个求两个集合 A 和 B 之差 C=A-B 的程序，即当且仅当 e 是 A 的一个元素，但不是 B 中的一个

元素时，e 才是 C 中的一个元素。集合用有序链表实现，初始时，A，B 集合中的元素按递增排列，C 为空；

操作完成后 A，B 保持不变，C 中元素按递增排列。下面的函数 append(last,e)是把值为 e 的新结点链接

在由指针 last 指向的结点的后面，并返回新结点的地址；函数 difference(A,B)实现集合运算 A-B，并返

回表示结果集合 C 的链表的首结点的地址。在执行 A-B 运算之前，用于表示结果集合的链表首先增加一个

附加的表头结点，以便新结点的添加，当 A-B 运算执行完毕，再删除并释放表示结果集合的链表的表头结

点。

程序(a)（编者略去这个 PASCAL 程序）

程序（b）

typedef struct node{ int element; struct node *link;

}NODE;

NODE *A，*B，*C;

NODE *append (NODE *last,int e)

{ last->link=(NODE*) malloc (sizeof(NODE));

last->link->element=e;

return(last->link);

}

NODE *difference(NODE *A,NODE *B)

《数据结构 1800 题》

郴州都市网 www.0735.cc 郴州人才网 www.CZHR.com www.989.org

{NODE *C,*last;

C=last=(NODE*) malloc (sizeof(NODE));

while (1)___

if (A->element<B->element) { last=append(last,A->element); A=A->link; }

else if (2) ___

{ A=A->link; B=B->link; } ELSE (3) ___ ;

while (4) __

{ last=append(last,A->element); A=A->link; }

(5) ___

; last=C; C=C->link; free (last); return (C);

}

/*call form:C=difference(A,B);*/【上海大学 2000 一、4 （10 分）】

四应用题

1．线性表有两种存储结构：一是顺序表，二是链表。试问：

（1）如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自

动地改变。在此情况下，应选用哪种存储结构？为什么？

（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，

那么应采用哪种存储结构？为什么？【西安电子科技大学 1999 软件二、1 （5 分）】

2．线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于

难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线

性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。【重庆大学 2000 二、5】

3．若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？

【北京航空航天大学 1998 一、2（4 分）】

4．线性结构包括______、______、_______和_______。线性表的存储结构分成______和______。请用类

PASCＡL 语言描述这两种结构。【华北计算机系统工程研究所 1999 一、2（10 分）】

5．线性表（a

，a

，…，a

）用顺序映射表示时，a

和a

i+1

（1<=i<n〉的物理位置相邻吗？链接表示时呢？

【东南大学 1996 一、1 （5 分）】

6. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。

【厦门大学 2000 五、1 （14%/3 分）】

7. 试述头结点,首元结点,头指针这三个概念的区别.

【武汉交通科技大学 1996 二、2 (3 分)】【西安电子科技大学 2001 计应用二、1（5 分）】

8. 已知有如下定义的静态链表：

TYPE component=RECORD

data:elemtp;

next:0..maxsize

END

VAR stalist:ARRAY[0..maxsize] OF component;

以及三个指针:av 指向头结点，p 指向当前结点，pre 指向前驱结点，现要求修改静态链表中 next 域中的

内容，使得该静态链表有双向链表的功能，从当前结点 p 既能往后查找，也能往前查找：

（1）定义 next 域中的内容。(用老的 next 域中的值表示)；

（2）如何得到当前结点 p 的前驱（pre）的前驱，给出计算式;

（3）如何得到 p 的后继，给出计算式;【中科院计算所 2000 四（10 分）】

9. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?

【西安电子科技大学 1999 计应用一、1 （5 分）】

10. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？

剩余176页未读，继续阅读

zspjyr

粉丝: 1
资源: 2

数据结构考研精华1800题精选：算法与复杂度详解

数据结构1800试题.pdf

数据结构1800题(+答案)

数据结构试题1800题

数据结构1800题 数据结构习题

数据结构1800题和答案 数据结构1800题和答案

数据结构题库1800题.zip

数据结构考试样题数据结构考试题

数据结构考研试题1800题集锦

数据结构考研试题1800题锦囊

数据结构考试1800题（附答案）

最新资源

数据结构1800题数据结构习题

数据结构1800题和答案数据结构1800题和答案