北邮C++数据结构课后习题-习题3参考答案.doc

习题3
1． 填空题（部分答案）
（1）栈的进出原则是（___________），队列的进出原则是（___________）。
答案：后进先出（LIFO） 先进先出（FIFO）
（2）设32位计算机系统中，空栈S存储int型数据，栈顶指针为1024H。经过操作序列 push(1)，push(2)，pop，push(5)，push(7)，pop，push(6)之后，栈顶元素为（___________），栈底元素为（___________），栈的高度为（___________），输出序列是（___________），栈顶指针为（___________）H。
答案：6 1 3 2,7 1030
（3）两栈共享存储空间，其数组大小为100，数组下标从0开始。top1和top2分别为栈1和栈2的栈顶元素下标，则栈1为空的条件为（___________），栈2为空的条件为（___________），栈1或栈2满的条件为（___________）。
答案：top1==-1 top2==100 top1+1==top2
（4）一个队列的入队顺序是1234，则队列的输出顺序是（___________）。
答案：1234
（5）设循环队列数组大小为100，队头指针为front，队尾指针为rear；约定front指向队头元素的前一个位置，该位置永远不存放数据。则入队操作时，修改rear=（___________），出队操作修改front=（___________），队空的判别条件为（___________），队满的判别条件为（___________）。若front=20，rear=60，则队列长度为（___________），若front=60,rear=20，则队列长度为（___________）。
答案：(rear+1)%100 (front+1)%100 rear==front (rear+1)%100=front 40 60
（6）朴素模式匹配算法中，每个串的起始下标均为1，变量i=100，j=10，分别表示主串和模式串当前比较的字符元素下标，若本次比较两字符不同，则i回溯为（___________），j回溯为（___________）。
答案：92 1
（7）用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别为（___________）和（___________）。
答案：O(1) O(n)
（8）一般来说，数组不执行（___________）和（___________）操作，所以通常采用（___________）方法来存储数组。通常有两种存储方式：（___________）和（___________）。
答案：删除 插入 顺序存储 行优先存储 列优先存储
（9）设8行8列的二维数组起始元素为A[0][0]，按行优先存储到起始元素下标为0的一维数组B中，则元素B[23]在原二维数组中为（___________）。若该二维数组为上三角矩阵，按行优先压缩存储上三角元素到起始元素下标为0的一维数组C中，则元素C[23]即为原矩阵中的（___________）元素。
答案：A[2][7] A[3][5]
（10）设二维数组A为6行8列，按行优先存储，每个元素占6字节，存储器按字节编址。已知A的起始存储地址为1000H，数组A占用的存储空间大小为（___________）字节，数组A的最后一个元素的下标为（___________），该元素的第一个字节地址为（___________）H，元素A[1][4]的第一个字节的地址为（___________）H。（提示：下标从0开始计）
答案：288 A[5][7] 111AH 1048H
（11）10行100列的二维数组A按行优先存储，其元素分别为A[1][1] ~ A[10][100]，每个元素占4字节，已知Loc(A[6][7])=10000H，则Loc(A[4][19])=（ ）。
答案：FD10H
（12）设C++中存储三维数组Amnp，则第一个元素为a000，若按行优先存储，则aijk前面共有（___________）个元素；若按列优先存储，则aijk前面共有（___________）个元素。
答案：inp+jp+k i+mj+mnk
（13）常见的稀疏矩阵压缩方法有：（___________）和（___________）。
答案：三元组表 十字链表

2． 选择题
（1）将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。
A. 数组 B. 栈 C. 队列 D. 二叉树
（2）四个元素1、2、3、4依次进栈，出栈次序不可能出现（ ）情况。
A. 1 2 3 4 B. 4 1 3 2 C. 1 4 3 2 D. 4 3 2 1
（3）设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（ ）。
A. r-f B. r-f+1 C. (r-f) mod n +1 D. (r-f+n) mod n
说明：这里的数组不是指C++数组，也就说假定数组长度依然为n，而不是n+1。
（4）设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为（ ）。
A. 连接 B. 模式匹配 C. 求子串 D. 求串长
（5）为了解决计算机主机和键盘输入之间速度不匹配问题，通常设置一个键盘缓冲区，该缓冲区应该是一个（ ）结构。
A. 栈 B. 队列 C. 数组 D. 线性表
（6）STL中的双端队列为（ ）。
A. 顺序容器 B. 容器适配器 C. 迭代器适配器 D. 泛函适配器
（7）STL中的（ ）允许用户为队列中的元素设置优先级。
A. 队列适配器 B. 双端队列 C. 优先级队列适配器 D. 栈适配器
（8）string类型不支持以（ ）的方式操作容器，因此不能使用front、back和pop_back操作。
A. 线性表 B.队列 C. 栈 D. 串

3. 问答题
（1）根据下面的矩阵，写出矩阵转置后的三元组表，起始行列值为1。

Row
Col
Item
1
3
-3
1
6
15
2
1
12
2
5
18
3
1
9
3
4
13
5
2
5
6
3
14
矩阵行数：7
矩阵列数：6
非零元素个数：8

（2）对于如下稀疏矩阵，请写出对应的三元组顺序表，若采用顺序取，直接存的算法进行转置运算，引入辅助数组number[]和position[]，分别表示矩阵各列的非零元素个数和矩阵中各列第一个非零元素在转置矩阵中的位置，请写出数组中的各元素（所有数组起始元素下标为0）。
原矩阵
Col
0
1
2
3
Number[col]
1
0
2
1
Position[col]
0
1
1
3

Row
Col
Item
0
2
2
1
0
3
2
2
-1
2
3
5
行数：4
列数：4
非零元素个数：4

（3）对于上题中的稀疏矩阵，写出对应的三元组表和十字链表。

三元组表：
Row
Col
Item
0
2
2
1
0
3
2
2
-1
2
3
5
行数：4
列数：4
非零元素个数：4
十字链表：

4.算法设计
（1）设计一个算法判断算数表达式的圆括号是否正确配对。
（2）假定用带头结点的循环链表表示队列，并且只设置一个指针指向队尾元素，试设计该队列类，完成相应的入队、出队、置空队、求队长等操作接口。
（3）设计算法把一个十进制数转换为任意指定进制数。
（4）设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为w1，w2，……，wn。问能否从这n件物品中选择若干件放入此背包，使得放入的重量之和正好为S。如果存在一种符合上述要求的选择，则称此背包问题有解，否则此问题无解，试用递归和非递归两种方法设计解决此背包问题的算法。
背包问题分析：
背包问题是一个经典的NP问题，它既简单形象容易理解，又在某种程度上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例题。本题目是最简单的01背包问题，除此之外，还有许多由此衍生出来的很多复杂的背包问题。
本题中，最容易想到的就是假定背包中已放入了部分物品，现将第i件物品试着放入背包中，如果可以放进去，背包的重量在原来的基础上增加了wi；如果不可以放进去，说明加入后太重了，换下一件物品。如果所有的剩余物品都不能放入，说明以前放入的物品不合适，拿出上一次放入的物品，继续试剩余的物品。

递归解法：
设背包函数为knapsack(int s, int n)，参数 int s 为剩余重量，int n 为剩余物品数，返回值表示背包分配是否成功。
（1） 如果s==0，表示分配成功，返回1；
（2） 如果s<0 或者 n<0，表示太重，或者物品分配完毕，返回0；
（3） 执行knapsack( s – wi, n-1)，测试当前这件物品放入是否成功。
（3.1） 如果成功，说明当前这件物品放入刚好最终分配成功。
（4） 返回knapsack( s , n-1)，说明当前物品不合适，减小剩余物品数，继续测试。
测试代码：
/*简单的背包问题递归解*/
#include"stdio.h"
#define N 6 /*物品数量*/
#define S 8 /*背包大小*/

int W[N+1]={0,1,2,3,4,5,6};/*数据，各物品重量，W[0]不使用*/

/*
背包函数
knapsack()
参数
int s 剩余重量
int n 剩余物品数
返回
int 背包分配是否成功
*/

int knapsack(int s,int n)
{
if(s == 0)/*分配结束，成功*/
return 1;
if(s < 0 || (s > 0 && n < 1))/*没有可用空间，或者物品分配完毕*/
return 0;
if( knapsack(s - W[n] , n - 1)){/*递归*/
printf("%-4d",W[n]); /*输出*/
return 1;
}
return knapsack(s , n - 1);
}
int main()
{
if(knapsack(S , N))/*递归调用*/
printf("\nOK!\n");
else
printf("Failed!");
return 1;
}/*main*/

非递归解法：
一件一件的物品往包（即栈）里放，发现有问题，拿出来，放其他的物品。
（1）i=1
（2）从第i件到第n件测试每件物品，对于第j次循环，测试第j件物品
（2.1）如果该物品可以放，入栈
（2.2）若栈的容量刚好达到要求，成功，打印栈元素。
（2.3）继续测试j+1件物品
（3）若没有成功
（3.1）若栈空，返回失败
（3.2）将栈顶物品（设第k个）出栈
（3.3）令i=k+1，返回（2）

代码：
#include"stdio.h"
#define N 6 /*物品数量*/
#define S 8 /*背包大小*/
int W[N+1]={0,1,2,3,4,5,6};/*数据，各物品重量，W[0]不使用*/
int stack[1000]={0};
int value=0;
int size=0;
knapsackstack()
{
int i=1;
while (1)
{
for (int j=i;j<=N;j++)
{
if (value+W[j]<=S) {stack[size++]=j; value+=W[j];}
if (value==S){
printf("得到一组解：");
for (int p=0;p<size;p++) printf("%d ",W[stack[p]]);
printf("OK!\n");
break;
}
else if (value>S) break;
}
if (size==0) {printf("Finished!");exit(0);}
i=stack[--size]+1;
value-=W[i-1];
}
}
void main()
{
knapsackstack();
}