1、中科院计算所数据结构试题 答案20101、线性表Lx, Ly按单链表结构存储并按递增排序。请给出算法，合并这两个表为一个新的线性表并仍按递增排序。（10分）void SqList_Intersect(SqList A,SqList B,SqList &C)/求元素递增排列的线性表A和B的元素的交集并存入C中 int i=1;j=1;k=0; while(A.elemi&B.elemj) if(A.elemiB.elemj) j+; if(A.elemi=B.elemj) C.elem+k=A.elemi; /当发现了一个在A,B中都存在的元素, i+;j+; /就添加到C中 /while/Sq
2、List_Intersect2、void replace( String s, String s1, String s2 )将s中是s1的字符串全部替换为s2，如s=“aabcaaabc”，s1=“abc”，s2=“efgh”，则在本函数执行完后s=“aefghaaefgh”，实现本算法，可以使用字符串的一些基本操作函数。（15分）3、字母A，B，C，D，E，F分别对应的频率为2，3，5，7，11，19。（15分）求：（1）最优树；（2）求带权路径长度；（3）求各字母的编码。4、使用散列函数hashf(x)=x mod 11，把一个整数值转换成散列表下标，现要把数据1，13，12，34，38，
3、33，27，22插入到散列表中。（15分）（1）使用线性探查再散列法来构造散列表；（2）使用二次探查法构造散列表。5、请给出快速排序的算法，并以初始关键字64，28，48，96，72，16，25为例，给出各趟排序后的状态。（15分）int Partition(SqList &L, int low, int high) / 算法10.6(a) / 交换顺序表L中子序列L.rlow.high的记录，使枢轴记录到位， / 并返回其所在位置，此时，在它之前（后）的记录均不大（小）于它 KeyType pivotkey; RedType temp; pivotkey = L.rlow.key; / 用子
4、表的第一个记录作枢轴记录 while (lowhigh) / 从表的两端交替地向中间扫描 while (low=pivotkey) -high; temp=L.rlow; L.rlow=L.rhigh; L.rhigh=temp; / 将比枢轴记录小的记录交换到低端 while (lowhigh & L.rlow.key=pivotkey) +low; temp=L.rlow; L.rlow=L.rhigh; L.rhigh=temp; / 将比枢轴记录大的记录交换到高端 return low; / 返回枢轴所在位置 / Partitionint Partition(SqList &L, in
5、t low, int high) / 算法10.6(b) / 交换顺序表L中子序列L.rlow.high的记录，使枢轴记录到位， / 并返回其所在位置，此时，在它之前（后）的记录均不大（小）于它 KeyType pivotkey; L.r0 = L.rlow; / 用子表的第一个记录作枢轴记录 pivotkey = L.rlow.key; / 枢轴记录关键字 while (lowhigh) / 从表的两端交替地向中间扫描 while (low=pivotkey) -high; L.rlow = L.rhigh; / 将比枢轴记录小的记录移到低端 while (lowhigh & L.rlow.
6、key=pivotkey) +low; L.rhigh = L.rlow; / 将比枢轴记录大的记录移到高端 L.rlow = L.r0; / 枢轴记录到位 return low; / 返回枢轴位置 / Partitionvoid QSort(SqList &L, int low, int high) /算法10.7 / 对顺序表L中的子序列L.rlow.high进行快速排序 int pivotloc; if (low high) / 长度大于1 pivotloc = Partition(L, low, high); / 将L.rlow.high一分为二 QSort(L, low, pivot
7、loc-1); / 对低子表递归排序，pivotloc是枢轴位置 QSort(L, pivotloc+1, high); / 对高子表递归排序 / Qsortvoid QuickSort(SqList &L) / 算法10.8 / 对顺序表L进行快速排序 QSort(L, 1, L.length); / QuickSort6、如下图所示的B树，分别插入B，L，Q，R后，请给出树的状态。（15分）7、假设有稀疏矩阵A和B均为三元组作为存储结构，另设三元组C存放结果矩阵，请编写相乘算法。（15分）20091、请写出求解八皇后问题的算法。（10分）int Count=0;void move(char
8、 x, int n, char z);void hanoi (int n, char x, char y, char z) / 算法3.5 / 将塔座x上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到 / 塔座z上，y可用作辅助塔座。 / 搬动操作 move (x, n, z) 可定义为： / (c是初值为0的全局变量，对搬动计数) / printf(%i. Move disk %i from %c to %cn, +c, n, x, z); if (n=1) move(x, 1, z); /将编号为的圆盘从x移到z else hanoi(n-1,x,z,y); move(x, n,
9、 z); /将编号为n的圆盘从x移到z hanoi(n-1, y, x, z); /将y上编号为至n-1的圆盘移到z,x作辅助塔 void move(char x, int n, char z) printf( %2i. Move disk %i from %c to %cn,+Count,n,x,z);2、已知主串s=“adbadabbaabadabbadada”，模式串pat=“adabbadada”，（1）求出模式串的nextval函数值优树；（10分）（2）列出KMP算法匹配的全过程。（10分）3、已知k1k2k3k4k5k6，请求出分别为q1=3，q2=q3=q4=q5=q6=1和q
10、1= q2=q3=q4=q5=q6=1的最优二叉排序树。（15分）4、验证哥德巴赫猜想，任何一个大于3的数可以表示为两个素数相加。（10分）5、请写出外部置换的败者树算法。（10分）6、请给出快速排序的算法，7个节点最少需要多少次比较？（10分）并举一个实例。（8分）int Partition(SqList &L, int low, int high) / 算法10.6(a) / 交换顺序表L中子序列L.rlow.high的记录，使枢轴记录到位， / 并返回其所在位置，此时，在它之前（后）的记录均不大（小）于它 KeyType pivotkey; RedType temp; pivotkey
11、= L.rlow.key; / 用子表的第一个记录作枢轴记录 while (lowhigh) / 从表的两端交替地向中间扫描 while (low=pivotkey) -high; temp=L.rlow; L.rlow=L.rhigh; L.rhigh=temp; / 将比枢轴记录小的记录交换到低端 while (lowhigh & L.rlow.key=pivotkey) +low; temp=L.rlow; L.rlow=L.rhigh; L.rhigh=temp; / 将比枢轴记录大的记录交换到高端 return low; / 返回枢轴所在位置 / Partitionint Parti
12、tion(SqList &L, int low, int high) / 算法10.6(b) / 交换顺序表L中子序列L.rlow.high的记录，使枢轴记录到位， / 并返回其所在位置，此时，在它之前（后）的记录均不大（小）于它 KeyType pivotkey; L.r0 = L.rlow; / 用子表的第一个记录作枢轴记录 pivotkey = L.rlow.key; / 枢轴记录关键字 while (lowhigh) / 从表的两端交替地向中间扫描 while (low=pivotkey) -high; L.rlow = L.rhigh; / 将比枢轴记录小的记录移到低端 while
13、(lowhigh & L.rlow.key=pivotkey) +low; L.rhigh = L.rlow; / 将比枢轴记录大的记录移到高端 L.rlow = L.r0; / 枢轴记录到位 return low; / 返回枢轴位置 / Partitionvoid QSort(SqList &L, int low, int high) /算法10.7 / 对顺序表L中的子序列L.rlow.high进行快速排序 int pivotloc; if (low high) / 长度大于1 pivotloc = Partition(L, low, high); / 将L.rlow.high一分为二 Q
14、Sort(L, low, pivotloc-1); / 对低子表递归排序，pivotloc是枢轴位置 QSort(L, pivotloc+1, high); / 对高子表递归排序 / Qsortvoid QuickSort(SqList &L) / 算法10.8 / 对顺序表L进行快速排序 QSort(L, 1, L.length); / QuickSort7、假设有稀疏矩阵A和B均以三元组作为存储结构，另设三元组C存放结果矩阵，请编写相乘算法。（15分）Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) / 算法5.3 / 求
15、矩阵乘积Q=M?N，采用行逻辑链接存储表示。 int arow,brow,p,q,t,ctemp30,l,ccol,tp; if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; / Q初始化 if (M.tu*N.tu != 0) / Q是非零矩阵 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 for (l=1; l=M.nu; +l) ctempl = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; if (arowM.mu) tp=M.rposa
16、row+1; else tp=M.tu+1; for (p=M.rposarow; ptp;+p) / 对当前行中每一个非零元 brow=M.datap.j; / 找到对应元在N中的行号 if (brow N.mu ) t = N.rposbrow+1; else t = N.tu+1; for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘积元素在Q中列号 ctempccol += M.datap.e * N.dataq.e; / for q / 求得Q中第crow( =arow)行的非零元 for (ccol=1; ccol MAXSIZE) r
17、eturn ERROR; Q.dataQ.tu.i=arow; Q.dataQ.tu.j=ccol; Q.dataQ.tu.e=ctempccol; / if / for arow / if return OK; / MultSMatrix20081、n阶Hanoi塔问题是这样的：假设有三个分别命名为A、B、C的塔座，在塔座A上插有n个直径大小各不相同、依小到大编号为1,2，n的圆盘，现在要求塔座A上的n歌圆盘移到塔座C上并且依然按同样的顺序叠排，圆盘移动时必须遵守下列的规则：（1）每次只能移动一个圆盘；（2）圆盘可以插在ABC中任何一个塔座上；（3）任何时候都不能把一个大的圆盘压在一个小的上
18、面。请写出求n阶Hanoi塔问题的算法。（10分）int Count=0;void move(char x, int n, char z);void hanoi (int n, char x, char y, char z) / 算法3.5 / 将塔座x上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到 / 塔座z上，y可用作辅助塔座。 / 搬动操作 move (x, n, z) 可定义为： / (c是初值为0的全局变量，对搬动计数) / printf(%i. Move disk %i from %c to %cn, +c, n, x, z); if (n=1) move(x, 1,
19、z); /将编号为的圆盘从x移到z else hanoi(n-1,x,z,y); move(x, n, z); /将编号为n的圆盘从x移到z hanoi(n-1, y, x, z); /将y上编号为至n-1的圆盘移到z,x作辅助塔 void move(char x, int n, char z) printf( %2i. Move disk %i from %c to %cn,+Count,n,x,z);2、设有两个字符串T和P，从目标T中查找模式P的字串的过程称为“模式匹配”。请编写无回溯的匹配算法。（15分）3、设计一种哈希表查找一个班级的人名，使得平均查找长度不超过R，并完成相应的建表和
20、查表程序。（15分）4、已知元素个数为12的字典，其元素集合为：Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec按元素顺序构造一颗AVL树，并求其在等概率情况下查找成功的平均查找长度。（15分）5、用Dijstra算法求下图中的从顶点v0到其他顶点的最短路径，要求写出此图的关系矩阵arcs和数组Dist在算法执行过程的变化，以及每一条最短的路径。（15）6、假设有稀疏矩阵A和B均以三元组作为存储结构，另设三元组C存放结果矩阵，请编写相加算法。（15分）7、请给出快速排序的算法，并以初始关键字64，28，48，96，72，16，25为例，给出各趟
21、排序后的状态。（15分）20071、编写算法实现十进制转二进制，并将结果存入一个数组。（10分）void conversion (int Num) / 算法3.1 / 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 ElemType e; SqStack S; InitStack(S); / 构造空栈 while (Num) Push(S, Num % 8); Num = Num/8; while (!StackEmpty(S) Pop(S,e); printf (%d, e); printf(n); / conversion2、编写八皇后问题的算法。（15分）3、void re
22、place( String s, String s1, String s2 )将s中是s1的字符串全部替换为s2，如s=“aabcaaabc”，s1=“abc”，s2=“efgh”，则在本函数执行完后s=“aefghaaefgh”，实现本算法，可以使用字符串的一些基本操作函数。（15分）void repl(String &s, String t, String v) k = Index(s, t );if( k ) StrAssign( temp, ); /temp为置换后得到的新串 n = StrLength( t ); m = StrLength( s ); while( k ) StrA
23、ssign( temp, Concat( temp , SubString( s, 1, k-1), v ) ); m -= ( k 1 ) n; StrAssign( s, SubString( s, k+n, m ) ); k = Index( s, t );StrAssign( s, Concat( temp, s ) );int HString_Replace(HString &S,HString T,HString V)/堆结构串上的置换操作,返回置换次数 for(n=0,i=0;i=S.length-T.length;i+) for(j=i,k=0;kT.length&S.chj=
24、T.chk;j+,k+); if(k=T.length) /找到了与T匹配的子串:分三种情况处理 if(T.length=V.length) for(l=1;l=T.length;l+) /新子串长度与原子串相同时:直接替换 S.chi+l-1=V.chl-1; else if(T.length=i+T.length;l-) S.chl+V.length-T.length=S.chl; for(l=0;lV.length;l+) Si+l=Vl; else /新子串长度小于原子串时:先将后部左移 for(l=i+V.length;lS.length+V.length-T.length;l+)
25、S.chl=S.chl-V.length+T.length; for(l=0;lV.length;l+) Si+l=Vl; S.length+=V.length-T.length; i+=V.length;n+; /if /for return n;/HString_Replace4、给出11个权值：23，15，66，07，11，45，33，52，39，26，58。试构造一颗具有最小带权路径长度的扩充4叉树，要求该4叉树中所有结点的度都是4，所有外部结点的度都是0，这棵4叉树的带权外部路径长度是多少？（15分）5、设有一组关键字1，13，12，34，38，33，27，22，采用哈希函数hash
26、f(x)=x mod 11，分别以线性探测再散列和链地址方法处理冲突，对该关键字序列构造哈希表。（15分）6、写出快速排序算法，并对一组给定的数1，21，33，17，4，89，20，写出每趟排序之后的序列（15分）7、关于内存管理中的边界标识符算法，请写出这个算法的分配与回收空间算法。（15分）20061、汉诺塔问题。2、（15分）设计算法frequency统计一个输入字符串各字符的出现频次。/ s是输入字符串，数组A 中记录字符串中有多少种不同的字符，C 中记录每一种字符的出现次数。这两个数组都应在调用程序中定义。k返回不同字符数。void frequency( string& s, cha
27、r A , int C , int &k ) int len = s.Length(); if(!len) k = 0; return; else A0 = s.ch0; C0 = 1; k = 1;/语句si是串的重载操作 int i,j; for (i = 1; i len; i+) Ci = 0; /初始化 for (i = 1; i len; i+)/检测串中所有字符 j = 0; while ( j 1。20041、请写出求解n阶Hanoi塔问题的算法。（10分）2、在格的国际象棋棋盘上放置8个皇后，使得任意两个皇后不能相互攻击，这样的一个格局称为问题的一个解。编写一个程序求出所有解。（15分）3、写一个程序把整数翻成二级制表示（不带打头0），二进制表示用一个数组表示。（15分）4、以二叉链表作存储结构，请编写算法将二叉树中所有的左右子树相互交换。（15分）5、使用散列函数hashf(x)=x mod 11，把一个整数值转换成散列表下标，现要把数据1，13，12，34，38，33，27，2
