2014春 算法与数据结构 期中 上机考试(开卷)

2014春 算法与数据结构 期中 上机考试(开卷) 说明： (1) 每两人一组选1题。不同的组所选择的题目不能相同。 (2) 开卷考试。 (3) 考试时间90分钟。 (4) 所有输入输出都是对文件操作。 (5) 工程构建时界面、数据与业务处理是分离的；函数的申明、定义与实现分别在不同的文件中，也是分离的。 1、用十字链表示稀疏矩阵，并实现稀疏矩阵加法。 2、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，时间复杂度尽可能的小，规定算法中不能使用求幂函数。 3、已知线性表L递增有序。试写一算法，将X插入到L的适当位置上，以保持线性表L的有序性。 4、写一算法，从顺序表中删除自第i个元素开始的k个元素。 5、已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 6、试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 7、假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C. 8、假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。 9、已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 10、设线性表A=(a1, a2,…,am)，B=(b1, b2,…,bn)，试写一个按下列规则合并A、B为线性表C的算法，使得： C= (a1, b1,…,am, bm, bm+1, …,bn)    当m≤n时； 或者    C= (a1, b1,…,an, bn, an+1, …,am)    当m>n时。 线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。 11、将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。 12、建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算 。 13、设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x值，求P(x)的值。 14、约瑟夫环问题 约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。 利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。 例如m的初值为20；n=7，7个人的密码依次是：3，1，7，2，4，8，4，出列的顺序为6，1，4，7，2，3，5。 15、假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。 16、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。 17、要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 18、停车场管理 设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。 试编写程序，模拟上述管理过程。要求以顺序栈模拟停车场，以链队列模拟便道。从终端读入汽车到达或离去的数据，每组数据包括三项：①是“到达”还是“离去”；②汽车牌照号码；③“到达”或“离去”的时刻。与每组输入信息相应的输出信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。 19、商品货架管理。 商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。用队列和栈作为周转，实现上述管理过程。 20、编写算法，实现串的基本操作StrReplace(S,T,V)。 21、假设以块链结构表示串，块的大小为1，且附设头结点。试编写算法，实现串的下列基本操作：StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； StrCat(S,T)； SubString(Sub,S,pos,len)。 22、S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。 23、S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。 24、写下列算法： （1）将顺序串r中所有值为ch1的字符换成ch2的字符。 （2）将顺序串r中所有字符按照相反的次序仍存放在r中。 （3）从顺序串r中删除其值等于ch的所有字符。 （4）从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。 （5）从顺序串r中删除所有与串r1相同的子串。 25、写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。 26、写算法，实现顺序串的基本操作StrCompare(s,t)。 27、写算法，实现顺序串的基本操作StrReplace(&s,t,v)。 28、假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。 29、在稀疏矩阵的快速转置算法中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 30、若矩阵Am×n中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。 31、从文件读入基础数据，测试各顺序表操作模块的功能。 （1）创建顺序表空表，输出初始化结构数据。 （2）在表尾依次插入1 2 3 4 5 6 7 8 9 10，并遍历输出。 （3）查找值为12的元素，并给出查询结果。 （4）删除值为9的元素，并遍历输出。 程序运行结果参考： 初始化L后：L.elem=2086 L.length=0 L.listsize=10 在L的表尾依次插入1～10后：L.elem=1 2 3 4 5 6 7 8 9 10 没有值为12的元素 依次输出L的元素：L.elem =1 2 3 4 5 6 7 8 9 10 32、应用顺序表的基本操作实现直接插入排序。 例如：初始数据 1 6 5 3 4 2 排序后 1 2 3 4 5 6 33、从文件读入基础数据，测试单链表操作模块的功能。 （1）创建空表，输出初始化结构数据。 （2）在表尾依次插入1 2 3 4 5 6 7 8 9 10，并遍历输出。 （3）查找值为12的元素，并给出查询结果。 （4）删除值为9的元素，并遍历输出。 程序运行结果参考： 在L的表尾依次插入1～10后：L=1 2 3 4 5 6 7 8 9 10 没有值为12的元素 依次输出L的元素：L=1 2 3 4 5 6 7 8 9 10 34、应用单链表的基本操作实现直接插入排序。 例如：初始数据 L=1 6 5 3 4 2 排序后 L=1 2 3 4 5 6 35、从文件读入基础数据，测试各顺序栈操作模块的功能。 （1）创建空栈，判断栈空。 （2）依次插入元素1 2 3 4 5 6 7 8 9 10，并输出。 （3）取栈顶元素，并给出查询结果。 （4）删除栈顶元素，并输出删除的元素。 程序运行结果参考： 初始化栈后，是否为否？1(1:空0:否) 栈中元素依次为：1 2 3 4 5 6 7 8 9 10 11 12 弹出的栈顶元素e=12 栈顶元素e=11 36、应用顺序栈的基本操作数制转换。 例如：八—十进制转换，输入十进制数 95 输出八进制数 135 37、从文件读入基础数据，测试循环队列基本操作模块的功能。 （1）创建空队列，判断队列空。 （2）依次插入元素1 2 3 4 5 6 7 8 9 10，并输出。 （3）取队头元素，并给出查询结果。 （4）删除队头元素，并输出结果。 程序运行结果参考： 初始化队列后，是否为否？1(1:空0:否) 队列中元素依次为：1 2 3 4 5 6 7 8 9 10 11 12 当前队头元素：e=1 删除的元素：e=1 38、应用循环队列的基本操作实现杨辉三角形输出。 例如：输入行数：4 输出杨辉三角形：      1 1    1 1    2    1 1  3    3    1 39、从文件读入基础数据，测试链队列基本操作模块的功能。