数据结构语言版第版习题答案—严蔚敏简化版.docx

《数据结构语言版第版习题答案—严蔚敏简化版.docx》由会员分享，可在线阅读，更多相关《数据结构语言版第版习题答案—严蔚敏简化版.docx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -第 2 章线性表1选择题（ 1）顺 序表中第一个元 素的储备的址 是 100 ，每 个元素的长度 为 2 ，就 第 5 个 元 素 的的 址 是 （）。A 110B 108C 100D 120答案： B说明：次序表中的数据连续储备，所以第5 个元素的的址为：100+2*4=108。（ 3）向一个有127 个元素的次序表中插入一个新元素并保持原先次序不变，平均要移动的元素个数为（）。A 8B 63.5C 63D 7答案： B说明：平均要移动的元素个数为：n/2 。（ 4）链接储备的储备结构所占储备空间（）。

2、A 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B 只有一部分，存放结点值C 只有一部分，储备表示结点间关系的指针D 分两部分，一部分存放结点值，另一部分存放结点所占单元数答案： A（ 5）线性表如采纳链式储备结构时，要求内存中可用储备单元的的址（）。A 必需是连续的B 部分的址必需是连续的C 肯定是不连续的D 连续或不连续都可以答案： D（ 6）线性表在（）情形下适用于使用链式结构实现。A 需常常修改中的结点值需不断对进行删除插入C 中含有大量的结点中结点结构复杂答案： B说明：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。（ 7）单链表的储备密度（）。A

3、大于1B 等于1C 小于1D 不能确定答案： C说明：储备密度是指一个结点数据本身所占的储备空间和整个结点所占的储备空间之比，假设单链表一个结点本身所占的空间为D ，指针域所占的空间为N ，就储备密度为： D/D+N，肯定小于1。（ 8）将两个各有n 个元素的有序表归并成一个有序表，其最少的比较次数是（）。A nB 2n-1C 2nD n-1答案： A可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 27 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结说明：当第一个有序表中全部的

4、元素都小于（或大于）其次个表中的元素，只需 要用其次个表中的第一个元素依次与第一个表的元素比较，总计比较n 次。（ 9）在一个长度为n 的次序表中，在第i 个元素（1 i n+1 ）之前插入一个新元素时须向后移动（）个元素。A n-iB n-i+1C n-i-1D I答案： B10线性表L=a 1 ， a2 ,an ，以下说法正确选项（）。A 每个元素都有一个直接前驱和一个直接后继B 线性表中至少有一个元素C 表中诸元素的排列必需是由小到大或由大到小D 除第一个和最终一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接可编辑资料 - - - 欢迎下载精品名师归纳总结后继。答案： D(12)

5、 以下说法错误选项（）。A 求表长、定位这两种运算在采纳次序储备结构时实现的效率不比采纳链式储备结可编辑资料 - - - 欢迎下载精品名师归纳总结构时实现的效率低B 次序储备的线性表可以随机存取C 由于次序储备要求连续的储备区域，所以在储备治理上不够敏捷 D 线性表的链式储备结构优于次序储备结构答案： D说明： 链式储备结构和次序储备结构各有优缺点，有不同的适用场合。(13) 在单链表中，要将s 所指结点插入到p 所指结点之后，其语句应为（）。A s-next=p+1; p-next=s;B *p.next=s; *s.next=*p.next;C s-next=p-next; p-next=

6、s-next; D s-next=p-next; p-next=s;答案： D(14) 在双向链表储备结构中，删除p 所指的结点时须修改指针（）。A p-next-prior=p-prior; p-prior-next=p-next; B p-next=p-next-next; p-next-prior=p;C p-prior-next=p; p-prior=p-prior-prior;D p-prior=p-next-next; p-next=p-prior-prior;答案： A(15) 在双向循环链表中，在p 指针所指的结点后插入q 所指向的新结点，其修改指针的操作是（）。A p-nex

7、t=q; q-prior=p; p-next-prior=q; q-next=q;B p-next=q; p-next-prior=q; q-prior=p; q-next=p-next; C q-prior=p; q-next=p-next; p-next-prior=q; p-next=q; D q-prior=p; q-next=p-next; p-next=q; p-next-prior=q;可编辑资料 - - - 欢迎下载精品名师归纳总结答案： C2算法设计题（ 1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原先两个链表的储备空间,不另外占用其它的储备空间。表中

8、不答应有重复的数据。算法描述void MergeListLinkList &La,LinkList &Lb,LinkList &Lc/合并链表La 和 Lb ，合并后的新表使用头指针Lc 指向pa=La-next; pb=Lb-next;/pa和 pb 分别是链表La 和 Lb 的工作指针, 初始化为相应链表的第一个结点Lc=pc=La; /用 La 的头结点作为Lc 的头结点whilepa & pbifpa-datadatapc-next=pa;pc=pa;pa=pa-next;/取较小者La 中的元素，将pa 链接在pc 的后面，pa 指针后移else ifpa-datapb-data p

9、c-next=pb; pc=pb; pb=pb-next;/取较小者Lb 中的元素，将pb 链接在pc 的后面，pb 指针后移else /相等时取La 中的元素，删除Lb 中的元素pc-next=pa;pc=pa;pa=pa-next; q=pb-next;delete pb ;pb =q;pc-next=pa.pa:pb;/插入剩余段delete Lb;/释放Lb 的头结点（ 6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。算法描述ElemType Max LinkList L ifL-next=NULL return NULL;pmax=L-next; /假定第一个结点中数据具有

10、最大值p=L-next-next;whilep .= NULL /假如下一个结点存在ifp-data pmax-data pmax=p;/假如 p 的值大于pmax 的值，就重新赋值p=p-next;/遍历链表return pmax-data;第 3 章栈和队列1选择题可编辑资料 - - - 欢迎下载精品名师归纳总结（ 1）如让元素1， 2， 3 ， 4， 5 依次进栈，就出栈次序不行能显现在（）种情形。 A 5 ， 4 ， 3， 2， 1B 2 ， 1 ， 5， 4， 3C 4， 3， 1 ， 2， 5D 2， 3， 5 ， 4 ， 1答案： C说明：栈是后进先出的线性表，不难发觉C 选项中

11、元素1 比元素2 先出栈，违反了栈的后进先出原就，所以不行能显现C 选项所示的情形。（ 2）如已知一个栈的入栈序列是1， 2， 3，, ，n，其输出序列为p1 ， p2 ， p3 ，, ，pn ，如 p1=n ，就pi 为（）。A iB n-iC n-i+1D不确定答案： C说明：栈是后进先出的线性表，一个栈的入栈序列是1， 2， 3，, ，n ，而输出序列的 第一个元素为n ，说明1，2 ，3，, ， n 一次性全部进栈，再进行输出，所以p1=n ，p2=n-1 ，, ， pi=n-i+1。（ 3）数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小

12、于，运算队列中元素个数的公式为（）。 A r-fB n+f-r%nC n+r-fD（ n+r-f%n答案： D说明：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（此题为n），然后与MAXSIZE（此题为n）求余，即（n+r-f%n。（ 4）链式栈结点为：data,link， top指向栈顶.如想摘除栈顶结点，并将删除结点的值储存到x 中 ,就应执行操作（）。A x=top-data;top=top-link。B top=top-link;x=top-link。C x=top;top=top-link。D x=top-lin

13、k。答案： A说明： x=top-data将结点的值储存到x中，top=top-link栈顶指针指向栈顶下一结点，即摘除栈顶结点。（ 5）设有一个递归算法如下int factint n /n 大于等于0ifn=0 return 1;else return n*factn-1;就运算factn 需要调用该函数的次数为（）。A n+1B n-1CnDn+2答案： A说明：特别值法。设n=0 ，易知仅调用一次factn函数，应选A 。（ 6）栈在（）中有所应用。A递归调用B函数调用C表达式求值D前三个选项都有答案： D说明：递归调用、函数调用、表达式求值均用到了栈的后进先出性质。可编辑资料 - -

14、- 欢迎下载精品名师归纳总结（ 7）为解决运算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机就依次从该缓冲区中取出数据。该缓冲区的逻 辑结构应当是（）。A队列B 栈C线性表D有序表答案： A说明：解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线性表。（ 8）设栈S 和队列Q 的初始状态为空，元素e1、 e2 、 e3、 e4 、 e5 和 e6 依次进入栈S， 一个元素出栈后即进入Q ，如 6 个元素出队的序列是e2、 e4 、e3 、e6、e5 和 e1 ，就栈S 的容量至少应当是（）。A 2B 3C 4D6答案：

15、B说明：元素出队的序列是e2、 e4 、 e3 、 e6、 e5 和 e1 ，可知元素入队的序列是e2、 e4、e3、 e6、 e5 和 e1，即元素出栈的序列也是e2 、 e4、 e3 、 e6、 e5 和 e1，而元素e1、 e2 、 e3、e4、 e5 和 e6 依次进入栈，易知栈S 中最多同时存在3 个元素，故栈S 的容量至少为3。（ 9）如一个栈以向量V1.n储备，初始栈顶指针top 设为 n+1 ，就元素x 进栈的正确操作是 。A top+; Vtop=x;B Vtop=x; top+;C top-; Vtop=x;D Vtop=x; top-;答案： C说明：初始栈顶指针top

16、为 n+1 ，说明元素从数组向量的高端的址进栈，又由于元素储备在向量空间V1.n中，所以进栈时top 指针先下移变为n，之后将元素x 储备在Vn 。（ 10 ）设计一个判别表达式中左，右括号是否配对显现的算法，采纳（）数据结构最佳。A线性表的次序储备结构B队列C.线性表的链式储备结构D.栈答案： D说明：利用栈的后进先出原就。（ 11）用链接方式储备的队列，在进行删除运算时（）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改答案： D说明：一般情形下只修改头指针，但是，当删除的是队列中最终一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。（ 12 ）循环

17、队列储备在数组A0.m中，就入队时的操作为（）。A. rear=rear+1B. rear=rear+1%m-1C. rear=rear+1%mD. rear=rear+1%m+1答案： D说明：数组A0.m中共含有m+1 个元素，故在求模运算时应除以m+1。可编辑资料 - - - 欢迎下载精品名师归纳总结（ 13 ）最大容量为n 的循环队列，队尾指针是rear，队头是front，就队空的条件是（）。A. rear+1%n=frontB. rear=frontC rear+1=frontD. rear-l%n=front答案： B解 释 ： 最 大 容 量 为n的 循 环 队 列 ， 队 满

18、条 件 是 rear+1%n=front， 队 空 条 件 是rear=front。（ 14 ）栈和队列的共同点是（）。A. 都是先进先出B.都是先进后出C.只答应在端点处插入和删除元素D.没有共同点答案： C说明：栈只答应在栈顶处进行插入和删除元素，队列只答应在队尾插入元素和在队头删除元素。（ 15 ）一个递归算法必需包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分答案： B2算法设计题（ 1）将编号为0 和 1 的两个栈存放于一个数组空间Vm 中， 栈底分别处于数组的两端。 当第0 号栈的栈顶指针top0 等于 -1 时该栈为空，当第1 号栈的栈顶指针top1

19、 等于m 时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判定栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下：Typedef structint top2,bot2;/ 栈顶和栈底指针SElemType *V;/ 栈数组int m;/ 栈最大可容纳元素个数DblStack 题目分析两栈共享向量空间，将两栈栈底设在向量两端，初始时，左栈顶指针为-1 ，右栈顶为m。两栈顶指针相邻时为栈满。两栈顶相向、迎面增长，栈顶指针指向栈顶元素。 算法描述(1) 栈初始化int InitS.top0=-1;S.top1=m;return 1; /初始化胜利(2) 入栈操作：int pushs

20、tk S ,int i,int x可编辑资料 - - - 欢迎下载精品名师归纳总结 i 为栈号，i=0 表示左栈，i=1 为右栈，x 是入栈元素。入栈胜利返回1，失败返回0ifi1 cout“栈号输入不对”endl;exit0; ifS.top1-S.top0=1 cout“栈已满 ”endl;return0;switchicase 0: S.V+S.top0=x; return1; break;case 1: S.V-S.top1=x; return1; push(3) 退栈操作ElemType popstk S,int i退栈。i 代表栈号，i=0 时为左栈，i=1 时为右栈。退栈胜利时返

21、回退栈元素否就返回-1ifi1cout“栈号输入错误”endl 。 exit0; switchicase 0: ifS.top0=-1 cout“栈空 ”endl 。 return （ -1 ）。 else returnS.VS.top0-;case 1: ifS.top1=m cout“栈空 ”endl; return-1; else returnS.VS.top1+; switch 算法终止(4) 判定栈空int Empty;return S.top0=-1 & S.top1=m; 算法争论请留意算法中两栈入栈和退栈时的栈顶指针的运算。左栈是通常意义下的栈，而右栈入栈操作时，其栈顶指针左移

22、（减1），退栈时，栈顶指针右移（加1）。（ 2）回文是指正读反读均相同的字符序列，如“abba ”和“ abdba ”均是回文，但“good ”不是回文。试写一个算法判定给定的字符向量是否为回文。 提示：将一半字符入栈 题目分析将字符串前一半入栈，然后，栈中元素和字符串后一半进行比较。即将第一个出栈元素 和后一半串中第一个字符比较，如相等，就再出栈一个元素与后一个字符比较，, ，直至栈空，结论为字符序列是回文。在出栈元素与串中字符比较不等时，结论字符序列不是回文。 算法描述#define StackSize 100 /假定预安排的栈空间最多为100 个元素typedef char DataTy

23、pe;/假定栈元素的数据类型为字符typedef structDataType dataStackSize;可编辑资料 - - - 欢迎下载精品名师归纳总结int top;SeqStack;int IsHuiwen char *t/判定t字符向量是否为回文，如是，返回1，否就返回0 SeqStack s;int i , len; char temp;InitStack &s;len=strlent; /求向量长度for i=0; ilen/2; i+/将一半字符入栈Push &s, ti;while .EmptyStack &s/每弹出一个字符与相应字符比较temp=Pop &s;if tem

24、p.=Sireturn 0 ;/不等就返回0 else i+;return 1 ; /比较完毕均相等就返回1（ 3）设从键盘输入一整数的序列：a1 , a2, a3 ， an ，试编写算法实现：用栈结构储备输入的整数，当ai -1 时，将ai 进栈。当ai =-1时，输出栈顶整数并出栈。算法应对反常情形（入栈满等）给出相应的信息。 算法描述#define maxsize栈空间容量void InOutSint smaxsize/s是元素为整数的栈，本算法进行入栈和退栈操作。int top=0;/top为栈顶指针，定义top=0时为栈空。fori=1; ix;/n个整数序列作处理。从键盘读入整数序

25、列。ifx.=-1/读入的整数不等于-1 时入栈。 iftop=maxsize-1cout“栈满”endl;exit0; else s+top=x; /x入栈。else/读入的整数等于-1 时退栈。iftop=0 cout“栈空”endl;exit0; else cout“出栈元素是” stop-rear = Q-rear-next;/将队尾指针指向头结点while Q-rear.=Q-rear-next/当队列非空，将队中元素逐个出队s=Q-rear-next;Q-rear-next=s-next; delete s;/ 回收结点空间(2) 判队空int EmptyQueue LinkQue

26、ue *Q / 判队空。当头结点的next 指针指向自己时为空队return Q-rear-next-next=Q-rear-next;(3) 入队void EnQueue LinkQueue *Q, Datatype x / 入队。也就是在尾结点处插入元素QueueNode *p=new QueueNode;/申请新结点p-data=x; p-next=Q-rear-next;/初始化新结点并链入Q-rear-next=p;Q-rear=p;/将尾指针移至新结点可编辑资料 - - - 欢迎下载精品名师归纳总结(4) 出队Datatype DeQueue LinkQueue *Q/ 出队 ,把

27、头结点之后的元素摘下 Datatype t;QueueNode *p; ifEmptyQueue Q ErrorQueue underflow;p=Q-rear-next-next; /p指向将要摘下的结点x=p-data; /储存结点中数据if p=Q-rear/ 当队列中只有一个结点时，p 结点出队后，要将队尾指针指向头结点Q-rear = Q-rear-next;Q-rear-next=p-next;elseQ-rear-next-next=p-next;/摘下结点p delete p;/ 释放被删结点return x;第 4 章串、数组和广义表1选择题（ 1）串是一种特别的线性表，其特

28、别性表达在（）。A 可以次序储备B 数据元素是一个字符C 可以链式储备答案：BD 数据元素可以是多个字符如（ 2）串下面关于串的的表达中，（）是不正确的？A 串是字符的有限序列B 空串是由空格构成的串C模式匹配是串的一种重要运算D 串既可以采纳次序储备，也可以采纳链式储备可编辑资料 - - - 欢迎下载精品名师归纳总结答案： B说明：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。（ 3）串“ ababaaababaa ”的next 数组为（）。A 012345678999B 012121111212答案： CC 01123422345

29、6D 0123012322345（ 4）串“ ababaabab ”的nextval为（）。A 010104101B 010102101答案： AC 010100011D 010101011（ 5）串的长度是指（）。A 串中所含不同字母的个数B 串中所含字符的个数C 串中所含不同字符的个数D 串中所含非空格字符的个数答案：B说明：串中字符的数目称为串的长度。（ 6）假设以行序为主序储备二维数组A=array1.100,1.100，设每个数据元素占2 个储备单元，基的址为10 ，就LOC5,5=（）。A 808B 818C 1010D 1020答案： B说明：以行序为主，就LOC5,5=（ 5-

30、1 ） *100+ （ 5-1 ） *2+10=818。（ 7）设有数组Ai,j，数组的每个元素长度为3 字节， i 的值为1 到 8，j 的 值为1 到 10 ，数组从内存首的址BA 开头次序存放，当用以列为主存放时，元素 A5,8 的储备首的址为（）。A BA+141B BA+180C BA+222D BA+225答案： B说明：以列序为主，就LOC5,8=（ 8-1 ） *8+ （ 5-1 ） *3+BA=BA+180。（ 8）设有一个10 阶的对称矩阵A ，采纳压缩储备方式，以行序为主储备，a11 为第一元素，其储备的址为1，每个元素占一个的址空间，就a85 的的址为（）。A 13B

31、32C 33D 40答案： C（ 9）如对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素 包括主对角线上全部元素 依次存放于一维数组B1.nn+1/2中，就在B 中确定a（ijij ）的位置k 的关系为 （）。A i*i-1/2+jB j*j-1/2+iC i*i+1/2+jD j*j+1/2+i答案：B（ 10 ）二维数组A 的每个元素是由10 个字符组成的串，其行下标i=0,1,8,列下标 j=1,2,10 。如 A 按行先储备，元素A8,5的起始的址与当A 按列先储备时的元素（） 的起始的址相同。设每个字符占一个字节。A A8,5B A3,10C. A5,8D A0,9答案： B可

32、编辑资料 - - - 欢迎下载精品名师归纳总结说明：设数组从内存首的址 M 开头次序存放，如数组按行先储备，元素 A8,5 的起始的址为： M+ （ 8-0 ） *10+ （ 5-1 ） *1=M+84 。如数组按列先储备，易运算出元素 A3,10 的起始的址为： M+ （ 10-1 ） *9+ （ 3-0 ） *1=M+84 。应选 B。（ 11）设二维数组A1. m， 1. n （即m 行 n 列）按行储备在数组B1. m*n中，就二维数组元素Ai,j在一维数组B 中的下标为（）。A i-1*n+jB i-1*n+j-1C i*j-1D j*m+i-1答案： A说明：特别值法。取i=j=1

33、 ，易知A1,1 的的下标为1，四个选项中仅有A 选项能确定的值为1，应选A 。（ 12 ）数组A0.4,-1.-3,5.7中含有元素的个数（）。A 55B 45C 36D 16答案： B说明：共有5*3*3=45个元素。（ 13 ）广义表A=a,b,c,d,e,f,g，就HeadTailHeadTailTailA的值为（）。A gB dC cD d答案： D说明： TailA=b,c,d,e,f,g。 TailTailA=c,d,e,f,g。HeadTailTailA= c,d 。 TailHeadTailTailA=d。 HeadTailHeadTailTailA=d。（ 14 ）广义表a

34、,b,c,d的表头是（），表尾是（）。A aB C a,b,c,dD b,c,d答案： C 、 B说明：表头为非空广义表的第一个元素，可以是一个单原子，也可以是一个子表，a,b,c,d的表头为一个子表a,b,c,d 。表尾为除去表头之外，由其余元素构成的表，表为肯定是个广义表，a,b,c,d的表尾为空表 。（ 15 ）设广义表L=a,b,c，就L 的长度和深度分别为（）。A 1 和 1B 1 和 3C 1 和 2D 2 和 3答案： C说明：广义表的深度是指广义表中绽开后所含括号的层数，广义表的长度是指广义表中所含元素的个数。依据定义易知L 的长度为1，深度为2。2应用题4 请将香蕉banan

35、a 用工具H Head ， T Tail 从 L 中取出。L=apple,orange,strawberry,banana,peach,pear答案： H（ H（ T（ H（ T（ H（ T（ L） ） ） ）3算法设计题（ 1）写一个算法统计在输入字符串中各个不同字符显现的频度并将结果存入文件（字符串中的合法字符为A-Z 这 26 个字母和0-9这 10 个数字）。可编辑资料 - - - 欢迎下载精品名师归纳总结 题目分析由于字母共26 个，加上数字符号10 个共36 个，所以设一长36 的整型数组，前 10 个重量存放数字字符显现的次数，余下存放字母显现的次数。从字符串中读出数字字符 时，

36、字符的ASCII代码值减去数字字符0的ASCII代码值，得出其数值0.9，字母的ASCII代码值减去字符A的 ASCII代码值加上10 ，存入其数组的对应下标重量中。遇其它符号不作处理，直至输入字符串终止。 算法描述void Count（）/统计输入字符串中数字字符和字母字符的个数。 int i， num36。char ch。for （ i 0 。 i36 。 i+ ） numi。 /初始化while（ch getchar（） .= # ）/ # 表示输入字符串终止。if （ 0 =ch= 9） i=ch 48;numi+。/数字字符elseif（ A =ch= Z） i=ch-65+10;n

37、umi+。 /字母字符for （ i=0 。 i10 。 i+ ）/输出数字字符的个数cout “数字”i“的个数= ” numiendl; for （ i 10 。 i36 。 i+ ） /求出字母字符的个数cout “字母字符”i+55“的个数=” numich;if ch.= ./规定 .是字符串输入终止标志InvertStoreA;Ai+ = ch;/字符串逆序储备Ai = 0; /字符串结尾标记（ 3）编写算法，实现下面函数的功能。函数void insertchar*s,char*t,int pos将字符串t插入到字符串s 中，插入位置为插入。（说明：不得使用任何库函数）pos 。假设安排给字符串s 的空间足够让字符串t可编辑资料 - - - 欢迎下载精品名师归纳总结 题目分析 此题是字符串的插入问题，要求在字符串 s 的 pos 位置，插入字符串 t 。第一应查