数据结构与算法 上海第二工业大学 二工大 期末考试 试卷.doc

一、 选择题：1、在数据结构中，线性结构中元素之间存在_关系。a: 一对一b: 一对多c: 多对一d: 多对多 2、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的_和运算等的学科。a: 结构b: 关系c: 操作d: 算法3、算法分析的两个主要方面是_。a: 空间复杂度和时间复杂度b: 正确性和简明性c: 可读性和文档性d: 数据复杂性和程序复杂性4、顺序表中逻辑上相邻的节点其物理位置也_。a: 一定相邻b: 不必相邻c: 按某种规律排列d: 无要求5、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_。a: s-next=p-next; p-next=s;b: p-next=s-next; s-next=p;c: q-next=s; s-next=p;d: p-next=s; s-next=q;6、一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是_。a: edcbab: decbac: dceabd: abcde7、循环队列用数组a0,m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_。a: (rear-front+m)%mb: rear-front+1c: rear-front-1d: rear-front8、关于空格串，下列说法中正确的有_。a: 空格串就是空串b: 空格串是零个字符的串c: 空格串的长度为零d: 空格串的长度就是其包含的空格个数9、数组a中，每个元素a的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址sa开始连续存放在存储器内，该数组按行存放时，元素a85的起始地址为_。a: sa+140b: sa+144c: sa+222d: sa+22510、对于一棵满二叉树，m个树叶，n个节点，深度为h，则_。a: n=h+mb: h+m=2nc: m=h-1d: n=2h-111、具有65个结点的完全二叉树其深度为_。（根的层次号为1）a: 8b: 7c: 6d: 512、满二叉树_二叉树。a: 一定是完全b: 不一定是完全c: 不是d: 不是完全13、将一棵有100个节点的完全二叉树从上到下，从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的左孩子编号为_。a: 99b: 98c: 50d: 4814、如果t2是由森林t转换而来的二叉树，那么t中结点的后序遍历就是t2中结点的_。a: 先序遍历b: 中序遍历c: 后序遍历d: 层次遍历15、将递归算法转换成对应的非递归算法时，通常需要使用_。a: 栈b: 队列c: 链表d: 树16、如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序为_。a: uwvtsb: vwutsc: wuvtsd: wutsv17、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有_个结点。a: 13b: 12c: 26d: 2518、按照二叉树的定义，具有3个结点的二叉树有_种。a: 3b: 4c: 5d: 619、如图所示的4棵二叉树中，_不是完全二叉树。a: b: c: d: 20、所谓稀疏矩阵指的是_。a: 零元素个数较多的矩阵b: 零元素个数占矩阵元素总个数一半的矩阵c: 零元素个数远远多于非零元素个数且分布没有规律的矩阵d: 包含有零元素的矩阵二、序列(a,b,c,d,e)已存在静态链表如下图a，头指针指向1号结点。请完成：1在静态链表中标出此序列的逻辑关系。2画出依次执行了b前插入f，删除e，c后插入g操作后的新的静态链表图b。112c23e34a45d56b677图a图b三、已知一个稀疏矩阵如下：1给出它的三元组顺序表表示2. 给出它逆置后的三元组顺序表3.给出它的十字链表表示020000100000030000000040050006ijvijv a b四、对下图的二叉树完成如下要求：1写出该树的深度2写出该深度的满二叉数的总结点数3写出二叉树的后序遍历的序列4将二叉树还原成森林 a b fc g h d i je五、假设用于通信的电文仅由8个字母（ah）组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试用这8个字母进行以下操作：1构造一棵赫夫曼树（左结点的权小于右结点的权）2求出带权路径的长度3设计赫夫曼编码（左分支为“0”，右分支为“1”）六、任意一棵有n个结点的二叉树，已知它有m个叶子结点。试证明非叶子结点中度数为2的有m-1个，其余的度数为1。七、简述以下算法的功能（栈和队列的元素类型为int）。void algo (queue &q) stack s; int d; initstack(s);while (!queueempty(q) dequeue(q,d); push (s,d);while (!stackempty(s) pop(s,d); enqueue (q,d);八、算法题：1、设计一个算法按层次输出二叉树中的所有结点，要求同一层次的从左向右输出（存储按二叉树表）。2、已知一单链表，头指针为h，指向表头结点，请写出算法对此单链表就地逆转。（h仍旧为逆转后的单链表的头指针指向表头结点）。注：逆转为：原单链表的序列为（a1,a2an），则逆转后为（an,an-1,a1）3、写一算法，实现统计带表头的单链表中元素值为奇数的接点个数。九、已知线性链表如下图，头指针为la，写出语句序列使左图中的指针指向改成右图中的指针指向。a b c la a b c la 十、在一个c语言程序中，有结构类型student的定义和结构数组allstudents的声明如下：struct student char name8; int number;student allstudents1050; allstudents是一个二维数组，它的每个元素都是包含name和number的结构类型。已知在c语言中，二维数组使用以行序为主序的存储结构，char类型占用1字节，int类型占用4字节。 假定allstudents在内存中的起始存储位置是2000，请写出计算allstudentsij的存储位置的算式，并计算allstudents35的存储位置。十一、用下标从0到4的一维数组存储一个循环队列，目前其中有两个元素a、b，状态如图(a)。如果此后有17个数据元素c、d、p、q、r、s依次进队列，其间又有16个元素先后出队列，请在图(b)中填写队列最后的状态，包括其中的元素和指针的位置。rearbfronta (a) (b)十二、附加题：1、josephus问题是下面的游戏：n个人从1到n编号，围坐成一个圆圈。从1号开始传递一个热土豆。经过m次传递后拿着热土豆的人被清除离座，围坐的圆圈缩小，由坐在被清除的人后面的人拿土豆继续进行游戏。最后剩下的人取胜。因此，如果m=0和n=5，则依次被清除的人的顺序是2，4，1，5。a.写一个算法思想解决m和n在一般值下的josephus问题，应使你的程序尽可能地高效，要确保能够清除单元。（包括采用的数据结构、方法） b.估计你的程序时间复杂度。2.计算n!的递归函数fac(n)如下，试分析它的时间复杂度。（请写出详细的分析步骤）int fac(int n) if(n=40（即e3=40）”，在true内输入800，在false内输入600，确定（其余行可以采用填充柄完成，或重复上述的顺序）选择实发工资项下的一个单元格，输入“=基本工资（在该行的单元格名）+奖金（同上）-住房基金（同上）-保险费（同上）”，确认（回车）（其余单元格采用填充柄完成，或重复上述顺序）保存文件本题完成11. if函数的应用：根据教师工作表教师职称确定其职务津贴练习excel2003p140：excel2003电子表格的编辑操作2. 排序3. （1）打开当前试题目录下文件excel-24.xls；（2）在b4单元格内键入数字“45637”；（3）表格所有数字格式为带1位小数格式（如：23456.0）；（4）将sheet1的所有内容复制到工作表sheet2的相应单元格内，并以“电器”为关键字，对四个季度所有数据递减排序；（5）同名存盘。打开当前试题目录下文件excel-24.xls点b4单元格，输入“45637”选中表格内的所有数字格式，点右键，点设置单元格格式，点数字，设小数位为1，确定全选sheet1（即当前的文件），点复制，点开sheet2，点当前页面的左上角的单元格，点粘贴点“电器”单元格，点表格，点排序，主要关键字下选择电器，点降序，确定保存文件本题完成4. （1）打开当前试题目录下文件excel-29.xls；（2）根据工作表中数据，在b4单元格内键入数据“2580”；（3）表格数字数据设置为“0,000.0”的格式；（4）以“1997年”为关键字，对不同规格所有相应数据进行递减排序；（5）同名存盘。打开当前试题目录下文件excel-29.xls点b4单元格，输入“2580”选中表格内的所有数字格式，点右键，点设置单元格格式，点数值，设小数位为1，点使用千分分隔符为有效，确定点“1997年”单元格，点表格，点排序，主要关键字下选择1997，点降序，确定保存文件本题完成5. （1）打开当前试题目录下文件excel-33.xls；（2）根据工作表中数据，在e4单元格内键入数据“商务出版社”；（3）将sheet1所有内容复制到工作表sheet2的相应位置，并以“单价”为关键字，递减排序；（4）同名存盘。打开当前试题目录下文件excel-33.xls点e4单元格，输入“商务出版社”全选sheet1（即当前的文件），点复制，点开sheet2，点当前页面的左上角的单元格，点粘贴点“单价”单元格，点表格，点排序，主要关键字下选择单价，点降序，确定保存文件本题完成6. （1）打开当前试题目录下文件excel-23.xls；（2）根据工作表中数据，在a4单元格内键入数据“李四”；（3）“总成绩”列数据都设置为带一位小数格式；（4）将所有内容复制到sheet2工作表中相应单元格，并以“总成绩”为关键字递增排序；（5）同名存盘。打开当前试题目录下文件excel-23.xls点a4单元格，输入“李四”选中总成绩列的全部数据，点右键，点设置单元格格式，点数字，点数值，设小数位为1位，确定全选sheet1（即当前的文件），点复制，点开sheet2，点当前页面的左上角的单元格，点粘贴点“总成绩”单元格，点表格，点排序，主要关键字下选择总成绩，点升序，确定保存文件本题完成7. （1）打开当前试题目录下文件excel-36.xls；（2）根据工作表中数据，在a4单元格内键入数据“狮子座”；（3）a4单元格数据格式与该列其它相应数据格式保持一致；（4）将sheet1的所有内容复制到sheet2中，并以“赤纬（度）”为关键字，递减排序；（5）同名存盘。打开当前试题目录下文件excel-36.xls点a4单元格，输入“狮子座”选中a4单元格所在列的其他单元格，点格式刷，点a4单元格全选sheet1（即当前的文件），点复制，点开sheet2，点当前页面的左上角的单元格，点粘贴点“赤纬（度）”单元格，点表格，点排序，主要关键字下选择赤纬（度），点降序，确定保存文件本题完成8. （1）打开当前试题目录下文件excel-21.xls；（2）根据工作表中数据，在b5单元格内键入数据2719840；（3）b列、c列数字都以单元格格式中货币类的“￥”货币符号、小数点后2位小数表现（如：￥3,200,000.00”）；（4）将所有内容拷贝到sheet2中相应位置，并按关键字“增长率”递减排序；（5）同名存盘。打开当前试题目录下文件excel-21.xls点b5单元格，输入“2719840”选中b、c列下的数字（单元格），点右键，点设置单元格格式，点数字，点货币，设货币符号为“￥”，设小数点位为2位，采用千分隔符，确定全选sheet1（即当前的文件），点复制，点开sheet2，点当前页面的左上角的单元格，点粘贴点“增长率”单元格，点表格，点排序，主要关键字下选择增长率，点降序，确定保存文件本题完成9. （1）打开当前试题目录下文件excel-30.xls；（2）根据工作表中数据，在c4单元格内键入数据“3650”；（3）所有数字所在格式为0,000.0格式；（4）将sheet1的所有内容复制到sheet2相应单元格并以“木材”为关键字，递减排序；（5）同名存盘。打开当前试题目录下文件excel-30.xls点c4单元格，输入“3650”选中所有数字单元格，点右键，点设置单元格格式，点数字，点数值，设小数位为1位，采用千分隔符，确定全选sheet1（即当前的文件），点复制，点开sheet2，点当前页面的左上角的单元格，点粘贴点“木材”单元格，点表格，点排序，主要关键字下选择增长率，点降序，确定保存文件本题完成10. （1）打开当前试题目录下文件excel-27.xls；（2）根据工作表中数据，在b3单元格内键入数据“1000200015”；（3）设置报价列数据带1位小数格式；（4）将所有内容复制到工作表sheet2的相应位置，并以“报价”为关键字，递减排序；（5）同名存盘。打开当前试题目录下文件excel-27.xls点b3单元格，输入“1000200015”选中报价列下的数字单元格，点右键，点设置单元格格式，点数字，点数值，设小数位为1位，确定全选sheet1（即当前的文件），点复制，点开sheet2，点当前页面的左上角的单元格，点粘贴点“报价”单元格，点表格，点排序，主要关键字下选择报价，点降序，确定保存文件本题完成11. （1）打开当前试题目录下文件excel-22.xls；（2）根据工作表中数据，在e8单元格内键入数据40115.7；（3）“房价款（元）”列数字都以单元格格式中货币类的“￥”货币符号、小数点后2位小数表现（如：￥44,886.20）；（4）将所有内容拷贝到sheet2中的相应单元格内，并按关键字“房价款”递增排序；（5）同名存盘。打开当前试题目录下文件excel-22.xls点e8单元格，输入“40115.7”选中“房价（元）”列下的数字单元格，点右键，点设置单元格格式，点数字，点货币，设货币符号为“￥”，设小数位为2位，确定全选sheet1（即当前的文件），点复制，点开sheet2，点当前页面的左上角的单元格，点粘贴点“房价款”单元格，点表格，点排序，主要关键字下选择房价款，点升序，确定保存文件本题完成12. 图表13. （1）打开当前试题目录下文件excel-47.xls；（2）根据工作表中数据，建立折线图；（3）生成图表的作用数据区域是a2:a6和e2:e6，数据系列产生在列，使用前一列为分类（x）轴坐标刻度标志，使用前一行作为图例说明；（4）图表标题为“消费水平调查表”；（5）生成新图表工作表（不是在原工作表中嵌入），图表工作表的名称为“图表1”；（6）同名存盘。打开当前试题目录下文件excel-47.xls点插入，点图表，在标准类型下，点折线图，选择一种折线图，点下一步，点数据区域右侧的按钮，出现另外一个对话框，在工作表中选择“a2:a6”数据区域，点对话框右侧的按钮，返回到数据区域对话框，选择系列产生在列，点下一步，点标题，图表标题内输入“消费水平调查表”，点下一步，选择“作为新工作表插入（即第一个选择）”，名称为“图表1”，确定保存文件本题完成14. （1）打开当前试题目录下文件excel-56.xls；（2）根据工作表中数据，建立数据点折线图；（3）生成图表的作用数据区域是a2:e4，数据系列产生在“行”；（4）图表标题为“净利润”，图例不显示，数据标志显示类别名称；（5）生成新图表工作表存于原工作表中；（6）同名存盘。打开当前试题目录下文件excel-56.xls点插入，点图表，在标准类型下，点折线图，选择数据点折线图，点下一步，点数据区域右侧的按钮，出现另外一个对话框，在工作表中选择“a2:e4”数据区域，点对话框右侧的按钮，返回到数据区域对话框，选择系列产生在行，点下一步，点标题，图表标题内输入“净利润”，点图例，选择显示图例，点数据标志，选择类别名称为有效，点下一步，选择“作为其中的对象插入（即第二个选择）”，名称为默认的设置，确定保存文件本题完成15. （1）打开当前试题目录下文件excel-43.xls；（2）根据工作表中数据，建立数据点折线图；（3）生成图表的作用数据区域是a3:b7，数据系列产生在列，使用前一列为分类（x）轴坐标刻度线标志；使用前一行作为图例说明；（4）图表标题为“销售额统计表”；（5）生成新图表工作表（不是在原工作表中嵌入），图表工作表的名称为“图表1”；（6）同名存盘。打开当前试题目录下文件excel-43.xls点插入，点图表，在标准类型下，点折线图，选择数据点折线图，点下一步，点数据区域右侧的按钮，出现另外一个对话框，在工作表中选择“a3:b7”数据区域，点对话框右侧的按钮，返回到数据区域对话框，选择系列产生在列，点下一步，点标题，图表标题内输入“销售额统计表”，点下一步，选择“作为新工作表插入（即第一个选择）”，名称为图表1，确定保存文件本题完成16. （1）打开当前试题目录下文件excel-49.xls；（2）根据工作表中数据，建立簇状柱形图；（3）生成图表的作用数据区域是a2:a5和f2:f5，数据系列产生在列，使用前一列为分类（x）轴坐标刻度标志，使用前一行作为图例说明；（4）图表标题为“总成绩图”；（5）生成新图表工作表（不是在原工作表中嵌入），图表工作表的名称为“图表1”；（6）同名存盘。打开当前试题目录下文件excel-49.xls点插入，点图表，在标准类型下，点柱形图，选择簇状柱形图，点下一步，点数据区域右侧的按钮，出现另外一个对话框，在工作表中选择“a2:a5”数据区域，点对话框右侧的按钮，返回到数据区域对话框，选择系列产生在列，点下一步，点标题，图表标题内输入“总成绩图”，点下一步，选择“作为新工作表插入（即第一个选择）”，名称为图表1，确定保存文件本题完成17. （1）打开当前试题目录下文件excel-41.xls；（2）根据工作表中数据，建立簇状条形图；（3）生成图表的作用数据区域是a2:c6，数据系列产生在列，使用前一列为分类（x）轴坐标刻度标志，使用前一行作为图例说明；（4）图表标题为“家电销售情况图”；（5）生成新图表工作表（不是在原工作表中嵌入），图表工作表的名称为“图表1”；（6）同名存盘。打开当前试题目录下文件excel-41.xls点插入，点图表，在标准类型下，点条形图，选择簇状条形图，点下一步，点数据区域右侧的按钮，出现另外一个对话框，在工作表中选择“a2:c6”数据区域，点对话框右侧的按钮，返回到数据区域对话框，选择系列产生在列，点下一步，点标题，图表标题内输入“家电销售情况图”，点下一步，选择“作为新工作表插入（即第一个选择）”，名称为图表1，确定保存文件本题完成18. （1）打开当前试题目录下文件excel-51.xls；（2）根据工作表中数据，建立折线图；（3）生成图表的作用数据区域是a2:e5，数据系列产生在行，使用销售类型作为图例说明；（4）图表标题为“计算机市场销售额”；（5）生成新图表工作表（不是在原工作表中嵌入），图表工作表的名称为“图表1”；（6）同名存盘。打开当前试题目录下文件excel-51.xls点插入，点图表，在标准类型下，点折线图，选择其中的一种折线图，点下一步，点数据区域右侧的按钮，出现另外一个对话框，在工作表中选择“a2:e5”数据区域，点对话框右侧的按钮，返回到数据区域对话框，选择系列产生在行，点下一步，点标题，图表标题内输入“计算机市场销售额”，点下一步，选择“作为新工作表插入（即第一个选择）”，名称为图表1，确定保存文件本题完成19. （1）打开当前试题目录下文件excel-46.xls；（2）根据工作表中数据，建立簇状柱形图；（3）生成图表的作用数据区域是a2:e5，数据系列产生在列，使用前一列为分类（x）轴坐标刻度标志，使用前一行作为图例说明；（4）图表标题为“企业财务指标”；（5）生成新图表工作表（不是在原工作表中嵌入），图表工作表的名称为“图表1”；（6）同名存盘。打开当前试题目录下文件excel-46.xls点插入，点图表，在标准类型下，点柱形图，选择簇状柱形图，点下一步，点数据区域右侧的按钮，出现另外一个对话框，在工作表中选择“a2:e5”数据区域，点对话框右侧的按钮，返回到数据区域对话框，选择系列产生在列，点下一步，点标题，图表标题内输入“企业财务指标”，点下一步，选择“作为新工作表插入（即第一个选择）”，名称为图表1，确定保存文件本题完成20. （1）打开当前试题目录下文件excel-53.xls；（2）根据工作表中数据，建立三维簇状柱形图；（3）生成图表的作用数据区域是a2:b5，数据系列产生在“行”；（4）图表标题为“2000年净资产收益率”，图例在底部显示；（5）生成新图表工作表存于原工作表中；（6）同名存盘。打开当前试题目录下文件excel-53.xls点插入，点图表，在标准类型下，点柱形图，选择三维簇状柱形图，点下一步，点数据区域右侧的按钮，出现另外一个对话框，在工作表中选择“a2:b5”数据区域，点对话框右侧的按钮，返回到数据区域对话框，选择系列产生在行，点下一步，点标题，图表标题内输入“2000年净资产收益率”，点图例，选择在底部显示，点下一步，“作为其中的对象插入（即第二个选择）”，名称为默认的设置，确定保存文件本题完成21. 工作表22. （1）打开当前试题目录下文件excel-62.xls；（2）对“财务指标”复制新工作表“指标2”，移至工作表sheet3前；（3）将工作表名“sheet2”标签设为红色；（4）设置工作表“sheet3”的显示比例为125%；（5）同名存盘。打开当前试题目录下文件excel-62.xls点“财务指标”工作表名，点右键，点移动或复制工作表，在“下列工作表之前”项下选择sheet3，选择建立副本，确定右键点击“财务指标（2）”，点重命名，将名称改为“指标2”，确认（回车）右键点工作表名“sheet2”，点工作表标签颜色，点红色，点确定点开工作表“sheet3”，点视图，点显示比例，设比例为“125%”（在自定义内输入），确定保存文件本题完成23. （1）打开当前试题目录下文件excel-61.xls；（2）对“彩色图表”复制新工作表“复制图表”，移至最后；（3）设置新表“复制图表”的显示比例为50%；（4）把表“彩色图表”的a3:e7范围内的底色设为无；（5）同名存盘。打开当前试题目录下文件excel-61.xls点“彩色图表”工作表名，点右键，点移动或复制工作表，在“下列工作表之前”项下选择移到最后，选择建立副本，确定右键点击“彩色图表（2）”，点重命名，将名称改为“复制图表”，确认（回车），点视图，点显示比例，设比例为50%，确定点开“彩色图表”工作表，选择a3:e7单元格，点右键，点设置单元格格式，点图案，设颜色为无，确定保存文件本题完成24. （1）打开当前试题目录下文件excel-66.xls；（2）将“2001年”和“2002年”工作表隐藏；（3）将“2002年（2）”工作表标签改为“2003年”；（4）设置工作表“sheet3”的显示比例为125%；（5）同名存盘。打开当前试题目录下文件excel-66.xls点开“2001年”工作表，点格式，点工作表，点隐藏，对“2002年”工作表进行与“2001年”工作表同样的操作右键点击“2002年（2）”，点重命名，将名称改为“2003年”，确认（回车），点视图，点显示比例，设比例为125%（在自定义输入），确定保存文件本题完成25. （1）打开当前试题目录下文件excel-64.xls；（2）对工作表“一季度部门信息”进行复制，生成“三季度部门信息”，并移至最后；（3）将工作表名“一季度部门信息”移动为第一个工作表（移动到最左边）；（4）同名存盘。打开当前试题目录下文件excel-64.xls点“一季度部门信息”工作表名，点右键，点移动或复制工作表，在“下列工作表之前”项下选择移到最后，选择建立副本，确定右键点击“一季度部门信息（2）”，点重命名，将名称改为“三