《数据结构与算法》第四章-串-考研真题精选

习题答案1.填空题（1）非线性、一对多（2）前驱（3）叶结点（叶子结点）（4）度数（5）两（6）满二叉（7）从根结点到该结点之间的路径长度与该结点的权值的乘积（8）树中所有叶结点的带权路径长度之和（9）递增（10）平衡因子（11）B树的阶2.选择题（1）B （2）D （3）A （4）C （5）B （6）A （7）D （8）D3.思考题（1）如果i=1，则结点i无双亲，为根结点。

如果i>1，则结点i的双亲结点是结点i/2。

如果2i≤n，则结点i的左孩子是结点2i，否则结点i为叶结点。

如果2i+1≤n，则结点i的右孩子是结点2i+1，否则结点i无右孩子。

（2）非叶结点最多只有M个孩子，且M>2。

除根结点以外的非叶结点都有k个孩子和k-1个数据元素，k值满足[M/2]≤k≤M。

每一个叶结点都有k-1个数据元素，k值满足[M/2]≤k≤M。

所有叶结点都在同一层次。

所有分支结点的信息数据一致（n,A0,K1,A1,K2,A2……K n,A n），其中：K i（i=1,2……n）为关键字，且K i<K i+1（i=1,2……n-1）；A i为指向孩子结点的指针，且指针A i−1指向子树中的所有结点均小于K i，A n所指子树中的所有结点的关键字均大于K n；n为关键字的个数（[M/2]-1≤n≤M-1）。

（3）B+树是B树的升级版，区别在于叶结点在B+树的最底层（所有叶结点都在同一层），叶结点中存放索引值、指向记录的指针、指向下一个叶结点的指针。

叶结点按照关键字的大小，从小到大顺序链接。

分支结点不保存数据，只用来作索引，所有数据都保存在叶结点。

B*树是B+树的变体，B*树不同于B+树的是：其非根和非叶子结点上增加了指向兄弟结点的指针。

4.编程题（1）1//参数1为树的结点个数，参数2起始结点编号2btree_t *btree_create(int n, int i){3 btree_t *t;4 //使用malloc函数为结点申请内存空间5 t = (btree_t *)malloc(sizeof(btree_t));6 //将结点编号作为数据，保存至data中7 t->data = i;89 if(2 * i <= n){ //满足条件，说明结点有左孩子，编号为2i10 //递归调用，为左孩子的创建申请空间11 t->lchild = btree_create(n, 2 * i);12 }13 else{ //不满足条件，则没有左孩子14 t->lchild = NULL;15 }1617 if(2 * i + 1 <= n){ //满足条件，说明结点有右孩子，编号为2i+118 //递归调用，为右孩子的创建申请空间19 t->rchild = btree_create(n, 2 * i + 1);20 }21 else{ //不满足条件，则没有右孩子22 t->rchild = NULL;23 }2425 return t;26}。

数据结构考研真题精选
咱今儿就来唠唠数据结构考研真题这档子事儿！
你说这数据结构啊，那可真是让不少考研学子又爱又恨。

就拿我当年认识的一个学弟来说吧，他叫小李。

小李那可是个拼命三郎，整天泡在图书馆里啃数据结构的书。

有一次我路过图书馆，看到他正对着一道真题抓耳挠腮。

那道题是关于二叉树的遍历，题目给了一个复杂的二叉树结构，让求出先序、中序和后序遍历的结果。

小李在草稿纸上画了一遍又一遍，额头上都冒出了汗珠。

咱再来说说这考研真题里常见的链表问题。

链表的插入、删除操作那可是重点中的重点。

有一年的真题就考了个链表的反转，要求在原地实现链表节点顺序的反转。

这题看似简单，实则暗藏玄机。

要是对链表的指针操作不熟练，那可就容易掉坑里。

还有数组和字符串相关的真题，也是常考不衰。

比如说，给你一个字符串，让你找出其中最长的回文子串。

这就得考验你对字符串操作的细致程度和算法的巧妙运用了。

再比如图的算法，像最短路径问题、最小生成树问题，那都是热门考点。

曾经有一道真题是关于城市之间的交通网络，要求找出从一个城市到其他所有城市的最短路径。

这就需要你熟练掌握迪杰斯特拉算法或者弗洛伊德算法。

数据结构的考研真题啊，就像是一个个隐藏在暗处的小怪兽，你得有足够的智慧和技巧才能把它们一一打败。

就像小李，经过无数次的刷题和总结，他终于找到了对付这些真题的窍门。

总之，数据结构的考研真题虽然难，但只要咱下足功夫，多练多总结，就一定能攻克它们！相信自己，加油冲吧！。

第 4 章 树结构1.选择题（1）C （2）C （3）B （4）B （5）B （6）C （7）C （8）D （9）A （10）D （11）D （12）B （13）B （14）D （15）B2.判断题（1）√（2）√ （3）Ⅹ （4）Ⅹ（5）√ （6）Ⅹ（7）√ （8）√（9）√（10）Ⅹ （11）Ⅹ（12）Ⅹ（13）√（14）Ⅹ（15）Ⅹ（16）Ⅹ（17）√（18）Ⅹ（19）Ⅹ（20）√3.简答题（1）一棵度为 2 的树与一棵二叉树有何区别？树与二叉树之间有何区别？【解答】①二叉树是有序树，度为 2 的树是无序树，二叉树的度不一定是 2。

②二叉树是有序树，每个结点最多有两棵子树，树是无序树，且每个结点可以有多棵子树。

A（2）对于图 4-37 所示二叉树，试给出： 1）它的顺序存储结构示意图；BC2）它的二叉链表存储结构示意图； 3）它的三叉链表存储结构示意图。

DEF【解答】 1）顺序存储结构示意图：AB CDEF ^ ^ ^ G^ ^ HGH(图 4-37)2）二叉链表存储结构示意图：3）三叉链表存储结构示意图：ABC^^D^E^ ^ F^G^^H^A^BC^^ D^E^^F^ G^^ H^（3）对于图 4-38 所示的树，试给出： 1）双亲数组表示法示意图； 2）孩子链表表示法示意图； 3）孩子兄弟链表表示法示意图。

ABCGFEDIHJKMN(图 4-38)【解答】 1）双亲数组表示法示意图：2）孩子链表表示法示意图：0 A -1 1 B0 2 C0 3 D2 4 E2 5F1 6 G1 7 H5 8I 2 9J 4 10 K 4 11 M 3 12 N 83）孩子兄弟链表表示法示意图：0A 1B 2C 3D 4E 5F 6G 7H 8I 9J 10 K 11 M 12 N12^56^348^11 ^ 910 ^7^12 ^ABC^^GFEDI^^ H^^J^ K^ ^ M^ ^ N^（4）画出图 4-39 所示的森林经转换后所对应的二叉树，并指出森林中满足什么条件的 结点在二叉树中是叶子。

计算机考研数据结构试卷四（练习题含答案）（PS：其他正在整理，敬请期待）数据结构试卷4一、选择题1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。

(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n2)2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。

kk-1k(A)2k-1(B)2(C)2(D)2-13．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。

(A)n(B)e(C)2n(D)2e4．在二叉排序树中插入一个结点的时间复杂度为（）。

2(A)O(1)(B)O(n)(C)O(log2n)(D)O(n)5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。

(A)n(B)n-1(C)m(D)m-16．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。

(A)3(B)4(C)5(D)87．设用链表作为栈的存储结构则退栈操作（）。

(A)必须判别栈是否为满(B)必须判别栈是否为空(C)判别栈元素的类型(D)对栈不作任何判别8．下列四种排序中（）的空间复杂度最大。

(A)快速排序(B)冒泡排序(C)希尔排序(D)堆9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。

(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素某的最多比较次数不超过（）。

(A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1)二、填空题1．设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。

2．设指针变量p指向双向循环链表中的结点某，则删除结点某需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。

考研真题精选一、选择题1．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2 若串S1=‘ABCDEFG’, S2=‘9898’,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（）A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345E．ABC###G1234 F．ABCD###1234 G．ABC###012343．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串B．联接C．匹配D．求串长4．已知串S=‘aaab’,其next数组值为（）。

A．0123 B．1123 C．1231 D．12115．串‘ababaaababaa’的next数组为（）。

A．012345678999 B．012121111212 C．011234223456 D．0123012322345 6．字符串‘ababaabab’的nextval 为（）A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 )7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval数组的值为（）。

A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 18．若串S=’software’,其子串的数目是（）。

第4章串1．采用顺序结构存储串，编写一个实现串通配符匹配的算法pattern______index（），其中的通配符只有“？”，它可以和任一字符匹配成功，例如，pattern______index（″? re″，″there are″）返回的结果是2。

答：本题的基础是Brute—Force模式匹配算法，只是增加了“？”的处理功能。

对应的算法如下：2．有两个串s1和s2，设计一个算法求这样一个串，该串中的字符是s1和s2中的公共字符。

答：扫描s1，对于当前字符s1.data[i]，若在s2中，则将其加入到串s3中。

最后返回s3串。

对应的算法如下：3．设目标为t=’abcaabbabcabaacbacba’，模式p=’abcabaa’。

（1）计算模式P的nextval函数值。

（2）不写算法，只画出利用KMP算法进行模式匹配时的每一趟匹配过程。

答：（1）先计算next数组，在此基础上求nextval数组，如表4-1所示。

表4-1 计算next数组和nextval数组（2）采用KMP算法求子串位置的过程如下（开始时i=0，j=0）：第1趟匹配：此时i=4，j=4，匹配失败，而nextval[4]=0，则i=4，j=nextval[4]=0，即：第2趟匹配：此时i=6，j=2，匹配失败，而nextval[2]=0，则i=6，j=nextval[2]=0，即：第3趟匹配：此时i=6，j=0，匹配失败，而nextval[0]=-1，则i=6，j=nextval[0]=-1。

因j=-1，执行i=i+1=7，j=j+1=0，即：第4趟匹配：此时i=14，j=7，匹配成功，返回v=i-t．1ength=14-7=7。

上机实验题4实验题1编写一个程序algo4-1.cpp，实现顺序串的各种基本运算，并在此基础上设计一个程序exp4-1.cpp完成如下功能：（1）建立串s=″abcdefghefghijklmn″和串sl=″xyz″；（2）输出串s；（3）输出串s的长度；（4）在串s的第9个字符位置插入串s1而产生串s2；（5）输出串s2；（6）删除串s第2个字符开始的5个字符而产生串s2；（7）输出串s2；（8）将串s第2个字符开始的5个字符替换成串s1而产生串s2；（9）输出串s2；（10）提取串s的第2个字符开始的10个字符而产生串s3；（11）输出串s3；（12）将串s1和串s2连接起来而产生串s4；（13）输出串s4。

第4章习题解答一、填空1.字符串是一种特殊的线性表，特殊在于它的数据元素只能是一字符,特殊在于串可以作为一个__________ 参与所需要的处理。

2.空格串是由___ 组成的串，空串是_________ 的串，因此空格串和空串不是一个概念。

3.字符串中任意多个_______ 字符所组成的子序列，被称作是这个串的“子串”，这个字符串木身则称为“主串”。

4.我们说两个字符串相等，在计算机内部实际上是通过对相应位置上字符__________ 码的比较而得到的结论。

5.设有串s=<t I am a teacher"。

该串的长度是_________ 。

6.设有三个串：sl=“Good", s2=9', s3=“bye!''。

则si、s2、s3连接后的结果串应该是7.所谓“数组”，是指〃(H>1)个具有」业L类型的数据的有序集合。

8.矩阵与通常所说的[维数组冇关。

9.所谓“特殊矩阵”,是指那些元素在矩阵小的分布具有一定规律性的矩阵；而矩阵小的零元素个数远远多于非零元素的个数，但非零元素的分布却没有规律，这样的矩阵被称为“稀疏矩阵”。

10.在一个阶方阵A中，若所有元素都有性质：= n),就称其为对称矩阵。

二、选择1 •设有两个串si和s20求s2在si中首次出现的位置的操作称为__________ oA.连接B.模式匹配C.求了串D.求串长2・有串：“①"，那么它的长度是____ oA. 0B. 1C. 2D. 33.设有串sl=“ABCDEFG'和s2=“PQRSF'。

已知:算法con(x, y)返回串x和y的连接串；subs(s, i, j)返回串s的第i个字符开始往后j个字符组成的子串；len(s)返回串s的长度。

那么，con(subs(sl, 2, len(s2)), subs(sl, len(s2), 2))的操作结果是串__________ 。

第四章串一单项选择题：1．下列那些为空串（）A）S=“ ” B）S=“”C）S=“φ” D）S=“θ”2．S1=“ABCD”，S2=“CD”则S2在S3中的位置是（）A）1 B）2 C）3D）43.假设S=“abcaabcaaabca”，T=“bca”，Index (S,T,3) 的结果是（）A）2 B）6 C）11 D）04.在串中，对于SubString(&Sub,S,pos,len)基本操作，pos和len的约束条件是（）A）0<pos<StrLength(S)+1且1<=len<=StrLength(S)-pos+1B）0<pos<StrLength(S)+1且0<=len<=StrLength(S)-pos-1C）1<=pos<=StrLength(S) 且0<=len<=StrLength(S)-pos+1D）1<=pos<=StrLength(S) 且1<=len<=StrLength(S)-pos-15. 串是一种特殊的线性表，其特殊性体现在( )。

A．可以顺序存储B. 数据元素是一个字符C．可以链接存储D. 数据元素可以是多个字符6. 串是( )。

A．少于一个字母的序列B. 任意个字母的序列C．不少于一个字符的序列D. 有限个字符的序列7. 串的长度是( )。

A．串中不同字母的个数B. 串中不同字符的个数C．串中所含的字符的个数D. 串中所含字符的个数，且大于08. 设有S1=‘ABCDEFG’，S2=‘PQRST’，函数con(x，y)返回x和y串的连接串，subs(I，j)返回串S的从序号I的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(S1，2，len(S2))，subs(S1，len(S2)，2))的结果是( )。

A．BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF9. 若某串的长度小于一个常数，则采用( )存储方式最为节省空间。

《数据结构与算法》第四章串知识点及例题精选串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成。

4.1 串及其基本运算4.1.1 串的基本概念１．串的定义串是由零个或多个任意字符组成的字符序列。

一般记作：s=＂s1 s2 … s n＂＂其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；a i(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。

２．几个术语子串与主串：串中任意连续的字符组成的子序列称为该串的子串。

包含子串的串相应地称为主串。

子串的位置：子串的第一个字符在主串中的序号称为子串的位置。

串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。

4.2 串的定长顺序存储及基本运算因为串是数据元素类型为字符型的线性表，所以线性表的存储方式仍适用于串，也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。

4.2.1 串的定长顺序存储类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：#define MAXSIZE 256char s[MAXSIZE];则串的最大长度不能超过256。

如何标识实际长度？1. 类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedef struct{ char data[MAXSIZE];int curlen;} SeqString;定义一个串变量：SeqString s;这种存储方式可以直接得到串的长度：s.curlen+1。

如图4.1所示。

s.dataMAXSIZE-1图4.1 串的顺序存储方式12. 在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。