导读：学年第一学期课程设计题目及要求，本课程设计一共包括六道大题，请根据要求完成，并撰写课程设计报告（电子版），实习报告的开头给出题目、班级、姓名、学号和完成日期，说明调和设计的任务，（4）测试数据，2、概要设计，说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关，实现概要设计中定义的所有数据类型，问题描述：设计一个能演示集合的并、交和差运算的程序，要学年第一学期 课程设计题目及要求
本课程设计一共包括六道大题，请同学们根据自己的爱好选择其中一道大题。每道大题分为若干小题，请根据要求完成，并撰写课程设计报告（电子版）。 实习报告规范 实习报告的开头给出题目、班级、姓名、学号和完成日期，并包括以下内容： 1、需求分析 说明调和设计的任务，主要内容包括： （1）输入的形式和输入值得范围。 （2）输出的形式。 （3）程序所能达到的功能。 （4）测试数据。 2、概要设计 说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系（最好用图说明） 3、详细设计 实现概要设计中定义的所有数据类型，画出函数的调用关系图。 4、调试分析 5、用户使用说明 6、测试结果 7、附录（附全部代码）
一、线性表（第1和第2题均为必做题，难度：?）
1、集合的并、交和差运算的算法。（必做） 问题描述：设计一个能演示集合的并、交和差运算的程序。 要求：演示程序以用户和计算机的对话方式执行。
2、一元多项式的操作。(任意选择三项要求) 问题描述：设计一个一元稀疏多项式简单计算器。 要求： （1）输入并建立多项式。 （2）输出多项式，输出形式为整数序列：n，c1，e1，，c2，e2，?，cn，en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列。 （3）多项式a和b相加，建立多项式a+b。 （4）多项式a和b相减，建立多项式a-b。 （5）计算多项式在x处的值。 （6）求多项式a的导函数。 （7）多项式a和b相乘，建立多项式a*b。
二、栈、队列和递归程序设计（第1题必做，第2和3题任选一题，难度：???）
1、求算术表达式的值。（必做） 问题描述：设计一个程序，演示用算符优先法对算术表达式求值的过程。 要求：以字符序列的形式从终端输入以“#”结束表达式。如果表达式正确计算表达式的值，否则指出表达式中错误的类型。在输入的表达式中可以有加、减、乘、除和括号运算，输入的数据为实数。输出表达式的值，并且输出在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。
2、迷宫问题。 问题描述：随机产生一个m*n的迷宫，0和1分别表示迷宫中的通路和障碍。求出一条从入口到出口的通路，或得到没有通路的结论。 要求：以链表作存储结构的栈类型，写一个非递归程序。
3、HANOI问题的求解演示。 问题描述：设计一个程序，演示HANOI问题的实现过程。 要求： （1）用户可手工移动圆盘实现求解。 （2）用户可让计算机演示求解过程。 （3）用非递归算法实现。
三、数组和广义表（第1和2题均为必做题，难度：??） 1、三元组表示的稀疏矩阵的转置、加法和乘法的实现。（必做） 问题描述：设计一个程序，演示用三元组和十字链表表示的稀疏矩阵的转置、加法和乘法的实现。 要求： （1）演示稀疏矩阵A的三元组和十字链表的建立过程。 （2）演示稀疏矩阵A的转置过程。 （3）演示稀疏矩阵A和B的相加过程。 （4）演示稀疏矩阵A和B的相乘过程。
2、识别广义表的“头”或“尾”的演示。（必做） 问题描述：设计一个程序，建立广义表的存储结构，演示在此存储结构上实现的广义表求头/尾操作序列的结果。 要求： （1）设计一个广义表，允许分多行输入，其中可以任意输入空格符，原则上是不限长的仅由字母或数字组成的串。 （2）按表头和表尾的分解方法编写建立广义表存储结构的算法。
四、树（第1和2题均为必做题，难度：???） 1、二叉树的遍历。（必做） 问题描述：设计一个程序演示在二叉树上进行三种遍历的过程。 要求： （1）从键盘上输入二叉树的每一个结点，演示二叉树T的建立过程。 （2）演示各种遍历的遍历过程。
2、线索二叉树的应用。（必做） 问题描述：设计一个程序，演示线索二叉树的建立和插入、删除结点的过程。 要求： （1）从键盘上输入线索二叉树的每一个结点，演示线索二叉树T的建立过程。 （2）演示在T上插入一棵子树的过程。 （3）演示在T上删除一棵子树的过程。
五、图（第1和2题均为必做题，难度：???） 1、图扁历的演示。（必做） 问题描述：设计一个程序，演示在有向图或无向图中遍历所有结点的过程。 要求： （1）分别用深度优先或广度优先实现（选择一项）。 （2）从任意指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 2、最小生成树。（必做） 问题描述：设计一个程序求连通网中的最小生成树 要求： （1）构造一个不少于10个顶点30条边的连通网。 （2）用Kruskal算法求从任意指定的结点开始的最小生成树。 （3）演示生成过程。
六、查找和排序（第1和2题均为必做题，难度：???） 1、平衡二叉树的操作。 问题描述：利用平衡二叉树实现一个动态查找表 要求： （1）从键盘上接受数据，建立一棵平衡二叉树的过程。 （2）实现动态查找表的三种基本功能：查找、插入和删除。 （3）合并两棵平衡二叉树。 （4）把一棵平衡二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等于X，另一棵树中的任一关键字都大于X。
2、内部排序算法的比较。 问题描述：设计一个程序演示各种内部排序方法在排序时，关键字的比较次数和关键字的移动次数 要求： （1）对常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、系尔排序和堆排序。 （2）随机产生100个以上数据。 包含总结汇报、党团工作、资格考试、工作范文、旅游景点、出国留学、外语学习、行业论文、IT计算机、人文社科以及《数据结构》课程设计题目及要求等内容。
相关内容搜索扫一扫下载手机客户端
扫描我，关注团购信息，享更多优惠
||网络安全
| | | | | | | | | | | | | | | |
||电子电工
汽车交通| | | | | | | | | |
||投资理财
| | | | | | | | | | | | | | | | |
| | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
||外语考试
| | | | | | | | |
| 视频教程|
数据结构与算法（C语言版）（第2版）
定价：￥35.00
校园优惠价：￥24.50 (70折)
促销活动：
商品已成功飞到您的手机啦！快登录手机站看看吧！
下载客户端
> 微信关注“互动出版网”，便捷查询订单，更多惊喜天天有
ISBN：6上架时间：出版日期：2014 年10月开本：16开页码：277版次：2-1
所属分类：
《数据结构与算法：C语言版(第2版)》涵盖数据结构的基本概念，定义了线性表、栈、队列、串、数组、广义表、树和二叉树、图、查找、排序等各种结构的抽象数据类型，给出了相应操作的实现算法，并在最后一章给出了几个课程设计的实例。另一方面，本书采用C语言描述算法，并给出了各种算法的效率分析，以及这些结构在计算机科学及其他领域的应用。此外，每章后均配有典型例题、上机实验和习题。本书中的所有算法都在VC++环境下调试通过。
《数据结构与算法：C语言版(第2版)》在内容安排上突出由浅入深、循序渐进、通俗易懂的特点，算法分析透彻、讲解清晰、便于学生自学。为了激发学生的学习兴趣，培养学生解决实际问题的能力，书中融入了一些典型的应用实例，如命题公式真值表的求解算法、出栈序列的求解算法等。
《数据结构与算法：C语言版(第2版)》可作为高等院校计算机及相关专业本科生的“数据结构”课程教材，也可供相关科技人员学习参考。
《数据结构与算法：C语言版(第2版)》
1.1数据结构的研究对象
1.2数据结构的发展概况
1.3基本概念与术语
1.4数据类型与抽象数据类型
1.4.1数据类型
1.4.2抽象数据类型
1.4.3抽象数据类型的表示与实现
1.5算法与算法分析
1.5.2算法设计的原则
1.5.3算法效率的衡量方法和准则
1.5.4算法的存储空间需求
1.6典型例题
1.7上机实验
　　“数据结构”是计算机程序设计的重要理论技术基础，是计算机学科的核心课程，也是计算机专业考研的必考课程，同时已成为其他理工科专业的热门课程。学好该课程，不仅对学习后续算法设计、数值分析、操作系统、编译原理等课程有很大帮助，而且在实际中有广泛的用途。
　　数据结构主要研究数据的各种组织形式以及建立在这些结构之上的各种运算的实现。它不仅为用计算机语言进行程序设计提供了方法性的理论指导，还在一个更高的层次上总结了程序设计的常用方法和常用技巧。
　　“数据结构”课程的特点是概念多、算法灵活和抽象性强。针对这种情况，我们在参考各种数据结构教材的基础上，结合作者多年的教学经验，编写了这本适用于普通高等院校计算机及相关专业本科生的数据结构教材。本书的编写突出了课程学科能力的培养，体现了“理论和应用”兼顾的教学改革理念。
　　本书分为11章：第1章绪论，介绍数据、数据结构、抽象数据类型等基本概念，特别是算法分析的方法；第2章线性表，介绍线性表的两种存储结构（顺序表和链表）的逻辑结构与基本运算的实现过程；第3章栈与队列，介绍两种特殊的线性结构的概念与应用；第4章串，介绍串的概念与模式匹配算法；第5章数组与广义表，介绍数组和稀疏矩阵的概念及相关运算的实现，以及广义表的存储结构及相关运算的实现；第6章树与二叉树，介绍树与二叉树的概念和各种运算的实现过程，其中特别突出二叉树的各种递归和非递归算法；第7章图，介绍图的基本概念和各种运算的实现过程；第8章查找，介绍各种常用查找算法的实现过程；第9章排序，介绍各种常用排序算法的实现过程；第10章文件，介绍常用的文件结构；第11章课程设计举例，给出了几个重要数据结构的具体实例。
　　数据结构是一门应用性非常强的课程，必须在掌握了各种数据结构的基础上，尽可能多地上机练习。为此，本书每章后面都配有相应的上机实验题。
　　全书采用C语言作为数据结构和算法的描述语言，所有算法均在VC++环境下调试通过。
　　本书具有以下特色：
　　1）语言通俗易懂，阐述简洁明了。
　　2）重点突出算法设计思路，注重培养学生的编程思想和解决实际问题的能力。
　　3）为激发学生学习该课程的兴趣，增强学生的创新意识，书中融入了一些利用所学知识解决实际问题的例子，如真值表的求解算法、出栈序列的求解算法等。
　　4）算法丰富，讲解透彻，便于学生自学。
　　5）通过课程设计的综合训练，使学生在学习理论知识的同时，进一步提高解决实际问题的能力，进一步强化综合应用训练，熟练掌握利用计算机解决问题的一般步骤。
　　6）通过典型算法设计的分析，使学生所学的知识更加系统化和条理化，更易于对所学知识融会贯通和举一反三。
　　7）为方便教师教学，本书配有电子教案和习题答案，可登录华章网站（）下载或发送邮件至xfs@与作者联系。
　　在编写中我们参阅了许多数据结构教材和相关资料，在此向其作者一并表示感谢。本教材的出版得到了德州学院教材出版基金的资助。最后，还要特别感谢机械工业出版社华章公司的大力支持，使得本书得以顺利出版。
　　限于作者水平，书中不当和疏漏之处在所难免，敬请读者不吝指正。
　　随着计算机产业的飞速发展，计算机的应用领域越来越广泛，已不再局限于科学计算，而是更多地用于控制、管理及数据处理等非数值计算的处理工作。所有的系统软件和应用软件都要用到各种类型的数据结构，在计算机中如何组织数据、处理数据就成了人们进行程序设计的关键所在。因此，我们必须研究数据的特性和数据间的相互关系及其对应的存储表示，并设计出相应的算法，更好地实现程序。数据结构是计算机专业的核心课程，该课程的学习可以帮助人们更好地进行程序设计，解决实际问题。
　　1.1数据结构的研究对象
　　自然界中的许多问题是可以用数学工具进行描述的。例如，造桥中的受力问题可描述为线性方程，人口增长的情况可描述为微分方程。但更多的非数值计算问题无法用数学方程加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。请看以下列举的具体问题。
　　例1学生信息检索系统。当我们需要查找某个学生的有关信息或某个专业的情况时，只要建立了相应的数据结构，按照某种算法编写了程序，就可以实现计算机自动检索。由此，可以在学生信息检索系统中建立一个按学号顺序排列的学生信息表和按专业排列的索引表，如表1-1所示。由这个表构成的文件便是学生信息检索的数学模型，计算机的操作就是按照某种要求对学生信息文件进行查询。
　　表1-1学生信息查询系统中的数据结构
　　a）学生信息表
　　学号姓名性别专业年级
　　韦志君男信息管理与信息系统2007级
　　唐立男计算机科学与技术2007级
　　宋奇锋男信息管理与信息系统2007级
　　熊伟男计算机科学与技术2007级
　　许文锋男计算机科学与技术2007级
　　张小龙男信息管理与信息系统2007级
　　陈亚雯女信息管理与信息系统2007级
　　彭金萍女计算机科学与技术2007级
　　b）专业索引表
　　信息管理与信息系统1，3，6，7
　　计算机科学与技术2，4，5，8
系列图书推荐 ￥49.00￥33.32
同类热销商品￥108.00￥86.40
订单处理配送
北京奥维博世图书发行有限公司 china-pub,All Rights Reserved数据结构习题与解析(C语言版)下载李春葆 PDF电子书_清华大学出版社出版西西软件下载
西西软件园多重安全检测下载网站、值得信赖的软件下载站！
相关软件 /中文/ /中文/ /中文/ /中文/ /中文/ /中文/ /中文/ /中文/ /中文/ /中文/顶好评:50%踩坏评:50%请简要描述您遇到的错误，我们将尽快予以修正。轮坛转帖HTML方式轮坛转帖UBB方式
49.0M/中文/4.5
73M/中文/6.0
14.7M/中文/4.8
14.8M/多国语言[中文]/4.0
30.3M/中文/9.1
9.4M/中文/7.3
本书是针对清华大学出版社出版的《数据结构》(秦玉平和马靖善主编)一书编写的辅导教材。本书对教材中的所有习题都做了分析和解答，题目分为单选题、判断题、算法填空题、计算操作题和算法设计题五种类型。针对教学重点和难点，根据教材内容给出了十六组实验题目。另外，本书给出了程序员考试和研究生入学考试的样题和答案，便于学生的复习。本书内容丰富，讲解通俗易懂，具有很强的实用性。&特点：&本书遵循数据结构课程的教学大纲的要求。从内容上分为13章：第1章是概述，讨论数据结构的基本概念及相关题解；第2章是顺序表，讨论基本顺序表即向量、栈和队列的基本内容及相关题解；第3章是链表，讨论各种链表的基本内容及相关题解；第4章是串，讨论串的基本内容及相关题解；第5章是数组和稀疏矩阵，讨论数组和稀疏矩阵的基本内容及相关题解；第6章是递归，讨论基本递归设计方法及相关题解；第7章是广义表，讨论广义表的基本内容及相关题解；第8章是树形结构，讨论树和二叉树的基本内容及相关题解；第9章是图，讨论图的基本内容及相关题解；第10章是查找，讨论基本查找方法及相关题解；第11章是内排序，讨论基本内排序方法及相关题解；第l 2章是文件，讨论基本文件组织结构及相关题解；第13章是外排序，讨论基本外排序方法及相关题解。 李春葆：数据结构习题与解析(C语言版)，很好的习题，有详细答案。目录：第1章　概述1. 1　基本概念1. 1. 1　数据结构1. 1. 2　存储方式1. 1. 3　算法及评价1. 2　基本题1. 2. 1　选择题1. 2. 2　填空题1. 3　习题解析第2章　顺序表2. 1　基本概念和运算2. 1. 1　向量2. 1. 2　栈2. 1. 3　队列2. 2　基本题2. 2. 1　选择题2. 2. 2　填空题2. 3　习题解析2. 3. 1　向量2. 3. 2　栈2. 3. 3　队列第3章　链表3 .1　基本概念和运算3. 1. 1　单链表3. 1. 2　双链表3. 2　基本题3. 2. 1　选择题3. 2. 2　填空题3. 3　习题解析3. 3. 1　单链表3. 3. 2　双链表第4章　串4. 1　串的存储及其运算4. 1. 1　顺序存储及其基本运算4. 1. 2　链接存储及其基本运算4. 2　基本题4. 2. 1　选择题4. 2. 2　填空题4. 3　习题解析第5章　数组和稀疏矩阵5. 1　基本概念和运算5. 1. 1　多维数组5. 1. 2　稀疏矩阵5. 2　基本题5. 2. 1　选择题5. 2. 2　填空题5. 3　习题解析第6章　广义表6. 1　广义表的表示及其运算6. 1. 1　广义表的表示6. 1. 2　广义表的基本运算6. 2　基本题6. 2. 1　选择题6. 2. 2　填空题6. 3　习题解析第7章　速归7. 1　递归设计方法7. 1. 1　递归模型7. 1. 2　递归的执行过程7. 1. 3　递归设计7. 1. 4　递归到非递归的转换7. 2　基本题7. 2. 1　选择题7. 2. 2　填空题7. 3　习题解析第8章　树形结构8. 1　基本概念和运算8. 1. 1　树8. 1. 2　二叉树8. 1. 3　二叉排序树8. 1. 4　树和森林8. 1. 5 huffman树8. 2　基本题8. 2. 1　选择题8. 2. 2　填空题8. 3　习题解析第9章　图9. 1　图的存储及其运算9. 1. 1　图的基本术语
安卓官方手机版
IOS官方手机版
数据结构习题与解析(C语言版) 李春葆 PDF电子书
下载帮助西西破解版软件均来自互联网, 如有侵犯您的版权, 请与我们联系。【数据结构历年考研试题】第5章数组和广义表_甜梦文库
【数据结构历年考研试题】第5章数组和广义表
第 5章 数组和广义表一、选择题 1.设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a11 为第一元素，其 存储地址为 1，每个元素占一个地址空间，则 a85 的地址为（ ）【燕山大学 2001 一、2 。 （2 分） 】 A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组 A[1:6， 0:7] 每个数组元素用相邻的 6 个字节存储， 存储器按字节编址， 那么这个数组的体积是（①）个字节。假设存储数组元素 A[1，0]的第一个字节的地址是 0， 则存储数组 A 的最后一个元素的第一个字节的地址是（②） 。若按行存储，则 A[2，4]的第 一个字节的地址是（③） 。若按列存储，则 A[5，7]的第一个字节的地址是（④） 。就一般情 况而言，当（⑤）时，按行存储的 A[I，J]地址与按列存储的 A[J，I]地址相等。供选择的 答案： 【上海海运学院 1998 二、2 （5 分） 】 ①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120 G. 156 H. 234 I. 276 J. 282 K. 283 L. 288 ⑤： A．行与列的上界相同 B. 行与列的下界相同 C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同 3. 设有数组 A[i,j]，数组的每个元素长度为 3 字节，i 的值为 1 到 8 ，j 的值为 1 到 10， 数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素 A[5，8]的存储首地址为 ( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 【南京理工大学 1997 一、8 （2 分） 】 4. 假设以行序为主序存储二维数组 A=array[1..100，1..100]，设每个数据元素占 2 个存 储单元，基地址为 10，则 LOC[5，5]=（ ）【福州大学 1998 一、10 (2 分)】 。 A. 808 B. 818 C. 1010 D. 1020 5. 数组 A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A[5，5]的地址是( )。 【南京理工大学 2001 一、13 （1.5 分） 】 A. 1175 B. 1180 C. 1205 D. 1210 6. 有一个二维数组 A[0:8,1:5],每个数组元素用相邻的 4 个字节存储，存储器按字节编址， 假设存储数组元素 A[0,1]的第一个字节的地址是 0， 存储数组 A 的最后一个元素的第一个字 节的地址是（ ① ） 。若按行存储，则 A[3,5]和 A[5,3]的第一个字节的地址是（ ② ） 和（ ③ ） 。若按列存储，则 A[7,1]和 A[2,4]的第一个字节的地址是（ ④ ）和（ ⑤ ） 。 【上海海运学院 1996 二、1 （5 分） 】 ①-⑤:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188 7. 将一个 A[1..100，1..100]的三对角矩阵，按行优先存入一维数组 B[1E298]中，A 中元 素 A6665（即该元素下标 i=66，j=65） ，在 B 数组中的位置 K 为（ ） 。供选择的答案： A. 198 B. 195 C. 197 【北京邮电大学 1998 二、5 （2 分） 】 8. 二维数组 A 的元素都是 6 个字符组成的串，行下标 i 的范围从 0 到 8，列下标 j 的范圈 从 1 到 10。从供选择的答案中选出应填入下列关于数组存储叙述中（ ）内的正确答案。 （1）存放 A 至少需要（ ）个字节； （2）A 的第 8 列和第 5 行共占（ ）个字节； （3）若 A 按行存放，元素 A[8，5]的起始地址与 A 按列存放时的元素（ ）的起始地址一致。 供选择的答案： （1）A. 90 B. 180 C. 240 D. 270 E. 540 （2）A. 108 B. 114 C. 54 D. 60 E. 150 （3）A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9] 【山东工业大学 2000 三、1 （4 分） 【山东大学 1998 三、1 (4 分)】 】 9. 二维数 组 A 的每 个元素是 由 6 个 字符组成的串，其 行下 标 i=0,1,? ,8,列下 标 j=1,2,?,10。 A 按行先存储， 若 元素 A[8,5]的起始地址与当 A 按列先存储时的元素 （ ） 的起始地址相同。设每个字符占一个字节。 【西安电子科技大学 1998 一、2 （2 分） 】 A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9] 10. 若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素) 依次存放于一维数组 B 1..(n(n+1))/2］ 则在 B 中确定 aij ［ 中， （i&j） 的位置 k 的关系为( )。 A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i 【北京航空航天大学 2000 一、2 （2 分） 】 11. 设 A 是 n*n 的对称矩阵， A 的对角线及对角线上方的元素以列为主的次序存放在一维 将 数组 B[1..n(n+1)/2]中， 对上述任一元素 aij(1≤i， j≤n， i≤j)在 B 中的位置为( 且 )。 A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-1 【南京理工大学 1999 一、9（2 分） 】 12. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组 T[N（N+1）/2] 中，则对任一上三角元素 a[i][j]对应 T[k]的下标 k 是（ ）【青岛大学 2002 二、6 （2 。 分） 】 A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1 13. 设二维数组 A[1.. m，1.. n]（即 m 行 n 列）按行存储在数组 B[1.. m*n]中，则二维数 组元素 A[i，j]在一维数组 B 中的下标为( )。 【南京理工大学 1998 一、2 （2 分） 】 A.（i-1）*n+j B.（i-1）*n+j-1 C. i*（j-1） D. j*m+i-1 14. 有一个 100*90 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表 示该矩阵时，所需的字节数是（ ）【南京理工大学 1999 二、8 （2 分） 。 】 A. 60 B. 66 C. 18000 D. 33 15. 数组 A[0..4,-1..-3,5..7]中含有元素的个数（ ）【中山大学 1998 二、5（2 分） 。 】 A. 55 B. 45 C. 36 D. 16 16. 用数组 r 存储静态链表，结点的 next 域指向后继，工作指针 j 指向链中结点，使 j 沿 链移动的操作为( )。 【南京理工大学 2001 一、16（1.5 分） 】 A. j=r[j].next B. j=j+1 C. j=j-&next D. j=r[j]-& next 17. 对稀疏矩阵进行压缩存储目的是（ ）【北京工商大学 2001 一、1 (3 分)】 。 A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间 复杂度 18. 已知广义表 L=（ （x,y,z） （u，t，w），从 L 表中取出原子项 t 的运算是（ ，a， ） ） 。 A. head（tail（tail（L）） ） B. tail（head（head（tail（L）） ）） C. head（tail（head（tail（L）） ）） D. head（tail(head（tail（tail（L））)） ） 【北京邮电大学 1998 二、4（2 分） 】 19. 已知广义表 LS＝((a,b,c),(d,e,f)),运用 head 和 tail 函数取出 LS 中原子 e 的运算是 ( )。 A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS))))【西安电子科技大学 2001 应用一、3（2 分） 】 20. 广义表 A=(a,b,(c,d),(e,(f,g))),则下面式子的值为 （ ） 。 【北京邮电大学 1999 一、 2（2 分） 】 Head(Tail(Head(Tail(Tail(A))))) A. (g) B. (d) C. c D. d 21. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C))) =( )。 【长沙铁道学院 1998 三、4 (2 分)】 A.（a） B. A C. a D. (b) E. b F. (A) 22. 广义表运算式 Tail(((a,b),(c,d)))的操作结果是（ ）【西安电子科技大学 1998 。 一、4（2 分） 】 A. (c,d) B. c,d C. ((c,d)) D. d 23. 广义表 L=（a， （b，c），进行 Tail（L）操作后的结果为（ ）【中山大学 1999 一、 ） 。 10】 A. c B. b，c C.（b，c） D.（ （b，c） ） 24. 广义表（ （a,b,c,d） ）的表头是（ ） ，表尾是（ ）【青岛大学 2002 二、7 （2 。 分） 】 A. a B.（） C.（a,b,c,d） D.（b,c,d） 25. 广义表（a,(b,c),d,e）的表头为（ ）【中山大学 1998 二、6（2 分） 。 】 A. a B. a,(b,c) C. (a,(b,c)) D. (a) 26. 设广义表 L=（ （a,b,c），则 L 的长度和深度分别为（ ） ）【武汉大学 2000 二、9】 。 A. 1 和 1 B. 1 和 3 C. 1 和 2 D. 2 和 3 27. 下面说法不正确的是( )。 【南京理工大学 2001 一、3 （1.5 分） 】 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 二、判断题 1. 数组不适合作为任何二叉树的存储结构。（ ）【南京航空航天大学 1995 五、2 （1 分） 】 2. 从逻辑结构上看，n 维数组的每个元素均属于 n 个向量。（ ） 【东南大学 2001 一、2 （1 分）【中山大学 1994 】 一、2 （2 分） 】 3. 稀疏矩阵压缩存储后， 必会失去随机存取功能。 （ ） 【中科院软件所 1997 一、 （1 1 分） 】 4. 数组是同类型值的集合。 （ ） 【上海海运学院 1996 一、3（1 分）1999 一、4（1 分） 】 5. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。 （ ） 【上海交通大学 1998 一、5】 6. 一个稀疏矩阵 Am*n 采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换， 并把 m 和 n 的值互换，则就完成了 Am*n 的转置运算。（ ） 【西安交通大学 1996 二、8 (3 分)】 7. 二维以上的数组其实是一种特殊的广义表。（ ） 【北京邮电大学 2002 一、5 （1 分） 】 8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ） 【南京航空航天大学 1996 六、2 （1 分） 】 9. 若一个广义表的表头为空表，则此广义表亦为空表。（ ）【中科院软件所 1997 一、8（1 分） 【长沙铁道学院 1998 一、8 (1 分)】 】 10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。 （ ） 【合肥工业大学 2000 二、3 （1 分） 】 11. 所谓取广义表的表尾就是返回广义表中最后一个元素。 （ ） 【合肥工业大学 2001 二、 3 （1 分） 】 12. 广义表的同级元素（直属于同一个表中的各元素）具有线性关系。 （ ） 【华南理工大学 2002 一、9（1 分） 】 13. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。 （ ） 【华南理工大学 2002 一、10（1 分） 】 14. 一个广义表可以为其它广义表所共享。 （ ） 【山东大学 2001 一、2（1 分） 】 三、 填空题 1. 数组的存储结构采用_______存储方式。 【中山大学 1998 一、6（1 分） 】 2. 设二维数组 A[-20..30,-30..20], 每个元素占有 4 个存储单元, 存储起始地址为 200. 如按行优先顺序存储,则元素 A[25,18]的存储地址为__（1）_；如按列优先顺序存储,则元 素 A[-18,-25]的存储地址为__（2）_。 【北方交通大学 1999 二、3（4 分） 】 3. 设数组 a[1..50,1..80]的基地址为 2000， 每个元素占 2 个存储单元， 若以行序为主序顺 序存储， 则元素 a[45,68]的存储地址为_ （1） _;若以列序为主序顺序存储， 则元素 a[45,68] 的存储地址为_（2）_。 【华中理工大学 2000 一、5（2 分） 】 4. 将整型数组 A[1..8，1..8]按行优先次序存储在起始地址为 1000 的连续的内存单元中， 则元素 A[7，3]的地址是：_______。 【合肥工业大学 1999 三、4（2 分） 】 5. 二维数组 a[4][5][6]（下标从 0 开始计，a 有 4*5*6 个元素） ，每个元素的长度是 2，则 a[2][3][4]的地址是____。(设 a[0][0][0]的地址是 1000,数据以行为主方式存储) 【南京理工大学 2000 二、11（1.5 分） 】 6. 设有二维数组 A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为 100， 若按列优先顺序存储， 则元素 A[6,6]存储地址为_______。【北京工商大学 2001 二、 （4 5 分） 】 7. 已知数组 A[0..9,0..9]的每个元素占 5 个存储单元， 将其按行优先次序存储在起始地址 为 1000 的连续的内存单元中，则元素 A[6，8]的地址为_______。 【合肥工业大学 2001 三、 4（2 分） 】 8. 已知二维数组 A[1..10，0..9]中每个元素占 4 个单元，在按行优先方式将其存储到起始 地址为 1000 的连续存储区域时，A[5，9]的地址是：_______。 【厦门大学 2002 六、5 （4 分）】 9. 用一维数组 B 与列优先存放带状矩阵 A 中的非零元素 A[i,j] (1≤i≤n,i-2≤j≤i+2),B 中的第 8 个元素是 A 中的第_（1）_行，第_（2）_列的元素。 【北京邮电大学 2001 二、3 （4 分） 】 10. 设数组 A[0..8,1..10],数组中任一元素 A[i,j]均占内存 48 个二进制位， 从首地址 2000 开始连续存放在主内存里，主内存字长为 16 位，那么 （l） 存放该数组至少需要的单元数是_______; （2） 存放数组的第 8 列的所有元素至少需要的单元数是_______; （3） 数组按列存储时，元素 A[5,8]的起始地址是_______。 【中国矿业大学 2000 一、 4（4 分） 】 11．设 n 行 n 列的下三角矩阵 A 已压缩到一维数组 B[1..n*（n+1）/2]中，若按行为主序存储，则 A[i,j]对应的 B 中存储位置为_______。 【武汉大学 2000 一、1】 12. n 阶对称矩阵 a 满足 a[i][j]=a[j][i],i,j=1..n,，用一维数组 t 存储时，t 的长度为 __(1)______，当 i=j，a[i][j]=t[(2)],i&j,a[i][j]=t[(3)],i&j,a[i][j]=t[(4)]。 【青岛 大学 2001 六、1（3 分） 】 13．己知三对角矩阵 A【1..9,1..9】的每个元素占 2 个单元，现将其三条对角线上的元素 逐行存储在起始地址为 1000 的连续的内存单元中，则元素 A[7,8]的地址为______。 【合肥 工业大学 2000 三、4（2 分） 】 14. 设有一个 10 阶对称矩阵 A 采用压缩存储方式（以行为主序存储：a11=1），则 a85 的地 址为_______。 【西安电子科技大学 1999 软件 一、3 （2 分） 】 15. 所谓稀疏矩阵指的是_______。【厦门大学 2001 一、2 （14%/5 分） 】 16. 对矩阵压缩是为了_______。 【北京理工大学 2000 二、3（2 分） 】 17. 上三角矩阵压缩的下标对应关系为：_______。 【福州大学 1998 二、6 (2 分)】 【南京 大学 1999】 18. 假设一个 15 阶的上三角矩阵 A 按行优先顺序压缩存储在一维数组 B 中， 则非零元素 A9,9 在 B 中的存储位置 k=_______。 （注： 矩阵元素下标从 1 开始） 【北京工商大学 2001 二、 （4 1 分） 】19．设下三角矩阵 A= 如果按行序为主序将下三角元素 Ai j (i,j)存储在一个一维数组 B[ 1..n(n+1)/2]中，对 任一个三角矩阵元素 Aij ,它在数组 B 中的下标为_______。 【北方交通大学 2001 二、3】 20. 当广义表中的每个元素都是原子时，广义表便成了_______。 【长沙铁道学院 1998 二、 8 (2 分)】 21. 广义表的表尾是指除第一个元素之外，_______。 【中山大学 1998 一、7 （1 分） 】 22. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于 (1)____。为了区分原子和表，一般用 (2)____表示表，用 (3)_____表示原子。一个表 的长度是指 (4)__，而表的深度是指__(5)__【山东工业大学 2000 一、3（3 分） 【山 】 东大学 1998 一、2 (3 分)】 23. 广义表的_______ 定义为广义表中括弧的重数。 【重庆大学 2000 一、5】 24．设广义表 L=((),()), 则 head(L)是(1)___；tail(L)是(2)____；L 的长度是(3)___； 深度是 (4)__。 【中科院计算所 1998 一、2（4 分）【中国科技大学 1998 一、2（4 分） 】 】 25. 已知广义表 A=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作 Head( )和 Tail( ) 将原子元素 99 从 A 中取出来。 【西安交通大学 1996 四、5 (5 分)】 26. 广义表的深度是_______。 【北京轻工业学院 2000 一、1（2 分） 】 27. 广义表(a,(a,b),d,e,((i,j),k))的长度是（1）_，深度是（2）_。 【山东大学 2001 三、 9 (2 分)】 【西安电子科技大学 2001 软件 一、5 （2 分） 【哈尔滨工业大学 2001 一、2 （2 】 分） 】 28. 已知广义表 LS=(a，(b，c，d)，e),运用 head 和 tail 函数取出 LS 中原子 b 的运算是_______。 【燕山大学 2001 二、2 （3 分） 】 29. 广义表 A=（（a，b）（c，d，e）） （ ， ），取出 A 中的原子 e 的操作是: _______。 【合肥工业大学 1999 三、5（2 分） 】 30. 设某广义表 H=（A， （a,b,c） ，运用 head 函数和 tail 函数求出广义表 H 中某元素 b ） 的运算式_______。 【北京科技大学 1997 一、5】 31. 广义表 A((( ),(a,(b),c)))，head(tail(head(tail(head(A))))等于 。 【合肥工业大学 2000 三、5（2 分） 】 32. 广义表运算式 HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。 【西安电子科技大学 1999 软件 一、9（2 分） 】 33. 已知广义表 A=（（a，b）（c）（d，e）） （ ， ， ），head（tail（tail（head（A）） ））的结果 是_______。 【合肥工业大学 2001 三、5 （2 分） 】 34. 利用广义表的 GetHead 和 GetTail 操作， 从广义表 L=（apple， （ pear） banana， （ ， orange） ） 中分离出原子 banana 的函数表达式是_______。 【山东大学 2001 三、6 (2 分)】 35. 已知 a 数组元素共 5 个， 依次为 12， 10， 3， b 数组元素共 4 个， 5， 1； 依次为 4,6,8,15， 则执行如下所示的过程语句 sort 后得到 c 数组各元素依次为 15,12,10,8,6,5,4,3,1； 数组 a,b,c 的长度分别为 l=5,m=4,n=9 请在程序中方框内填入正确的成分，完成上述要求。 PROCEDURE VAR i, j, k, x: d: ARRAY[1..m] OF BEGIN FOR i:=1 TO m DO d[i]:=(1) ; i:=1; j:=1; k:=1; WHILE (i&=l) AND (j&=m) DO BEGIN IF a[i]&d[j] THEN BEGIN(2) ; (3) _END ELSE BEGIN (4)__; (5) __END; c[k]:=x; (6) END; WHILE(7) _DO BEGIN c[k]:=a[i]; k:=k+1; i:=i+1；END; WHILE(8) _DO BEGIN c[k]:=d[j]; k:=k+1; j:=j+1；END; END. {sort} 【上海交通大学 1998 七 (12 分)】 36. 下列程序段 search(a,n,k)在数组 a 的前 n(n&=1)个元素中找出第 k(1&=k&=n)小的值。 这里假设数组 a 中各元素的值都不相同。 #define MAXN 100 int a[MAXN],n,k; int search_c(int a[], int n, int k) {int low, high, i, j, m, k--,;low=0 ;high=n-1; do {i= j= t=a[low]; do{while (i&j && t&a[j]) j--;if (i&j) a[i++]=a[j]; while (i&j && t&=a[i]) i++ if (i&j) a[j--]=a[i]; } while (i&j); a[i]=t; if (1) ; if (i&k) low= (2) ; else high= (3) ; }while(4) _; return(a[k]); } 【上海大学 1999 一、1（8 分） 】 37. 完善下列程序，每小题在 PASCAL 语言（a）和 C 语言（b）中任选一题。下面是一个将 广义表逆置的过程。 例如原来广义表为 （a,b） （d,e）， （ ,c, ） 经逆置后为： （ （e,d） （b,a）。 ,c, ） （a）算法的 PASCAL 语言过程描述（编者略）（b）算法的 C 语言过程描述： ： typedef struct glistnode { struct glistnode * union{ struct{struct glistnode *hp,*} } }*glist, glist reverse(p) {glist q,h,t,s; if(p==NULL) q=NULL; else {if(1) { q=(glist)malloc(sizeof(gnode)); q-&tag=0; q-&val.data=p-&val. } else {(2) if (3) {t=reverse(p-&val.ptr.tp); s=t; while(s-&val.ptr.tp!=NULL) s=s-&val.ptr. s-&val.ptr.tp=(glist)malloc(sizeof(gnode)); s=s-&val.ptr.s-&tag=1;s-&val.ptr.tp=NULL; s-&val.ptr.hp=h; (4) __ } else {q=(glist)malloc(sizeof(gnode));q-&tag=1; q-&val.ptr.tp=NULL; (5) ; } } } return(q); } 【上海大学 2002 六、3 （10 分） 】 38. 完善下列程序，每小题在 PASCAL 语言（a）和 C 语言（b）中任选一题。下面的程序将 数列 1,2,3,?,n*n,依次按蛇型方式存放在二维数组 A[1..n,1..n]中。 (示意D编者略)。 即 （a）算法的 PASCAL 语言程序描述（编者略）（b）算法的 C 语言程序描述： ：#define NMAX 10 #include “stdio.h” main() { int i,j,n,k,p,q,m; int a [NMAX][NMAX]; scanf(“%d”,&n); m=1; for(k=1；(1) ；k++) {if（k&n） q=k； else(2) __; for(p=1;p&=q;p++) {if(3) {i=q-p+1；j=p；} else{i=p；j=q-p+1；} if(4) {i=i+n-q；j=j+n-q；} a[i][j]=m；(5) _; } for（i=1；i&=n;i++） { for（j=1；j&=n；j++） printf（ “%4d”,a[i][j]）;printf(“\n”); } } } 【上海大学 2002 六、1 （10 分） 】 39. 约瑟夫环问题：设有 n 个人围坐一圈，并按顺时针方向 1―n 编号。从第 s 个人开始进 行报数， 报数到第 m 个人， 此人出圈， 再从他的下一个人重新开始从 1 到 m 的报数进行下去 ， 直到所有的人都出圈为止。 PROCEDURE Josef (A:ARRAY [1..n] OF s,m:integer); BEGIN FOR i:= 1 TO n DO A[i]:=i; sl:=s; FOR i:=n DOWNTO 2 DO BEGIN sl:= (1) __；//计算出圈人 s1 IF sl=0 THEN (2) _； w:=A[sl]; //A[s1]出圈 FOR j:= (3) __ DO A[j]:=A[j+1]; A[i]:=w; END; write('出圈序列为：’)；//输出出圈序列 FOR i :=n DOWNTO 1 DO write(A[i]); writeln ； END; 【华南师范大学 2000 五、2 (9 分)】 40. 设有一个背包可以放入的物品重量为 S，现有 n 件物品，重量分别为 W1，W2，...，Wn。 问能否从这 n 件物品中选择若干件放入背包，使得放入的重量之和正好是 S。设布尔函数 Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组 W 中。 请在下列算法的下划线处填空，使其正确求解背包问题。 Knap(S，n) 若 S=0则 Knap←true 否则若（S&0）或(S&0 且 n&1) 则 Knap←false 否则若 Knap(1) , _=true 则 print(W[n])；Knap ←true 否则 Knap←Knap(2) _ , _ 【山东工业大学 1996 五（10 分）1998 二、1 （4 分） 】 四 应用题 1. 数组 A[1..8，-2..6，0..6]以行为主序存储，设第一个元素的首地址是 78，每个元素的 长度为 4，试求元素 A[4,2,3]的存储首地址。【厦门大学 1998 五、1 （5 分）】 2. 已知 b 对角矩阵（aij）n*n，以行主序将 b 条对角线上的非零元存储在一维数组中，每个 数据元素占Ｌ个存储单元，存储基地址为Ｓ，请用 i，j 表示出 aij 的存储位置。 【北方交通 大学 1996 三（10 分） 】 3. 数组 A 中， 每个元素 A[i,j]的长度均为 32 个二进位,行下标从-1 到 9， 列下标从 1 到 11， 从首地址 S 开始连续存放主存储器中，主存储器字长为 16 位。求： （1）存放该数组所需多少单元？ （2）存放数组第 4 列所有元素至少需多少单元？ （3）数组按行存放时，元素 A[7,4]的起始地址是多少？ （4）数组按列存放时，元素 A[4,7]的起始地址是多少？ 【大连海事大学 1996 四、1 (6 分)】 4．假设按低下标优先存储整型数组 A（-3:8,3:5,-4:0,0:7）时，第一个元素的字节存储地 址是 100，每个整数占 4 个字节，问 A（0，4，-2，5）的存储地址是什么？【清华大学 1996 三】 5．设有三维数组 A[-2:4,0:3,-5:1]按列序存放，数组的起始地址为 1210，试求 A(1,3,-2） 所在的地址。 【长沙铁道学院 1997 三、1 (3 分)】 6. 三维数组 A[1..10,-2..6,2..8]的每个元素的长度为 4 个字节，试问该数组要占多少个 字节的存储空间？如果数组元素以行优先的顺序存贮，设第一个元素的首地址是 100，试求 元素 A[5,0,7] 的存贮首地址。 【上海海运学院 1995 三（6 分） 1997 三（8 分） 】 7. 设有五对角矩阵 A=(aij)20*20，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于 数组 A[-10：m]中，计算元素 A[15,16]的存储位置。 【东北大学 1999 一、2（4 分） 】 8． 数组 A[0..8, 1..10] 的元素是 6 个字符组成的串， 则存放 A 至少需要多少个字节？ A 的 第 8 列和第 5 行共占多少个字节？若 A 按行优先方式存储，元素 A[8,5]的起始地址与当 A 按列优先方式存储时的哪个元素的起始地址一致？ 【厦门大学 2000 五、3（14%/3 分）】 9. 若按照压缩存储的思想将 n×n 阶的对称矩阵 A 的下三角部分 （包括主对角线元素） 以行 序为主序方式存放于一维数组 B[1..n(n+1)/2]中，那么，A 中任一个下三角元素 aij(i≥j), 在数组 B 中的下标位置 k 是什么？【北京航空航天大学 1998 一、4（4 分） 】 10. 设 m×n 阶稀疏矩阵 A 有 t 个非零元素，其三元组表表示为 LTMA[1..（t+1）,1..3]， 试问： 非零元素的个数 t 达到什么程度时用 LTMA 表示 A 才有意义？ 【北京航空航天大学 1998 一、5（4 分） 】 11. 利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间。 【西北工业大学 1998 三、2(5 分)】 12. 对一个有 t 个非零元素的 Amn 矩阵, 用 B[0..t][1..3]的数组来表示，其中第 0 行的三个元素分别为 m,n,t, 从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元 素的行号， 第二列为其列号， 第三列为其值。 对这样的表示法， 如果需要经常进行该操作--确定任意一个元素 A[i][j]在 B 中的位置并修改其值，应如何设计算法可以使时间得到改 善？【长沙铁道学院 1998 四、4 (6 分)】 13. 有一个二维数组 A[0:8,1:5],每个数组元素用相邻的 4 个字节存储,存储器按字节编址, 假设存储数组元素 A[0,1]的第一个字节的地址是 0,那么存储数组的最后一个元素的第一个 字节的地址是多少?若按行存储,则 A[3,5]和 A[5,3]的第一个字节的地址是多少?若按列存 储,则 A[7,1]和 A[2,4]的第一个字节的地址是多少?【上海海运学院 1999 三（10 分） 】 14. 设有三对角矩阵(ai,j)mwn,将其三条对角线上的元素逐行的存于数组 B(1:3n-2)中，使得 B[k]=ai,j，求： （1）用 i,j 表示 k 的下标变换公式； 3 （2）若 n=10 ,每个元素占用 L 个单元，则用 B[K]方式比常规存储节省多少单元。 【西安电子科技大学 1996 二、4 （5 分） 】 15. 已知 A 为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构（二维数组和三元组表）完成求运算的优缺点。 【西安电子科技大学 1996 二、6（5 分） 】16. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？ 【北京邮电大学 2001 三、1（5 分） 】 17. 试叙述一维数组与有序表的异同。 【西安电子科技大学 1999 计应用一、2（5 分） 】 18. 一个 nwn 的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？ 【西安电子科技大学 1999 计应用 一、3（5 分） 】 19. 给出数组 A∶ARRAY[3..8,2..6] OF INTEGER;当它在内存中按行存放和按列存放时，分 别写出数组元素 A[i,j]地址计算公式（设每个元素占两个存储单元）【南开大学 1998 一 。 (8 分)】 20. 已知 n 阶下三角矩阵 A（即当 i&j 时，有 aij=0） ，按照压缩存储的思想，可以将其主对 角线以下所有元素(包括主对角线上元素 )依次存放于一维数组 B 中，请写出从第一列开始 采用列序为主序分配方式时在 B 中确定元素 aij 的存放位置的公式。北京航空航天大学 1999 【 二(10 分)】 【中山大学 1999 三 2】 21. 设有三对角矩阵(aij)n*n，将其三条对角线上的元素逐行地存于数组 B(1:3n-2)中，使 得 B[k]=aij，求： （1）用 i,j 表示 k 的下标变换公式； （2）用 k 表示 i,j 的下标变化公式。 【山东科技大学 2001 一、6 （6 分）【长沙铁道学院 1997 五、1 (10 分)】 】 【东北大学 2002 一 (4 分)】 【北京工业大学 2000 二、1 (9 分)】 【南京航空航天大学 2000 四】 22. 算法 Print 及所引用的数组 A 的值如下，写出调用 Print(1)的运行结果（其中 n=15） 。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G O O H 0 I J K L PROCEDURE print（i：integer） ； BEGIN IF（i&=n〉 AND （A[i] &&‘0’ THEN ） BEGIN Print（2*i） ；write（A[i]） ；Print（2*i+1） END； ； END； 【合肥工业大学 1999 四、1（5 分） 】23. 设数组 A 的长度为 2N，前 N 个元素 A[1..N]递减有序，后 N 个元素 A[N+1.. 2N]递增有 序， 2N 是 2 的整数次幂， k=log22N 为整数。 且 即 例如 A[1..8]=[90,85,50,10,30,65,80,100] 满足上述要求， 这里 N=4,k=3,A 的前 4 个元素和后 4 个元素分别递减和递增有序。 用此例调 用如下的 Demo 过程，并要求： （1）给出 for 循环中每次执行 PerfectShuffle（A,N）和 CompareExchange（A,N）的结果； （2）解释 Demo 的功能； （3）给出 Demo 的时间复杂度。 PROCEDURE PerfectShuffle(VAR A: N:integer) [ i:=1; j:=1; WHILE i&=N DO [ B[j]:=A[i]; B[j+1]:=A[i+N]; i:=i+1; j:=j+2; ] A[1..2N]:=B[1..2N]; //B copy to A ] PROCEDURE CompareExchange(VAR A: N:integer) [ j:=1; WHILE j&2N DO [ IF A[j]&A[j+1] THEN A[j]←→A[j+1]; //交换 A[j]和 A[j+1] j:=j+2; ] ] PROCEDURE Demo (VAR A:N:integer) //A 的长度为 2N,k=log22N 为整数 [ FOR i:=1 TO log22N DO [ PerfectShuffle(A,N); CompareExchange(A,N); ] ] 【中科院计算所 1998 四 （15 分） 【中国科技大学
分） 】 】 24. 现有算法及正整数 n 和数组 A 如下，求数组 C 的值。 VAR A,B,C:Array[1..100] FUNC AAA(s,t:integer): IF s=t THEN IF B[s]=0 THEN AAA:=S ELSE AAA:=-s ELSE BEGIN l:=AAA(s,(s+t) DIV 2); r:=AAA((s+t) DIV 2+1,t); IF l&0 THEN AAA:=l ELSE AAA:=r; IF (r&0) AND (A[l]&A[r]) THEN AAA:=r END ENDF; PROC BBB; FOR i:=1 TO n DO B[i]:=0; FOR i:=1 TO n DO B[AAA(1,n)]:=i; FOR i:=1 TO n DO C[B[i]]:=A[i]; ENDP; 初始值：n=10,A={121,22,323,212,636,939,828,424,55,262}; 【北京邮电大学 2002 五、1（10 分） 】25. 设有矩阵ａ且 a=执行下列语句后，矩阵ｃ和ａ的结果分别是什么？（1） FOR i:=1 TO 3 DO FOR j:=1 TO 3 DO c[i,j]:=a[a[i,j],a[j,i]] （2） FOR i:=1 TO 3 DO FOR j:=1 TO 3 DO a[i,j]:=a[a[i,j],a[j,i]] 【浙江大学 1997 三 (8 分)】26. 设矩阵 A 为 i:=1 TO 3 DO j:=1 TO 3 DO ① C[i,j]:=A[A[i,j],A[j,i]] 结果 C 矩阵的值是什么？ （2）所选择的下标 i,j 的次序有关系吗？ （3）在语句①中，用 A 代替 C，A 的结果值是什么？ （4）对 i,j 这对下标取反序，即 （3，3）（3，2）（3，1） ， ， ，??， （1，3）（1，2）（1，1） ， ， 重复执行 （3）,把所得结果与（3）中所得结果作比较。 【吉林大学 1995 二 (15 分)】 27. 指出下列算法中错误、低效之处，并将其改成一个正确且高效的算法。 PROCEDURE delk(A, m , last,i, k) ; ｛从数组 A[１..last]中删除第 i 个元素起的 k 个元素，m 为 A 上限｝ BEGIN IF(i&1) OR (i&last) OR(k&0) OR(last&m) THEN write ('error') ELSE FOR count: = 1 TO k TO [FOR j:=last DOWNTO i+1 DO A[j-1]:=A[j]; last:=last-1] ENDP;{delk} 【北方交通大学 1997 一 （10 分） 】 28. 设输入为整数数组 A[1..n]， 其中 1&=A[i]&=k(1&=i&=n)； 输出数组为 b[1..n]； c[1..k] 是临时工作空间；阅读下述算法后，回答下列问题： PROC Demo(A,B,k){ (1)FOR i:=1 TO k DO C[i]:=0; (2)FOR j:=1 TO n DO C[A[j]]:= C[A[j]]+1; (3)FOR i:=2 TO k DO C[i]:= C[i]+ C[i-1] (4)FOR j:=n DOWNTO 1 DO { (5) B[C[A[j]]]:=A[j]; (6)C[A[j]]:=C[A[j]]-1 } } (a).当标号（2）行的循环执行完后，C[i](1&=i&=n)的值有何意义？ （1）执行语句 FOR FOR(b).当标号（3）行的循环执行完后，C[i](1&=i&=n)的值有何意义？ (c).算法执行后，B 的内容有何特点？ (d).当 k=O(n)时，算法的时间复杂度是多少？ 【中科院软件所 1997 二、2（9 分） 】 29．上三角阵 A（N*N）按行主序压缩存放在数组 B 中，其中 A[i,j]=B[k].写出用 i，j 表示 的 k。 【北京工业大学 2001 二、1 (5 分)】 30. 设有上三角矩阵(aij)n*n，将其上三角中的元素按先行后列的顺序存于数组 B（1:m）中， 使得 B[k]= aij 且 k=f1(i)+f2(j)+c，请推导出函数 f1,f2 和常数 c，要求 f1 和 f2 中不含 常数项。 【中科院自动化所 1999】 【山东科技大学 2002 一、5 （6 分） 】31． 设矩阵 A= (1) 若将 A 视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取 A 中元素 aij (0&=i,j&4)； (2) 若将 A 视为稀疏矩阵，画出 A 的十字链表结构。 【北京科技大学 1997 三 （10 分） 】32. 设对称矩阵 A= （1）若将 A 中包括主对角线的下三角元素按列的顺序压缩到数组 S 中, 即 S: 1下标：10023000502 3 4 5 6 7 8 9 10 试求出 A 中任一元素的行列下标[i,j](1&=i,j&=4)与 S 中元素的下标 K 之间的关系. （2）若将 A 视为稀疏矩阵时,画出其三元组表形式压缩存储表。 【北京科技大学 1999 三 （10 分） 】33. 设对角线矩阵 A= （ 行列下标 i ,j 满足：1≤i,j≤5） （1）若将矩阵 A 压缩存储到数组 S 中： 1 2 1 0 1 2 1 0 0 0 1 3 5 下标： 1 2 3 4 5 6 7 8 9 10 11 12 13 试求出 A 中已存储之元素的行列下标（i， j）与 S 中元素的下标 K 之间的关系 （2） 若将 A 视为稀疏距阵时， 请画出其行逻辑链接顺序表。 【北京科技大学 2000 三(10 分)】 34．设有一个三维数组 a[c1:d1,c2:d2,c3:d3]，其中 ci:di 是第 i 维的界偶，如该数组在 内存中按行排列，且 a[c1,c2,c3]的地址为 a0，那么请导出下标变量 a[i1,i2,i3]的地址， 假设每个元素占 L 个单元。【山东师范大学 1999 四、1 （5 分） 】 35 ． 假 定 有 下 列 n n矩阵（n为奇数）A= 如果用一维数组 B 按行主次序存储 A 的非零元素，问： （1）A 中非零元素的行下标与列下标的关系； （2）给出 A 中非零元素 aij 的下标(i,j)与 B 中的下标 R 的关系; （3） 假定矩阵中每个元素占一个存贮单元且 B 的起始地址为 A0， 给出利用 aij 的下标(i,j) 定位在 B 中的位置公式。 【上海交通大学 1998 三(12 分)】 36. 对于一个对称矩阵采用压缩存储，只存放它的上三角部分， 并按列存放。例如对于一个 n*n 的对称矩阵 A (如右图) ，用一 个一维数组 B 来存放它的上三角部分： B=[A11，A12，A22，A13，A23，A33，A14，?，A1n，A2n，?，Ann] 同时有两个函数：MAX(i,j)和 MIN(i,j)，分别计算下标 i 和 j 中的大者与小者。试利用它们给出求任意一个 Aij 在 B 中存放 位置的公式。 （若式中没有 MAX(I,j)和 MIN（i，j）则不给分） 【清华大学 1997 五 (10 分)】 37. 用三元数组表示稀疏矩阵的转置矩阵,并简要写出解题步骤。 【山东工业大学 1995 五 （10 分） 】 38. 简述广义表属于线性结构的理由。【西北大学 2000 一、5 (3 分)】 39. 数组，广义表与线性表之间有什么样的关系？【西北工业大学 1998 一、2 (4 分)】 40. 什么是广义表？请简述广义表和线性表的主要区别。 【北京大学 1997 二、2 （5 分） 】 41. 求下列广义表的运算结果。 【南京航空航天大学 1998 三 （10 分） 】 （1）CAR(CDR(((a,b),(c,d),(e,f)))) （2）CDR(CAR(((a,b),(c,d),(e,f)))) （3）CAR(CDR(CAR(((a,b),(e,f))))) （4）CDR(CAR(CDR(((a,b),(e,f))))) （5）CDR(CDR(CAR(((a,b),(e,f))))) 注：CAR 运算相当于有些教材中的 Head 运算，CDR 运算相当于 Tail 运算。 42. 利用广义表的 Head 和Ｔail 运算，把原子 d 分别从下列广义表中分离出来，L1＝ (((((a),b),d),e))；L2＝（a,(b,((d)),e）。 【北方交通大学 1996 一、2（5 分） ） 】类似本题的另外叙述有：(1) 已知广义表 L=((((a))),((b)),(c),d)，试利用 head 和 tail 运算把原子项 c 从 L 中分离出来。 【北京邮电大学 1992 三、2（25/4 分）【青岛海洋大学 1999 一、6 （5 分） 】 】 (2) 画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子 e。 （ a,（ （）,ｂ）,（（ｅ））。 （ ））【清华大学 1995 二 （10 分） 】 (3) 已知广义表 A=((a,b,c),(d,e,f)) 试写出从表 A 中取出原子元素 e 的运算。 【西安电子科技大学 1996 二、3 （5 分） 】 (4)请将香蕉 banana 用工具 H( )―Head( )，T( )―Tail( )从 L 中取出。 L=(apple,(orange,(strawberry,(banana)),peach),pear) 【北京邮电大学 2000 三、2 （5 分） 】 (5) 试利用广义表取表头 head(ls)和取表尾 tail(ls)的基本运算， 将原子 d 从下列表中 分解出来，请写出每一步的运算结果。 L=((a,(b)),((c,d)),(e,f)) 【北京工商大学 2001 三 （10 分） 】 (6) 画出广义表 A=（a,（b,()）,(((),c))）的第一种存储结构（表结点第二指针指向 余表）图，并用取首元（head()）和取尾元（tail()）函数表示原子 c。 【北京工业大学 2001 二、2 (5 分)】 43. 画出下列广义表的两种存储结构图((),A,(B,(C,D)),(E,F))。 南京航空航天大学 1999 【 三（10 分） 】 44. 假设采用以下两种结点的链表作为广义表的存贮结构， 表结点： (tag=1,hp,tp), 元素 结点；(tag=0,data)。请画出下列广义表的存储结构图，并求它的深度和长度。 ( ( ) , ( ( ( ) ) , ( ( ( ) ) ) ) ) 【北方交通大学 1998 一（13 分） 】 45．知广义表 A=（（a）， ，c， ，（ （ ）（b） （a）（（d，e）） ）） （1）画出其一种存贮结构图； （2）写出表的长度与深度； （3）用求头部，尾部的方式求出 e。 【东北大学 1997 一、2 (5 分)】 46．画出具有共享结构广义表（（b,c）,d）,(a),((a),((b,c),d)),e,()）的存贮表示。 （ 【北京工业大学 1996 一、3 (6 分)】 47. 广义表的结点结构如下:(TAG,DATA,LINK)。其中 LINK 为指向表中下一元素的指针;TAG 为标志域；DATA 为数据域，具体含义如下: TAG=0 表示该结点为原子结点，DATA 为其数据； TAG=1 表示该结点为一个子表，DATA 为指向该子表的指针。 （1） 说明下列算法 A 的功能(注:算法中 p,t,m,n,r,q 为指针;算法中的 NIL 对应图中的^) PROCEDURE A(p,t) BEGIN q:=NIL; WHILE p&&NIL DO BEGIN IF p^.TAG&&0 THEN BEGIN m:=p^.DATA; A(m,n); p^.DATA:=n; END; r:=p^.LINK; p^.LINK:=q; q:=p; p:=r END;t:=q; END. （2）对于 p 所指的广义表,画出执行算法 A 后的表结构以及 p，t 的值:【北方交通大学 1993 六（20 分） 】类似本题的另外叙述有：题目基本相同， 差别仅在于子表(b,c)与原子 d 的前后顺序颠倒。浙江大学 1994 六 (7 【 分)】 48. 写出对广义表 A=(x,((a,b),c,d))作运算 head(head(tail(A)))后的结果。 【西安电子科技大学 2000 计应用 一、5（5 分） 】 49．写出广义表的运算结果: TAIL[HEAD[TAIL[((a,b),(c,d))]]]=? 【武汉交通科技大学 1996 二、7 (3 分)】 50. 广义表中原子个数是否即为广义表的长度？ 【西安电子科技大学 2000 计应用一、 （5 9 分） 】 51. 给出下列所示的 3 元多项式的广义表表示（分别以 X1，X2，X3 第一到第三层变元） 5 3 5 2 4 5 3 3 4 2 P（X1X2X3）=X1 X2 X3+2X1 X2 X3 +5X1 X2 X3 +3X1X2 X3 +X2X3+6 【华南理工大学 2001 一、2（4 分） 】 52. 设某表 H 如下： A a1 a2 B b1 c1 C c2 X其中 A,B,C 为子表名，a1,a2,b1,c1,c2,x 为其元素。 （1）试用广义表形式表示 H,并写出运算 HEAD(H)和 TAIL(H) 函数从 H 中取出单元素 a2 的 运算； （2）画出表 H 的链式存储结构； 【北京科技大学 1998 三（10 分） 】 五 算法设计题 1. 设有大小不等的 n 个数据组（n 个数据组中数据的总数为 m） ，顺序存放在空间区 D 内, 每个数据占一个存储单元，数据组的首地址由数组 S 给出， （如下图所示） ，试编写将新数据 x 插入到第 i 个数据组的末尾且属于第 i 个数据组的算法， 插入后， 空间区 D 和数组 S 的相 互关系仍保持正确。 【东北大学 2000 六 (15 分)】2. 以三元组表存贮的稀疏矩阵 A，B 非零元个数分别为 m 和 n。试用类 PASCAL 语言编写时 间复杂度为 O（m+n）的算法将矩阵 B 加到矩阵 A 上去。A 的空间足够大，不另加辅助空间。 要求描述所用结构。 【北京工业大学 1997 三 (10 分)】 3. 设整数 x1,x2,?,xN 已存放在数组 A 中，编写一 PASCAL 递归过程，输出从这 n 个数中取 出所有 k 个数的所有组合（k&=n） 。例：若 A 中存放的数是 1，2，3，4，5，k 为 3，则输出 结果应为：543，542，541，532，531，521，432，431，421，321。 【山东大学 1992 五 (13 分)】类似本题的另外叙述有：（1）题目基本相同，只是叙述不同，要求用 PASCAL 语言。 【东南大学 2001 三 （10 分） 】 4． 编写一个过程， 对一个 n×n 矩阵， 通过行变换， 使其每行元素的平均值按递增顺序排列。 【中科院软件所 1996 】 5. 设原来将 N 个自然数 1,2,?,N 按某个顺序存于数组 A 中， 经过下面的语句计算， A[I] 使 的值变为 A[1]到 A[I-1]中小于原 A[I]值的个数。 FOR I:=N DOWNTO 1 DO BEGIN C：=0； FOR J：=1 TO I-1 DO IF A[J]&A[I] THEN C：=C+1； A[I]：=C END； 编程将经过上述处理后的 A 还原成原来的 A。 【上海大学 1996 二 （16 分） 】 6．请编写完整的程序。如果矩阵 A 中存在这样的一个元素 A[i,j]满足条件:A[i,j]是第 i 行中值最小的元素,且又是第 j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程 计算出 m*n 的矩阵 A 的所有马鞍点。 【上海大学 2000 三 （20 分） 中科院自动化所 1997】 】 【 7． 给定一个整数数组 b[0..N-1]， 中连续的相等元素构成的子序列称为平台。 b 试设计算法， 求出 b 中最长平台的长度。 【中科院计算所 1999 五、2 （20 分） 】 8. 给定 nxm 矩阵 A[a..b,c..d],并设 A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和 A[i,j]≤ A[i+1,j](a≤i≤b-1,c≤j≤d).设计一算法判定 X 的值是否在 A 中,要求时间复杂度为 O(m+n)。 【东南大学 2001 六(13 分)】类似本题的另外叙述有：（1）给定整型数组 B[0..m,0..n] 。已知 B 中数据在每一维方向上都按从小到大的次序 排列，且整型变量 x 在 B 中存在。试设计一个程序段找出一对满足 B[i,j]=x 的(i,j)值，要 求比较次数不超过 m+n.。 【清华大学 1998 六（10 分） 】 (2) 给定 n×m 矩阵 A[a..b,c..d]，并设 A[i,j]&=A[i,j+1]（a&=i&=b,c&=j&=d-1）知 A[i,j]&=A[i+1,j],(a&=i&=b-1, c&=j&=d)。设计一算法以比 O(n*m)小的最坏时间复杂性判 定值 x 是否在 A 中。 【东南大学 1994 三(17 分)】 9. 编写算法，将自然数 1～n 按“蛇形”填入 n×n 矩阵中。例（1～4 ）如图所示： （用 程序实现）【南京航空航天大学 1997 八 （12 分） 【中科院计算所 1996】 】 10. 设二维数组 a[1..m, 1..n] 含有 m*n 个整数。 (1) 写出算法(pascal 过程或 c 函数)： 判断 a 中所有元素是否互不相同?输出相关信息 (yes/no)； (2) 试分析算法的时间复杂度。 【华中理工大学 1999 五 （10 分） 】 n 11. 二项式(a+b) 展开式的系数为 C（n，0）=1，C（n，n）=1，对于 n&=0 C（n，k）=C（n-1，k）+C（n-1，k-1） ，对于 0&k&n 形成著名的杨辉三角形，如图所 示。 (1)试写一个递归算法，根据以上公式生成 C（n,k）（6 分） 。 (2)试画出计算 C（6，4）的递归树。 分） （4 (3)试写一个非递归算法，既不用数组也不用栈，对于任意的 0&=k&=n 计算 C(n,k)（6 分）【清华大学 1999 五 （16 分） 】 12． 设任意 n 个整数存放于数组 A(1:n)中， 试编写程序， 将所有正数排在所有负数前面 （要 求算法复杂性为 0( n)） 【山东大学 1993 三 (12 分)】. 。类似本题的另外叙述有：（1）已知数组 A[1..n]的元素类型为整型，设计算法调整 A，使其左边的所有元素小于 零，右边的所有元素大于等于零。 （要求算法的时间复杂度和空间复杂度均为 0（n） ） 【北京理工大学 2000 四、1 （4 分） 】 （2）设计一个算法，把整数数组中所有的偶数放到所有的奇数之前。要求时间、空间效 率尽可能高。 【华南师范大学 1999 六、1 (10 分)】 （3）设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部 分，将所有的偶数存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。请 试着分析你实现的算法的时间复杂度和空间复杂度。 【南开大学 2000 三、2】 （4）设计算法将数组 A[1..n]调整为左右两部分，使的左边所有的元素小于右边的所有 元素， 并给出这一划分的分界位置。 要求算法的时间复度为 O(n)。 【合肥工业大学 2001 五、 3 （8 分） 】 13.若 S 是 n 个元素的集合，则 S 的幂集 P(S)定义为 S 所有子集的集合。例如， S=(a,b,c),P(S)={() ,(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}给定 S，写一递归算法求P(S)。 【东南大学 1993 五 （15 分）【东南大学 1997 五 （15 分） 】 】 14．编写算法打印出由指针 Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非 零元的个数。注意：行、列及总表头结点的形式为： row down col val right它们已用 val 域链接成循环链表。 非零元的结点形式也同上， 每一行 （列） 的非零元由 right （down）域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。 【上海大学 1998 五 （16 分） 】 15. 试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义 表按如下形式输入（a1,a2,a3,?,an） n&=0，其中 ai 或为单字母表示的原子或为广义表，n=0 时为只含空格字符的空表。(注:算法可用类 pascal 或类 c 书写) 【北京工业大学 1998 十 (15 分)】 16. 广义表是 n(n&=0)个数据元素 a1,a2,a3,?,an 的有限序列。其中 ai (1&=i&=n)或者是单 个数据元素（原子），或仍然是一个广义表。广义表的结点具有不同的结构，即原子结点和 子表元素结点，为了将两者统一，用了一个标志 tag，当其为 0 时表示是原子结点，其 data 域存储结点值，link 域指向下一个结点，当其 tag 为 1 时表示是子表结点，其 sublist 为 指向子表的指针。因此，广义表可采用如下结构存储： TYPE glist=^ gnode=RECORD link: CASE tag:0..1 OF 0:(data:char); 1:(sublist:glist) END; （1）画出广义表((a,b),c)的存储结构； （2）写出计算一个广义表的原子结点个数的递归算法表示式； （3）编写实现上述算法的过程或函数程序。【厦门大学 2002 三 （12 分）】 17. 广义表 GL=(a1,a2 ,?,an),其中 ak(k=1,2,...,n)或是单个数据元素（原子），或仍然 是个广义表。给定如下有关广义表的类型定义： TYPE tagtype=0..1; glist=^ gnode=RECORD link: {link 域指向下一个结点} CASE tag:tagtype OF ｛tag=0 表示原子结点｝ 0: (data :integer); 1:(sublist: glist) END; 编写一个过程或函数计算一个广义表的所有原子结点数据域之和，例如对广义表 (3,(2,4,5),(6,3）) 数据域之和为 23。【厦门大学 2000 四、2 （9 分）】 18. 数组 H[ 1：1000] 中存放着 1000 个大小不同的正整数; （1） 选择一分类算法使能最快地得到其中 10 个最大的数，简要说明理由；（2） 编写一程序 seek() ，执行该程序时，在命令行中提供二个参数； seek a n&enter& 表示需打印 H[ ]中 n 个最大数。 seek I n&enter& 表示需打印 H[ ]中 n 个最小数。 【浙江大学 1994 八 (18 分)】 19．已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列 中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一 数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任 意一个数组进行排序操作。例如， 第一个数组为：4,12,28 第二个数组为：1,7,9,29,45 输出结果为：1,4,7--------------第一个数组 9,12,28,29,45---------第二个数组 【上海大学 1998 四 （20 分） 】 20. 设数组 A[1..n]中，A[n-2k+1..n-k]和[n-k+1..n]中元素各自从小到大排好序，试设计 一个算法使 A[n-2k+1..n]按从小到大次序排好序。并分析算法所需的计算时间。 【福州大学 1998 四、3 (10 分)】 21. 设 A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于 1 至 100 之间，现要求按 B[1..100]的内容调整 A 中记录的次序，比如当 B[1]=ll 时，则要求将 A[1] 的内容调整到 A[11]中去。 规定可使用的附加空间为 O(1)。 中科院计算所 2000 七 【 （15 分） 】 22. 给定有 m 个整数的递增有序数组 a[1..m]和有 n 个整数的递减有序数组 b[1..n]，试写 出算法:将数组 a 和 b 归并为递增有序数组 c[l..m+n]。 (要求： 算法的时间复杂度为 O(m+n)) 【华中理工大学 2000 八、1（10 分） 】 23．在数组 A[1..n]中有 n 个数据，试建立一个带有头结点的循环链表，头指针为 h，要求 链中数据从小到大排列，重复的数据在链中只保存一个。 【南京理工大学 1998 七、2 （7 分） 】第五章 数组和广义表一、选择题 1.B 6.4A 15.B 27.A 二、判断题 1. × 13.√ 2.√ 14.√ 3.√ 4.× 5.× 6. × 7.√ 8.× 9.× 10.× 11.× 12.√ 2.1L 6.5F 16.A 2.2J 7.B 17.C 2.3C 8.1E 18.D 2.4I 8.2A 19.C 2.5C 8.3B 20.D 3.B 9.B 21.F 4.B 10.B 22.C 5.A 11.B 23.D 6.1H 12.B 24.C 6.2C 13.A 25.A 6.3E 14.B 26.C部分答案解释如下。 1. 错误。对于完全二叉树，用一维数组作存储结构是效率高的（存储密度大） 。 4. 错误。数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此， 可以说数祖是元素值和下标构成的偶对的有穷集合。 5. 错误。数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。 6. 错误。稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三 元组中的位置。 8. 错误。广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能 是原子。9. 错误。广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。 10. 错误。广义表中元素可以是原子，也可以是表（包括空表和非空表） 。 11. 错误。广义表的表尾，指去掉表头元素后，剩余元素所组成的表。 三、填空题 1. 顺序存储结构 2.（1）28 3.（1）88 4. 64 公式：LOC(aijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l (l 为每个元素所 占单元数) 6. 232 7. 96 9. 第 1 行第 3 列 10. (1)270 (2)27 (3)2204 11. i(i-1)/2+j (1&=i,j&=n) 12. (1)n(n+1)/2 (2)i(i+1)/2 (或 j(j+1)/2) (3)i(i-1)/2+j (4)j(j-1)/2+i (1&=i,j&=n) 13. 1038 三对角矩阵按行存储：k=2(i-1)+j (1&=i,j&=n) 14. 33 (k=i(i-1)/2+j) (1&=i,j&=n) 15. 非零元很少(t&&m*n)且分布没有规律 16. 节省存储空间。 17. 上三角矩阵中，主对角线上第 r(1?r?n) 行有 n-r+1 个元素，aij 所在行的元素数是 j-i+1 。 所 以 ， 元 素 在 一 维 数 组 的 下 标 k 和 二 维 数 组 下 标 关 系:k=((i-1)*(2n-i+2))/2+(j-i+1)=(i-1)(2n-i)/2+j (i?j) 18. 93 19. i(i-1)/2+j 20. 线性表 21. 其余元素 组成的表 22. （1） 原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而表带结构， 本质就是广义表，因作为广义表的元素故称为子表。 （2）大写字母 （3）小写字母 （4）表中元素的个数（5）表展开后所含括号的层数 23. 深度 24.（1） （） （2）（） （3）2 （4）2 （ ） 25. head（head（tail（tail（head（tail（tail（A）））） ））） 26. 表展开后所含括号的层数 27.（1）5 （2）3 28. head(head(tail(LS))) 29. head(tail(tail(head(tail(head(A)))))) 30. head(tail(head(tail(H)))) 31. (b) 32. (x,y,z) 33. (d,e) 34. GetHead(GetHead(GetTail(L))) 35. 本算法中， 首先数组 b 中元素以逆置顺序放入 d 数组中， 然后数组 a 和数组 d 的元素比 较， 将大者拷贝到数组 c。 第一个 WHILE 循环到数组 a 或数组 d 结尾， 第二个和第三个 WHILE 语句只能执行其中的一个。 （1）b[m-i+1]（2）x:=a[i]（3）i:=i+1（4）x:=d[j]（5）j:=j+1 （6）k:=k+1（7）i&=l （8）j&=m 36.（1）(i==k) return（2）i+1（3）i-1（4）i!=k 本算法利用快速排序思想，找到第 k 个元素的位置（下标 k-1 因而开初有 k--） 。内层 do 循环以 t(t=a[low])为“枢轴”找到其应在 i 位置。这时若 i 等于 k，则算法结束。 （即第一 个空格处 if(i==k) return)。否则，若 i&k，就在 i+1 至 high 中间去查；若 i&k，则在 low 到 i-1 间去找，直到找到 i=k 为止。 37.逆置广义表的递归模型如下f(LS)= 上面 appEND(a,b)功能是将广义表 a 和 b 作为元素的广义表连接起来。 （1）(p-&tag==0) //处理原子 （2）h=reverse(p-&val.ptr.hp) //处理表头 （3）(p-&val.ptr.tp) //产生表尾的逆置广义表 （4）s-&val.ptr.tp=t; //连接 （5）q-&val.ptr.hp=h //头结点指向广义表 38. 本题要求将 1，2，...,n*n 个自然数，按蛇型方式存放在二位数组 A[n][n]中。 “蛇型” 2 方式，即是按“副对角线”平行的各对角线，从左下到右上，再从右上到左下，存放 n 个 整数。对角线共 2n-1 条，在副对角线上方的对角线，题目中用 k 表示第 k 条对角线（最左 上角 k=1） ，数组元素 x 和 y 方向坐标之和为 k+1（即题目中的 i+j=k+1） 。副对角线下方第 k 条对角线与第 2n-k 条对角线对称，其元素的下标等于其对称元素的相应坐标各加(k-n)。 （1）k&=2*n-1 //共填 2*n-1 条对角线 （2）q=2*n-k //副对角线以下的各条对角线上的元素数 （3） k%2！ =0 //k 为偶数时从右上到左下， 否则从左下向右上填数。 （本处计算下标 i 和 j） （4）k&=n //修改副对角线下方的下标 i 和 j。 （5）m++；或 m=m+1 //为填下个数作准备，m 变化范围 1..n*n。 本题解法的另一种思路见本章算法设计题第 9 题。 39.本题难点有二： 一是如何求下一出圈人的位置， 二是某人出圈后对该人的位置如何处理。 按题中要求，从第 s 个人开始报数，报到第 m 个人，此人出圈。n 个人围成一圈，可看 作环状，则下个出圈人，其位置是(s+m-1)%n。n 是人数，是个变量，出圈一人减 1，算法中 用 i 表示。对第二个问题，算法中用出圈人后面人的位置依次前移，并把出圈人的位置（下 标）存放到当时最后一个人的位置（下标） 。算法最后打印出圈人的顺序。 （1）(s+m-1) MOD i //计算出圈人 s1 （2）s1:=i //若 s1=0,说明是第 i 个人出圈（i%i=0） （3）s1 TO i-1 //从 s1 到 i 依次前移，使人数减 1，并将出圈人放到当前最后一个 位置 A[i]=w。 40. 若第 n 件物品能放入背包， 则问题变为能否再从 n-1 件物品中选出若干件放入背包 （这 时背包可放入物品的重量变为 s-w[n]） 。若第 n 件物品不能放入背包，则考虑从 n-1 件物品 选若干件放入背包（这时背包可放入物品仍为 s） 。若最终 s=0,则有一解；否则，若 s&0 或 虽然 s&0 但物品数 n&1,则无解。 （1）s-w[n],n-1 //Knap(s-w[n],n-1)=true （2）s,n-1 // Knap←Knap(s,n-1) 四、应用题 1、958 三维数组以行为主序存储，其元素地址公式为： LOC(Aijk)=LOC(Ac1c2c3)+[(i-c1)V2V3+(j-c2)V3+(k-c3)]*L+1 其中 ci,di 是各维的下界和上界，Vi=di-ci+1 是各维元素个数，L 是一个元素所占的存储 单元数。2. b 对角矩阵的 b 条对角线，在主对角线上方和下方各有 ?b/2? 条对角线(为叙述方便，下 面设 a=?b/2?)。 从第 1 行至第 a 行， 每行上的元素数依次是 a+1,a+2,...,b-2,b-1,最后的 a 行上的元素个数是 b-1，b-2,...,a+1。中间的(n-2a )行，每行元素个数都是 b。故 b 条对 角线上元素个数为 (n-2a)b+a*(a+b)。存放在一维数组 V[1..nb-a(b-a)]中，其下标 k 与元 素在二维数组中下标 i 和 j 的关系为：k= 3．每个元素 32 个二进制位，主存字长 16 位，故每个元素占 2 个字长，行下标可平移至 1 到 11。 （1）242 （2）22 （3）s+182 （4）s+142 4．1784 (公式：Loc(Aijkl)=100(基地址)+[(i-c1)v2v3v4+(j-c2)v3v4+(k-c3)v4+(l-c4)]*4 5. L (LOC(A[1,3,-2])=1210+[(k-c3)v2v1+(j-c2)v1+(i-c1)]*L（设每个元素占 L 个 存储单元） 6. 数组占的存储字节数=10*9*7*4=2520； A[5,0,7]的存储地址=100+[4*9*7+2*7+5]*4=1184 7. 五对角矩阵按行存储，元素在一维数组中下标（从 1 开始）k 与 i,j 的关系如下:k= A[15,16]是第 71 个元素，在向量[-10:m]中的存储位置是 60 。 8． （1）540 （2）108 （3）i=3,j=10，即 A[3,10] 9． k=i(i-1)/2+j 10. 稀疏矩阵 A 有 t 个非零元素，加上行数 mu、列数 nu 和非零元素个数 tu(也算一个三元 组)，共占用三元组表 LTMA 的 3(t+1)个存储单元，用二维数组存储时占用 m*n 个单元，只 有当 3(t+1)&m*n 时，用 LTMA 表示 A 才有意义。解不等式得 t&m*n/3-1。 11．参见 10。 12. 题中矩阵非零元素用三元组表存储， 查找某非零元素时， 按常规要从第一个元素开始查 找，属于顺序查找，时间复杂度为 O(n)。若使查找时间得到改善，可以建立索引，将各行 行号及各行第一个非零元素在数组 B 中的位置（下标）偶对放入一向量 C 中。若查找非零元 素， 可先在数组 C 中用折半查找到该非零元素的行号， 并取出该行第一个非零元素在 B 中的 位置，再到 B 中顺序（或折半）查找该元素，这时时间复杂度为 O(logn)。 13． （1）176 （2）76 和 108 （3）28 和 116。 14． （1）k = 3(i-1) (主对角线左下角，即 i=j+1) k = 3(i-1)+1 (主对角线上，即 i=j) k = 3(i-1)+2 (主对角线上，即 i=j-1) 由以上三式，得 k=2(i-1)+j (1?i,j?n; 1?k?3n-2) 3 3 3 （2）10 *10 -(3*10 -2) 15. 稀疏矩阵 A 采用二维数组存储时，需要 n*n 个存储单元，完成求Σ aii(1&=i&=n)时，由 于 a[i][i]随机存取，速度快。但采用三元组表时，若非零元素个数为 t，需 3(t+1)个存储 单元（第一个分量中存稀疏矩阵 A 的行数，列数和非零元素个数，以后 t 个分量存各非零元 素的行值、列值、元素值） ，比二维数组节省存储单元；但在求Σ aii(1&=i&=n)时，要扫描整个三元组表，以便找到行列值相等的非零元素求和，其时间性能比采用二维数组时差。 16. 特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律， 因此可以对非零元素分 配单元（对值相同元素只分配一个单元） ，将非零元素存储在向量中，元素的下标 i 和 j 和 该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩 阵是指非零元素和矩阵容量相比很小（t&&m*n） ，且分布没有规律。用十字链表作存储结构 自然失去了随机存取的功能。 即使用三元组表的顺序存储结构， 存取下标为 i 和 j 的元素时， 要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为 O(1)，最差 情况下是 O(n)，因此也失去了随机存取的功能。 17．一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中元素按值排序（非递增 或非递减） ，而一维数组中元素没有按元素值排列顺序的要求。 2 18．n(n+1)/2（压缩存储） 或 n （不采用压缩存储） 19．LOC（A[i,j]）=LOC（A[3，2]）+[（i-3）*5+（j-2）]×2 （按行存放） LOC（A[i,j]）=LOC（A[3，2]）+[（j-2）*6+（i-3）]×2 （按列存放） 20．n 阶下三角矩阵元素 A[i][j]（1&=i,j&=n,i&=j） 。第 1 列有 n 个元素，第 j 列有 n-j+1 个元素，第 1 列到第 j-1 列是等腰梯形，元素数为(n+(n-j+2)(j-1)/2，而 aij 在第 j 列上的 位置是为 i-j+1。所以 n 阶下三角矩阵 A 按列存储，其元素 aij 在一维数组 B 中的存储位置 k 与 i 和 j 的关系为： k=(n+(n-(j-1)+1)(j-1)/2+(i-j+1)=(2n-j)(j-1)/2+i 21．三对角矩阵第一行和最后一行各有两个非零元素，其余每行均有三个非零元素，所以共 有 3n-2 个元素。 （1） 主对角线左下对角线上的元素下标间有 i=j+1 关系， 与 i 和 j 的关系为 k=3(i-1); k 主对角线上元素下标间有关系 i=j，k 与 i 和 j 的关系为 k=3(i-1)+1; 主对角线右上那条对 角线上元素下标间有关系 i=j-1，k 与 i 和 j 的关系为 k=3(i-1)+2。综合以上三等式，有 k=2(i-1)+j (1&=i,j&=n, |i-j|&=1) （2）i=k/3+1； （1≤k≤3n-2） // k/3 取小于 k/3 的最大整数。下同 j=k-2(i-1)=k-2(k/3)=k%3+k/3 22．这是一个递归调用问题，运行结果为：DBHEAIFJCKGL 23.（1）FOR 循环中，每次执行 PerfectShuffle(A,N)和 CompareExchange(A,N)的结果： 第 1 次：A[1..8]=[90,30,85,65,50,80,10,100] A[1..8]=[30,90,65,85,50,80,10,100] 第 2 次：A[1..8]=[30,50,90,80,65,10,85,100] A[1..8]=[30,50,80,90,10,65,85,100] 第 3 次：A[1..8]=[30,10,50,65,80,85,90,100] A[1..8]=[10,30,50,65,80,85,90,100] （2）Demo 的功能是将数组 A 中元素按递增顺序排序。 （3）PerfectShuffle 中 WHILE 循环内是赋值语句，共 2N 次，WHILE 外成组赋值语句， 相当 2N 个简单赋值语句；CompareExchange 中 WHILE 循环内是交换语句，最好情况下不发 生交换， 最差情况下发生 N 次交换， 相当于 3N 个赋值语句； Demo 中 FOR 循环循环次数 log22N， 故按赋值语句次数计算 Demo 的时间复杂度为：最好情况：O(4N*log22N)≈O(Nlog(2*N))； 最差情况：O((4N+3N)*log22N)≈O(Nlog(2*N))。 24. 这是一个排序程序。运行后 B 数组存放 A 数组各数在排序后的位置。结果是： A={121,22,323,212,636,939,828,424,55,262} B={3,1,6,4,8,10,9,7,2,5} C={22,55,121,212,262,323,424,639,828,939}25.（1）c=（2）a=26.（1）同上面 26 题（1） （2）对 c 数组的赋值同所选择的下标 i 和 j 的次序（指外层循环用 j 内层用 i）没有关 系 （3）同上题 26（2） （4）对 i,j 下标取反序后，重复执行第（3）步，A 数组所有元素均变为 2。 （在机器上 验证，反复循环 3 次后，所有元素均变为 2） 27．错误有以下几处： （1）过程参数没有类型说明； （2）出错条件判断：缺少 OR（i+k&last+1） ； （3）删除元素时 FOR 循环应正向，不应用反向 DOWNTO； （4）count 没定义； 低效体现在两处： （1）删除 k 个元素时，不必一个一个元素前移，而应一次前移 k 个位置； （2）last 指针不应一次减 1，而应最后一次减 k。 正确的高效算法如下： const m=64； TYPE ARR=ARRAY[1..m] OF integer； PROCEDURE delk（VAR A:ARR；VAR last:i,k：integer） ； {从数组 A[1..last]中删除第 i 个元素起的 k 个元素，m 为 A 的上限} VAR count：integer； BEGIN IF（i&0）OR（i&last）OR（k&0）OR（last&m）OR（i+k&last+1） THEN write（’error’ ） ELSE[FOR count：= i+k TO last DO A[count-k]：=A[count]； last：=last-k；] END； 28. 这是计数排序程序。 （a）c[i](1&=i&=n)中存放 A 数组中值为 i 的元素个数。 （b）c[i](1&=i&=n)中存放 A 数组中小于等于 i 的个数。 （c）B 中存放排序结果，B[1..n]已经有序。 （d）算法中有 4 个并列 for 循环语句，算法的时间复杂度为 O(n)。 29．上三角矩阵第一行有 n 个元素，第 i-1 行有 n-（i-1）+1 个元素，第一行到第 i-1 行是 等腰梯形，而第 i 行上第 j 个元素（即 aij）是第 i 行上第 j-i+1 个元素，故元素 Aij 在一维 数组中的存储位置（下标 k）为： k=(n+(n-(i-1)+1))(i-1)/2+(j-i+1)=(2n-i+2)(i-1)/2+j-i+1 30．将上面 29 题的等式进一步整理为： 2 k=（n+1/2）i-i /2+j-n， 2 则得 f1（i）=（n+1/2）i-i /2，f2（j）=j，c=-n。 31.（1）将对称矩阵对角线及以下元素按行序存入一维数组中，结果如下：（2）因行列表头的“行列域”值用了 0 和 0，下面十字链表中行和列下标均从 1 开始。注：上侧列表头 Hi 和左侧行表头 Hi 是一个（即 H1、H2、H3 和 H4） ，为了清楚，画成了 两个。 32.（1）k=(2n-j+2)(j-1)/2+i-j+1 （当 i≥j 时，本题 n=4） k=(2n-i+2)(i-1)/2+j-i+1 （当 i&j 时，本题 n=4） （ 2 ） 稀 疏 矩 阵 的 三 元 组 表 为 ： s=((4,4,6),(1,1,1),(1,4,2),(2,2,3),(3,4,5),(4,1,2),(4,3,5)。 其中第一个三元组是稀 疏矩阵行数、列数和非零元素个数。其它三元组均为非零元素行值、列值和元素值。 33.（1）k=2（i-1）+j （1≤i，j≤n，|i-j|≤1） i=floor（k/3）+1 // floor（a）是取小于等于 a 的最大整数 j=k-2（i-1） 推导过程见上面第 25 题。 （2）行逻辑链接顺序表是稀梳矩阵压缩存储的一种形式。为了随机存取任意一行的非零 元，需要知道每一行第一个非零元在三元组表中的位置。为此，除非零元的三元组表外，还 需要一个向量，其元素值是每行第一个非零元在三元组表中的位置。其类型定义如下： typedef struct { int mu,nu, //稀梳矩阵的行数、列数和非零元素个数 int rpos[maxrow+1]; //行向量， 其元素值是每行第一个非零元在三元组表中的 位置。 Triple data[maxsize]; }SparsM 因篇幅所限，不再画出行逻辑链接顺序表。 34．各维的元素数为 di-ci+1，则 a[i1，i2，i3]的地址为： a0+[（i1-c1） 3- c3+1） 2- c2+1）+（i2-c2） 2- c2+1）+（i3-c3）]*L （d （d （d 35．主对角线上元素的坐标是 i=j，副对角线上元素的坐标 i 和 j 有 i+j=n+1 的关系 （1）i=j 或 i=n+1-j （1≤i，j≤n） （2）非零元素分布在两条主、副对角线上，除对角线相交处一个元素（下称“中心元素” ）外，其余每行都有两个元素。主对角线上的元素，在向量 B 中存储的下标是 k=2i-1(i=j, 1 ≤i，j≤n，1&=k&=2n-1)。 副对角线上的元素，在中心元素前，在向量 B 中存储的下标是 k=2i(i&&j, 1≤i，j≤ n/2)；在中心元素后，其下标是 k=2(i-1)(i&&j，n/2+1≤i，j≤n, 1&=k&=2n-1)。（3）aij 在 B 中的位置 K= 36. 由于对称矩阵采用压缩存储，上三角矩阵第一列一个元素，第二列两个元素，第 j 列 j 个元素。 上三角矩阵共有 n (n+1)/2 个元素。 我们将这些元素存储到一个向量 B[n(n+1)/2+1] 中。可以看到 B[k]和矩阵中的元素 aij 之间存在着一一对应关系：则 其 对 应 关 系 可 表 示 为 ： k=( 1&=i,j&=n,1&=k&=n(n+1)/2) int MAX(int x,int y) { return(x&y?x:y); } int MIN(int x,int y) { return(x&y?x:y); } 37. 设用 mu,nu 和 tu 表示稀疏矩阵行数，列数和非零元素个数，则转置矩阵的行数，列数 和非零元素的个数分别是 nu,mu 和 tu。转置可按转置矩阵的三元组表中的元素顺序进行， 即按稀疏矩阵的列序，从第 1 列到第 nu 列，每列中按行值递增顺序，找出非零元素，逐个 放入转置矩阵的三元组表中，转时行列值互换，元素值复制。按这种方法，第 1 列到第 1 个非零元素一定是转置后矩阵的三元组表中的第 1 个元素， 1 列非零元素在第 2 列非零元 第 素的前面。这种方法时间复杂度是 O(n*P)，其中 p 是非零元素个数，当 p 和 m*n 同量级时， 时间复杂度为 O(n3)。 另一种转