发布时间 : 星期六 文章清华大学出版社数据结构(C++版)(第2版)课后习题答案最全整理更新完毕开始阅读
3.从栈顶指针为top的链栈中删除一个结点,用x保存被删除结点的值,则执行( )。
A x=top; top=top->next; B x=top->data;
C top=top->next; x=top->data; D x=top->data; top=top->next; 【解答】D
4.设元素1, 2, 3, P, A依次经过一个栈,进栈次序为123PA,在栈的输出序列中,有哪些序列可作为C++程序设计语言的变量名。 【解答】PA321, P3A21, P32A1, P321A, AP321
5.设S=\,其长度为( )。 【解答】15
6.对于栈和队列,无论它们采用顺序存储结构还是链接存储结构,进行插入和删除操作的时间复杂度都是( )。 【解答】O(1)
7.如果进栈序列为A、B、C、D,则可能的出栈序列是什么?
答:共14种,分别是:ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA 8.简述队列和栈这两种数据结构的相同点和不同点。
【解答】相同点:它们都是插入和删除操作的位置受限制的线性表。
不同点:栈是限定仅在表尾进行插入和删除的线性表,是后进先出的线性表,而
队列是限定在表的一端进行插入,在另一端进行删除的线性表,是先进先出的线性表。
9. 利用两个栈S1和S2模拟一个队列,如何利用栈的运算实现队列的插入和删除操作,请简述算法思想。
【解答】利用两个栈S1和S2模拟一个队列,当需要向队列中插入一个元素时,用S1来存放已输入的元素,即通过向栈S1执行入栈操作来实现;当需要从队列中删除元素时,则将S1中元素全部送入到S2中,再从S2中删除栈顶元素,最后再将S2中元素全部送入到S1中;判断队空的条件是:栈S1和S2同时为空。
10. 设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出。 【解答】算法基于原理:N=(N div d)×d + N mod d (div为整除运算,mod为求余运算)。
11.假设一个算术表达式中可以包含三种括号:圆括号“(”和“)”,方括号“[”和“]”以及花括号“{”和“}”,且这三种括号可按任意的次序嵌套使用。编写算法判断给定表达式中所含括号是否配对出现。 【解答】假设表达式已存入字符数组A[n]中,具体算法如下:
第 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×