数据结构入门：算法复杂度与基本概念详解

数据结构

需积分: 0 23 浏览量更新于2024-07-01 收藏 2.82MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

本资源是一份针对数据结构基础概念的练习题集，主要涵盖了数据结构学习的入门阶段，包括对算法复杂性、计算机算法定义、算法特性、数据结构分类以及算法分析等方面的知识点。 1. 算法复杂性：题目强调了算法的计算量，即算法的效率，这是衡量算法在解决特定问题时所需时间和资源的关键指标。选项B的“复杂性”符合这个概念，表示算法运行时间或空间需求随着输入规模的增长而变化的性质。 2. 算法时间复杂度：考察的是影响算法执行速度的主要因素，即问题的规模和数据的初始状态，选项C正确，因为时间复杂度通常与这两个因素相关。 3. 计算机算法：算法被定义为解决问题的明确步骤序列，必须具有可执行性（能够被机器理解并执行）、确定性（对于相同的输入总是得到相同的结果）和有穷性（有限的步骤完成任务），选项B中的这三个特性是算法的基本要素。 4. 算法特性与问题描述：算法不仅是具体的程序，更是问题求解步骤的抽象描述，选项D结合了程序和问题求解步骤的描述性特征。 5. 算法错误理解：题目的目标是测试对算法概念的理解，错误的说法包括算法最终必须编程实现（正确）、算法和程序的区别（不完全等同）、算法指令的清晰性（不是指二义性）以及算法效率与编程语言级别的关系（不一定成反比）。 6. 数据结构分类：逻辑上，数据结构分为动态结构和静态结构，这两类分别对应数据在内存中动态变化和静态不变的状态。 7. 存储结构与术语：循环队列、链表和哈希表都是数据结构的具体实现方式，与数据的存储结构有关，而栈虽然也是线性数据结构，但选项D的“初等结构、构造型结构”并不常见，可能是对数据结构类型的一种描述，但并非标准术语。 8. 线性结构识别：题目要求判断哪个数据结构是线性结构，线性结构的特点是元素之间存在一对一的线性关系，如数组、链表等。通过这些题目，学生可以检验自己对数据结构基础理论和概念的理解，以及对不同概念之间的区别和联系的掌握程度。解答这些题目有助于深化对数据结构设计和分析的理解，为后续深入学习打下坚实的基础。

资源详情

资源推荐

南邮通信培训中心

报名地址：南京邮电大学仙林校区梅兰西街梅苑 01101-1；南京邮电大学三牌楼校区综合科研楼 19 层

报名热线：025-83535877、18951896587、 18951896993、 18951896967

WHILE q^.freq>p^.pre^.freq DO p:=p^.pre;

IF p<>q THEN [ （3）______ ]

]；

IF （4）_ THEN [q^.next:=p, q^.pre;=p^.pre; p^.pre^.next:=q; p^.pre:=q]

return(q);

END;【北京工业大学 1999 五 (12 分)】

29．循环链表 a 和 b 的结点值为字母，其中 a 表非递减有序，下面的程序欲构造一个递增有序的循环链表 c，

其中结点的值为同时在 a，b 两链表中出现的字母，且 c 中字母不重复，请补上程序中空缺的部分，并估计

算法的时间复杂度。（设 a，b 的结点数分别为 m，n）

TYPE

link=^node;

node=RECORD

key:char; next:link

END;

PROC jj(a,b:link; VAR c:link);

VAR p,q,r,s:link;

BEGIN

new(c);c^.next:=c; q:=a; p:=a^.next;

WHILE p<>a DO

[（1）___；

WHILE p^.key=p^.next^.key DO [q:=p; p=p^.next];｛跳过相同字母｝

r:=b^.next ; （2）_____;

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

IF r<>b THEN

[ s:=p; q^.next:=p^.next; （3） ;

s^.next:=c^.next; c^.next:=s; c:=s ]

ELSE [ q:=p; p:=p^.next ]

]; c:=c^.next；

END;

算法时间复杂度为 O（4）___ 【北京工业大学 2000 四 (15 分)】

30. 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

void reverse(pointer h)

/* h 为附加头结点指针；类型 pointer 同算法设计第 3 题*/

{ pointer p,q;

p=h->next; h->next=NULL;

while((1)________)

{q=p; p=p->next; q->next=h->next; h->next=(2)________; }

}【西南交通大学 2000 一、9】

31. 下面是用 c 语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用 L 返回逆置后的链表的

头指针，试在空缺处填入适当的语句。

void reverse（linklist &L）{

p=null；q=L；

while（q！=null）

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

(3)_____;

南邮通信培训中心

报名地址：南京邮电大学仙林校区梅兰西街梅苑 01101-1；南京邮电大学三牌楼校区综合科研楼 19 层

报名热线：025-83535877、18951896587、 18951896993、 18951896967

}【北京理工大学 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);

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

BEGIN

南邮通信培训中心

报名地址：南京邮电大学仙林校区梅兰西街梅苑 01101-1；南京邮电大学三牌楼校区综合科研楼 19 层

报名热线：025-83535877、18951896587、 18951896993、 18951896967

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)

{NODE *C,*last;

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

while (1)___

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

南邮通信培训中心

报名地址：南京邮电大学仙林校区梅兰西街梅苑 01101-1；南京邮电大学三牌楼校区综合科研楼 19 层

报名热线：025-83535877、18951896587、 18951896993、 18951896967

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. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？

【中国人民大学 2001 二、4 （2 分）】

11. 下面是一算法的核心部分，试说明该算法的功能。

pre:=L↑.next;

{L 是一单链表，结点有数据域 data 和指针域 next}

IF pre<>NIL THEN

南邮通信培训中心

报名地址：南京邮电大学仙林校区梅兰西街梅苑 01101-1；南京邮电大学三牌楼校区综合科研楼 19 层

报名热线：025-83535877、18951896587、 18951896993、 18951896967

WHILE pre↑.next<>NIL DO

BEGIN p:=pre↑.next; IF p↑.data>=pre↑.data THEN pre:=p ELSE return(false) END;

return(true); 【燕山大学 2000 七、1 （7 分）】

12. 设单链表结点指针域为 next，试写出删除链表中指针 p 所指结点的直接后继的 C 语言语句。

【北京科技大学 2000 一、3】

13. 设单链表中某指针 p 所指结点（即 p 结点）的数据域为 data，链指针域为 next，请写出在 p 结点之前

插入 s 结点的操作（PASCAL 语句）。【北京科技大学 1999 一、2 （2 分）】

14. 有线性表(a

,…,a

),采用单链表存储，头指针为 H，每个结点中存放线性表中一个元素，现查找某

个元素值等于 X 的结点。分别写出下面三种情况的查找语句。要求时间尽量少。

（1）线性表中元素无序。（2）线性表中元素按递增有序。（3）线性表中元素按递减有序。

【北京邮电大学 1994 七（7 分）】

15．设 pa，pb 分别指向两个带头结点的有序（从小到大）单链表。仔细阅读如下的程序，并回答问题：

（1）程序的功能。（2） s1，s2 中值的含义。（3） pa，pb 中值的含义。

PROCEDURE exam(pa,pb)

BEGIN

p1:=pa↑.next; p2:=pb↑.next; pa↑.next:=∧; s1:=0; s2:=0;

WHILE p1≠∧ AND p2≠∧ DO

[ CASE p1↑.data<p2↑.data: [p:=p1; p1:=p1↑.next; s2:=s2+1; dispose(p) ];

p1↑.data>p2↑.data: p2:=p2↑.next;

p1↑.data=p2↑.data: [p:=p1; p1:=p1↑.next; p↑.next:= pa↑.next;

pa↑.next:= p; p2:= p2↑.next;s1:=s1+1; ];

END

];

WHILE p1≠∧ DO [ p:=p1; p1:=p1↑.next; dispose(p); s2:=s2+1 ]

END;【南京航空航天大学 1995 十（9 分）】

16．写出下图双链表中对换值为 23 和 15 的两个结点相互位置时修改指针的有关语句。

结点结构为：(llink,data,rlink) 【北京邮电大学 1992 三、4 （25/4 分）】

17．按照下列题目中的算法功能说明，将算法描述片段中的错误改正过来。

（1）（４分）下面的算法描述片段用于在双链表中删除指针变量 p 所指的结点：

p^.rlink←p^.llink^.rlink;

p^.llink←p.^rlink^.llink

dispose(p);

（2）（６分）下面的算法描述片段用于在双链表中指针变量 p 所指结点后插入一个新结点：

new(q);

q^.llink←p;

p^.rlink←q;

q^.rlink←p^.rlink;

q←p^.rlink^.llink; 【山东大学 1999 八（10 分）】

18．已知 L 是一个数据类型 linkedlist 的单循环链表，pa 和 pb 是指向 L 中结点的指针。简述下列程序段

的功能。【山东科技大学 2001 一、2 （5 分）】

TYPE linkedlist=↑node;

node=RECORD

10 23 15

剩余172页未读，继续阅读

阿玫小酱当当囧

粉丝: 17
资源: 324

数据结构入门：算法复杂度与基本概念详解

数据结构练习题.pdf

【20春】《数据结构》(本)纸考练习题.docx

数据结构-练习题1

数据结构练习题pdf

华东师范大学数据结构练习题

java基础数据结构练习题

python数据结构练习题

数据结构PAT练习题

数据结构的练习题有哪些

数据结构(殷人昆)练习题答案及源码.rar

浙江大学数据结构习题

数据结构线性表练习题

数据结构和算法练习题

数据结构的习题在哪里

浙大数据结构课后习题c语言何越

数据结构c语言版专升本习题

数据结构与算法 习题 c++

数据结构习题库1-8章测试题 章节练习带答案 pdf

浙大数据结构课后习题

scau数据结构如何复习

最新资源

数据结构与算法习题 c++

数据结构习题库1-8章测试题章节练习带答案 pdf