2-6习题

基础知识题

2.2[1] 填空题。

(1)在顺序表中插入或删除一个元素，需要平均移动_____元素，具体移动的元素个数与______有关。

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

(3)在单链表中，除了首元结点外，任一结点的存储位置由________表示。 (4)在单链表中设置头结点的作用是______________________________________ ___________________________________________。

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

2.6[2]已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列。

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

第 1 页 共 8 页

算法设计题

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

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

Int listsize; //当前分配的存储容量 } Sqlist; //顺序表类型

Typedef struct LNode{

ElemType data; Struct LNode *next;

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

‘2.12[3] 设A(a1,a2,,am)和B(b1,,bn)均为顺序表，A'和B分别为A和B

中除去最大共同前缀后的子表（例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大的共同前缀为(x,y,y,z)，在两表中除去最大共同前缀后的子表分别为

A'(x,z)和

B'(y,x,x,z)）。若

A'B'空表，则AB；若

A'空表，而B'空表，或者两者都不为空表，且A'的首元小于B'的首元，则

AB。试写一个比较A，B大小的算法（请注意：在算法中，不要破

第 2 页 共 8 页

‘坏原表A和B，并且，也不一定先求得A'和B才能进行比较）。

2.19[3] 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。

2.21[3] 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,,an)逆置为(an,an1a1)。

2.24[4] 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即Ａ表和Ｂ表）的结点空间构造Ｃ表。

2.25[4] 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其中元素为A和B中元素的交集，且表C的元素也依值递增有序排列。试对顺序表编写求C的算法。

2.29[5] 已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。

第三章

基础知识题

3.2[1] 简述栈和线性表的差别。

3.5[4] 假设以S和X分别表示入栈和出栈的操作，则初态和终态均为栈空的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列） 。试给出区分给定序列为合法或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。

3.8[3] 试推导求解n阶梵塔问题至少要执行的move操作的次数。

3.11[1] 简述队列和栈这两种数据类型的相同点和差异处。

第 3 页 共 8 页

3.14[4] 若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：

(1)能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；

(2)能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；

(3)既不能由输入受限的双端序列得到，也不能由输出受限的双端队列得到的输出序列。

算法设计题

3.17[3] 试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。

3.18[2] 试写一个判别表达式中开、闭括号是否配对出现的算法。

3.19[4] 假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”、方括号“[”和“]”和花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…）。编写判别给定表达式中所含括号是否正确配对出现的算法（已知表达式已存入数据元素为字符的顺序表中）。

3.21[3] 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式（即后缀表达式）。

第 4 页 共 8 页

3.27[5] 已知Ackerman函数的定义如下：

(1)写出递归算法； (2)写出非递归算法；

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

3.30[2] 假设将循环队列定义为：以域变量rear和length 分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。

第四章

基础知识题

4.3[1] 设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[1] 已知下列字符串

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=Replace(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.7[2] 令s=’aaab’, t=’abcabaa’, u=’abcaabbabcabaacbacba’。试分别求出他们的next函数值和nextval函数值。

4.8[2] 已知主串s=’ADBADABBAABADABBADADA’,

第 5 页 共 8 页

模式串pat=’ ADABBADADA’,

写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。

算法设计题

4.11[3] 编写算法，求得所有包含在串s中而不包含在串t中的u字符（s中重复的字符只选一个）构成的新串r，以及r中的每个字符在s中第一次出现的算法。

4.13[3] 编写算法，从串s中删除所有和串t相同的子串。

4.28[4] 假设以接点大小为1（带头结点）的链表结构表示串，则在利用next函数值进行串匹配时，在每个结点中需设三个域：数据域chdata、指针域succ、和指针域next。其中chdata域存放一个字符；succ域存放指向同一链表中后继结点的指针；next域在主串中存放指向同一链表中前驱结点的指针；在模式串中，存放指向当该结点的字符与主串中的字符不等时，模式串中下一个应进行比较的字符结点（即与该结点字符的next函数值相对应的字符结点）的指针，若该结点字符的next函数值为零，则其next域应指向头结点。试按上述定义的结构改写模式串的next函数值得算法。

4.30[5] 假设以定长顺序存储结构表示串，试设计一个算法，求串s和串t的一个最长公共子串，并分析你的算法的时间复杂度。若要求第一个出现的最长公共子串（即它在串s和串t的最左边的位置上出现）和所有的最长公共子串，讨论你的算法能否实现。

第五章

基础知识题

5.1假设有二维数组A6*8，每个元素相邻的6个字节存储，存储器按字节编址。已知A的起始位置（基地址）为1000，计算： (1)数组A的体积（即存储量）；

5.5[3]设有上三角矩阵(aij)n*n，将其上三角元素逐行存于数组B[m]中（m充分大），使得B[k]=aij且kf1(i)f2(j)c。试推导出函数f1,f2和常数c（要求f1,f2中不含常数项）。

5.8[3]设有一个准对角矩阵

第 6 页 共 8 页

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

写出由一对下标(i,j)求k的转换公式。

5.9[2]已知A为稀疏矩阵，试从空间和时间的角度采用两种不同的存储结构（二维数组和三元数组表）完成求aii 运算的优缺点。

i1n

算法设计题

5.18[5] 试设计一个算法，将数组An中的元素A[0]至A[n-1]循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O(n).

5.19[4] 若矩阵Am*n中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵Am*n，试编写求出矩阵中所有马鞍点的算法，并分析你的算法在最坏的情况下的时间复杂度。

5.23[2]三元组顺序表的一种变形是，从三元组顺序表中去掉行下标域得到二元组数序表，另设一个行起始向量，其每个分量是二元组顺序表的一个下标值，指示该行中第一个非零元素在二元组顺序表中的起始位置。试编写一个算法，由矩阵元素的下标值i,j求矩阵元素。试讨论这种方法和三元组顺序表相比有什么优缺点。

第 7 页 共 8 页

5.25[3] 若将稀疏矩阵A的非零元素以行序为主序的顺序存于一维数组V中，并用二维数组B表示A中的相应元素是否为零元素（以0和1分别表示零元素和非零元素）。例如，

表示。试写出一算法，实现在上述表示法中实现矩阵相加的运算。并分析你的算法的时间复杂度。

第 8 页 共 8 页