数据结构机试样题

《数据结构机试样题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构机试样题1.一元稀疏多项式加法运算描述：设计一个一元稀疏多项式加法运算器，完成多项式a和b相加，建立多项式a+b。输入说明：一组输入数据，所有数据均为整数。第1行为2个正整数n，m，其中n表示第一个多项式的项数，m表示第二个多项式的项数；第2行包含2n个整数，每两个整数分别表示第一个多项式每一项的系数和指数；第3行包含2m个整数，每两个整数分别表示第二个多项式每一项的系数和指数。（注：序列按指数升序排列）输出说明：在一行以类多项式形式输出结果，指数按从低到高的顺序。注意，系数值为1的非零次项的输出形式中略去系数1，如1x^2的输出形式为x^2，-1x^2的输出形式为-x^2。输入样

2、例：62101112131425-13-24输出样例：1+x+x^2-x^4+2x^52.括号匹配的检验描述：假设一个表达式或一段程序中含有三种括号：圆括号“（”和“）”、方括号“[”和“]”、花括号“{”和“}”。试写一个程序判别给定的表达式或程序中所含括号是否正确配对出现。输入说明：多组输入数据，第1行为1个正整数n，表明有n组测试数据；其余n行为n组测试数据，每行为一个含有括号的表达式或一段程序。输出说明：对于每一组测试数据，输出一个right或wrong，表明正确匹配与否。输入样例：3a=b+(c-d)*(e-f));while(m<(a[8]+t){m=m+1;t=t-1;}b=

3、a*(4+c)-c[i];输出样例：wrongwrongright3.根据二叉树的先序和中序列得到后序序列描述：二叉树的每个节点用一个字符表示，如果知道二叉树的先序序列和中序序列则可以构造出一颗二叉树，进而可以得到该二叉树的后序序列输入说明：仅一组数据，第一行为该二叉树的先序序列，第二行为该二叉树的中序遍历序列。输出说明：输出该二叉树的后序遍历序列输入样例：ABDGCEFHDGBAECHF输出样例：GDBEHFCA提示使用递归算法，根据先序序列找到树根，然后在中序序列中找到左右子树。此题不一定需要把树建立起来，可以在递归同时就得到后序序列。4.计算huffman树WPL描述：假设用于通信的

4、电文由ｎ（4

5、，分别表示该边的两个顶点和边上的权值。输出说明：输出得到的最小生成树的代价。输入样例：811123145161824725635103820461547115785812输出样例：59提示每次找到最小生成树的一条边时累加其权值即可得到最小生成树的代价6.求无向图连通子图描述：求无向图连通子图个数输入说明：仅一组数据，输入数据第一行为两个正整数n（1

6、数。输入样例：981213243457566789输出样例：3234提示图的连通性以图的遍历为基础，因此本题需要在图的遍历算法基础上实现7.最短路径描述：已知无向图的邻接矩阵，求顶点间的最短路径。输入说明：输入数据第一行为1个正整数，是顶点个数n(n≤20)，顶点编号为0，1，…，n-1。后面是邻接矩阵，n行n列（第i行第j个数表示顶点i-1和顶点j-1之间的边长，用10000来表示两个顶点之间无边）。下一行为正整数t，表示后面有t组测试数据。最后是t行，每行输入一对顶点x和y，x为起点，y为终点。输出说明：共2t行，每2行为一组测试数据的输出结果。每组输出的第一行为x到y顶点的最短路径长

7、度，每组输出的第二行为最短路径，顶点间用空格隔开。输入样例：80101210000100001000010000100001001000014100001000010000100001210000011151000010000100001000014110100001771000010000100001510000010000910000100001000010000171000001000081000010000100