下载文档原格式
第 4 章广义线性表——多维数组和广义表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按列优先方式存储时的（）元素的起始地址一致。
11． 写算法，实现顺序串的基本操作 StrReplace(&s,t,v)r1 中第 index 个字符起求出首次与串 r2 相同的子串的起始位置。
写一个函数将顺序串 s1 中的第 i 个字符到第 j 个字符之间的字符用 s2 串替换。
写算法，实现顺序串的基本操作 StrCompare(s,t) 。
第四章习题1. 设 s=' I AM A STUDENT , t= ' GOO D,q=' WORKER 给出下列操作的结果: StrLength(s); SubString(sub1,s,1,7);SubString(sub2,s,7,1);StrIndex(s, ' A ' ,4); StrReplace(s, ' STUDEN 'T,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 个字符。
1、已知无向连通网的邻接矩阵如下所示，试画出该无向连通网以及所对应的最小生成树。
2、对于给定的5个字符w ={a 、b 、c 、d 、e} ，它们出现的频率分别为 0.15 ， 0.25，0.20，0.05， 0.35请求出：①构造出赫夫曼树。
②WPL 值。
带权路径长度WPL=0.15*3+0.05*3+0.2*2+0.25*2+0.35*2=2.2 0.2 0.60 0.4 0.05 0.150.20.25 0.35 1.00 0 0 1 111 0 e b c ad 1、数据的逻辑结构被形式地定义为B=（K ，R ），其中K 是数据元素的有限集合，R是K上的（D）有限集合。
A、操作B、映像C、存储D、关系2、数据结构在计算机内存中的表示是指（ A ）A、数据的存储结构B、数据结构C、数据的逻辑结构D、数据元素之间的关系3、在数据结构中，与所使用的计算机无关的是数据的（ A ）结构。
A、逻辑B、存储C、逻辑和存储D、物理4、在数据结构中，从逻辑上可以把数据结构分成（ C ）A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构5、数据结构在计算机内存中的表示是指（ A ）A、数据的存储结构B、数据结构C、数据的逻辑结构D、数据元素之间的关系6、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ C ）。
A、数据的处理方法B、数据元素的类型C、数据元素之间的关系D、数据的存储方法7、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素的方法以及它们之间的（ B ）和运算等的学科。
A、结构B、关系C、运算D、算法8、数据的（B）包括集合、线性、树形和图状结构四种基本类型。
A、存储结构B、逻辑结构C、基本运算D、算法描述9、算法的计算量的大小称为计算的（ B ）A、效率B、复杂性C、现实性D、难度10、下面关于算法说法错误的是（ D ）A、算法最终必须由计算机程序实现B、为解决某问题的算法同为该问题编写的程序含义是相同的C、算法的可行性是指指令不能有二义性D、以上几个都是错误的11、以下数据结构中，（ A ）是非线性数据结构A、树B、字符串C、队D、栈12、连续存储设计时，存储单元的地址（ A ）A、一定连续B、一定不连续C、不一定连续D、部分连续，部分不连续13、以下数据结构中（ A ）是线性结构。
第一章绪论一、选择题1.D2.C3.C4.B5.D6.C7.D8.C9.A 10.D11.D 12.B二、填空题1. 逻辑结构存储结构运算2. 集合结构线性结构树形结构图状结构3. 有穷性. 确定性. 可行性. 输入. 输出4. 顺序存储. 链式存储5. 数据元素6. 线性结构非线性结构三、简答题1. 尽管算法的含义与程序非常相似，但两者还是有区别的。
首先，一个程序不一定满有穷性，因为它不是一个算法。
其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限制。
如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。
2. 数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（数据元素的组织形式）。
例如：队列的逻辑结构是线性表（先进后出）；队列在计算机中既可以采用顺序存储也可以采用链式存储；队列可进行删除数据元素. 插入数据元素. 判断是否为空队列，以及队列置空等操作。
3. 数据元素之间的逻辑关系，也称为数据的逻辑结构。
数据元素以及它们之间的相互关系在计算机存储器内的表示（又称映像）称为数据的存储结构，也称数据的物理结构。
4. 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或者多个操作。
此外，一个算法还具有下列5个特性：（1）有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完成。
（2）确定性：算法中每一步必须有明确的含义，不会产生二义性。
并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
（3）可行性：一个算法是能执行的，即算法中的每一步都可以通过已经实现的基本运算执行有限次得以实现。
（4）输入：一个算法有零个或者多个输入，它们是算法开始时对算法给出的初始量。
（5）输出：一个算法有一个或者多个输出，它们是与输入有特定关系的量5. 举例说明四种基本结构的区别:集合: 数据元素之间无任何关系,如集合A={x,5,t,&};线性结构: 数据元素之间存在一个对一个的关系,如线性表L=（2,3，4,5,7,10）；树形结构: 数据元素之间存在一个对多个的关系,如文件系统目录管理；图状结构: 数据元素之间存在多个对多个的关系,如教学计划课程安排顺序图。
Chap4一、选择题1．下面关于串的的叙述中，哪一个是不正确的？ BA．串是字符的有限序列 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)))其结果为（ E ）A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345E．ABC###G1234 F．ABCD###1234 G．ABC###012343．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ）A．求子串 B．联接 C．匹配 D．求串长4．已知串S=‘aaab’,其Next数组值为（ A ）。
A．0123 B．1123 C．1231 D．12115．串 ‘ababaaababaa’ 的next数组为（ C ）。
A．012345678999 B．012121111212 C．011234223456D．0123012322345ababaabab’ 的nextval 为（ A ）．字符串‘ababaabab6‘A．(0,1,0,1,0,4,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 )7．设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ D ）。
A．2n-1 B．n2 C．(n2/2)+(n/2) D．(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F.其他情况8．串的长度是指（ B ）A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数二、判断题1．KMP算法的特点是在模式匹配时指示主串的指针不会变小。
《数据结构》第四章习题一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）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．CDEFGFG3、串的长度是指（ B ）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数三、填空题1、串是一种特殊的线性表，其特殊性表现在_数据元素为字符，操作集也不同__；串的两种最基本的存储方式是_顺序存储_、__ 链式存储_；两个串相等的充分必要条件是__两串的长度相等且两串中对应位置的字符也相等__。
2、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_O(m+n)__。
第1xx绪论5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
A．存储结构B．存储实现C．逻辑结构D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说法正确的是（）。
A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构说明：注意几个概念：数据项是数据的最小单位而不是基本单位，数据元素才是数据的基本单位，数据结构是带有结构的数据元素的集合而不是数据项的集合。
（5）以下与数据的存储结构无关的术语是（）。
A．顺序队列B.链表C.有序表D.链栈说明：数据的存储结构只有数组（或称为顺序存储）和链表两种。
顺序队列是用数组存储的队列，链表和链栈都是用链表。
（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈第2xx线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
A．110B．108C．100D．120说明：计算公式：A+(i-1)*L，A为起始地址，i是元素序号，L是元素长度。
（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。
第4章栈和队列一、复习要点本章主要讨论3种线性结构：栈、队列与优先级队列。
这3种结构都是顺序存取的表，而且都是限制存取点的表。
栈限定只能在表的一端（栈顶）插入与删除，其特点是先进后出。
队列和优先级队列限定只能在表的一端（队尾）插入在另一端（队头）删除，不过优先级队列在插入和删除时需要根据数据对象的优先级做适当的调整，令优先级最高的对象调整到队头，其特点是优先级高的先出。
而队列不调整，其特点是先进先出。
这几种结构在开发各种软件时非常有用。
本章复习的要点：1、基本知识点要求理解栈的定义和特点，栈的抽象数据类型和在递归和表达式计算中的使用，在栈式铁路调车线上当进栈序列为1, 2, 3, , n时，可能的出栈序列计数，栈的顺序存储表示和链接存储表示，特别要注意，链式栈的栈顶应在链头，插入与删除都在链头进行。
另外，需要理解队列的定义和特点，队列的抽象数据类型和在分层处理中的使用，队列的顺序存储表示（循环队列）和链接存储表示，需要注意的是，链式队列的队头应在链头，队尾应在链尾。
还需要理解优先级队列的定义和特点。
优先级队列的最佳存储表示是堆（heap），本章介绍的表示看懂即可。
2、算法设计➢栈的5种操作（进栈、退栈、取栈顶元素、判栈空、置空栈）的在顺序存储表示下的实现，以及在链接存储表示下的实现。
➢使用栈的后缀表达式计算算法➢循环队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现➢链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现二、难点和重点1、栈：栈的特性、栈的基本运算➢栈的数组实现、栈的链表实现➢栈满及栈空条件、抽象数据类型中的先决条件与后置条件2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示3、队列：队列的特性、队列的基本运算➢队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件➢队列的链表实现：链式队列中的队头与队尾指针的表示、三、习题的解析4-2 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。
数据结构模拟试题四一、( 共30分，每题2分)单项选择题1．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为（）A．(rear-front+m) mod m B．rear-front+1 C．rear-front-1D．rear-front E．以上答案都不对2．数据结构中，与所使用的计算机无关的是数据的（）A．存储结构 B．物理结构 C．逻辑结构D．物理结构和存储结构E．以上答案都不对3．在具有n个结点的单链表中，实现（）的操作，其算法的时间复杂度都是O(n)。
A．遍历链表和求链表的第i个结点 B．在地址为p的结点之后插入一个结点 C．删除开始结点 D．删除地址为p的结点的后继结点E．以上答案都不对4．某二叉树的前序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列为（）A．JLKMNOI B．LKNJOMI C．LKJNOMI D．LKNOJMI E．以上答案都不对5．设n阶方阵是一个上三角矩阵，则需存储的元素个数为（）A．n B．n*n C．n*n/2 D．n(n+1)/2 E．以上答案都不对6．串的“模式匹配”是指（）A．判两个串是否相等 B．对两个串进行大小比较 C．找某字符在串中第一次出现位置 D．找某子串在主串中第一次出现的位置 E．以上答案都不对7．有n个结点的无向图的边数最多为（）A．n+1 B．n(n-1)/2 C．n(n+1) D．2n(n+1) E．以上答案都不对8．多关键字文件是指（）A．有多个主关键字 B．有多个次关键字 C．有一个主关键字多个次关键字D．有多个主关键字和多个次关键字 E．以上答案都不对9．某顺序存储的表格中有90000个元素，已按关键字值额定升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同。
用顺序查找法查找时，平均比较次数约为（）A．25000 B．30000 C．45000 D．90000 E．以上答案都不对10．对于序列(49,38,65,97,76,13,27,50)按由小到大进行排序，（）是初始步长d=4的希尔排序法第一趟的结果。
一、填空题（每空1分，共15分）1. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。
2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。
不允许插入和删除运算的一端称为栈底。
3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
4. 在一个循环队列中，队首指针指向队首元素的前一个位置。
5. 在具有n个单元的循环队列中，队满时共有n-1 个元素。
6. 向栈中压入元素的操作是先存入元素，后移动栈顶指针。
7.从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。
8.带表头结点的空循环双向链表的长度等于0。
二、判断正误（判断下列概念的正确性，并作出简要的说明。
）（每小题1分，共10分）（×）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
（×）2. 在表结构中最常用的是线性表，栈和队列不太常用。
（√）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
（√）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
（×）5. 栈和链表是两种不同的数据结构。
（×）6. 栈和队列是一种非线性数据结构。
（√）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。
（√）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
（×）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
（×）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。
三、单项选择题（每小题1分，共20分）（B）1.栈中元素的进出原则是Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出（C）2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定（B）3. 判定一个栈ST（最多元素为m0）为空的条件是Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0（A）4. 判定一个队列QU（最多元素为m0）为满队列的条件是Ａ．QU->rear-QU->front = = m0 Ｂ．QU->rear －QU->front －1= = m0 Ｃ．QU->front = = QU->rear Ｄ．QU->front = = QU->rear+1（D）5．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（Ａ）r－f; （Ｂ）（n＋f－r）% n;（Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n6.设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。
第4～5章串和数组自测卷答案一、填空题（每空1分，共20分）1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。
（对应严题集4.1①，简答题：简述空串和空格串的区别）2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为3。
4. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。
5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。
6. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。
7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。
已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288 B ；末尾元素A57的第一个字节地址为1282 ；若按行存储时，元素A14的第一个字节地址为(8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝1276 。
(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！)8. 〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950 。
答：不考虑0行0列，利用列优先公式：LOC(a ij)=LOC(a c1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝89509. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。
第1章绪论5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
A．存储结构B．存储实现C．逻辑结构D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说法正确的是（）。
A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构说明：注意几个概念：数据项是数据的最小单位而不是基本单位，数据元素才是数据的基本单位，数据结构是带有结构的数据元素的集合而不是数据项的集合。
（5）以下与数据的存储结构无关的术语是（）。
A．顺序队列 B. 链表 C. 有序表 D. 链栈说明：数据的存储结构只有数组（或称为顺序存储）和链表两种。
顺序队列是用数组存储的队列，链表和链栈都是用链表。
（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
A．110 B．108C．100 D．120说明：计算公式：A+(i-1)*L，A为起始地址，i是元素序号，L是元素长度。
（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。
第1章概论习题参考解答一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：（）、（）、（）、（）。
【答】集合、线性结构、树型结构和图状结构。
2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：（）、（）、（）、（）。
【答】顺序存储方法、链接存储方法、索引存储方法和散列存储方法。
二、选择题1、一个算法必须在执行有穷步之后结束，这是算法的（）。
（A）正确性（B）有穷性（C）确定性（D）可行性【答】B。
2、算法的每一步，必须有确切的定义。
也就是说，对于每步需要执行的动作必须严格、清楚地给出规定。
这是算法的（）。
（A）正确性（B）有穷性（C）确定性（D）可行性【答】C。
3、算法原则上都是能够由机器或人完成的。
整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作。
这是算法的（）。
（A）正确性（B）有穷性（C）确定性（D）可行性【答】D。
三、简答题1、算法与程序有何异同？【答】尽管算法的含义与程序非常相似，但两者还是有区别的。
首先，一个程序不一定满足有穷性，因此它不一定是算法。
例如，系统程序中的操作系统，只要整个系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一个新作业的进入。
因此操作系统就不是一个算法。
其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限止。
如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。
2、什么是数据结构？试举一个简单的例子说明。
【答】数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（即数据元素的组织形式）。
例如，队列的逻辑结构是线性表（先进先出）；队列在计算机中既可以采用顺序存储也可以采用链式存储；对队列可进行删除、插入数据元素以及判断是否为空队列、将队列置空等操作。
3、什么是数据的逻辑结构？什么是数据的存储结构？【答】数据元素之间的逻辑关系，也称为数据的逻辑结构。
79 单元测验4 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ） （√）（1）队列是限制在两端进行操作的线性表。 （√）（2）判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。 （╳）（3）在链队列上做出队操作时，会改变front指针的【值】所指向的位置或存儲空間。 （√）（4）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear- front。 （╳）（5）在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p->next=h。 （√）（6）链队列在一定范围内不会出现队满的情况。 （╳）（7）在循环链队列中[无]有溢出现象。 （╳）（8）栈和队列都是顺序存储的线性结构。不一定是順序存儲的 （╳）（9）在队列中允许删除的一端称为队【尾】頭。 （╳）（10）顺序队和循环队关于【队满和】队空的判断条件是一样的。隊滿的判斷條件不一樣
二．填空题 （1） 在队列中存取数据应遵循的原则是 先進先出 。 （2） 隊列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 （3） 在队列中，允许插入的一端称为 隊尾 。 （4） 在队列中，允许删除的一端称为 隊頭（或隊首） 。 （5） 队列在进行出队操作时，首先要判断队列是否为 空 。 （6） 顺序队列在进行入队操作时，首先要判断队列是否为 滿 。 （7） 顺序队列初始化后，front=rear= -1 。 （8） 解决顺序队列“假溢出”的方法是采用 循環隊列 。 （9） 循环队列的队首指针为front，队尾指针为rear，则队空的条件为 front=rear 。 （10） 链队列LQ为空时，LQ->front->next= NULL 。 （11） 设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为 O(n) 。 （12） 设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为 O（1） 。 （13） 在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为 空 。 80
（14） 设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为： front==（rear+1）%MAXLEN 。 （15） 在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为：front==rear && front !=NULL 。 ( 或front==rear && front <>NULL ) （16） 向一个循环队列中插入元素时，首先要判断 队尾指针 ，然后再向指针所指的位置写入新的数据。 （17） 读队首元素的操作 不改变（或不影响） 队列元素的个数。 （18） 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19，则循环队列中还有 8 个元素。 （L= (N＋rear－front)% N=（40＋19－11）% 40=8） （19）队列Q，经过下列运算：InitQueue(Q)(初始化队列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是 0 。 （20）队列Q经过InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b); ReadFront(Q,x)后，x的值是 a 。
三．选择题 （1）队列是限定在（ D ）进行操作的线性表。 A．中间 B．队首 C．队尾 D．端点 （2）队列中的元素个数是( B )。 A．不变的 B．可变的 C．任意的 D．0 （3）同一队列内各元素的类型( A )。 A．必须一致 B．不能一致 C．可以不一致 D．不限制 （4）队列是一个( C )线性表结构。 A．不加限制的 B．推广了的 C．加了限制的 D．非 （5）当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为（ B ）。 A．n-2 B．n-1 C．n D．n+1 （6）一个循环队列一旦说明，其占用空间的大小（ A ）。 A．已固定 B．可以变动 C．不能固定 D．动态变化 （7）循环队列占用的空间( A )。 A．必须连续 B．不必连续 C．不能连续 D．可以不连续 81
（8）存放循环队列元素的数组data有10个元素，则data数组的下标范围是( B )。 A．0..10 B．0..9 C．1..9 D．1..10 （9）若进队的序列为：A，B，C，D，则出队的序列是（ C ）。 A．B，C，D，A B．A，C，B，D C．A，B，C，D D．C，B，D，A （10）四个元素按：A，B，C，D顺序连续进队Q，则队尾元素是（ D ）。 A． A B． B C． C D． D （11）四个元素按：A，B，C，D顺序连续进队Q，执行一次OutQueue(Q)操作后，队头元素是（ B ）。 A． A B． B C． C D． D （12）四个元素按：A，B，C，D顺序连续进队Q，执行四次OutQueue(Q)操作后，再执行QEmpty(Q);后的值是（ B ）。 A． 0 B． 1 C． 2 D． 3 （13）队列Q，经过下列运算后，x 的值是（ B ）。 InitQueue(Q)(初始化队列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront (Q,x); A．a B．b C．0 D．1 （14）循环队列SQ队满的条件是( B )。 A．SQ->rear==SQ->front B．(SQ->rear+1)% MAXLEN ==SQ->front C．SQ->rear==0 D．SQ->front==0 （15）设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针。若想在链栈的栈顶插入一个由指针s所指的结点，则应执行下列（ A ）操作。 A．s->next=top->next；top->next=s； B．top->next=s； C．s->next=top；top=top->next； D．s->next=top；top=s； （16）带头结点的链队列LQ示意图如下，链队列的队头元素是（ A ）
LQ->front H A B C D Λ
LQ->rear A．A B．B C．C D．D 82
（17）带头结点的链队列LQ示意图如下，指向链队列的队头指针是（ C ） LQ->front H A B C D Λ
LQ->rear A．LQ->front B．LQ->rear C．LQ->front->next D．LQ->rear->next （18）带头结点的链队列LQ示意图如下，在进行进队运算时指针LQ->front（ A ） LQ->front
H A B C D Λ
LQ->rear A．始终不改变 B．有时改变 C．进队时改变 D．出队时改变 （19）队列Q，经过下列运算后，再执行QEmpty(Q) 的值是（ C ）。 InitQueue(Q) (初始化队列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadQueue(Q,x); A．a B．b C．0 D．1 （20）若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( B )。 A．5和1 B．4和2 C．2和4 D．1和5
四． 写出程序运行的结果 写出下列程序段的输出结果（队列中的元素类型为char）。 void main( ) { Queue Q; InitQueue (Q); // 初始化队列 char x="E"; y="C"; InQueue (Q, "H"); InQueue (Q, "R"); 83
InQueue (Q, y); OutQueue (Q,x); InQueue (Q,x); OutQueue (Q,x); InQueue (Q, "A"); while (!QEmpty(Q)) { OutQueue (Q,y); printf(y); }; printf(x); } 答：输出为“CHAR”。
五．程序填空 1．假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针rear，试填空完成向循环队列中插入一个元素为x的结点的函数。 typedef struct queuenode // 定义队列的存储结构 { int data; struct queuenode *next; }qu; InQueue(rear,x) // 向队列插入元素为x的函数
{ qu *rear； int x； { qu *head,*s; s= new qu ; s->data= x ; if (rear==NULL) // 循环队列为空，则建立一个结点的循环队列
{ rear=s; rear->next;} else { head= rear->next ; // 循环队列非空，则将s插到后面
rear->next= s ; rear=s; rear->next =head;} }
六. 算法设计题 1．设一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的记数器cont，试写出相应的入队算法和出队算法。
