发布时间 : 星期二 文章数据结构习题1更新完毕开始阅读0c9897303968011ca30091a9
3、已知Fibonacci数列的递归定义如下： 0??fib(n)??1?fib(n?1)?fib(n?2)?试写出求解fib(n)的递归算法。
n?0n?1n?1Int fibonacci(int n) { if(n= =0||n= =1)
fib=n;
else
fib=fibonacci(n-1)+fibonacci(n-2); return(fib); }
习
一、选择题：
题四
1、串是一种特殊的线性表，其特殊性体现在_____。 A、可以顺序存储 B、数据元素是一个字符
C、可以链接存储 D、数据元素可以是多个字符
2、设有两个串p 和q，求p 在q中首次出现的位置的运算称作 。 A、连接 B、求子串 C、模式匹配 D、求串长
3、串是任意有限个
A、符号构成的集合 B、符号构成的序列 C、字符构成的集合 D、字符构成的序列
4、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如图所示）按行序存放在一维数组B[1..n(n-1)/2]中，对下三角部分中任一个元素aij(ij)在一维数组B的下标位置k值是_____。
A、I(I-1)/2+j-1 B、I(I-1)/2+j C、I(I+1)/2+j-1 D、I(I+1)/2+j ?a11?a21a22?A???????an1an2?二、填空题：
?????ann?1、两个字符串相等的充分必要条件是_____。
2、字符在串中的位置，即是字符在该序列中的_____。
3、设有串S1=’I an a student’,S2=’st’,其index(S1,S2)= _____。 4、串是指_____。
5、含零个字符的串称为_____串，用_____表示；其他串称为_____串。任何串中所含_____的_____个数称为该串的长度。
6、一个串中任意个连续字符组成的子序列称为该串的_____串，该串称为它的所有子串的_____串。
7、广义表（a,(a,b),d,e,((I,j),k)）的长度是_____，深度是_____。 8、设数组a[50][80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45][68]的存储地址为_____；若以列序为主序存储，则元素a[45][68]的存储地址为
28
_____。
9、三维数组a[4][5][6]（下标从0开始计，a有4×5×6个元素），每个元素的长度是2，则a[2][3][4]的地址是_____。（设a[0][0][0]的地址是1000，数据以行为主序方式存储） 参考答案：
一、 选择题
1、B 2、C 3、D 4、B 二、 填空题：
1、长度相同且对应位置上的字符相同 2、序号 3 、8 4、含n个字符的有限序列且n≥0 5、空 ф 非空 字符 6、子 主 7、5 3 8、9174 8788 9、1164 三、
算法设计： Void reverse(char a[]) { char ch; int I; I=1;
do
{ scanf(“%c”,ch);
reverse(a);
a[I]=ch; I++;
}while(ch!=’#’&&I 2、试设计一算法测试一个串T的值是否为回文（即从左向右读出的内容与从右向左读出的内容一样）。 Int invert(char t[ ]) {int I,j; j=length(t)/2; for(I=0;I if(substr(t,I,1)!=substr(t,leng(t)-I+1,1) return (0); else return(1); } 1、 一个递归算法来实现字符串逆序存储，要求不另设串存储空间。 习 一、选择题 题五 1、一棵有n个结点的二叉树，按层次从上到下，同一层从左到右的顺序存储在一维数组A[n]中，则二叉树中第I个结点（I从1开始用上述方法编号）的右孩子在数组A中的位置是_____。 A、A[2I] (2I≤n) B、A[2I+1] (2I+1≤n) C、A[i/2] D、条件不充分，无法确定 2、将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是_____。 A、4 B、5 C、6 D、7 3、下列有关二叉树的说法正确的是_____。 29 A、二叉树的度为2 B、一棵二叉树度可以小于2 C、二叉树中至少有一个结点的度为2 D、 二叉树中任一个结点的度都为2 4、某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是_____。 A、EGFACDB B、EACBDGF C、EAGCFBD D、上面的都不对 5、设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中第一棵树的结点个数是_____。 A、m-n B、m-n-1 C、n+1 D、条件不充分，无法确定。 6、对二叉排序树进行_____遍历，可以得到该二叉树所有结点构成的排序序列。 A、前序 B、中序 C、后序 D、按层次 7、_____的遍历仍需要栈的支持 A、前序线索树 B、中序线索树 C、后序线索树 8、在一棵深度为h的完全二叉树中，所含结点的个数不小于_____。 2h 2h+1 2h-1 2h-1 9、在一棵具有n个结点的二叉树第I层上，最多具有_____个结点。 2I 2I+1 2I-1 2n 10、在下列情况中，可称为二叉树的是_____。 A、每个结点至多有两棵子树的树 B、哈夫曼树 C、每个结点至多有两棵子树的有序树 D、每个结点只有一棵右子树 11、树最适合用来表示_____ A、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据 12、以下说法错误的是_____。 A、一般在哈夫曼树中，权值越大的叶子离根结点越近 B、哈夫曼树中没有度数为1的分支结点 C、若初始森林中共有n棵二叉树，最终求得的哈夫曼树中共有2n-1个结点 D、若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下最终的哈夫曼树 13、以下说法错误的是_____。 A、二叉树可以是空集 B、二叉树的任一结点都可以有两棵子树 C、二叉树与树具有相同的树形结构 D、二叉树中任一结点的两棵子树有次序之分 14、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是_____的二叉树。 A、空或只有一个结点 B、任一结点无左子树 C、高度等于其结点数 D、任一结点无右子树 二、填空题 1、如果结点A有3兄弟，而且B是A的双亲，则B的度是_____。 2、高度为h的二叉树中叶子结点的数目至多为_____。 3、具有n个结点的二叉树，采用二叉链表存储，共有_____个空链域。 4、利用树的孩子兄弟表示法存储，可以将一棵树转换成_____。 5、二叉树的线索化实质是将二叉链表中的_____改为_____。 6、在一棵树中，_____结点没有前驱结点，其余每个结点有且只有一个_____，可以有任意多个_____结点。 7、二叉树有不同的链式存储结构，其中最常用的是_____与_____。 8、对于一棵完全二叉树，设一个结点的编号为I,若它的左孩子结点存在，则其编号为_____；若右孩子结点存在，则其编号为_____；而双亲结点的编号为_____。 30 9、对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为_____个，其中_____个用于指向孩子结点，_____个指针空闲着。 10、一棵左右子树均不空的二叉树在先序线索化后，其空指针域有_____个。 11、用一维数组存放一棵完全二叉树：ABCDEFGHIJKL,则后序遍历该二叉树的结点序列为_____。 12、深度为k的完全二叉树，其前k-1层共有_____个结点。 13、对任何二叉树，若度为2的结点数为n2，则叶子数n0=_____。 14、具有n个结点的完全二叉树若按层次从上到下，从左到右对其编号（根结点为1），则编号最大的分支结点序号是_____，编号最小的分支结点序号是_____，编号最大的叶子结点序号是_____，编号最小的叶子结点序号是_____。 15、结点最少的树为_____，结点最少的二叉树为_____。 16、若二叉树的一个叶子结点是某子树中根遍历序列中的第一个结点，则它必然是该子树后根遍历序列中的_____个结点。 17、二叉树通常有_____存储结构和_____存储结构。 18、哈夫曼树是带权路径长度_____的树，通常权值较大的结点离根_____。 参考答案： 一、 选择题 1、D 2、C 3、B 4、B 5、A 6、B 7、C 8、D 9、C 10、B 11、C 12、D 13、C 14、D 二、 填空题 1、4 2、2h-1 3、n+1 4、一棵二叉树 5、空指针域 存放该结点的前驱或后继信息 6、树根 双亲（或前驱） 孩子（或后继） 7、二叉链表 三叉链表 8、2i 2i+1 [i/2] 9、2n n-1 n+1 10、0 11、HIDJKEBLFGCA 12、2k-1-1 13、n2+1 14、[n/2] 1 n [n/2]+1 15、只有根结点的树 空二叉树 16、第一 17、顺序 链式 18、最短 较近 三、算法设计： 1、设某通讯电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数分别是16、5、9、3、30、1。试画出编码用的哈夫曼树 2、给定一棵用链表表示的二叉树，其根结点为root，试写出二叉树结点数目的算法。 int count(TREENODEPTR root) {int top ,num; TREENODEPTR stack[max]; Num=0; If(root!=NULL) {top=1; stack[top]=root; while(top>0) { top--; num++; if(root->rchild!=NULL) { top++; stack[top]=root->rchild; } 31