中学信息学《数据结构》习题及参考答案

云南财经大学信息学院

《数据结构》习题及参考答案

《数据结构》课程建设小组

第 1 章 绪 论

基础知识题

1.1 ① 简述下列术语：数据、数据元素、数据对象、存储结构、数据类型、和抽象数据类型。

1.2 ② 试描述数据结构和抽象类型的概念与程序设计语言中数据类型概念的区别。 1.3 ③设有数据结构（D，R），其中

D={d1,d2,d3,d4},R={r},r={(d1,d2),(d2,d3),(d3,d4)}。 试按图论中的画法惯例画出其逻辑结构图。

1.4 ②试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有

理数是其分子，分母均为自然数其分母不零的分数）。 1.5 ②试画出与下列程序段等价的框图 （1） product=1 ; i=1;

while (i<=n){ product * = i;

i++; }

(2) i=0 ;

do { i++

} while ((i !=n )&&(a[i]!=x));

(3) swith {

case x

case x=y : z =abs(x * y);break ; defult : z= (x – y) /abs (x) * abs (y); }

1.6 ② 在程序设计中，常用下列三种不同的出错处理方式：

（1） 用exit 语句终止执行并报告错误；

（2） 以函数的返回值区别正取返回或错误返回；

（3） 设置一个整型变量的函数参数以区别正取返回或错误返回；

试讨论这三种方法各自的优点

1.7 ③ 在程序设计中，可采用下列三种方法实现输出和输入：

（1） 通过 scanf和printf 语句；

(2) 通过函数的参数显示传递； （3） 通过全局变量隐式传递。

试讨论这三种方法的优缺点。

1.8 ④ 设 n 为正整数。试确定下列各程序段中前置以记号@的语句的频度：

(1) i = 1; k = 0;

While (i<=n - 1) { @ k + = 10 * I ;

i ++; }

(2) i = 1; k = 0;

do (i<=n - 1) { @ k + = 10 * I ; i ++;

} while (I< = n - 1); (3) i = 1; k = 0;

While (i<=n - 1) { i ++;

@ k + = 10 * i ; }

(4) k = 0;

for ( i = 1;i<=n ;i++) { for ( j = i;j<=n ;j++)

@ k + +; }

(5) for ( i = 1;i<=n ;i++) {

for ( j = i;j<=n ;j++) { for ( k = 1;k<=j ;k++) @ x + = delta; }

(6) i=1;j=0;

While (i+j<= n){ @ if (i>j) j++; else i++; }

(7) x= n; y= o;

while (x>=(y+1) * (y + 1)){ @ y ++; }

(8) x= 91; y= 100;

while (y>0){

@ if (x>100){x-=10; y - -; } else x ++ ; }

1.9 ③ 假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值

（以的函数形式表示）。

int Time( int n){ Count=0;x=2;

While (x

return (count)

} // Time

1.10 ② 按增长率由小到大的顺序排列下列各函数： 2100 (3/2)n (2/3)n (4/3)n nn n 3/2 n 2/3 n!

n, log2 n log22 n log2 ( log2 n)

nlog2 n n log 2n

1.11 ③ 已知有现实同一功能的两个算法，其时间复杂度分别为O（2n）和O（n10），

假设现实计算机可连续运算的时间为 107 秒（100多天），又每秒可执行基本操

5

作（根据这些操作来估算算法时间复杂度）10 次。试问在此条件下，这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由。 1.12 ③ 设有以下三个函数：

f (n) = 21n4 + n2 + 1000 g(n) = 15n4 + 500n3 h(n)=5000 n3.5 +nlogn 请判断以下断言正确与否： （1）f (n)和 O(g (n)) (2) h(n) 和O(f (n)) (3) g(n) 和O(h (n)) (4) h (n) 和O(n3.5) (5) h(n) 和O(nlogn)

1.13 ③ 试设定若干n的值，比较两函数n2 和50nlog2n 的增长趋势，并确定n在什

么范围内，函数n2 的值大于 50nlog2n 的值

1.14 ③ 判断下列各对函数f (n) 和g (n) ,n趋进于∞时，哪个函数增长更快？

1.15 试用数学归纳法证明：

算法设计题

1.16 ② 试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。 1.17 ③已知k阶裴波那契序列的定义为：

试编写k阶裴波那契序列的第 项值的函数算法，k和m均以值调用的 形式在函数参数表中出现。

1.18 ③ 假设有A，B，C，D，E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为：

项目名称 性 别 校 名 成 绩 得 分 编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。

1.19④ 试编写算法，计算 i !. 2i 的值并存入数组a[0…arrsize - 1] 的第i- 1个分量中（I= 1,2,….,n）。假设计算机中允许的整数最大值为maxint, 则当n>arrsize 或对某个k(1≤k≤n)使 k!. 2k >maxint 时，应按出错处理，注意选择你认为较好的出错处理方法。

1.20④ 试编写算法求一元多项式的值 的值Pn(x0) 并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为 aj (i= 0, 1,…..n) x0 和n,输出为 Pn(x0) 。

第 2 章 线 性 表

基础知识题

2.1① 描述以下三个概念的区别，头指针，头结点，首元结点（第一个元素结点）。 2.2① 填空题。

（1）在顺序表①中插入或删除一个元素，需要平均移动 元素，具体移动的元素与 有关。

（2）顺序表中逻辑上相邻的元素的物理位置 紧邻。单链表中逻辑的元素物理位置 紧邻。

（3）在单链表中，除了首元结点外，任一结点的存储位置由 指示。 （4）在单链表中设置头结点的作用是 。 2.3② 在什么情况下用顺序表比链表好？

2.4① 对以下单链表分别执行下列各程序段，并画出结果意图。

Q=P-> next; L=P->next;

R->data=R->data;

R->data=P->next->data;

P->next->next->next->data=P->data; T=P;

While (T!=NULL){ T->data=T->data * 2;T=T->next;}

(7) T= P

while (T-> next!=NULL) {T->data=T->data * 2;T=T->next;}

2.5① 画出执行下列各行语句后各指针及链表的示意图。 L= (LinKList)malloc(sizeof(L Node));P=L; for (i =1;i<=4;i++){

P->next =( LinKList)malloc(sizeof(LNode)); P=P->next;P->data= i* 2 – 1;

}

P-> next =NULL;

for (i=4;i>=4;i - -;) Ins_LinkList(L,i+1,i * 2); for (i=1;I<=3;i ++;)Del_LinkList(L, i ); 2.6② 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a.在P结点后插入S结点的语句序列是 b.在P结点前插入S结点的语句序列是 c.在表首插入S结点的语句序列是 d.在表首插入S结点的语句序列是

(1) P->next=S;

(2)P->next=P->next->next;

（1） （2） （3） （4） （5） （6）

(3)P->next=S->next; (4)S->next=P->next; (5)S->next=L;

(6)S->next=NULL; (7)Q=P;

(8)while (P->next!=Q)P=P->next;

(9) while (P->next!=NULL)P=P->next; (10) P=Q; (11) P=L; (12) L=S (13) L=P;

2.7② 已知L是带头结点的非空单链表，且P结点既不是首结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列是 a. 删除P结点的直接后继结点的语句序列是

b.删除P结点的直接后继结点的语句序列是 c.删除P结点的语句序列是 d.删除首元结点的语句序列是

e.删除尾元结点的语句序列是 . (1) P=P->mext; (2) P->next= P; (3) P->next=P;

(4) S->next=P->next->next; (5) While(P!=NULL)P=P->next;

(6) While(Q - >next! = NULL) {P=Q;Q=Q->next;} (7) While (P->next!=Q) P=P->next; (8) While(P->next->next!=Q)P=P->next; (9) While( P->next->next!=NULL)P=P->next (10) Q=P; (11) Q=P->next; (12) P=L; (13) L=L->next; (14) free(Q);

2.8② 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适 的合适语序序列。

a.在P结点后插入S结点的语句序列是 b.在P结点前插入S结点的语句序列是 c.删除P结点的直接后继结点的语句序列是

d.删除P结点的直接前驱结点的语句序列是 e.删除P结点的语句序列是 (1) P->next=P->next->next; (2) P->priou=P->priou->priou; (3) P->next=S; (4) P->priou=S; (5) S->next=P;

(6) S->priou=P;

(7) S->next=P->next; (8) S->priou =P->priou; (9) P->priou->next=P->next; (10) P->priou->next=P; (11) P-> next -> priou =P; (12) P->priou->next=S; (13) P->priou->next=S;

(14) P-> next -> priou =P->priou; (15) Q=P->next; (16) Q=P->priou; (17) Free(p); (18) Free(Q);

2.9② 简述以下算法的功能。

（1） Status A(Linked List L) { //L是无表头结点的单链表 If (L&&L->next){

Q=L;L=L->next;P=L;

While (P->next)P=P->next; P->next =Q; Q->next=NULL; }

return OK; }//A

(2) Void BB(Lnode * s,Lodes * q){

p=s;

while(p->next!=q)q=p-next; p->next=s; }//BB

void AA(Lnode * pa,Lnode * pb){

//pa 和 pb分别是指向单循环链表的类型定义如下： BB(pa,pb); BB(pb,pa); }//AA

算法设计题

本章算法设计题涉及的顺序表和线性表的类型定义如下： # define LIST_INIT_SIZE 100 # define LISTINCREMENT 10 typedef struct{

Elem Type * elem; //存储空间基址 int length; //当前长度

int listsize; //当前分配的存储容量 } SqList; //顺序表类型 typedef struct Lnode{ Elem Type data;

Struct Lnode *next;

} Lnode,* LinkList; //线性链表类型

2.10② 指出以下算法中的错误和低效（既费时）之处，并将它改写成一个既正确

又高效的算法。

Status DeleteK(SqList&a,inti,int k){

//本过程从顺序存储结构的线性表中a中删除第 i个元素起的k个元素 if (i,1||k<0||i+k>a.length)return INFEASIBLE //参数不合法 else {

for (count = 1;count

//删除一个元素

for(j=a.length;j>=i+1;j--)a.elem[j - 1]=a.elem[j]; a.length--; }

return OK; }//DeleteK

2.22 ② 设顺序表中的数据元素递增有序。试写一算法，将插入到顺序表的适当

位置上，以保持该表的有序性。

2.12 ③设A=（a1 , …am）B=( b1 ,…,bm )均为顺序表，A’ 和B’分别为A 和B中

同前缀为（x,y,y,z），在两表中除最大共同前缀后的子表分别为A’=（x,z）和 B’=（y,x,x,z）若A’ =B’=空表，则A=B；若A’ =空表，而B’ ≠空表，或者两者均不为空表，且A’的首元小于B’的首元，则A＜B；否则A ＞B。试写一个比较A，B大小的算法（请注意：在算法中，不要破坏原表A与B，并且也不一定先求得A’和 B’才进行比较）。

2.13②试写一算法在带头结点的单链表结构上的实现线性表操作LOCATE（L，X）。 2.14② 试写一算法在带头结点的单链表结构上的实现线性表操作LENGTH（L）。 2.15②已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长

度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表 的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。

2.16③已知指针la和lb分别指向两个无头结点单链表的首元结点。下列算法是从

表la中删除自第i个元素起共len个元素后，，将它们插入到表lb中第i个元素之前，试问此算法是否正确？若有错，则请改正之。

Status Dlete AndInsertSub(Linked la,LinkedList lb,int i ,int j ,int len{

If (i <0||j<0||len<0)return INFEASIBLE; p=la;k=1;

while(k< i){p==p->next;k++;} q=p;

while(k<=len){q=q->next;k++;} s=lb;k=1;

while(knext;k++;} s->next=p;q->next=s->next; return OK;

}//Delete AndInsertSub

2.17② 试写一算法，在无头结点的动态单链表上实现线性表操作INSERT（L，i，b），

并和在带头结点的动态单链表上实现相同操作的算法进行比较。

2.18② 同2.17题要求，试写一算法，实现线性表操作DELETE（L，i）。

2.19③ 已知线性表中的元素以值递增有序排列，并以单链表作存储结构，试写出一

高效算法，删除表中所有值大于mink且小于maxk的元素，（若表中存在这样的元素）同时释放被删除结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）

2.20②同2.19题条件，试写出一高效算法，删除表中所有值相同的多余元素（使得

操作后的线性表中所有元素的值均不相同），同时释放被删除结点空间，并分析你的算法的时间复杂度。

2.21③试写一算法，实现顺序表的就地逆置，即利用原表中的存储空间将线性表（a1 , …an）逆置为（an , …a1）。

2.22③是写一算法，对单链表实现就地逆置。 2.23③设线性表A=（a1 , …am）B=（b1 , …bm），试写一个按下列规则合并A，B为

线性表C的算法，即使得

C=（a1 , b1, …am ，bm , bm+1…bn）当m≤n 时；或者 C=（a1 , b1, …an ，bn , an+1…am） 当m＞n 时。

线性表A，B，C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成，注意：单链表的长度值m和n均未显示存储。

2.24④假设有两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结

构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。

2.25④假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同

一表中的元素各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列，试对顺序表编写求C的算法。

2.26④ 对2.25题。试对单链表编写求C的算法

2.27④对2.25题的条件作以下两点修改，对顺序表重新编写求得C的算法。

（1）假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C

中的元素值各不相同；

（2）利用A表空间存放表C。

2.28④对2.25题的条件作以下两点修改，对顺序表重新编写求得C的算法。

（1）假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C

中的元素值各不相同；

（2）利用原表（A表或B表）中的结点构造C，并释放A表中的无用节点空

间。

2.29⑤已知A，B和C为三个递增有序的线性表C，现要求对A表中作如下操作；删

除那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作算法，并分析你的算法的时间复杂度，（注意；题中没有特别指明同一表中的元素各不相同）。

2.30⑤要求同2.29题，试对单链表编写算法，请释放A表中的无用结点空间。

2.31②假设某个单向循环链表的长度大于1，且表中即无头结点也无头指针。已知s

为指向链表中的某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱节点。

2.32②已知有一个单向循环链表，其每一个结点中含三个域：pre，data和next，其中

data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空（NULL），

3.26④求解平方根的迭代函数定义如下；

其中，P是A的近似平方根，e是结果误差，试写出相应的递归函数算法，并消

除递归。

3.27⑤已知Ackerman函数定义如下： （1） 写出递归算法； （2） 写出非递归算法，

（3） 根据非递归算法，画出求akm（2，1）时栈的变化过程。

3.28②假设以带头结点的循环链表表示队列，并且只设一个指针指向对尾元素结

点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。

3.29②如果希望循环队列中的元素都能得到利用，则需要设置一个标志域tag，并以tag的值为0或1来区分，尾指针和头指针相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列较小而队列中每个元素占的空间较多时，哪一种方法较好）。

3.30②假设将循环队列定义为：以域变量rear和length分别指示循环队列中对尾

元素的位置和内含元素的个数，试给出此循环队列的对满条件，并写出相应的 入队列和出队列的算法（在出队列的算法中要返回对头元素）。

3.31③假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’

是回文，‘bcde’和‘ababa’则不是回文，试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

3.32④试利用循环队列编写求k阶斐波那契序列中前n+1项，（f0 ，f1 ，…. fn）

的算法,要求满足: fn ≤max而fn+1>max,其中max为某个约定的常数。（注意：本题所用循环队列的容量仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项 fn-k+1 ，…. fn） 。

3.33③在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每一个原始表示一个待处理表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于对头和对尾作业的平均时间，则插入在对头，否则插入在对尾。

3.34③ 假设在教科书3.4.1节中图3.9所示，铁道转轨网的输入端有n节车厢：硬座、硬卧、和软卧（分别以P，H和S表示）等待调度，要求这三种车厢在输出端铁道上的 排队次序为：硬座在 前，软卧在中，硬卧在后。试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：分别以字符‘E’和‘D’表示对双端队列的头端进行入队列和出队列的操作；以字符A表示对双端队列的尾端进行入队列的操作。

第 4 章 串

基础知识题

4.1① 简述空串和空格串

4.2②对于教科书4.1节所述串的各个基本操作，讨论是否可由其他基本操作构造

而得？如何构造？

4.3① 设s=‘I AM A STUDENT’,t=’GOOD’,q=’WORKER’. 求：StrLength(s),StrLength(t),SubString(s,8,7),SubString(t,2,1), Index(s,’A’),Index(s,t),Replace(s,’STUDENT’,q), Concat(SubString(s,6,2),Concat(t,SubString(s,7,8))). 4.4①已知下列字符串

a=’THIS’ ,f=’A SAMPLE’,c=’GOOD’,d=’NE’,b=’’,

s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)))), t=Replac(f,SubString(f,3,6),c),

u=Concat(SubString(c,3,1),d), g=’IS’

v=Concat(s,Concat(b,Concat(t,Concat(b,u)))),

试问： s,t,v,StrLength(s),Index(v,g),Index(u,g)各是什么？ 4.5①试问执行以下函数会产生怎样的输出结果？ Void demonstrate(){

StrAssign(s,’THIS IS A BOOK’);

Replace(s,SubString(s,3,7),)’ESE ARE’); StrAssign(t,Concat(s,’S’));

StrAssign(u,’XYXYXYXYXYXY’); StrAssign(v,SubSting(u,6,3)); StrAssign(w,’W’);

Printf(‘t=’,t,’v=’,v,’u=’,Replace(u,v,w,)); }//demonstrate

4.6②已知；s=’(XYZ)+*’,t=’(X+Z)*Y’试利用联接、求子串和置换等基本运算，将s

转化为t。

4.7②令=‘aaab’,t=’abcabaa’,u=’abcaabbabcabaacbacba’.。试分别求出它们的next

函数值和nextrval函数值。

4.8②已知主串s=‘ABADABBAABADABBADADA’， 模式串pat=‘ADABBADADA’，

写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程 4.9③在以链表存储串值时，存储密度是结点大小和串长的函数假设每个字符占一个

字节，每个指针占4个字节，每个结点的大小为4的整数倍。已知串长的分布函数为f（l）且，求结点大小为4k，串长为l时的存储密度d（4k，l）（用公式表示）。

算法设计题

在编写4.10至4.14题的算法时，请采用StringType数据类型； StringType是串的一个抽象数据类型，它包含以下五种基本操作： Void StrAssign（StringType &t,StringType s）

//将s的值赋给t。s的实际参数可以是串变量或者串常量（如：‘abcd’）。 int StringCompare(StringType s,StringType t)

//比较s和t。若s>t,返回值>0，若s=t,返回值=0；若s

返回s中的元素个数，即该串的长度。

StringType Concat(StringType s,StringType t) //返回由s和t联接而成的新串

StringType SubString(StringType s,int start ,int len)

//当1≤start≤ StrLength(s) 且 0≤len ≤StrLength(s)-start+1时 //返回s中第start个字符起长度为len的子串，否则返回空串。 4.10③ 编写对串求逆的递推算法。

4.11③编写算法，求得所有包含在串s中而不包含在串t中的字符（s中重复的字符

只选一个）构成的新串r，以及r中每个字符在s中第一次出现的位置。

4.12③编写一个实现串的置换操作Replace（&S，T，V）的算法。 4.13③编写算法，从串s中删除所有和串t相同的子串。

4.14④利用串的基本操作以及栈和集合的基本操作，编写“一个算术表达式的前缀

式求后缀式”的递推算法（假设前缀式不含语法错误）。

在编写4.15至4.20题的算法时，请采用教科书4.2.1节中所定义的定长顺序存储

表示，而不允许调用串的基本操作。

4.15③编写算法，实现串的基本操作StringAssign（&T,chars）. 4.16③编写算法，实现串的基本操作StrCompare（S，T）。 4.17③编写算法，实现串的基本操作Replace（&S，T，V）。

4.18③编写算法，求串s所含不同字符的总数和每种字符的个数。 4.19③在串的定长顺序存储结构上直接实现4.11题要求的算法。 4.20③编写算法，从s中删除所有和串相同的子串。

4.21④假设以结点大小为1且附设头结点的链表结构表示串，试编写实现下列六种

串的基本操作StrAssign，StrCopy，StrCopare，StrLength，Contact和SubSring的函数。

4.22④假设以块链结构表示串，试编写将串s插入到串t中某个字符之后的算法，（若

串t中不存在此字符，则将串s联接在串的末尾）。

4.23④假设以块链结构作为串的存储结构。试编写判别给定串是否是具有对称性的

算法，并要求算法的时间复杂度为O（StrLength（S））。

在编写4.24到4.26题的算法时，请采用教科书4.2.2节中所定义的堆分配存储表示 4.24③试写一算法，在串的堆存储结构上实现基本操作Concat(&T,s1.s2). 4.25③试写一算法，实现堆存储结构的串的置换操作Replace（&S，T，V）。 4.26③试写一算法，实现堆存储结构的串的插入操作StrIsert（&S，pos，T）。 4.27③当以教科书4.2.1节中定义的定长顺序结构表示串时，可如下所述改进定位

函数的算法；先将模式串t中的第一个字符和最后一个字符与主串s中相应的字符比较，在两次比较都相等之后，再依次从t的第二个字符起逐个比较，这样做可以克服算法Index（算法4.5）在模式串‘ak b’（ak 表示连续k个字符‘a’ ）在主串‘an b’（k≤n）中的定位函数时产生的弊病，试编写上述改进算法，并比较这两种算法在作Index（‘an b’，‘ak b’）运算时所需进行的字符间的比较次数。

4.28④假设以结点大小为1，（带头结点）的链表的结构表示串，则在利用next函

数值进行匹配时，在每个结点中需要设三个域：数据域chdata、指针域succ和指针域next。其中chdata域存放一个字符，succ域存放指向同一链表中后继结点的指针；next域在主串中存放指向同一链表中前驱结点的指针，在模式串中，存放指向当该结点的字符与主串中的字符不等时，模式串中下一个应进行比较的字符的next函数值为零，则其next域的值应指

向头结点，试按上述定义的结构改写模式串的next函数值的算法。

4.29④试按4.28题定义的结构改写串匹配的改写算法（KMP算法）。

4.30⑤ 假设以定长顺序存储结构表示串，试设计一个算法，求串s中出现的第一

个最长重复子串及其位置，并分析你的算法的时间复杂度。

4.31⑤假设定长顺序存储结构表示串，试设计一个算法，求串s和串t的一个最长

公共子串，并分析你的算法的时间复杂度，若要求第一个出现的最长公共子串（既它在串s和串 t的最左边的 位置上出现）和所有的最长公共子串，讨论你的算法能否实现。

第五章 数组与广义表

基础知识题

5.1①假设有二维数组A6×8 ，每个元素用相邻的6个字节存储，存储器按字节编

址。已知A的起始存储位置（基地址）为1000，计算：

（1） 数组A的体积（即存储量）；

（2） 数组A的最后一个元素a57 的第一个字节的地址； （3） 按行存储时，元素a14的第一个字节的地址； （4） 按行存储时，元素a47 的第一个字节的地址；

5.2①假设按低下标优先存储整数数组A9×3×5×8 时，第一个元素的字节 地址是100，每个整数占四个字节，问下列元素的存储地址是什么？ （1）a0000 （2）a1111 （3）a3125 （4）a8247

5.3①按高下标优先存储方式（以最右的下标为主序），顺序列出数组A9×3×5×8中所有元素aijkl，，为了简化表达，可以只例出（i，j，k，l）的序列。 5.4①将教科书5.3.1节中的式（5-3）改写为一个等式的形式。

5.5③设有上三角矩阵（aij）m×n ，将其上三角元素逐行存于数组B[m]中，（m充分大）使得B[k]=aij 且k=f l （i）+ f 2 （i） +c 。试推导出函数f l，f 2 和常数c （要求f l和 f 2 中 不含常数项 ）

5.6③设有三对角矩阵（aij）m×n ，将其上三角元素逐行存于数组B[3][n]中，使的元素B[u][v]= aij，试推导出从（i，j）到（u，v）的下标变换公式。

5.7③设有三对角矩阵（aij）m×n ，将其上三角元素逐行存于数组B[3n-2]中，使得B[3n-2]中，使得B[k]= aij ，求：

（1） 用i ，j表示k的下标变换公式； （2） 用k表示i、j 的下标变换公式

5.8③假设一个准对矩阵

按以下方式存于一维数组B[4m]中：

0 1 2 3 4 5 6 k 4m-2 4m-1 a11 a12 a21 a22 a33 a34 a43 … aij … a2m-1,2m a2m,2m-1 a2m,2m 写出由一对下标（i，j）求k的转换公式。 5.9②已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二维

数组和三元组表）完成 求 运算的优缺点。

5.10②求下列广义表操作的结果： （1） GetHead【（p,h,w）】； （2） GetTail【（b,k,p,h）】； （3） GetHead【（a,b）(c,d)】； （4） GetTail【（a,b）(c,d)】； （5） GetHead【GetTail【（a,b）(c,d)】】； （6） GetTail【GetHead【（a,b）(c,d)】】； （7） GetHead【GetTail【GetHead【（a,b）(c,d)】】】； （8） GetTail【GetHead【GetTail【（a,b）(c,d)】】】； 注意：【】 是函数的符号。

5.11② 利用广义表的GetHead和GetTail 操作写出如上题的函数表达式，把原子

本文来源：https://www.bwwdw.com/article/kxj6.html