下载文档原格式
数据结构考试题及答案一、选择题（每题2分，共20分）1. 以下哪个不是线性数据结构？A. 数组B. 链表C. 树D. 图2. 在一个单链表中，删除一个节点的操作需要知道该节点的：A. 地址B. 值C. 索引D. 前驱节点的引用3. 栈（Stack）是一种：A. 线性表B. 树状结构C. 图结构D. 散列表4. 哈希表解决冲突最常用的方法是：A. 排序B. 链地址法C. 再散列D. 除留余数法5. 以下哪个排序算法是稳定的？A. 快速排序B. 冒泡排序C. 选择排序D. 堆排序二、简答题（每题10分，共30分）1. 简述数组和链表的区别。
2. 解释二叉搜索树的基本概念及其优势。
3. 什么是递归？请给出一个简单的递归算法例子。
三、计算题（每题25分，共50分）1. 给定一个无序数组，请写出一个时间复杂度为O(n log n)的排序算法，并说明其工作原理。
2. 描述如何使用队列来实现一个简单的文本编辑器的撤销和重做功能。
四、编程题（共30分）编写一个函数，该函数接受一个整数数组作为参数，返回数组中所有元素的和。
如果数组为空，返回0。
答案一、选择题1. 答案：C（树和图都是非线性结构）2. 答案：D（需要前驱节点的引用来删除节点）3. 答案：A（栈是一种后进先出的特殊线性表）4. 答案：B（链地址法是解决哈希冲突的常用方法）5. 答案：B（冒泡排序是稳定的排序算法）二、简答题1. 数组和链表的区别：- 数组是连续的内存空间，链表是非连续的。
- 数组的索引访问速度快，链表需要遍历。
- 数组的大小固定，链表动态可变。
2. 二叉搜索树的基本概念及其优势：- 二叉搜索树是一种特殊的二叉树，左子树上所有节点的值小于它的根节点的值，右子树上所有节点的值大于它的根节点的值。
- 优势：支持快速的查找、插入和删除操作。
3. 递归是函数自己调用自己的过程。
例如，计算n的阶乘的递归算法： ```cint factorial(int n) {if (n <= 1) return 1;return n * factorial(n - 1);}```三、计算题1. 快速排序算法：- 选择一个元素作为“基准”（pivot）。
C数据结构笔试题C语言提供的合法数据关键字是?下面就由店铺为大家介绍一下C 数据结构笔试题的文章，欢迎阅读。
C数据结构笔试题篇1树是结点的集合，它的根结点数目是A) 有且只有1B) 1或多于1C) 0或1D) 至少2程序设计语言的基本成分是数据成分、运算成分、控制成分和A) 对象成分B) 变量成分C) 语句成分D) 传输成分下列不属于软件工程的3个要素的是A) 工具B) 过程C) 方法D) 环境正确答案: D数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及A) 数据的存储结构B) 计算方法C) 数据映象D) 逻辑存储正确答案: A在计算机中，算法是指A) 加工方法B) 解题方案的准确而完整的描述C) 排序方法D) 查询方法正确答案: B开发软件所需高成本和产品的低质量之间有着尖锐的矛盾，这种现象称作A) 软件投机B) 软件危机C) 软件工程D) 软件产生正确答案: B下面不属于软件设计原则的是A) 抽象B) 模块化C) 自底向上D) 信息隐蔽正确答案: C开发大型软件时，产生困难的根本原因是A) 大系统的复杂性B) 人员知识不足C) 客观世界千变万化D) 时间紧、任务重正确答案: A单个用户使用的数据视图的描述称为A) 外模式 B) 概念模式C) 内模式 D) 存储模式正确答案: ASQL语言又称为A) 结构化定义语言B) 结构化控制语言C) 结构化查询语言D) 结构化操纵语言正确答案: C将E-R图转换到关系模式时，实体与联系都可以表示成A) 属性B) 关系C) 键D) 域正确答案: B下列SQL语句中，用于修改表结构的是A) ALTERB) CREATEC) UPDATED) INSERT正确答案: A数据库、数据库系统和数据库管理系统之间的关系是A) 数据库包括数据库系统和数据库管理系统B) 数据库系统包括数据库和数据库管理系统C) 数据库管理系统包括数据库和数据库系统D) 3者没有明显的包含关系正确答案: BC数据结构笔试题篇2关系表中的每一横行称为一个A) 元组B) 字段C) 属性D) 码正确答案: A在下列C语言程序中，可以用做变量名的是( B )。
现在的公司招聘,都要笔试面试.如果你不是那种编程功底非常深厚的人,又不好好准备一番,在笔试面试中往往会处于被动局面.虽然有些笔试题是故意为难我们，有点钻牛角尖.但是很多笔试题面试题确实能够很好地看出我们的基础.在这里,我就略去那些钻牛角尖的题.从csdn论坛我近半年的收集中选出10道有代表性的题目,难度基本上是逐渐加大.对数组,指针,数据结构,算法,字符串,文件操作等问题都有覆盖.主要以c语言的实现为主,也有c++的题.大家可以先做做这10道题,测试一下自己的水平.1. 下面这段代码的输出是多少(在32位机上).char *p;char *q[20];char *m[20][20];int (*n)[10];struct MyStruct{char dda;double dda1;int type ;}；MyStruct k;printf("%d %d %d %d",sizeof(p),sizeof(q),sizeof(m),sizeof(n),sizeof(k));2.(1)char a[2][2][3]={{{1,6,3},{5,4,15}},{{3,5,33},{23,12,7}} };for(int i=0;i<12;i++)printf("%d ",_______);在空格处填上合适的语句，顺序打印出a中的数字(2)char **p, a[16][8];问：p=a是否会导致程序在以后出现问题？为什么？答：p是char**类型，而a是char[16][8]类型。
经过退化，a可以作为一个指针右值，类型为char(*)[8]，或者在参数列表中表达为char[][8]。
char**指针和char(*)[8]不是完全兼容的指针，无法无条件地相互转换。
编译器应该对p = a 这种试图进行隐式转换的表达式产生一个警告（C）或错误（C++）。
从语言层面来说，p 和 a 具有不同的类型，表达式p = a 体现了错误的语义。
数据结构笔试题1. 实现一个栈数据结构，包含以下功能：- 入栈操作（push）：将元素加入栈顶- 出栈操作（pop）：将栈顶元素移除并返回- 判断栈是否为空（isEmpty）：若栈为空，则返回真；否则返回假- 获取栈顶元素（top）：返回栈顶元素，但不移除2. 解析逆波兰表达式逆波兰表达式是一种将运算符写在操作数之后的表达式表示法，例如：1 2 + 3 * 表示 (1 + 2) * 3。
在不使用括号的情况下，通过使用栈可以轻松地解析并计算逆波兰表达式。
以下是解析逆波兰表达式的步骤：- 创建一个栈用于存储操作数- 从左到右扫描逆波兰表达式的每个元素- 若遇到操作数，则将其入栈- 若遇到运算符，则取出栈顶的两个操作数，进行相应的运算，并将结果入栈- 扫描完整个逆波兰表达式后，栈顶的元素即为表达式的结果例如，对于逆波兰表达式 "2 3 +"，我们可以逐步进行计算：- 遇到2，将其入栈：栈为 [2]- 遇到3，将其入栈：栈为 [2, 3]- 遇到+运算符，取出2和3，进行相加，并将结果5入栈：栈为[5]最终栈顶的元素5即为逆波兰表达式 "2 3 +" 的结果。
3. 实现一个队列数据结构，包含以下功能：- 入队操作（enqueue）：将元素加入队尾- 出队操作（dequeue）：将队首元素移除并返回- 判断队列是否为空（isEmpty）：若队列为空，则返回真；否则返回假- 获取队首元素（front）：返回队首元素，但不移除队列是一种先进先出（FIFO）的数据结构，类似于现实生活中的排队情况。
4. 二叉树的前序、中序和后序遍历- 前序遍历：按照「根节点 - 左子树 - 右子树」的顺序遍历二叉树 - 中序遍历：按照「左子树 - 根节点 - 右子树」的顺序遍历二叉树- 后序遍历：按照「左子树 - 右子树 - 根节点」的顺序遍历二叉树以上三种遍历方式是针对二叉树的，通过递归或使用栈数据结构可以实现遍历操作。
数据结构试题一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（B ）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。
A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（）。
A．有向图B．无向图C．无向无环图D．有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。
A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。
A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。
A．行号B．列号C．元素值D．非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（）。
A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。
当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。
数据结构面试笔试题
以下是一些常见的面试笔试题，用于测试应聘者对数据结构的理解和应用能力：
1. 什么是数据结构？请列举几种常见的数据结构，并简要描述它们的特性和用途。
2. 什么是线性数据结构和非线性数据结构？请分别给出几个例子。
3. 什么是数组、链表、栈、队列、树、图等数据结构？请简要描述它们的特性和用途。
4. 请解释什么是哈希表，并给出几个常见的哈希函数。
5. 请解释什么是二叉树，并给出几个常见的二叉树类型。
6. 请解释什么是平衡二叉树，并给出几个常见的平衡二叉树类型。
7. 请解释什么是堆，并给出几个常见的堆类型。
8. 请解释什么是排序算法，并给出几个常见的排序算法。
9. 请解释什么是查找算法，并给出几个常见的查找算法。
10. 请解释什么是贪心算法，并给出几个常见的贪心算法。
11. 请解释什么是动态规划，并给出几个常见的动态规划问题。
12. 请解释什么是分治算法，并给出几个常见的分治算法。
13. 请解释什么是回溯算法，并给出几个常见的回溯算法。
14. 如果你需要在内存中存储一个大型数组，你将选择哪种数据结构？为什么？
15. 你如何比较两个数组或两个链表的长度？
16. 假设我们有一个二叉树，其节点存储的是整数值，我们想找出最小的节点值。
请设计一个有效的算法来解决这个问题。
17. 假设我们有一个无序数组，我们想将其排序。
请设计一个有效的算法来解决这个问题。
18. 假设我们有一个整数数组，我们想找到数组中的最大值和最小值。
请设计一个有效的算法来解决这个问题。
数据结构入门笔试题
以下是一些数据结构的入门笔试题：
1. 给定一个数组，找到数组中最大的元素。
输入示例：[1, 5, 3, 9, 2, 7]
输出示例：9
2. 给定一个链表，反转链表。
输入示例：1 -> 2 -> 3 -> 4 -> 5
输出示例：5 -> 4 -> 3 -> 2 -> 1
3. 实现一个栈，包括入栈(push)、出栈(pop)和获取栈顶元素(peek)的操作。
4. 实现一个队列，包括入队(enqueue)、出队(dequeue)和获取队首元素(peek)的操作。
5. 给定两个排序数组，合并成一个排序数组。
输入示例：arr1 = [1, 3, 5], arr2 = [2, 4, 6]
输出示例：[1, 2, 3, 4, 5, 6]
6. 实现一个二叉树，包括插入节点(insert)、删除节点(delete)和查找节点(search)的操作。
7. 给定一个字符串，判断它是否是回文字符串（正读和反读都一样）。
输入示例： "racecar"
输出示例： true
8. 给定一个字符串，计算它的字符频率。
输入示例： "hello"
输出示例： {'h': 1, 'e': 1, 'l': 2, 'o': 1}
这些题目涉及到了数组、链表、栈、队列、树等常见的数据结构，是入门学习数据结构时的常见笔试题。
数据结构算法笔试题汇总1. 在计算机中，算法是指什么？答案：解题方案的准确而完整的描述。
2. 在下列选项中，哪个不是一个算法一般应该具有的基本特征？说明：算法的四个基本特征是：可行性、确定性、有穷性和拥有足够的情报。
答案：无穷性。
3. 算法一般都可以用哪几种控制结构组合而成？答案：顺序、选择、循环。
4. 算法的时间复杂度是指？答案：算法执行过程中所需要的基本运算次数。
5. 算法的空间复杂度是指？答案：执行过程中所需要的存储空间。
6. 算法分析的目的是？答案：分析算法的效率以求改进。
7. 下列叙述正确的是（C）A．算法的执行效率与数据的存储结构无关B．算法的空间复杂度是指算法程序中指令（或语句）的条数C．算法的有穷性是指算法必须能在执行有限个步骤之后终止D．算法的时间复杂度是指执行算法程序所需要的时间8. 数据结构作为计算机的一门学科，主要研究什么？答案：主要研究数据的逻辑结构、对各种数据结构进行的运算，以及数据的存储结构。
9. 数据结构中与所使用的计算机无关的是数据的（C）A．存储结构B．物理结构C．逻辑结构D．物理和存储结构10. 下列叙述中，错误的是（B）A．数据的存储结构与数据处理的效率密切相关B．数据的存储结构与数据处理的效率无关C．数据的存储结构在计算机中所占的空间不一定是连续的D．一种数据的逻辑结构可以有多种存储结构11. 数据的存储结构是指什么？答案：数据的逻辑结构在计算机中的表示。
12. 数据的逻辑结构是指？答案：反映数据元素之间逻辑关系的数据结构。
13. 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为？答案：线性结构和非线性结构。
14. 下列数据结构具有记忆功能的是（C）A．队列B．循环队列C．栈D．顺序表15. 下列数据结构中，按先进后出原则组织数据的是（B）A．线性链表B．栈C．循环链表D．顺序表16. 递归算法一般需要利用什么实现？答案：队列17. 下列关于栈的叙述中正确的是（D）A．在栈中只能插入数据B．在栈中只能删除数据C．栈是先进先出的线性表D．栈是先进后出的线性表18. 由两个栈共享一个存储空间的好处是？答案：节省存储空间，降低上溢发生的机率。
数据结构考试试题题库一、选择题1. 在数据结构中，栈（Stack）是一种特殊的线性表，其特点是：A. 允许在表的任意位置插入和删除元素B. 只能在表的一端进行插入和删除操作C. 只能在表的两端进行插入和删除操作D. 只能在表的中间进行插入和删除操作答案：B2. 假设有一个单链表，头结点的指针域为head，链表中每个结点包含一个数据域data和指向下一个结点的指针域next。
若要删除指针p所指向的结点，以下哪个操作是正确的？A. p = p->nextB. p->next = p->next->nextC. p = p->next->nextD. p = NULL答案：B3. 在二叉树的遍历算法中，先序遍历的顺序是：A. 先访问根节点，然后遍历左子树，最后遍历右子树B. 先遍历左子树，然后访问根节点，最后遍历右子树C. 先遍历右子树，然后访问根节点，最后遍历左子树D. 同时遍历左子树和右子树答案：A4. 哈希表的冲突可以通过多种方式解决，以下哪种不是解决哈希表冲突的方法？A. 链地址法B. 开放地址法C. 再哈希法D. 排序法答案：D5. 快速排序算法的时间复杂度在最好、最坏和平均情况下分别是：A. O(n log n), O(n^2), O(n)B. O(n), O(n log n), O(n^2)C. O(n log n), O(n), O(n log n)D. O(n^2), O(n log n), O(n)答案：A二、简答题1. 请简述什么是图，并说明图的两种基本表示方法。
答案：图是一种数据结构，由顶点（或称为节点）和边组成。
图可以表示为有向图或无向图。
图的两种基本表示方法为邻接矩阵和邻接表。
邻接矩阵是一个二维数组，其元素表示顶点之间的连接关系；邻接表则使用链表存储每个顶点的邻接点。
2. 什么是二叉搜索树（BST）？请简述其特点。
答案：二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于或等于其左子树中所有节点的值，并且小于或等于其右子树中所有节点的值。
数据结构笔试题题目数据结构笔试题题目一、选择题1.下面哪种排序法对123456798在空间和时间上最优( )A. 快速排序B. 冒泡排序C. 插入排序D. 堆排序2. 2.就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（）A．堆排序〈快速排序〈归并排序B．堆排序〈归并排序〈快速排序C．堆排序〉归并排序〉快速排序D．堆排序> 快速排序> 归并排序E．以上答案都不对3. 3.一株二叉树的以某种遍历方式的序列为A、B、C、D、E、F、G，.若该二叉树的根结点为E,则它的一种可能的前序遍历为____ ,相应的后序遍历为____A. ECBADFG, BDCAFGEB. ECBADFG, EFACDBGC. ECBADGF, EACBDGFD. EACBDGF, BDCAFGE（常见题型，给出树的前序遍历和中序遍历，中序和后续遍历，推出二叉树）4.关于图和树，下面说法正确的是________A. 树和图都允许有环B. 图的深度遍历和广度遍历结果可能一样C. 二叉树是每个节点都有两个孩子节点的树D. 二叉树的前序遍历和后序遍历结果肯定不一样5.完成在双循环链表结点p之后插入s的操作是（）A．p->next=s ; s->priou=p; p->next->priou=s ; s->next=p->next;B．p->next->priou=s; p->next=s; s->priou=p; s->next=p->next;C．s->priou=p; s->next=p->next; p->next=s; p->next->priou=s ;D．s->priou=p; s->next=p->next; p->next->priou=s ; p->next=s;二、填空题1.用链表表示的数据的简单选择排序，结点的域为数据域data ，指针域next ；链表首指针为head ，链表无头结点。
现在的公司招聘,都要笔试面试.如果你不是那种编程功底非常深厚的人,又不好好准备一番,在笔试面试中往往会处于被动局面.虽然有些笔试题是故意为难我们，有点钻牛角尖.但是很多笔试题面试题确实能够很好地看出我们的基础.在这里,我就略去那些钻牛角尖的题.从csdn论坛我近半年的收集中选出10道有代表性的题目,难度基本上是逐渐加大.对数组,指针,数据结构,算法,字符串,文件操作等问题都有覆盖.主要以c语言的实现为主,也有c++的题.大家可以先做做这10道题,测试一下自己的水平.1. 下面这段代码的输出是多少(在32位机上).char *p;char *q[20];char *m[20][20];int (*n)[10];struct MyStruct{char dda;double dda1;int type ;}；MyStruct k;printf("%d %d %d %d",sizeof(p),sizeof(q),sizeof(m),sizeof(n),sizeof(k));2.(1)char a[2][2][3]={{{1,6,3},{5,4,15}},{{3,5,33},{23,12,7}} };for(int i=0;i<12;i++)printf("%d ",_______);在空格处填上合适的语句，顺序打印出a中的数字(2)char **p, a[16][8];问：p=a是否会导致程序在以后出现问题？为什么？答：p是char**类型，而a是char[16][8]类型。
经过退化，a可以作为一个指针右值，类型为char(*)[8]，或者在参数列表中表达为char[][8]。
char**指针和char(*)[8]不是完全兼容的指针，无法无条件地相互转换。
编译器应该对p = a 这种试图进行隐式转换的表达式产生一个警告（C）或错误（C++）。
从语言层面来说，p 和 a 具有不同的类型，表达式p = a 体现了错误的语义。
从实现层面上来看，由于C/C++的数组长度不是一个左值，多维数组实际上只是数组的数组，换用不兼容的指针类型指向的对象和数组可能占用相同的存储器单元（线性地址空间的边界一致），那么不一定会出现和预期不符的问题。
但在参数传递等情况下，这个问题很容易复杂化。
事实上，LZ的问题是使用者对语言的误用。
解决方法就是保证p为char(*)[8]类型：char(*p)[8];char a[16][8];p = &a;或者（尤其是在数组大小需要改变的情况下）不要使用内置的静态数组，用指针和表达数组大小的整数来实现动态数组。
----LS linxxx3 错误，尽管这里a 和p 在语言实现（目标代码）中一般不保留类型信息而体现行为一致性，语言本身也允许相同的访问方式，但在编译期a 冗余了的类型比p 更严格，a 不只是指针，本质是不同的。
3.用递归方式,非递归方式写函数将一个字符串反转.函数原型如下:char *reverse(char *str);答：// 递归实现字符串反转char *reverse(char *str){if( !str ){return NULL;}int len = strlen(str);if( len > 1 ){char ctemp =str[0];str[0] = str[len-1];str[len-1] = '\0';// 最后一个字符在下次递归时不再处理reverse(str+1); // 递归调用str[len-1] = ctemp;}return str;}// 非递归实现字符串反转char *reverse(char *str){if( !str ){return NULL;}int len = strlen(str);char temp;for( int i = 0; i < len / 2; i++ ){// 交换前后两个相应位置的字符temp = *(str + i);*(str + i) = *(str + len - 1 - i);*(str + len - 1 - i) = temp;}return str;}int _tmain(int argc, _TCHAR* argv[]){char src[] = {"abcdef"};char *pdest = reverse(src);getchar();return 0;}4.strcpy函数和memcpy函数有什么区别?它们各自使用时应该注意什么问题?5.写一个函数将一个链表逆序.一个单链表，不知道长度，写一个函数快速找到中间节点的位置.写一个函数找出一个单向链表的倒数第n个节点的指针.(把能想到的最好算法写出).6.用递归算法判断数组a[N]是否为一个递增数组。
7.有一个文件(名为a.txt)如下,每行有4项,第一项是他们的名次,写一个c程序,将五个人的名字打印出来.并按名次排序后将5行数据仍然保存到a.txt中.使文件按名次排列每行.2,07010188,0711,李镇豪,1,07010154,0421,陈亦良,3,07010194,0312,凌瑞松,4,07010209,0351,罗安祥,5,07010237,0961,黄世传,8.写一个函数,判断一个unsigned char 字符有几位是1.写一个函数判断计算机的字节存储顺序是升序(little-endian)还是降序(big-endian).9.微软的笔试题.Implement a string class in C++ with basic functionality like comparison, concatenation, input and output. Please also provide some test cases and using scenarios (sample code of using this class). Please do not use MFC, STL and other libraries in your implementation.10.有个数组a[100]存放了100个数,这100个数取自1-99,且只有两个相同的数,剩下的98个数不同,写一个搜索算法找出相同的那个数的值.(注意空间效率时间效率尽可能要低).这十道题还是能够看出自己的水平如何的.如果你能不假思索地做出这10道题,估计去国外大公司是没有问题了,呵呵.答案我在整理中,以后陆续发布.................下面有些题也不错,可以参考.１．下面的代码输出是什么，为什么？void foo(void){unsigned int a = 6;int b = -20;(a+b>6)?puts(">6"):puts("<=6");//puts为打印函数}输出>6．就是考察隐式转换．int型变量转化成unsigned int,b成了正数．2. b)运行下面的函数会有什么结果？为什么？void foo(void){char string[10],str1[10];int i;for(i=0;i<10;i++){str1 = 'a';}strcpy(string, str1);printf("%s",string);}首先搞清strcpy函数的实现方法，char * strcpy(char * strDest,const char * strSrc){if ((strDest==NULL)||(strSrc==NULL))throw "Invalid argument(s)";char * strDestCopy=strDest;while ((*strDest++=*strSrc++)!='\0');return strDestCopy;}由于str1末尾没有'\0’结束标志，所以strcpy不知道拷贝到何时结束．printf函数，对于输出char* 类型，顺序打印字符串中的字符直到遇到空字符（＇＼０＇）或已打印了由精度指定的字符数为止．下面是微软的两道笔试题....3. Implement a string class in C++ with basic functionality like comparison, concatenation, input and output. Please also provide some test cases and using scenarios (sample code of using this class).Please do not use MFC, STL and other libraries in your implementation.我的实现方案如下,这道题真地对c++的主要特性都进行了较好地考察.String.h:#ifndef STRING_H#define STRING_H#include <iostream>using namespace std;class String{public:String(int n,char c);String(const char* source);String(const String& s);//String& operator=(char* s);String& operator=(const String& s);~String();char& operator[](int i){return a;}const char& operator[](int i) const {return a;}//对常量的索引.String& operator+=(const String& s);int length();friend istream& operator>>(istream& is, String& s);//搞清为什么将>>设置为友元函数的原因.//friend bool operator< (const String& left,const String& right);friend bool operator> (const String& left, const String& right);//下面三个运算符都没必要设成友元函数,这里是为了简单.friend bool operator== (const String& left, const String& right);friend bool operator!= (const String& left, const String& right);private:char* a;int size;};#endifString.cpp:#include "String.h"#include <cstring>#include <cstdlib>String::String(){a = new char[1];a[0] = '\0';size = 0;}String::String(int n,char c){a = new char[n + 1];memset(a,c,n);a[n] = '\0';size = n;}String::String(const char* source){if(source == NULL){a = new char[1];a[0] = '\0';}else{ size = strlen(source);a = new char[size + 1];strcpy(a,source);}}String::String(const String& s){size = strlen(s.a);//可以访问私有变量.a = new char[size + 1];//if(a == NULL)strcpy(a,s.a);}String& String::operator=(const String& s){ if(this == &s)return *this;else{delete[] a;size = strlen(s.a);a = new char[size + 1];strcpy(a,s.a);return *this;}}String::~String(){delete[] a;//}String& String::operator+=(const String& s){ int j = strlen(a);int size = j + strlen(s.a);char* tmp = new char[size+1];strcpy(tmp,a);strcpy(tmp+j,s.a);delete[] a;a = tmp;return *this;}int String::length(){return strlen(a);}main.cpp:#include <iostream>#include "String.h"using namespace std;bool operator==(const String& left, const String& right) {int a = strcmp(left.a,right.a);if(a == 0)return true;elsereturn false;}bool operator!=(const String& left, const String& right) {return !(left == right);}ostream& operator<<(ostream& os,String& s){int length = s.length();for(int i = 0;i < length;i++)//os << s.a;这么不行,私有变量.os << s;return os;}String operator+(const String& a,const String& b){ String temp;temp = a;temp += b;return temp;}bool operator<(const String& left,const String& right){int j = 0;while((left[j] != '\0') && (right[j] != '\0')){if(left[j] < right[j])return true;else{if(left[j] == right[j]){j++;continue;}elsereturn false;}}if((left[j] == '\0') && (right[j] != '\0'))return true;elsereturn false;}bool operator>(const String& left, const String& right) { int a = strcmp(left.a,right.a);if(a > 0)return true;elsereturn false;}istream& operator>>(istream& is, String& s){delete[] s.a;s.a = new char[20];int m = 20;char c;int i = 0;while (is.get(c) && isspace(c));if (is) {do {s.a = c;i++;/*if(i >= 20){cout << "Input too much characters!" << endl;exit(-1);}*/if(i == m - 1 ){s.a = '\0';char* b = new char[m];strcpy(b,s.a);m = m * 2;s.a = new char[m];strcpy(s.a,b);delete[] b;}}while (is.get(c) && !isspace(c));//如果读到空白,将其放回.if (is)is.unget();}s.size = i;s.a = '\0';return is;}int main(){String a = "abcd";String b = "www";//String c(6,b);这么写不对.String c(6,'l');String d;String e = a;//abcdString f;cin >> f;//需要输入...String g;g = a + b;//abcdwwwif(a < b)cout << "a < b" << endl;elsecout << "a >= b" << endl;if(e == a)cout << "e == a" << endl;elsecout << "e != a" << endl;b += a;cout << a << endl;cout << b << endl;cout << c << endl;cout << d << endl;cout << e << endl;cout << f << endl;cout << g << endl;cout << g[0] << endl;return 0;}4. Implement a single-direction linked list sorting algorithm. Please first define the data structure of linked list and then implement the sorting algorithm.5.编写一个函数，返回两个字符串的最大公串！例如，“adbccadebbca”和“edabccadece”,返回“ccade”联想笔试题1．设计函数int atoi(char *s)。
