内容发布更新时间 : 2024/12/22 20:25:16星期一 下面是文章的全部内容请认真阅读。

习题1

1．解释以下概念：逻辑结构，存储结构，操作，数据结构，数据结构的表示，数据结构的实现，抽象数据类型，算法，算法的时间代价，算法的空间代价，大O表示法。

2．理解以下关系：算法与数据结构的关系；数据结构与抽象数据类型的关系；算法和数据结构与问题求解的关系。

3. 写出下列程序段的平均情况下的时间代价O表示式。 (1) a=b+c; d=a+e (2) sum=0;

for (i=0;i<3;i++) for (j=0;j

while (x>=(y+1)*(y+1)) y++; (4) s=0; if(even(n))

for (i=0;i0){

if(x>lO0){ x=x-10; n=n-1; }else

x=x+1; }

4．对于给定的n个元素，可以构造出有 ， ， ， 四种。

逻辑结构

的 5.按增长率由小到大的顺序排列下列各函数：

33n2n4nn

2, ( ), ( ), ( ), n, n2 , n!, n, log2n, n/log2n

233100

习题2

2.1已知L是无头结点的单链表，且p结点既不是第一个结点，也不是最后一个结点，试从下列提供的语句中选出合适的语句序列： (1)在p结点之后插入s结点： (2)在p结点之前插入s结点： (3)在单链表L首插入s结点： (4)在单链表L后插入s结点： 提供的语句：

①p->next＝s； ②p->next＝p->next->next； ③p->next=s->next； ④s->next=p->next； ⑤s->next＝L； ⑥s->next=p； ⑦s->next=NULL； ⑧q＝p；

⑨while(p->next!=q)p=p->next； ⑩while(p->next!=NULL)p=p->next； ⑾p=q； ⑿p=L； ⒀L＝s； ⒁L＝p；

2.2已知p结点是某双向链表的中间结点，试从下列提供的语句中选出合适的语句序列。

(1)在p结点之后插入s结点： (2)在p结点之前插入s结点： (3)删除p结点的直接后继结点： (4)删除p结点的直接前驱结点： 提供的语句：

①p->next＝p->next->next； ②p->prior=p->prior->prior； ③p->next=s； ④p->prior=s； ⑤s->next=p； ⑥s->prior＝p；

⑦s->next=p->next； ⑧s->prior=p->prior； ⑨p->prior->next=p->next； ⑩p->prior->next＝p； ⑾p->next->prior＝p； ⑿p->next->prior＝s；

⒀p->prior->next=s； ⒁p->next->prior=p->prior； ⒂q=p->next； ⒃q=p->prior； ⒄free(p)； ⒅free(q)；

2.3试编写一个计算头结点指针为L的单链表长度的算法。 2.4试编写一个将单循环链表逆置的算法。

2.5已知一顺序表A，其元素值非递减有序排列，编写一个算法，删除顺序表中多余的值相同的元素。

习题3

3.1 简述栈和线性表的区别。简述栈和队列的相同点和不同点。

3.2 如果进栈的数据元素序列为1、2、3、4、5、6，能否得到4、3、5、6、1、2和1、3、5、4、2、6的出栈序列?并说明为什么得不到或如何得到。 3.3 利用两个栈模拟一个队列的入队、出队和判断队列空的运算。 3.4 写一算法，将一个顺序栈中的元素依次取出，并打印元素值。 3.5 写一算法，将一个非负十进制整数转换成二进制。

3.6 写一算法，将一个链式队列中的元素依次取出，并打印元素值。

3.7 设有编号为1、2、3、4的4辆车，顺序进入一个栈式结构的站台，试写出这4辆车开出站台的所有可能的顺序。

3.8 写一个算法，借助于栈将一个单链表逆置。

习题4

4.1 空串和空格串有什么区别?

4.2 两个字符串相等的充要条件是什么? 4.3 串的三种机内表示方法是什么?

4.4 设S＝'I am a student'，T＝'good'，Q＝'worker'。求： (1)StrLength(S)

(2)SubString(&Sub，S，8，7) (3)SubString(&Sub，T，2，1) (4)Index(S，'a'，1) (5)Index(S，T，1)

(6)Replace(&S，'Student'，Q)

(7)Concat(&N，SubString(&V，S，6，2)，Concat(&P，T，SubString(&W,S,7,8)))

4.5 设A＝'This'，F＝'a sample'，C＝'good'，D＝'ne'，B＝' '，G＝'is'。求：

(1)Coneat(&S，A，Concat(&Z，SubString(&Y，F，2，7)，Concat(&X，B，SubString(A，3，2))))

(2)Concat(&U，SubString(&X，C，3，1)，D) (3) Replace(&F，SubString(&X，F，3，6)，C) (4)StrLength(S) (5)Index(V，G，1) (6)Index(U，G，1)

(7) Concat(&V，S，Concat(&Z，B，Concat(&Y，F，Concat(&X，B，U))))