习题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)
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)10行100列的二维数组A 按行优先存储,其元素分别为A[1][1] ~ A[10][100],每个元
素占4字节,已知Loc(A[6][7])=10000H,则Loc(A[4][19])=( )。
A. FC11H B. 9248H C. 2F00H D. FD10H
(5)设有两个串s1和s2,求s2在s1中首次出现的位置的运算称为( )。
A. 连接 B. 模式匹配 C. 求子串 D. 求串长
(6)为了解决计算机主机和键盘输入之间速度不匹配问题,通常设置一个键盘缓冲区,该缓冲区应该是一个( )结构。
A. 栈 B. 队列 C. 数组 D. 线性表
(7)STL 中的双端队列为( )。
A. 顺序容器 B. 容器适配器 C. 迭代器适配器 D. 泛函适配器
(8)STL 中的( )允许用户为队列中的元素设置优先级。
A. 队列适配器 B. 双端队列 C. 优先级队列适配器 D. 栈适配器
(9)string 类型不支持以( )的方式操作容器,因此不能使用front 、back 和pop_back操作。
A. 线性表 B. 队列 C. 栈 D. 串
3. 算法设计
(1)设计一个算法判断算数表达式的圆括号是否正确配对。
(2)假定用带头结点的循环链表表示队列,并且只设置一个指针指向队尾元素,试设计该队列类,完成相应的入队、出队、置空队、求队长等操作接口。
(3)设计算法把一个十进制数转换为任意指定进制数。
(4)设有一个背包可以放入的物品重量为S ,现有n 件物品,重量分别为w 1,w 2,……,w n 。问能否从这n 件物品中选择若干件放入此背包,使得放入的重量之和正好为S 。如果存在一种符合上述要求的选择,则称此背包问题有解,否则此问题无解,试用递归和非递归两种方法设计解决此背包问题的算法。
背包问题分析:
背包问题是一个经典的NP 问题,它既简单形象容易理解,又在某种程度上能够揭示动态规划的本质,故不少教材都把它作为动态规划部分的第一道例题。本题目是最简单的01背包问题,除此之外,还有许多由此衍生出来的很多复杂的背包问题。
本题中,最容易想到的就是假定背包中已放入了部分物品,现将第i 件物品试着放入背包中,如果可以放进去,背包的重量在原来的基础上增加了w i ;如果不可以放进去,说明加入后太重了,换下一件物品。如果所有的剩余物品都不能放入,说明以前放入的物品不合适,拿出上一次放入的物品,继续试剩余的物品。
递归解法:
设背包函数为knapsack(int s, int n),参数 int s 为剩余重量,int n 为剩余物品数,返回值表示背包分配是否成功。
(1) 如果s==0,表示分配成功,返回1;
(2) 如果s
(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 && n
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
{
if (value+W[j]
printf("得到一组解:");
for (int p=0;p
break;
}
else if (value>S) break;
}
if (size==0) {printf("Finished!");exit(0);}
i=stack[--size]+1;
value-=W[i-1];
}
}
void main()
{
knapsackstack();
}
习题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)
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)10行100列的二维数组A 按行优先存储,其元素分别为A[1][1] ~ A[10][100],每个元
素占4字节,已知Loc(A[6][7])=10000H,则Loc(A[4][19])=( )。
A. FC11H B. 9248H C. 2F00H D. FD10H
(5)设有两个串s1和s2,求s2在s1中首次出现的位置的运算称为( )。
A. 连接 B. 模式匹配 C. 求子串 D. 求串长
(6)为了解决计算机主机和键盘输入之间速度不匹配问题,通常设置一个键盘缓冲区,该缓冲区应该是一个( )结构。
A. 栈 B. 队列 C. 数组 D. 线性表
(7)STL 中的双端队列为( )。
A. 顺序容器 B. 容器适配器 C. 迭代器适配器 D. 泛函适配器
(8)STL 中的( )允许用户为队列中的元素设置优先级。
A. 队列适配器 B. 双端队列 C. 优先级队列适配器 D. 栈适配器
(9)string 类型不支持以( )的方式操作容器,因此不能使用front 、back 和pop_back操作。
A. 线性表 B. 队列 C. 栈 D. 串
3. 算法设计
(1)设计一个算法判断算数表达式的圆括号是否正确配对。
(2)假定用带头结点的循环链表表示队列,并且只设置一个指针指向队尾元素,试设计该队列类,完成相应的入队、出队、置空队、求队长等操作接口。
(3)设计算法把一个十进制数转换为任意指定进制数。
(4)设有一个背包可以放入的物品重量为S ,现有n 件物品,重量分别为w 1,w 2,……,w n 。问能否从这n 件物品中选择若干件放入此背包,使得放入的重量之和正好为S 。如果存在一种符合上述要求的选择,则称此背包问题有解,否则此问题无解,试用递归和非递归两种方法设计解决此背包问题的算法。
背包问题分析:
背包问题是一个经典的NP 问题,它既简单形象容易理解,又在某种程度上能够揭示动态规划的本质,故不少教材都把它作为动态规划部分的第一道例题。本题目是最简单的01背包问题,除此之外,还有许多由此衍生出来的很多复杂的背包问题。
本题中,最容易想到的就是假定背包中已放入了部分物品,现将第i 件物品试着放入背包中,如果可以放进去,背包的重量在原来的基础上增加了w i ;如果不可以放进去,说明加入后太重了,换下一件物品。如果所有的剩余物品都不能放入,说明以前放入的物品不合适,拿出上一次放入的物品,继续试剩余的物品。
递归解法:
设背包函数为knapsack(int s, int n),参数 int s 为剩余重量,int n 为剩余物品数,返回值表示背包分配是否成功。
(1) 如果s==0,表示分配成功,返回1;
(2) 如果s
(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 && n
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
{
if (value+W[j]
printf("得到一组解:");
for (int p=0;p
break;
}
else if (value>S) break;
}
if (size==0) {printf("Finished!");exit(0);}
i=stack[--size]+1;
value-=W[i-1];
}
}
void main()
{
knapsackstack();
}