严蔚敏++数据结构习题集答案(2)

解：（1，4，3，2）

（1，4，5） （8，2） （3，5，2）。

提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，，直至求得满足条件的解，或者无解。

由于回溯求解的规则规则是“后进先出”因此自然要用到栈。

2． 模拟停车厂管理的问题。

设停车厂只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达的先后顺序依次排列，若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门后，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走。试设计一个停车场管理程序。

第四章习题

算法设计题

1．利用C的库函数strlen,strcpy和strcat写一个算法void StrInsert(char *S,char *T,int t) ，将串T插入到S的第i个位置上。若i大于S的长度，则插入不执行。

2．利用C的库函数strlen,strcpy（或strncpy）写一个算法void StrDelete(char *S,int t,int m) ，删除串S中从位置I开始的连续的m个字符。若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则将S中从位置i开始直至末尾的字符均被删去。

3．采用顺序结构存储串，编写一个函数，求串和串的一个最长的公共子串。

4．采用顺序存储结构存储串，编写一个函数计算一个子串在一个字符串中出现的次数，如果该子串不出现则为0。

第五章习题

一、单项选择题

1. 二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范 围从0到8，列下标j的范围从1到10，则存放M至少需要（1）个字节；M的第8列和第5行共占（2）个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的（3）元素的起始地址一致。（） （1） A.90 B.180 C.240 D.540

（2） A.108 B.114 C.54 D.60

（3） A.M[8][5] B.M[3][10] C.M[5][8] D.M[0][9]

2. 二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范 围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素（1）的起始地址相同。（）

A.m[2][4] B.M[3][4] C.M[3][5] D.M[4][4]

3. 数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（1），若该数组按行存放时，元素A[8][5]的起始地址是（2），若该数组按列存放时，元素A[8][5]的起始地址是（３）。

（1） A. 80 B.100 C.240 D.270

（2） A.SA+141 B.SA+144 C.SA+222 D.SA+225 （3） A.SA+141 B.SA+180 C.SA+222 D.SA+225

4. 稀疏矩阵一般的压缩存储方法有两种，即（） A.二维数组和三维数组 B. 三元组和散列 C.三元组和十字链表 D. 散列和十字链表

5.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（） A.正确 B.错误

6.假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址时１００，每个整数占４个字节。问下列元素的存储地址是什么。

(1) a0000 (2)a1111 (3)a3125 (4)a8247

7.设有三对角矩阵An×n，将其三条对角线上的元素存于数组B[3][n]中，使得元素B[u][v]=aij，试推倒出从（i,j）到 (u,v)的下标变换公式。

8.假设一个准对角矩阵：

a11 a12

a21 a22

a33 a34

a43 a44

…. aij a2m-1,2m-1 a2m-1,2m a2m,2m-1 a2m,2m

按以下方式存储于一维数组B[4m]中: 0 1 2 3 4 5 6 … k … 4m-1 4m A11 a12 a21 a22 a33 a34 a43 … aij … a2m-1,2m a2m,2m-1 a2m,2m

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

9.画出下列广义表的存储结构式意图。

（１） A=((a,b,c),d,(a,b,c)) （２） B=(a,(b,(c,d),e),f)

二、算法设计

1．对于二维数组A[m][n],其中m<=80,n<=80，先读入m,n，然后读该数组的全部元素，对如下三种情况分别编写相应函数： (1)求数组A靠边元素之和

(2)求从A[0][0]开始的互不相邻的各元素之和

(3)当m=n时，分别求两条对角线的元素之和，否则打印m!=n的信息

2．有数组A[4][4]，把1到16个整数分别按顺序放入A[0][0]...A[0][3]，A[1][0]...A[1][3] A[2][0]...A[2][3]，A[3][0]...A[3][3]中，编写一个函数获取数据并求出两条对角线元素的乘积。

3．只猴子要选大王，选举办法如下：所有猴子按1，2，...，n编号围坐一圈，从第1号开始按1、2、...、m报数，凡报m号的退出圈外，如此循环报数，直到圈内剩下一只猴子时，这只猴子就是大王。n和m由键盘输入，打印出最后剩下的猴子号。编写一个程序实现上述函数。

4．如果矩阵A中存在这样的一个元素A[i][j]满足下列条件：A[i][j]是第i行中值最小的元素，且又是第j列中最大的元素，则称之为该矩阵的一个马鞍点。编写一个函数计算出m*n的矩阵A的所有马鞍点。

5．现有如下的稀疏矩阵A（如图所示），要求画出以下各种表示方法。 （1）三元组表示法 （2）十字链表法

15 0 0 22 0 -15 0 13 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0

0 0 28 0 0 0

6．假设稀疏矩阵A和B（具有相同的大小m*n）都采用三元组表示，编写一个函数计算C=A+B，要求C也采用三元组表示。

7．假设稀疏矩阵A和B（分别为m*n和n*1矩阵）采用三元组表示，编写一个函数计算C=A*B，要求C也是采用稀疏矩阵的三元组表示。

8．假设稀疏矩阵只存放其非0元素的行号、列号和数值，以一维数组顺次存放，行号为-1结束标志。

例如：如图所示的稀疏矩阵M，则存在一维数组D中： D[0]=1， D[1]=1，D[2]=1，D[3]=1，D[4]=5 D[5]=10，D[6]=3，D[7]=9，D[8]=5，D[9]= -1 M =:

1 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 …… 此处隐藏：3078字，全部文档内容请下载后查看。喜欢就下载吧 ……