数据结构课后答案 - 北邮 下载本文

3.size:195 4.size:100 (3)程序段三

int a[]={1,2,3,4,5}; list ilist(3,2); ilist.assign(a,a+5);

ilist.pop_back (); //1 2 3 4 ilist.insert (ilist.end(),7); ilist.pop_front (); //2 3 4 7 ilist.front ()=20; //20 3 4 7 ilist.sort(); //3 4 7 20

for ( list::iterator it = ilist.begin (); it != ilist.end(); it++ )

cout << *it <<\; cout << endl;

//1 2 3 4 7

答案:3 4 7 20

5.算法设计

(1)分别编程实现顺序表类和链表类,并设计完整的测试程序对每个接口进行测试。 (2)设A=(a1,a2,a3,......an)和B=(b1,b2,.. .,bm)是两个线性表(假定所含数据元素均为整数)。若n=m且ai=bi(i=1,.. .,n),则称A=B;若ai=bi(i=1,.. .,j)且aj+1B。试编写一个比较A和B的算法,当AB是分别输出-1,0或者1。

(3)假设有两个按数据元素值递增有序排列的线性表A和B,均以单链表作存储结构。编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序,允许值相同)排列的线性表C,并要求利用原表(即A表和B表的)结点空间存放表C。

(4)试分别以顺序表和单链表作为存储结构,各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法,在原表的存储空间内将线性表(a1,a2,,??,an-1,an)逆置为(an,an-1,??,a2,a1)。

(5)假设在长度大于1的循环链表中,既无头结点也无头指针。s为指向链表中某个结点的指针,试编写算法删除结点*s的直接前趋结点。 答案:

template

void DeletePreNode (Node * s) { }

(6)已知一单链表中的数据元素含有三类字符(即:字

Node * p = s;

//得到s的结点的前一个结点的前一个结点 while (p->next->next != s) p=p->next; //删除p->next指向的结点 Node * q = p->next; p->next = s; delete q;

母字符、数字字符和其它字符)。试编写算法,构造三个循环链表,使每个循环链表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。

(7)Josephus环问题:任给正整数n、k,按下述方法可得排列1,2,??,n的一个置换:将数字1,2,??,n环形排列(如图2-36所示),按顺时针方向从1开始计数,计满k时输出该位置上的数字(并从环中删去该数字),然后从下一个数字开始继续计数,直到环中所有数

n-1n-2n123图2-36 Josephus环 字均被输出为止。例如,n=10,k=3时,输出的置换是3,6,9,2,7,1,8,5,10,4。试编写一算法,对输入的任意正整数n、k,输出相应的置换数字序列。

习题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)0 (front+1)0 rear==front (rear+1)0=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. 二叉树 D. 4 3 2 1

(2)四个元素1、2、3、4依次进栈,出栈次序不可能出现( )情况。 A. 1 2 3 4

B. 4 1 3 2

C. 1 4 3 2

(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. 队列 (7)STL中的双端队列为( )。 A. 顺序容器 A. 队列适配器

B. 容器适配器 B. 双端队列

C. 数组

D. 线性表 D. 泛函适配器

C. 迭代器适配器

(8)STL中的( )允许用户为队列中的元素设置优先级。

C. 优先级队列适配器 D. 栈适配器

(9)string类型不支持以( )的方式操作容器,因此不能使用front、back和pop_back操作。 A. 线性表

B.队列

C. 栈

D. 串

3. 算法设计

(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),说明当前物品不合适,减小剩余物品数,继续测试。 测试代码:

/*简单的背包问题递归解*/