数据结构复习资料 第4章
第4章栈和队列
一、复习要点
本章主要讨论3种线性结构：栈、队列与优先级队列。这3种结构都是顺序存取的表，而且都是限制存取点的表。栈限定只能在表的一端（栈顶）插入与删除，其特点是先进后出。队列和优先级队列限定只能在表的一端（队尾）插入在另一端（队头）删除，不过优先级队列在插入和删除时需要根据数据对象的优先级做适当的调整，令优先级最高的对象调整到队头，其特点是优先级高的先出。而队列不调整，其特点是先进先出。这几种结构在开发各种软件时非常有用。
本章复习的要点：
1、基本知识点
要求理解栈的定义和特点，栈的抽象数据类型和在递归和表达式计算中的使用，在栈式铁路调车线上当进栈序列为1, 2, 3, , n时，可能的出栈序列计数，栈的顺序存储表示和链接存储表示，特别要注意，链式栈的栈顶应在链头，插入与删除都在链头进行。另外，需要理解队列的定义和特点，队列的抽象数据类型和在分层处理中的使用，队列的顺序存储表示（循环队列）和链接存储表示，需要注意的是，链式队列的队头应在链头，队尾应在链尾。还需要理解优先级队列的定义和特点。优先级队列的最佳存储表示是堆（heap），本章介绍的表示看懂即可。
2、算法设计
➢栈的5种操作（进栈、退栈、取栈顶元素、判栈空、置空栈）的在顺序存储表示下的实现，以及在链接存储表示下的实现。
➢使用栈的后缀表达式计算算法
➢循环队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现
➢链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现
二、难点和重点
1、栈：栈的特性、栈的基本运算
➢栈的数组实现、栈的链表实现
➢栈满及栈空条件、抽象数据类型中的先决条件与后置条件
2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示
3、队列：队列的特性、队列的基本运算
➢队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件
➢队列的链表实现：链式队列中的队头与队尾指针的表示、
三、习题的解析
4-2 铁路进行列车调度时, 常把站台设计成栈式结构的站台，
如右图所示。试问：
(1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构
的站台, 则可能的出栈序列有多少种?
()132)16/(16
12=*+C (2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出"进栈"或"出栈"的序列)。 【解答】
(1) 可能的不同出栈序列有 种。 (2) 不能得到435612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。
3
32
32
325
325 3256
32564 325641
1 1 13 135 **** ****
2 13542
135426
4-5 写出下列中缀表达式的后缀形式： (1) A * B * C (2) - A + B - C + D (3) A* - B + C (4) (A + B) * D + E / (F + A * D) + C 【解答】 (1) A B * C * (2) A - B + C - D + (3) A B - * C + (4) A B + D * E F A D * + / + C +
4-7 设表达式的中缀表示为a * x - b / x ↑2，试利用栈将它改为后缀表示ax * bx2↑/ -。写出转换过程中栈的变化。 【解答】
若设当前扫描到的运算符ch 的优先级为icp(ch)，该运算符进栈后的优先级为isp(ch)， isp 也叫做栈内(in stack priority )优先数，icp 也叫做栈外(in coming priority )优先数。当刚扫描到的运算符ch 的icp (ch )大于isp (stack )时，则ch 进栈；当刚扫描到的运算符ch 的icp (ch )小于isp (stack )时，则位于栈顶的运算符退栈并输出。从表中可知，icp (“(”)最高，但当“(”进栈后，isp(“(”)变得极低。其它运算符进入栈中后优先数都升1，这样可体现在中缀表达式中相同优先级的运算符自左向右计算的要求。运算符优先数相等的情况只出现在括号配对“)”或栈底的“;”号与输入流最后的“;”号配对时。前者将连续退出位于栈顶
的运算符，直到遇到“(”为止。然后将“(”退栈以对消括号，后者将结束算法。
步序扫描项项类型动作栈的变化输出
0 ☞ ';' 进栈, 读下一符号;
1 a 操作数☞直接输出, 读下一符号; A
2 * 操作符☞ isp ( ' ; ' ) < icp ( ' * ' ), 进栈, 读下一符号; * A
3 x 操作数☞直接输出, 读下一符号; * a x
4 - 操作符☞ isp ( ' * ' ) > icp ( ' - ' ), 退栈输出; a x *
☞ isp ( ' ; ' ) < icp ( ' - ' ), 进栈, 读下一符号;- a x *
5 b 操作数☞直接输出, 读下一符号;- a x * b
6 / 操作符☞ isp ( ' - ' ) < icp ( '/' ), 进栈, 读下一符号;-/ a x * b
7 x 操作数☞直接输出, 读下一符号;-/ a x * b x
8 ↑操作符☞ isp ( ' / ' ) < icp ( '↑' ), 进栈, 读下一符号;-/↑ a x * b x
9 2 操作数☞直接输出, 读下一符号;-/↑ a x * b x 2
10 ; 操作符☞ isp ( '↑' ) > icp ( ' ;' ), 退栈输出;-/ a x * b x 2↑
☞ isp ( ' / ' ) > icp ( ' ;' ), 退栈输出; - a x * b x 2↑/
☞ isp ( ' -' ) > icp ( ' ;' ), 退栈输出; a x * b x 2↑/
-
☞结束
4-9 假设以数组Q[m]存放循环队列中的元素, 同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(enqueue)和删除(dlqueue)元素的操作。
【解答】
循环队列类定义
#include
template
public:
Queue ( int=10 );
~Queue ( ) { delete [ ] elements;}
void EnQueue ( Type& item );
Type DeQueue ( );
Type GetFront ( );
void MakeEmpty ( ) { length = 0;}//置空队列
int IsEmpty ( ) const{ return length == 0; }//判队列空否
int IsFull ( ) const{ return length == maxSize; }//判队列满否
private:
int rear, length; //队尾指针和队列长度
Type *elements; //存放队列元素的数组
int maxSize; //队列最大可容纳元素个数}
template
//构造函数：建立一个最大具有maxSize个元素的空队列。
elements = new Type[maxSize]; //创建队列空间
assert ( elements != 0 ); //断言:动态存储分配成功与否}
template
//插入函数
assert ( ! IsFull ( ) );//判队列是否不满，满则出错处理
length++; //长度加1
rear =( rear +1) % maxSize;//队尾位置进1
elements[rear] = item;//进队列
}
template
//删除函数
assert ( ! IsEmpty ( ) );//判断队列是否不空，空则出错处理
length--;//队列长度减1
return elements[(rear-length+maxSize) % maxSize];//返回原队头元素值
}
template
//读取队头元素值函数
assert ( ! IsEmpty ( ) );
return elements[(rear-length+1+maxSize) % maxSize];//返回队头元素值
}
4-11 若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的插入(enqueue)和删除(dequeue)算法，并给出p为何值时队列空。
【解答】
链式队列的类定义
template
template
friend class Queue
private:
Type data; //数据域
QueueNode
public:
QueueNode ( Type d = 0, QueueNode *l = NULL ) : data (d), link (l) { } //构造函数};
template
public:
Queue ( ) : p ( NULL ) { }//构造函数
~Queue ( );//析构函数
void EnQueue ( const Type& item );//将item加入到队列中
Type DeQueue ( );//删除并返回队头元素
Type GetFront ( );//查看队头元素的值
void MakeEmpty ( );//置空队列，实现与~Queue ( ) 相同
int IsEmpty ( ) const{ return p == NULL;}//判队列空否
private:
QueueNode
template
//队列的析构函数
QueueNode
while ( p != NULL ) { s = p;p = p->link;delete s; }//逐个删除队列中的结点}
template
//队列的插入函数
if ( p == NULL ) {//队列空, 新结点成为第一个结点p = new QueueNode
}
else {//队列不空, 新结点链入p之后
QueueNode
s->link = p->link; p =p->link = s;//结点p指向新的队尾
}
}
队列的删除函数
template
//队列的插入函数
if ( p == NULL ) { cout << "队列空, 不能删除！" << endl; return 0; }
QueueNode
p->link = s->link; //重新链接, 将结点s从链中摘下
Type retvalue = s->data;delete s; //保存原队头结点中的值, 释放原队头结点
return retvalue; //返回数据存放地址
}
队空条件p == NULL。
四、其他练习题
4-16 单选题
(1) 栈的插入和删除操作在________进行。
A 栈顶
B 栈底
C 任意位置
D 指定位置
(2) 当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行________语句修改top指针。
A top++;
B top--;
C top = 0;
D top;
(3) 若让元素1,2,3依次进栈，则出栈次序不可能出现________种情况。
A 3,2,1
B 2,1,3
C 3,1,2
D 1,3,2
(4) 在一个顺序存储的循环队列中，队头指针指向队头元素的________位置。
A 前一个
B 后一个
C 当前
D 后面
(5) 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为________。
A n-2
B n-1
C n
D n+1
(6) 从一个顺序存储的循环队列中删除一个元素时，首先需要________。
A 队头指针加一
B 队头指针减一
C 取出队头指针所指的元素
D 取出队尾指针所指的元素
(7) 假定一个顺序存储的循环队列的队头和队尾指针分别为f和r，则判断队空的条件为________。
A f+1 == r
B r+1 == f
C f == 0
D f == r
(8) 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为________。
A front == rear
B front != NULL
C rear != NULL
D front == NULL
【解答】
(1) A (2) B (3) C (4) A (5) B (6) B
(7) D (8) D
4-17 填空题
(1) 队列的插入操作在________进行，删除操作在________进行。
(2) 栈又称为________的表，队列又称为________的表。
(3) 向一个顺序栈插入一个元素时，首先使________后移一个位置，然后把待插入元素________到这个位置上。
(4) 从一个栈删除元素时，需要前移一位________。
(5) 在一个循环队列Q中，判断队空的条件为________，判断队满的条件为________。
(6) 在一个顺序栈中，若栈顶指针等于________，则为空栈；若栈顶指针等于________，则为满栈。
(7) 在一个链式栈中，若栈顶指针等于NULL则为________；在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为________或该队列________。
(8) 向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给________，然后把新结点的存储位置赋给________。
(9) 向一个循环队列中插入元素时，需要首先移动________，然后再向所指位置________新插入的元素。
(10) 当用长度为n的数组顺序存储一个栈时，若用top == n表示栈空，则表示栈满的条件为________。
(11) 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行________和________操作。
(12) 从一个栈顶指针为top的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行________操作。
(13) 假定front和rear分别为一个链式队列的队头和队尾指针，则该链式队列中只有一个结点的条件为________。
(14) 中缀表达式3*(x+2)-5所对应的后缀表达式为________。
(15) 后缀表达式“4 5 * 3 2 + -”的值为________。
【解答】
(1) 队尾，队头
(2) 后进先出，先进先出
(3) 栈顶指针，写入
(4) 栈顶指针
(5) Q.front == Q.rear，(Q.rear+1) % MaxSize+1 == Q.front
(6) –1，MaxSize-1
(7) 空栈，空，只含有一个结点
(8) 新结点的指针域，栈顶指针
(9) 队尾指针，写入
(10) top == 0
(11) p->link = top，top = p
(12) top = top->link
(13) front == rear && front != NULL或者front == rear && rear != NULL
(14) 3 x 2 + * 5 -
(15) 15
4-18 设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？
【解答】
3
4-19 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行下列哪一个操作？
(1) top->link = s;(2)s->link = top->link;top->link = s;
(3) s->link = top;top = s;(4) s->link = top;top = top->link;
【解答】
(3)
4-20 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列哪一个操作？
(1) x = top->data;top = top->link;(2) top = top->link;x = top->data;
(3) x = top;top = top->link;(4) x = top->data;
【解答】
(1)
4-21 设循环队列的结构是
const int MaxSize = 100;
typedef int DataType;
typedef struct {
DataType data[MaxSize];
int front, rear;
} Queue;
若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句？
(1) Q.front == Q.rear;(2) Q.front - Q.rear == MaxSize;
(3) Q.front + Q.rear == MaxSize;(4) Q.front == (Q.rear+1) % MaxSize;
【解答】
(4)
4-22 设循环队列的结构如4-21。若有一个Queue类型的队列Q，试问应用下列哪一个语句计算队列元素个数？
(1) (Q.rear - Q.front + MaxSize ) % MaxSize;(2) Q.rear - Q.front +1;
(3) Q.rear - Q.front -1;(4) Q.rear - Qfront;
【解答】
(1)
4-23 假设以数组Q[m]存放循环队列中的元素, 同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(EnQueue)和删除(DlQueue)元素的操作。
【解答】
队空：length == 0 队满：length == Maxsize
4-24 所谓回文，是指从前向后顺读和从后向前倒读都一样的不含空白字符的串。例如did，madamimadam，pop即是回文。试编写一个算法，以判断一个串是否是回文。
【解答1】
将字符串中全部字符进栈，然后将栈中的字符逐个与原字符串中的字符进行比较。算法如下：
int palindrome ( char A[ ], int n ) {
stack
int yes = 1, i = 0;
while( A[i] != “\0” ) { st.Push ( A[i] );i++; }//扫描字符串，所有字符进栈
i = 0;
while( A[i] != “\0” )//比较字符串
if ( A[i] == st.GetTop ( ) ) { st.Pop ( );i++; }
else { yes = 0; break; }
return yes;
}
【解答2】
采用递归算法，判断从s到e中的字符串是否回文，通过函数返回是或不是。
int palindrome ( char A[ ], int s, int e ) {
if ( A[s] != A[e] ) return 0;
else if ( s > e ) return 1;
else palindrome ( A, s+1, e-1 );
}
4-25 借助栈实现单链表上的逆置运算。
【解答】由于进栈与出栈顺序正好相反，因此，借助栈可以实现单链表的逆置运算。方法是让单链表中的结点依次进栈，再依次出栈。
#include "stack.h"
#include "LinkList.h"
template
Stack
ListNode
while ( p != NULL ) { S.Push(p); p = p.Next ( ); } //依次将链中结点进栈
p = L.Firster ( );p->setLink ( NULL ); //单链表表头结点链指针置空
while ( !S.IsEmpty( ) ) { //将栈中保存的结点依次出栈
q = S.GetTop ( );S.Pop ( );
q->SetLink ( p->getLink ( ) );//链入逆置后的链中
p->setLink ( q );
p = p->getLink ( );
}
}
4-27试编写一个算法，检查一个程序中的花括号、方括号和圆括号是否配对，若能够全部配对则返回1，否则返回0。
【解答】在算法中，扫描程序中的每一个字符，当扫描到每个花、中、圆左括号时，令其进栈，当扫描到花、中、圆右括号时，则检查栈顶是否为相应的左括号，若是则作退栈处理，若不是则表明出现了语法错误，应返回0。当扫描到程序文件结尾后，若栈为空则表明没有发现括号配对错误，应返回1，否则表明栈中还有未配对的括号，应返回0。另外，对于一对单引号或双引号内的字符不进行括号配对检查。
根据分析，编写出算法如下：
#include
#include“stack.h”
int BracketsCheck ( char* fname) {
//对由fname所指字符串为文件名的文件进行括号配对检查
ifstream ifstr ( fname, ios::in|ios::nocreate );
//用文件输入流对象ifstr打开以fname所指字符串为文件名的文件
if ( !ifstr ) {
cerr << "File" << "\'" << fname << "\'"<< "not found!" << endl;
exit (1);
}
stack
while ( ifstr >> ch ) {//顺序扫描文件中的每一个字符
if ( ch == 39 ) {//单引号内的字符不参与配对比较
while ( ifstr >> ch )
if ( ch == 39 ) break; //39为单引号的ASCII值
if ( !ifstr ) return 0;
}
else if ( ch == 34 ) {//双引号内的字符不参与配对比较
while ( ifstr >> ch )
if ( ch == 34 ) break;//34为双引号的ASCII值
if ( !ifstr ) return 0;
}
switch ( ch ) {
case '{' : case '[' : case '(' :S.Push(ch); break;//出现以上三种左括号则进栈
case '}' : if ( S.GetTop( ) == '{' ) S.Pop( ); //栈顶的左花括号出栈
else return 0; break;
case ']' : if ( S.GetTop ( ) == '[' ) S.Pop( );//栈顶的左中括号出栈
else return 0; break;
case ')' : if ( S.GetTop( ) == '(' ) S.Pop( );//栈顶的左圆括号出栈
else return 0;
}
}
if ( S.IsEmpty( ) ) return 1;
else return 0;
}
数据结构第四章考试题库(含答案)
第四章串 一、选择题 1．下面关于串的的叙述中，哪一个是不正确的（）【北方交通大学 2001 一、5（2分）】 A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index (S2,‘8’),length(S2))) 其结果为（）【北方交通大学 1999 一、5 （25/7分）】A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234 3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（） A．求子串 B．联接 C．匹配 D．求串长 【北京邮电大学 2000 二、4（20/8分）】【西安电子科技大学 1996 一、1 （2分）】 4．已知串S=‘aaab’,其Next数组值为（）。【西安电子科技大学 1996 一、
7 （2分）】 A．0123 B．1123 C．1231 D．1211 5．串‘ababaaababaa’的next数组为（）。【中山大学 1999 一、7】A．0 B．012121111212 C．0 D．0 6．字符串‘ababaabab’的nextval 为（） A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1) C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 ) 【北京邮电大学 1999 一、1（2分）】 7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval 数组的值为（）。 A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1 【北京邮电大学 1998 二、3 （2分）】 8．若串S=’software’,其子串的数目是（）。【西安电子科技大学 2001应用一、2（2分）】
数据结构课后习题答案第四章
第四章 一、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答： ●空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 ●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 ●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 ●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。 ●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。 二、假设有如下的串说明： char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p; (1)在执行如下的每个语句后p的值是什么? p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); (3)调用函数strcmp(s1,s2)的返回值是什么?
数据结构答案第4章
第4xxxx线性表——多维数组和xx表 2005-07-14 第4章广义线性表——多维数组和广义表课后习题讲解 1.填空 ⑴数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。 【解答】存取，修改，顺序存储 【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。 ⑵二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。 【解答】1140 【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是 1000+140=1140。 ⑶设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。 【解答】d+41 【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。 ⑷稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。 【解答】三元组顺序表，十字链表
⑸广义表((a),(((b),c)),(d))的长度是（），深度是（），表头是（），表尾是（）。 【解答】3，4，(a)，((((b),c)),(d)) ⑹已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b 的运算是（）。 【解答】Head(Head(Tail(LS))) 2.选择题 ⑴二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。 A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A[8][5] I A[3][10] J A[5][8] K A[4][9] 【解答】D，E，K 【分析】数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元，第8列和第5行共有18个元素（注意行列有一个交叉元素），所以，共占108个字节，元素A[8][5]按行优先存储的起始地址为 d+8×10+5=d+85，设元素A[i][j]按列优先存储的起始地址与之相同，则 d+j×9+i=d+85，解此方程，得i=4，j=9。 ⑵将数组称为随机存取结构是因为（） A数组元素是随机的B对数组任一元素的存取时间是相等的 C随时可以对数组进行访问D数组的存储结构是不定 【解答】B ⑶下面的说法中，不正确的是（）
数据结构课后习题及解析第四章
第四章习题 1. 设s=’I AM A STUDENT’,t=’GOOD’,q=’WORKER’。给出下列操作的结果： StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,’A’,4);StrReplace(s,’STUDENT’,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); 2. 编写算法，实现串的基本操作StrReplace(S,T,V)。 3. 假设以块链结构表示串，块的大小为1，且附设头结点。 试编写算法，实现串的下列基本操作： StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； StrCat(S,T)； SubString(Sub,S,pos,len)。 4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。 5．已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将S转换为T. 6．S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。 7．S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。 以下算法用定长顺序串： 8．编写下列算法： （1）将顺序串r中所有值为ch1的字符换成ch2的字符。
（2）将顺序串r中所有字符按照相反的次序仍存放在r中。 （3）从顺序串r中删除其值等于ch的所有字符。 （4）从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。 （5）从顺序串r中删除所有与串r1相同的子串。 9．写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。 10．写算法，实现顺序串的基本操作StrCompare(s,t)。 11．写算法，实现顺序串的基本操作StrReplace(&s,t,v)。 实习题 1．已知串S和T，试以以下两种方式编写算法，求得所有包含在S中而不包含在T中的字符构成的新串R，以及新串R中每个字符在串S中第一次出现的位置。 （1）利用CONCAT、LEN、SUB和EQUAL四种基本运算来实现。 （2）以顺序串作为存储结构来实现。 2．编写一个行编辑程序EDLINE，完成以下功能： （1）显示若干行：list [[n1]-[n2]]：显示第n1行到第n2行，n1缺省时，从第一行开始，n2缺省时，到最后一行， （2）删除若干行。del [[n1]-[n2]]： n1、n2说明同（1）。 （3）编辑第n行。edit n：显示第n行的内容，另输入一行替换该行。 （4）插入一行。ins n：在第n行之前插入一行。
数据结构复习要点(整理版)
第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2.数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 （补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。） 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。（有时候也叫做属性。） 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 （1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2.线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3.树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4.图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个（或零个）直接后继。 （2）数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。 想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1.顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2.链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5.时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n无关系T(n)=O(1) 2.线性阶：算法的时间复杂度与问题规模n成线性关系T(n)=O(n) 3.平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 《数据结构》第四章习题 一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”） 1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。( √) 2、串是一种数据对象和操作都特殊的线性表。( √) 3、只包含空白字符的串称为空串（空白串）。( ×) 4、稀疏矩阵压缩存储后，必会（不会）失去随机存取功能。( ×) 5、使用三元组表示稀疏矩阵的非零元素能节省存储空间。( √) 6、插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常使用。（×） 7、若采用三元组表存储稀疏矩阵，只要把每个元素的行下标和列下标互换（错的），就完成了对该矩阵的转置运算。（×） 二、单项选择题 1．下面关于串的的叙述中，哪一个是不正确的？（ B ） A．串是字符的有限序列B．空串是由空格构成的串（空串是长度为零的串）C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．有串S1=’ABCDEFG’，S2 = ’PQRST’，假设函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回中s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（ D ）。 A．BCDEF B．BCDEFG C．BCPQRST D．CDEFGFG 3、串的长度是指（ B ） A．串中所含不同字母的个数B．串中所含字符的个数 C．串中所含不同字符的个数D．串中所含非空格字符的个数 三、填空题 1、串是一种特殊的线性表，其特殊性表现在_数据元素为字符，操作集也不同__；串的两种最基本的存储方式是_顺序存储_、__ 链式存储_；两个串相等的充分必要条件是__两串的长度相等且两串中对应位置的字符也相等__。 2、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_O(m+n)__。 3、模式串P=‘abaabcac’的next函数值序列为_{-1,0,0,1,1,2,0,1}___。 4、已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为__1340___。 四、综合题 1、KMP算法较Brute-Force算法有哪些改进? 【解答】 朴素的模式匹配（Brute－Force）时间复杂度是O（m*n），KMP算法有一定改进，时间复杂度达到O（m＋n）。KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。 2、课本P183 4.1题 【解答】 A[2][2] = 644+2*n+2 = 676 A[3][3] = 644+3*n+3 = 692 3、课本P184 4.7题 《数据结构》第四章串习题 《数据结构》第四章串习题 基本概念题： 4-1 设S1 =“Data Structure Course”，S2 =“Structure”，S3 =“Base”，求：（1）Length(S1)；（2）Compare(S2, S3)； （3）Insert(S1, 5, S3)；（4）Delete(S1, 5, 9)； （5）SubString(S1, 5, 9, T)；（6）Search(S1, 0, S2)； （7）Replace(S1, 0, S2, S3) 4-2 什么叫串？串和字符在存储方法上有什么不同？空串和空格串是否相同，为什么？ 4-3 串是由字符组成的，长度为1的串和字符是否相同。为什么？ 4-4 串是不定长的，表示串的长度有几种方法？C语言中的串采用哪种方法？ 4-5 可以说串是数据类型固定为字符类型的线性表，但是串操作和线性表操作的主要不同之处在哪里？ 4-6 可以用几种存储方法存储串？ 4-7 分别写出串的静态数组存储结构和串的动态数组存储结构的结构体定义。 4-8 为什么动态数组结构下串的实现要增加撤消函数？ 复杂概念题： 4-9 令t1=“aaab”, t2=“abcabaa”, t3=“abcaabbabcabaacba”，试分别求出他们的next[j]值。 4-10 简述模式匹配的Brute-Force算法思想。简述模式匹配的KMP算法思想。 4-11 简述求子串的next[j]值的算法思想。 算法设计题： 4-12 设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有等于和不等于两种情况。 4-13 设串采用静态数组存储结构，编写函数实现两个串的比较 第4章栈和队列 一、复习要点 本章主要讨论3种线性结构：栈、队列与优先级队列。这3种结构都是顺序存取的表，而且都是限制存取点的表。栈限定只能在表的一端（栈顶）插入与删除，其特点是先进后出。队列和优先级队列限定只能在表的一端（队尾）插入在另一端（队头）删除，不过优先级队列在插入和删除时需要根据数据对象的优先级做适当的调整，令优先级最高的对象调整到队头，其特点是优先级高的先出。而队列不调整，其特点是先进先出。这几种结构在开发各种软件时非常有用。 本章复习的要点： 1、基本知识点 要求理解栈的定义和特点，栈的抽象数据类型和在递归和表达式计算中的使用，在栈式铁路调车线上当进栈序列为1, 2, 3, , n时，可能的出栈序列计数，栈的顺序存储表示和链接存储表示，特别要注意，链式栈的栈顶应在链头，插入与删除都在链头进行。另外，需要理解队列的定义和特点，队列的抽象数据类型和在分层处理中的使用，队列的顺序存储表示（循环队列）和链接存储表示，需要注意的是，链式队列的队头应在链头，队尾应在链尾。还需要理解优先级队列的定义和特点。优先级队列的最佳存储表示是堆（heap），本章介绍的表示看懂即可。 2、算法设计 ➢栈的5种操作（进栈、退栈、取栈顶元素、判栈空、置空栈）的在顺序存储表示下的实现，以及在链接存储表示下的实现。 ➢使用栈的后缀表达式计算算法 ➢循环队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现 ➢链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现 二、难点和重点 1、栈：栈的特性、栈的基本运算 ➢栈的数组实现、栈的链表实现 ➢栈满及栈空条件、抽象数据类型中的先决条件与后置条件 2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示 3、队列：队列的特性、队列的基本运算 ➢队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件 ➢队列的链表实现：链式队列中的队头与队尾指针的表示、 三、习题的解析 4-2 铁路进行列车调度时, 常把站台设计成栈式结构的站台， 如右图所示。试问： (1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构 的站台, 则可能的出栈序列有多少种? 习题 4.1选择题 1、空串与空格串是（B）。 A、相同 B、不相同Ｃ、不能确定 2、串是一种特殊的线性表，其特殊性体现在（B）。 A、可以顺序存储 B、数据元素是一个字符 C、可以链式存储 D、数据元素可以是多个字符 3、设有两个串p和q，求q在p中首次出现的位置的操作是（B）。 A、连接 B、模式匹配 C、求子串 D、求串长 4、设串s1=“ABCDEFG”，s2=“PQRST”函数strconcat（s，t）返回s和t串的连接串，strsub（s，i，j）返回串s中从第i个字符开始的、由连续j个字符组成的子串。strlength(s)返回串s的长度。则strconcat（strsub（s1，2，strlength（s2）），strsub（s1，strlength（s2），2））的结果串是（D）。 A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 5、若串s=“software”，其子串个数是（B）。 A、8 B、37 C、36 D、9 4.2简答题 1、简述空串与空格串、主串与子串、串名与串值每对术语的区别？ 答：空串是指长度为0的串，即没有任何字符的串。 空格串是指由一个或多个空格组成的串，长度不为0。 子串是指由串中任意个连续字符组成的子序列，包含子串的串称为主串。 串名是串的一个名称，不指组成串的字符序列。 串值是指组成串的若干个字符序列，即双引号中的内容。 2、两个字符串相等的充要条件是什么？ 答：条件一是两个串的长度必须相等 条件二是串中各个对应位置上的字符都相等。 3、串有哪几种存储结构？ 答：有三种存储结构，分别为：顺序存储、链式存储和索引存储。 4、已知两个串：s1=”fg cdb cabcadr”, s2=”abc”, 试求两个串的长度，判断串s2是否是串s1的子串，并指出串s2在串s1中的位置。 答：（1）串s1的长度为14，串s2的长度为3。 （2）串s2是串s1的子串，在串s2中的位置为9。 5、已知：s1=〃I’m a student〃，s2=〃student〃，s3=〃teacher〃，试求下列各操作的结果： strlength(s1)；答：13 strconcat(s2,s3)；答：”studentteachar” strdelsub(s1,4,10)；答：I’m 6、设s1=”AB”，s2=”ABCD”，s3=”EFGHIJK，试画出它们在各种存储结构下的结构图。答： 顺序存储方式下： 第4章串、数组和广义表 一、填空题 1、零个或多个字符组成的有限序列称为串。 二、判断题 1、稀疏矩阵压缩存储后，必会失去随机存取功能。（√） 2、数组是线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（╳） 3、若采用三元组存储稀疏矩阵，把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。（╳） 4、若一个广义表的表头为空表，则此广义表亦为空表。（╳） 5、所谓取广义表的表尾就是返回广义表中最后一个元素。（╳） 三、单项选择题 1、串是一种特殊的线性表，其特殊性体现在（B）。 A．可以顺序存储B．数据元素是一个字符 C．可以链式存储D．数据元素可以是多个字符若 2、串下面关于串的的叙述中，（B）是不正确的？ A．串是字符的有限序列B．空串是由空格构成的串 C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储 解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。 3、串“ababaaababaa”的next数组为（C）。 A．012345678999 B．012121111212 C．011234223456 D．0123012322345 4、串“ababaabab”的nextval为（A）。 A．010104101B．010102101 C．010100011 D．010101011 5、串的长度是指（B）。 A．串中所含不同字母的个数B．串中所含字符的个数 C．串中所含不同字符的个数D．串中所含非空格字符的个数 解释：串中字符的数目称为串的长度。 6、假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（B）。 A．808 B．818 C．1010 D．1020 解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。 7、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（B）。A．BA+141 B．BA+180 C．BA+222 D．BA+225 解释：以列序为主，则LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。 8、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（C）。 A．13 B．32 C．33 D．40 9、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定a ij（i 数据结构复习资料 第一章绪论 1.1基本概念和术语 1.数据是对客观事物的符号表示；数据元素是数据的基本单位，一个数据元素可由若干个数据项组成，数据项是数据的不可分割的最小单位；数据对象是性质相同的数据元素的集合，是数据的一个子集。 2.数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 3. A.数据结构的三要素：①数据的逻辑结构②数据的存储结构③数据的运算（算法） B.任何一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构 4.数据的逻辑结构:①集合②线性结构③树型结构④图状结构或网状结构 1.2算法和算法分析 1.算法的五个特性：①有穷性②确定性③可行性④输入⑤输出 2.时间复杂度：时间复杂度是指执行算法所需要的计算工作量 空间复杂度：空间复杂度是指执行这个算法所需要的内存空间 第二章线性表 2.1线性表的顺序表示和实现 1.线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 2.优点：线性表的顺序存储结构是一种随机存取的存储结构 3.顺序线性表插入： 顺序线性表删除： 4.线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(可连续，可不连续) 5.对数据元素来说，除了存储其自身的信息之外，还需存储一个指示其直接后继的信息(存储位置)，这两部分信息组成数据元素的存储映像，称为结点。他包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或域。N个结点链结成一个链表，即为线性表的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称为线性链表或单链表。 6.链表的插入与删除 7.双向链表的插入与删除 第三章栈和队列 3.1 栈 1．栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应的，表头端称为栈底。不含元素的空表称为空栈。 2.栈又称为后进先出的线性表 3.栈的进栈与出栈操作 第四章串 习题4 一、选择题 1.串是一种特殊的线性表，其特殊性体现在（）。 A.可以顺序存储 B.数据元素是一个字符 C.可以连接存储 D.数据元素可以是多个字符 2.有两个串P和Q，求P在Q中首次出现的位置的运算称为（）。 A.模式匹配 B.联接 C.求子串 D.求串长 3.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（）。 A.n2 B.（n2/2）+（n/2） C.（n2/2）+（n/2）-1 D.（n2/2）-（n/2）-1 4.设串s1=“ABCDEFG”,s2=“PQRST”，函数concat（x，y）返回x和y串的连接串，subString（s，i，j）返回串s的从序号i的字符开始的j个字符组成的子串，Strlength（s）返回串s的长度，则concat（subString（s1，2，Strlength （s2）），subString(s1，Strlength（s2），2)））的结果串是（）。 A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 5.顺序串中，根据空间分配方式的不同，可分为（）。 A.直接分配和间接分配 B.静态分配和动态分配 C.顺序分配和链式分配 D.随机分配和固定分配 6.设串S=“abcdefgh”，则S的所有非平凡子串（除空串和S自身的串）的个数是（）。 A.8 B.37 C.36 D.35 7.设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（）。 A.O(m) B.O（n） C.O（m+n） D.O（n*m） 8.已知串S=“aaab”，其next数组值为（）。 A.0123 B.1123 C.1231 D.1211 二丶填空题 1.在空串和空格串中，长度不为0的是（）。 2.空格串是指（），其长度等于（）。 3.按存储结构的不同，串可分为（）、（）和（）。 4.C语言中，以字符（）表示串值的终结。 5.在块链串中，为了提高存储密度，应该增大（）。 6.假设每个字符占1个字节，若结点大小为4个字节的链串的存储密度为50％，则其每个指针占（）个字节。 7.串操作虽然较多，但都可以通过五中基本操作（）、（）、（）、（）和（）构成的最小子集中的操作来实现。 8.设串S=“Ilikecomputer.”，T=“com”，则Length（S）=（），Index（S,T,1）=（）。 9.在KMP算法中，next[j]只与（）串有关，而与（）串无关。 10.字符串“ababaaab”的nextval函数值为（）。 11.两个字符串相等的充分必要条件是（）。 12.实现字符串复制的函数strcpy为： 数据结构答案第4章 第4xxxx线性表--- 多维数组和xx表 2005-07-14第4章广义线性表一一多维数组和广义表课后习题讲解 1. 填空 ⑴数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。 【解答】存取，修改，顺序存储 【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。 ⑵二维数组A中行下标从10到20,列下标从5到10,按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000,则元素A[15][10]的存储地址是（）。 【解答】1140 【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了（1510） X 6椅元素，每个元素占4个存储单元，所以，其存储地址是1000+140=114（! ⑶设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d,每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。 【解答】d+41 【分析】元素A[8][5]的前面共存储了（1+2+ +8）+5=4价元素。 ⑷稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。 【解答】三元组顺序表，十字链表 ⑸广义表（（a）, （（（b）,c））,（d））勺长度是（），深度是（），表头是（），表尾是 【解答】3, 4, (a), ((((b),c)),(d)) ⑹已知广义表LS=(a (b, c, d), e),用Head和Tail函数取出LS中原子b 的运算是 ()。 【解答】Head(Head(Tail(LS))) 2. 选择题 ⑴二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8, 列下标的范围是从0~9,则存放A至少需要()个字节，A的第8列和第5行共占()个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的()元素的起始地址一致。 A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A[8][5] I A[3][10] J A[5][8] K A[4][9] 【解答】D, E, K 列和8个存储单元，第90X 6=54(￡少需要A个元素，所以，存放90列，共有10行9为A【分析】数组.第5行共有18个元素(注意行列有一个交叉元素)，所以，共占108个字节，元素A[8][5]按行优先存储的起始地址为d+8 x 10+5=d+85设元素A[i][j]按列优先存储的起始地址与之相同，贝U d+j x 9+i=d+85军此方程，得i=4, j=9。 ⑵将数组称为随机存取结构是因为() A数组元素是随机的B对数组任一元素的存取时间是相等的 C随时可以对数组进行访问D数组的存储结构是不定 【解答】B ⑶下面的说法中，不正确的是() A数组是一种线性结构B数组是一种定长的线性结构 C除了插入与删除操作外，数组的基本操作还有存取、修改、检 习题4 1. 填空题 （1）一般来说，数组不执行（___________）和（___________）操作，所以通常采用（___________）方法来存储数组。通常有两种存储方式：（___________）和（___________）。 答案：删除 插入 顺序存储 行优先存储 列优先存储 （2）设8行8列的二维数组起始元素为A[0][0]，按行优先存储到起始元素下标为0的一维数组B 中，则元素B[23]在原二维数组中为（___________）。若该二维数组为上三角矩阵，按行优先压缩存储上三角元素到起始元素下标为0的一维数组C 中，则元素C[23]即为原矩阵中的（___________）元素。 答案：A[2][7] A[3][5] （3）设二维数组A 为6行8列，按行优先存储，每个元素占6字节，存储器按字节编址。已知A 的起始存储地址为1000H ，数组A 占用的存储空间大小为（___________）字节，数组A 的最后一个元素的下标为（___________），该元素的第一个字节地址为（___________）H ，元素A[1][4]的第一个字节的地址为（___________）H 。（提示：下标从0开始计） 答案：288 A[5][7] 111AH 1048H （4）设C++中存储三维数组A mnp ，则第一个元素为a 000，若按行优先存储，则a ijk 前面共有（___________）个元素；若按列优先存储，则a ijk 前面共有（___________）个元素。 答案：inp+jp+k i+mj+mnk （5）常见的稀疏矩阵压缩方法有：（___________）和（___________）。 答案：三元组表 十字链表 （6）广义表（（a ），（（b ，c ），d ），（e ））的长度为（___________），表头为（___________），表尾为（___________）。 答案：3 （a ） （（（b ，c ），d ），（e ）） （7）设广义表LS ＝（（a ），（（b ，c ），d ），（e ）），若用取表头操作GetHead （）和取表尾操作GetTail （）进行组合操作，则取出元素b 的运算为（___________）。 答案：GetHead(GetHead(GetHead(GetTail(LS)))) （8）若广义表A 满足GetHead （A ）＝GetTail （A ），则A ＝（___________）。 答案：（（）） 2. 问答题 （1）根据下面的矩阵，写出矩阵转置后的三元组表，起始行列值为1。 ⎪⎪⎪⎪⎪⎪⎪⎪⎭ ⎫ ⎝⎛-00000015000001800000130001400003005000000009120 第4～5章串和数组练习题 一、填空题 1. 称为空串； 称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)= , “/”的字符定位的位置为。 4. 子串的定位运算称为串的模式匹配；称为目标串， 称为模式。 5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第次匹配成功。 6. 若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为。 7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量） 为；末尾元素A57的第一个字节地址为；若按行存储时，元素A14的第一个字节地址为；若按列存储时，元素A47的第一个字节地址为。 8. 设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存.储地址为。 9. 三元组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。 10.求下列广义表操作的结果： （1）GetHead【((a,b),(c,d))】=== ; （2）GetHead【GetTail【((a,b),(c,d))】】=== ; （3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ; （4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ; 二、单选题 （）1. 串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （）2. 设有两个串p和q，求q在p中首次出现的位置的运算称作： 第四章串 ◎课后思考题及解答： 思考题： 1＞名词解释：字符串、空串、空格串、串相等、子串和主串 字符串：由零个或多个字符组成的有限序列。 空串：零个字符的串称为空串，记作“ 0"或"0 空格串：由一个或多个空格组成的串。 串相等：两个串相等，当且仅当：其两个串的长度相等,并且各个对应位置的字符都相等。子串：串中任意个连续的字符组成的子序列 主串：包含子串的串 2、串的两种最基木的存储方式是顺序存储和链式存储 3、两个串相等的充分必要条件是其两个串的长度相等■并且各个对应位置的字符都相等 4、设模式串为t= "abaabcac"，请写出该模式串的next函数值序列。 序列：01122312 前两个字母next序列分别为01,直接写上 第三个怙’时,它前一个字母为b从头开始字母为4a!=b所以为1 第四个“才时,前字母为a从头开始字母为aa=a所以值为1 + 1=2 （相等时为串长加1） 第五个“b”,前个字母为a从头开始a沪a为2 第六个叱:前个字母为b,再往前是aab,从头开始ab串，ab=ab,因此值为2+1 = 3 第七个字母为卞：前个字母为C与从头开始的第一个字母不相等，所以为1 第八个为叱:前个字母为耳与开始第一个字母相等，因此为2 5、编写算法，从字符串S中删除所有和字符串T相同的子串。 6、（1）釆川顺序结构存储串，设计一个算法计算一个子串在一个字符串屮出现的次数，如果该子串不出现则为0。 （2）假设以链式存储结构表示串。设计一个将串t插入到串s中某个字符（第一次出现）之前的算法（若s屮不存在此字符，则将串t连接在串s的末尾）。 第五章数组和广义表 ◎木章小结: 数组和广义表 本章讨论的购种数拯结构一数组和广义表町以看成是线性衣的扩展，即农中的数据元索本乃也是-个线性茨. 线件农八仃相同类住的数据兀索的仃限序列・ 将元倉的类空进行扩充 回忆： 什么足线性衣？ 线性衣一从有相同类 | ■制捕;、需点：数抑;兀索郁足非结构的原/类巾，元纵的 ffl足不再分割的. 理一一仅任农兄进行插入和删除操*的线杵农. 队列―住必进h MiAttfl .血刃端进行郦操作的线性 农. 申一冬个或多个字符组成的右眼胖列・限制元素类巾为7符广 义 线 性 衣 （女维）数组线性鸟屮的数据尤索对以足 线性衣，但所右尤索的类型相同。 广义表—线性我中的数抑:元索nJ以足线性衣, 1T簸的类型町以不相同. 线性及一 JUffll同类屯的数据元索的冇限庁列.《数据结构》第四章习题参考答案
《数据结构》第四章串习题
数据结构复习资料 第4章
数据结构(C语言版)习题及答案第四章
《数据结构及其应用》笔记含答案 第四章_串、数组和广义表
数据结构期末复习资料
数据结构课后习题第四章
数据结构答案第4章
数据结构第四章参考答案
数据结构第4—5章练习题
《数据结构教学资料》4-10章复习资料.doc