发布时间 : 星期三 文章1数据结构习题及参考答案更新完毕开始阅读b9320a082cc58bd63086bd2d
指针指向当前队尾元素的位置）
6)设有一个顺序共享栈S[0；n-1]，其中第一个栈项指针top 1 的初值为-1，第二个栈顶指针top2 的初值为n，则判断共享栈满的条件是______________
7)设F和R分别表示顺序循环队列指针和尾指针，则判断该循环队列为空的条件为_______________
8)顺序循环队列判空的条件是（使用front,rear,n表示）_________ 9)顺序循环队列判满的条件是（使用front,rear,n表示）_________ 10)顺序循环队列MAXSIZE=N，最多可以存储____________元素 习题3参考答案 3.1.选择题
(1). D (2). C (3). D (4). C (5). B (6). C (7). C (8). C (9). B (10).AB
(11). D (12). B (13). D (14). C (15). C (16). D(17). B (18). C (19). C (20). C 3.2.填空题
（1） FILO, FIFO
（2） -1, 3 4 X * + 2 Y * 3 / -
（3） stack.top++, stack.s[stack.top]=x
（4） p>llink->rlink=p->rlink, p->rlink->llink=p->rlink （5） (R-F+M)%M （6） top1+1=top2 （7） F==R
（8） front==rear
（9） front==(rear+1)%n （10） N-1
习题4 4.1 选择题
（1）如下陈述中正确的是______。
A.串是一种特殊的线性表 B.串的长度必须大于零 C.串中的元素只能是字母 D.空串就是空白串 （2） 下列关于串的叙述中，正确的是______。 A.串长度是指串中不同字符的个数 B.串是n个字母有序数列
C.如果两个串含有相同的字符，则它们相等
D.只有当两个串的长度相等，并且各个对应位置的字符都相符是串才相等 （3） 字符串的长度是指______。
A.串中不同字符的个数 B.串中不同字母的个数 C.串中所含字符的个数 D.串中不同数字的个数 (4) 两个字符串长度相等的充要条件是______。
A.两个字符串长度相等 B.两个字符串中对应位置上的字符相等 C.同时具备（A）和（B）D.以上答案都不对
（5） 串是一种特殊的线性表，其特殊性体现在______。 A.可以顺序存储 B.数据元素是一个字符 C.可以连接存储 D.数据元素可以是多个字符
（6）设有两个串p和q，求q在p中首次出现的位置的运算称为______。
A.链接B.模式匹配C.求子串D.求串长
（7）设串sI=“ABCDEFG”,S2=“PQRST”,函数con(X,Y)返回X和Y串的连接串，subs（s,I,j）返回串s的从序号i的字符开始的j个字符组成的字串，len(s)返回串s的长度，则con(subs(sI,2,len(s2)),2的结果串是______。 A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF
（8）函数substr(“DATASTRUCTURE”,5,9)的返回值为______。 A.“STRUCTURE” B.“DATA”
C.“ASTRUCTUR” D.“DATASTRUCTURE” (9) 常对数组进行的两种基本操作是______。 A.建立与删除 B.索引与修改 C.查找与修改 D.查找与索引
（10） 设串S= “IAMATEACHER!”,其长度是______。 A.16 B.11 C.14 D.15 4.2 填空题
（1）两个串相等的充要条件是__________________。 （2）空串是______，其长度为______。 （3）空格串是______，其长度是______。 （4）s=“I am a men”长度为______。 （5）s1=“hello”，s2=“boy”,s1,s2连接后为______。 （6）s=“this is the main string”，sub= “string”,strindex(s,sub)是（7）int a[10][10],已知a=1000，sizeof(int)=2,求a[3][3]地址＿＿（8）设有两个串p和q，求q和p中首次出现的位置的运算称为______________ 。
（9）串的长度是指：________________________。
（10）s=“xiaotech”所含字串的个数是________________。
习题4参考答案 4.1 选择题：
(1). A (2). D (3). C (4). C (5). B (6). B (7). D (8). A (9). B (10). D 4.2 填空题：
（1） 串长相等且对应位置字符相等 （2） 不含任何元素的串，0
（3） 所含字符均是空格，所含空格数 （4） 10
（5） “helloboy” （6） 18 （7） 1066
（8） 由零个或多个任意字符组成的字符序列 （9） 串中所含不同字符的个数 （10） 36 第五章 一、选择题
1.树最适合用来表示（）。
A. 有序数据元素 B. 无序数据元素
C. 元素间具有分层次关系的数据 D. 元素间无联系的数据 2.在m叉树中，度为0的结点称为（）。
A. 兄弟 B. 树叶 C. 树根 D. 分支结点
3.如果树的结点A有4个兄弟，而且B为A的双亲，则B的度为（）。 A. 3 B. 4 C. 5 D. 1
4.根据二叉树的定义可知二叉树共有（）种不同的形态。 A. 4 B. 5 C. 6 D. 7
5.由3个结点可以构造出（）种不同形态的二叉树。 A. 3 B. 4 C. 5 D. 6 6.具有20个结点的二叉树，其深度最多为（）。 A. 4 B. 5 C. 6 D. 20 7.高度为h的满二叉树的结点数是（）个。 A. log2h+1 B. 2h+1 C. 2h-1 D. 2h-1 8.深度为5的二叉树至多有（）个据点。
A. 16 B. 32 C. 31 D. 10 9.设一颗二叉树共有50发业主据点（终端据点），则共有（）个度为2的结点。 A. 25 B. 49 C. 50 D. 51 10.一颗二叉树中根结点的编号为1，而且23好结点有左孩子但没有右孩子，则完全二叉树总共有（）个结点。
A. 24 B. 45 C. 46 D. 47 11.二叉树的第3层最少有（）个结点。
A. 0 B. 1 C. 2 D. 3
12.设n、m为一颗二叉树上的俩个结点，在中序遍历时，n在m之前的条件是（）。 A. n在m的右方 B. n是m祖先 C. n在m的左方 D. n是m子孙
13.某二叉树的先序序列和后序序列正好相反，则该二叉树可能是（）的二叉树。 A. 高度大于1的左单支 B. 高度大于1的右单支 C. 最多只有一个结点 D. 既有左孩子又有右孩子
14..某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A. 空或只有一个结点 B, 高度等于其结点数 C. 任一结点无左孩子 D. 任一结点无右孩子 15.有n个结点的二叉树链共有（）个空指针域。 A. n-1 B. n C. n+1 D. n+2 二、填空题
1. 一颗深度为5的二叉树，至少有 1 个叶子结点。
2.一颗完全二叉树采用顺序存储结构，每个结点占4字节，设编号为5的元素地址为 1016，且它有左孩子和右孩子，则该左孩子和右孩子的地址分别为 1036 和 1040 。 3.一颗完全二叉树采用顺序存储结构，若编号为i的元素左孩子，则该左孩子的编号为
2i 。
4.一颗含有n(n>1)个结点的K叉树，当k= 1 时深度最大，此最大深度为 n ； 当k= n-1 时深度最小，此最小深度为 2 。
k-1k
5.深度为K的完全二叉树至少有 2 个结点，至多有 2-1 个结点。
6.已知一颗二叉树的先序遍历序列为EBADCFHGIKJ，中序遍历序列为ABCDEFGHIJK， 则该二叉树的后序遍历序列为 ACDBGJKIHFE 。
7.如果指针p指向一颗二叉树的一个结点，则判断p没有左孩子的逻辑表达式为p!=NULL。
8.在由n个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为Huffman树 。
9.在树的孩子兄弟表示法中，每个结点有俩个指针域，一个指向 其第一个孩子；另一个指向
下一个兄弟 。
10.树的先根遍历结果与其转换的相应二叉树的 先序遍历 结果相同；树的后根遍历结果与其转换的相应二叉树的 中序遍历 结果相同。 习题5参考答案 5.1 选择
（1）C（2）B（3）C（4）B（5）C（6）D（7）C（8）C（9）B（10）C （11）B（12）C（13）C（14）C（15）C
5.2 填空 （1）1
（2）1036；1040 （3）2i
（4） 1 ； n ; n-1 ; 2
k-1k
（5）2；2-1 （6）ACDBGJKIHFE （7）p!=NULL （8）Huffman树
（9）其第一个孩子; 下一个兄弟 （10）先序遍历；中序遍历
6.1 选择题
（1）一个有8个顶点的有向图，所有顶点的入度之和与所有顶点的初读之和的差是（）。 A. 16 B. 4 C. 0 D. 2 (2)一个有n个顶点的连通无向图至少有（）条边。 A. n-1 B.n C.n+1 D. n+2 (3)具有n个顶点的完全有向图的弧数为（）。
A. n(n-1) /2 B. n(n-1) C. n^2 D. n^2-1 (4)一个n 条边的连通无向图.其顶点的个数至多为（）。 A. n-1 B. n C. n+1 D. n+2 （5）设无向图的顶点个数为n，则该图最多有（）条边。
A. n-1 B.n（n-1）/2 C. n（n+1）/2 D. 0 (6)任何一个无向连通图的最小生成树（）。
A. 只有一颗 B. 有一颗或多颗 C. 一定有多颗 D.可能不存在 （7）下列算法中，（）算法用来球图中某顶点到其他所有顶点之间的最短路径。 A.Dijkstra B.Floyed C.Prim D.Kruskal (8)在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A. 2 B. 3 C. 1 D. 1.5 （9）下面关于图的存储的叙述中正确的是（）。
A. 用邻接表法储存图，占用的存储空间大小只与图中边数有关，而与顶点个数无关 B. 用邻接表法储存图，占用的存储空间大小与图中边数喝顶点个数都有关