习题1
1.1数据结构研究的内容是什么？
1.2什么是算法？评价算法（算法设计）的标准是什么？在保证正确性的前提下，算法设计的首要目标是什么？
1.3 viod sum(int n, int &s) {
int i,j,s=0;
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
s=s+i*j;
}
问题：(1) 对变量s的赋值操作总共执行了次。
(2) 算法的时间复杂度是。
1.4 编一高效算法，求 1！+2！+……+n! 。
1.5 将一组无序的数据排列成一个有序序列，写一算法实现。
习题2
2.1什么是线性表？线性表有哪两种存储结构？请比较这两种存储结构的不同。
2.2什么是头指针？什么是头结点？它们的作用是什么？
2.3若线性表以一维数组为存储结构，该表中有1000个数据元素，第一个元素的地址为1000，每个元
素的值需占用4个存储单元，该线性表需要多大的存储空间？第200个元素的起始地址是多少？在第300处插入一个元素，有多少个元素会移动？
2.4设线性表存于a[1..arrsize]的前n个分量中, 且递增有序. 写一算法，将x插入到线性表的适当位置, 以保持线性表的有序性。
2.5已知线性表存于a[1..array]中的前n个分量中，写一算法，删除从第i个元素起的k个元素。
2.6写一算法, 将顺序存储的线性表（v1,v2,…,v n）改变成(v k+1,v k+2,…,v n,v1,v2,…,v k)。
2.7写一算法，将所有值为x的元素移到顺序表的末尾.
2.8写出在带头结点的动态单链表结构上实现线性表操作 LOCATE(L,X)和 LENGTH(L)的算法
2.9已知ha和hb分别指向两个单链表的头结点, 且头结点的数据域(整型)中存放链表的长度, 写一算法将这两个链表接在一起, 并要求以尽可能短的时间完成。
2.10已知线性表中的元素按值递增排列, 并以单链表作存储结构. 写一高效算法, 删除表中的多余元素, 使得运算后的线性表中所有元素的值均不相同。
2.11  以一维数组、单向链表、双向循环链表作存储结构, 实现线性表就地逆置的算法, 即将线性表：(a1,a2,...an)==>(an,...,a2,a1)
2.12 已知单向循环链表表示的线性表中含有三全域:pre、数据和next, 其中数据为数据域,next为指针域，值为后继, pre也是指针域, 其值为NIL. 写一算法, 将此链改为双向链表。
2.13 在其元素值按递增排序的双向链表中增加一个freq频度域(初值为0), 每当进行LOCATE(L,X) 运算时, X结点的freq加1, 写一算法完成LOCATE(L,X), 并保证其有序性。
2.14设计一个算法, 将一个用循环链表表示的稀疏多项式分解成两个多项式, 使这两个多项式中各自仅含奇次项或偶次项, 并要求利用原链表的结点空间来构成这两个链表。
习题3
3.1什么是栈？若入栈顺序为1234，列出所有可能的出栈序列。
3.2什么是栈？什么是队列？它们各自有什么特点？它们的共同点是什么？他们与线性表有何不同。
3.3 什么是队列？什么是顺序队列？什么是循环队列？循环队列的优点是什么？举一例说明队列的应用。
3.4 在火车站的入口处有n节硬席或软席车厢(分别用Ｈ和Ｓ来表示)等待调度，写一算法，输出对这n 节车厢进行调度的操作序列，使和所有的软件席车厢调到硬席车厢之前。
3.5 写一个判别表达式中开、闭括号是否配对出现的算法。
3.6 在一个带头结点的循环队列中，只设一个尾指针指向队尾元素结点，编写算法实现队列初始化、入队和出队。
3.7 以数组q[m]存放循环队列的元素，同时设rear和quelen表示循环队列中队尾的位置和内含的元素个数, 给出队满条件, 并写出相应的入队列和出队列的算法。
习题4
4.1 简述空串和空格串（或称空格符串）的区别。
4.2 对于字符串的每个基本运算，讨论是否可由其它基本运算构造而得？如何构造？
4.3 设s=“I AM A STUDENT”, t=“GOOD”, q=“WORKER”。
求：StrLength(s),  SubString(s,8,7), Index(s,“a”), Index(s,t), Replace(s,“STUDENT”,q), Concat（Substring（s,6,2）, Concat(t, Substring(s,7,8))）。
4.4 已知：s=ˊ(XYZ)+*ˊ,t=ˊ(X+Z)*Y。利用联接、求子串和置换等基本运算，将s转化为t。
4.5 以4.2.1中所述类型SString 作存储结构实现以下基本操作：
（1）CONCAT；(2）EQUAL；（3）REPLACE。
4.6 以4.2.1中所述类型SString 作存储结构，利用Index等基本运算，编写在文本s中删除所有和串t相同的子串的算法。
4.7  令s=”abcd”,t=”abcabaa”,u=”abcaabbabcabaacbacba”。求出它们的next函数值。
习题5
5.1为什么以顺序存储结构为矩阵的存储结构？有哪两顺序存储方式？请从线性表的角度来理解一个矩阵。
5.2 将一个a[100][100]的三对角矩阵以行主序存入一维数组B[298]中，元素a[65][64]在B数组中的位置k等于多少？
5.3简述广义表与线性表的区别与联系。
5.4 画出广义表（((0)),a,((b,c),(((e))))）的存储结构图。
5.5 写一算法，求广义表的长度和宽度。
5.6 写一算法，求A10*30*B30*70*C70*1*D1*200
习题6
6.1度为2的树与二叉树有什么区别?
6.2画出3个结点的树和二叉树的所有形态。
6.3 如下表所示，
问已知答前序遍历时
N在M前?
中序遍历时N
在M前?
后序遍历时N
在M前?
N在M的左边
N在M的右边
N是M的祖先
N是M的子孙
6.4 已知树结点的中序序列是cbaedfg，后序序列是cbegfda，画出这棵树的逻辑结构图。
6.5 已知完全二叉树结点的前序序列是abcdefghi，画出这棵完全二叉树的逻辑结构图。
6.6 已知6个叶子结点的权值分别为2、5、5、7、9、13。请画出相应的哈夫曼树。
6.7 以二叉链表作为存储结构, 编一算法判别给定二叉树是否为完全二叉树.
6.8 已知一棵以二叉链为存储结构的二叉树，编写按求每一结点所在的层次的算法.
6.9 以二叉链为存储结构, 编写求二叉树的叶子数的递归算法。
6.10 以二叉链为存储结构, 写出将二叉树中所有结点的左、右孩子相互交换的递归算法.
6.11 以二叉链为存储结构, 写一个求二叉树深度的递归算法.
6.12 已知一棵二叉树以二叉链作为存储结构，编写完成下列操作的算法: 对于树中每一个元素值为x的结点, 删去以它为根的子树, 并释放相应的空间.
6.13以二叉链为存储结构，在二叉树中查x结点，写一算法，
打印值为x的结点的所有祖先的算法。
6.14已知一棵二叉树以二叉链作为存储结构, 求这样一个结点, 它在前序遍历序列中处于第k个位置。
6.15 写一计算树的深度的算法.
6.16以孩子-兄弟链链表示法，写一算法求森林中的树的棵数.。
习题7
7.1对n个结点的有向图，采用邻接矩阵和邻接表表示时，如何判断下列问题：
（1）图中有多少条边？
（2）任意两个顶点i和j是否有边相连？
（3）任意一个顶点的度是多少？
7.2 对图7_1所示无向图，完成下列操作：
（1）指出每个顶点的度。
（2）写出它的邻接矩阵。
（3）画出它的邻接表。
7.3对图7_1所示无向图，
（1）从顶点v6开始进行深度遍历，列出所有的深度遍历序列；
（2）从顶点v6开始进行广度遍历，列出所有的广度遍历序列。
7.4对图7_1所示无向图，用prim方法和kruskal方法构造最小生成树。
7_1
7.5写出教材图7.28所示的AOV网的所有的拓扑序列。
7.6对图7_2所示AOE网，求（1）各事件的最早和最迟开始时间；（2）关键路径。
事件    1  2 3 4 5 6 7 8 9
最早开始时间
最迟开始时间
图 7_2
7.7以邻接表为存储结构，写一算法求有向图中每一顶点的入度和出度。
7.8以邻接表为存储结构，写出深度优先搜索遍历的非递归算法
7.9以邻接表为存储结构，基于深度优先搜索，判断有向图中是否存在由顶点vi到顶点vj的路径
(i<>j)。
7.10以邻接数组为存储结构，基于广度优先搜索，判断有向图中是否存在由顶点vi到顶点vj的路径
(i<>j)。
7.11给定n个村庄，若村庄i和村庄j之间有一条道路，则顶点i和j用边相连，边上的权表示这条路的长度。现要建立一所医院，问这所医院建在哪个村庄为最佳？为什么？用算法实现。
习题8
8.1 什么是查？查算法中在保证正确性的情况下，算法设计的首要目标是什么？
8.2 折半查的先决条件是什么？叙述查方法。为什么不能用链表作为存储结构？
8.3 什么是二叉排序树？二叉排序树特点是什么？怎样通过二叉排序树得到一个有序序列？
8.4以{20,13,24,37,90,53,12}构造二叉排序树。
8.5以{20,13,24,37,90,53,12}构造二叉平衡树。
8.6在地址空间为0--16的散列区中，对关键字序列(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep, Oct,Nov, Dec),
（1）构造HASH表。 H(x)=i mod 17 （或 H(x)=i % 17 ），其中i 为关键字x中第一个字母在字母表中的序号, 解决冲突的方法用线性探测法。
（2）求出查成功和查失败的平均查长度。
8.7 用链地址法处理冲突，重做第8.6题。
8.8一棵5阶B+树由依次插入以下18个关键字构成：51,49,39,46,38,29,14,61,15,30,10, 48,52,13, 33,37,25,36，试画出这棵B+树。
8.9写一个在非循环单向链表上实现顺序查的算法。
8.10写一个分块查算法，要求索引存储结构中的每一块用单向链表表示，在索引表上通过顺序查确定所在块。字符串是什么数据结构
8.11 写一个查算法，分别出二叉排序树中关键字最大的元素和关键字最小的元素。
8.12 写一个算法，在二叉排序树中查关键字为x的结点，依次输出查过程中所遇结点的关键字。
8.13写一个用于判别某棵二叉树是否是二叉排序树。
8.14写一个算法，求二叉树中所有结点的平衡因子。
习题9
9.1给定关键字序列{123,543,067,216,351,374,230,014}，写出
（1）直接插入排序
（2）简单选择排序
（3）冒泡排序
（4）快速排序
（5）归并排序
（6）堆排序
（7）基数排序
的过程。
9.2以单链表为存储结构, 写一算法实现选择排序。
9.3以单链表为存储结构, 写一算法实现插入排序。
9.4以单链表为存储结构, 写一算法实现归并排序。
9.5以单链表为存储结构，写一算法完成基数排序。
9.6在我们讨论过的2－路归并方式中，排序是从n个大小为1的子文件（每个子文件只有一个记录）开始的。另一种改进的方法是：首先对待排序的文件进行一次扫描，将它们划分成最少个数的有序子文件。重写2－路归并排序算法。
9.7 已知(k1,k2,...kn)是堆，在堆中插入一元素，使之仍成为堆。用一高效算法实现。
9.8给定值k(1<k<n), 要求在无序记录a[1]..a[n]中到关键字从小到大排序的第k位上的记录，设
计一个你认为最合适的算法。
习题10
10.1已知10个初始顺串的长度分别是3,7,8,9,15,16,18,20,23,25，请画出相应的最优3路归并树。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。