数据结构试题库集及答案

导读:第4~5章串和数组自测卷答案,它包含有三个数据项,A.可以顺序存储B.数据元素是一个字符,C.可以链式存储D.数据元素可以是多个字符,A.16902B.16904C.14454D.答案A,B,C均不对,供选择的答案:,答案:ABCDE=8,3,5,1,6,答案:ABCD=12,10,3,9,(√)1.若二叉树用二叉链表作存贮结构,教材答案是“完全k叉树”,(C)2.二叉树是非线性数据结构,(A

数据结构试题库集及答案

4.设循环队列的容量为40(序号从0到39),现经过一系列的入队和出队运算后,有

① front=11,rear=19; ② front=19,rear=11;问在这两种情况下,循环队列中各有元素多少个?

答:用队列长度计算公式: (N+r-f)% N

① L=(40+19-11)% 40=8 ② L=(40+11-19)% 40=32

第4~5章串和数组自测卷答案

一、填空题(每空1分,共20分)

1. 称为空串;称为空白串。

(对应严题集4.1①,简答题:简述空串和空格串的区别)

2. 设S=“A;/document/Mary.doc”,则strlen(s)=, “/”的字符定位的位置为。

4. 子串的定位运算称为串的模式匹配;被匹配的主串称为目标串,子串称为模式。

5. 设目标T=”abccdcdccbaa”,模式P=“cdcc”,则第次匹配成功。

6. 若n为主串长,m为子串长,则串的古典(朴素)匹配算法最坏的情况下需要比较字符的总次数为。

7. 假设有二维数组A6×8,每个元素用相邻的6个字节存储,存储器按字节编址。已知A的起始存储位置(基地址)为1000,则数组A的体积(存储量)为;末尾元素A57的第一个字节地址为1282 ;若按行存储时,元素A14的第一个字节地址为(8+4)×6+1000=1072;若按列存储时,元素A47的第一个字节地址为(6×7+4)×6+1000)=

(注:数组是从0行0列还是从1行1列计算起呢?由末单元为A57可知,是从0行0列开始!)

8.设数组a[1?60, 1?70]的基地址为2048,每个元素占2个存储单元,若以列序为主序顺序存储,则元素a[32,58]的存储地址为8950。

答:不考虑0行0列,利用列优先公式:LOC(aij)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L

得:LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2=8950

9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素

的行下标、列下标和元素值。

10.求下列广义表操作的结果:

(1)GetHead【((a,b),(c,d))】===(a, b); //头元素不必加括号

(2)GetHead【GetTail【((a,b),(c,d))】】===(c,d);

(3)GetHead【GetTail【GetHead【((a,b),(c,d))】】】===b;

(4)GetTail【GetHead【GetTail【((a,b),(c,d))】】】===(d);

二、单选题(每小题1分,共15分)

(B)1.串是一种特殊的线性表,其特殊性体现在:

A.可以顺序存储B.数据元素是一个字符

C.可以链式存储D.数据元素可以是多个字符

(B)2.设有两个串p和q,求q在p中首次出现的位置的运算称作:

A.连接B.模式匹配C.求子串D.求串长

(D )3.设串s1=?ABCDEFG?,s2=?PQRST?,函数con(x,y)返回x和y串的连接串,subs(s,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.BCDEFEF

解:con(x,y)返回x和y串的连接串,即con(x,y)=‘ABCDEFGPQRST’;

subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串,则

subs(s1,2,len(s2))=subs(s1,2, 5)=? BCDEF?; subs(s1,len(s2),2)=subs(s1,5, 2)=? EF?;

所以con(subs(s1,2,len(s2)),subs(s1,len(s2),2))=con(? BCDEF?, ? EF?)之连接,即BCDEFEF

(A )4.假设有60行70列的二维数组a[1?60, 1?70]以列序为主序顺序存储,其基地址为10000,每个元素占2个存储单元,那么第32行第58列的元素a[32,58]的存储地址为。(无第0行第0列元素)

A.16902 B.16904 C.14454 D.答案A, B, C均不对

答:此题与填空题第8小题相似。(57列×60行+31行)×2字节+10000=16902

( B )5. 设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分(如下图所示)按行序存放在一维数组B[ 1, n(n-

1)/2 ]中,对下三角部分中任一元素ai,j(i≤j),在一维数组B中下标k的值是:

A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j

?a1,1?a2,1A???????an,1a2,2an,2??????an,n??

6.

有一个二维数组A,行下标的范围是0到8,列下标的范围是1到5,每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。

存储数组A的最后一个元素的第一个字节的地址是 A 。若按行存储,则A[3,5]和A[5,3]的第一个字节的地址分别是

和。若按列存储,则A[7,1]和A[2,4]的第一个字节的地址分别是。

供选择的答案:

A~E:①28 ② 44 ③ 76 ④ 92 ⑤ 108

⑥ 116 ⑦ 132 ⑧ 176 ⑨ 184 ⑩ 188

答案:ABCDE=8, 3, 5, 1, 6

7. 有一个二维数组A,行下标的范围是1到6,列下标的范围是0到7,每个数组元素用相邻的6个字节存储,存储器按字节编址。那么,这个数组的体积是 A 个字节。假设存储数组元素A[1,0]的第一个字节的地址是0,则存储数组A的最后一个元素的第一个字节的地址是 B 。若按行存储,则A[2,4]的第一个字节的地址是 C 。若按列存储,则A[5,7]的第一个字节的地址是

供选择的答案

A~D:①12 ② 66 ③ 72 ④ 96 ⑤ 114 ⑥ 120

⑦ 156 ⑧ 234 ⑨ 276 ⑩ 282 (11)283 (12)288

答案:ABCD=12, 10, 3, 9

第6章树和二叉树自测卷解答

一、下面是有关二叉树的叙述,请判断正误(每小题1分,共10分)

(√)1. 若二叉树用二叉链表作存贮结构,则在n个结点的二叉树链表中只有n—1个非空指针域。

(×)2.二叉树中每个结点的两棵子树的高度差等于1。

(√)3.二叉树中每个结点的两棵子树是有序的。

(×)4.二叉树中每个结点有两棵非空子树或有两棵空子树。

(×)5.二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值,且小于其右非空子树

(若存在的话)所有结点的关键字值。(应当是二叉排序树的特点)

k-1(×)6.二叉树中所有结点个数是2-1,其中k是树的深度。(应2i-1)

(×)7.二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。

(×)8.对于一棵非空二叉树,它的根结点作为第一层,则它的第i层上最多能有2i—1个结点。(应2i-1)

(√)9.用二叉链表法(link-rlink)存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。

(正确。用二叉链表存储包含n个结点的二叉树,结点共有2n个链域。由于二叉树中,除根结点外,每一个结点有且仅有一个双亲,所以只有n-1个结点的链域存放指向非空子女结点的指针,还有n+1个空指针。)即有后继链接的指针仅n-1个。

(√)10.具有12个结点的完全二叉树有5个度为2的结点。

最快方法:用叶子数=[n/2]=6,再求n2=n0-1=5

二、填空(每空1分,共15分)

1.由3个结点所构成的二叉树有种形态。

2. 一棵深度为6的满二叉树有6-1个叶子。

注:满二叉树没有度为1

3.一棵具有257个结点的完全二叉树,它的深度为。

(注:用? log2(n) ?+1= ? 8.xx ?+1=9

4. 设一棵完全二叉树有700个结点,则共有个叶子结点。

答:最快方法:用叶子数=[n/2]=350

5. 设一棵完全二叉树具有1000个结点,则此完全二叉树有个叶子结点,有个度为2的结点,有个结点只有非空左子树,有0个结点只有非空右子树。

答:最快方法:用叶子数=[n/2]=500,n2=n0-1=499。另外,最后一结点为2i属于左叶子,右叶子是空的,所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况,所以非空右子树数=0.

6.一棵含有n个结点的k叉树,可能达到的最大深度为,最小深度为。

答:当k=1(单叉树)时应该最深,深度=n(层);当k=n-1(n-1叉树)时应该最浅,深度=2(层),但不包括n=0或1时的特例情况。教材答案是“完全k叉树”,未定量。)

7.二叉树的基本组成部分是:根(D)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种:前序法(即按N L R次序),后序法(即按L R D次序)和中序法(也称对称序法,即按L N R次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是F E G H D C 。解:法1:先由已知条件画图,再后序遍历得到结果;

法2:不画图也能快速得出后序序列,只要找到根的位置特征。由

前序先确定root,由中序先确定左子树。例如,前序遍历BEFCGDH

中,根结点在最前面,是B;则后序遍历中B一定在最后面。

法3:递归计算。如B在前序序列中第一,中序中在中间(可知左

右子树上有哪些元素),则在后序中必为最后。如法对B的左右子树同

样处理,则问题得解。

8.中序遍历的递归算法平均空间复杂度为O(n)。

答:即递归最大嵌套层数,即栈的占用单元数。精确值应为树的深度

k+1,包括叶子的空域也递归了一次。

9.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是。

解:先构造哈夫曼树,得到各叶子的路径长度之后便可求出WPL=(4+5+3)×2+(1+2)×3=33

(注:两个合并值先后不同会导致编码不同,即哈夫曼编码不唯一)

3 (注:合并值应排在叶子值之后)

1 2

(注:原题为选择题:A.32 B.33 C.34 D.15)

三、单项选择题(每小题1分,共11分)

(C)1.不含任何结点的空树。

(A)是一棵树;(B)是一棵二叉树;

(C)是一棵树也是一棵二叉树;(D)既不是树也不是二叉树

答:以前的标答是B,因为那时树的定义是n≥1

(C)2.二叉树是非线性数据结构,所以。

(A)它不能用顺序存储结构存储;(B)它不能用链式存储结构存储;

(C)顺序存储结构和链式存储结构都能存储;(D)顺序存储结构和链式存储结构都不能使用

( C)3. 具有n(n>0)个结点的完全二叉树的深度为。

(A) ?log2(n)?(B) ? log2(n)?(C) ? log2(n) ?+1(D) ?log2(n)+1?

注1:?x?表示不小于x的最小整数;?x?表示不大于x的最大整数,它们与[ ]含义不同!

注2:选(A)是错误的。例如当n为2的整数幂时就会少算一层。似乎? log2(n) +1?是对的?

(A)4.把一棵树转换为二叉树后,这棵二叉树的形态是。

(A)唯一的(B)有多种

(C)有多种,但根结点都没有左孩子(D)有多种,但根结点都没有右孩子

5.

树是结点的有限集合,它A 根结点,记为T。其余的结点分成为m(m≥0)个 B

的集合T1,T2,?,Tm,每个集合又都是树,此时结点T称为Ti的父结点,Ti称为T的子结点(1≤i≤m)。一个结点的子结点个数为该结点的 C 。

供选择的答案

A:①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上

B: ①互不相交 ②允许相交③允许叶结点相交④允许树枝结点相交

C:①权 ②维数③次数(或度)④序

答案:ABC=1,1,3

6.

二叉树 A 。在完全的二叉树中,若一个结点没有 B ,则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里,一个结点N的左子女是N在原树里对应结点的 C ,而N的右子女是它在原树里对应结点的 D 。

供选择的答案

A:①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树形结构

B: ①左子结点②右子结点③左子结点或者没有右子结点④兄弟

C~D:①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟

⑤最左的兄弟⑥最右的兄弟

答案:A= B= C= D=

答案:ABCDE=2,1,1,3

四、简答题(每小题4分,共20分)

1. 一棵度为2的树与一棵二叉树有何区别?

答:度为2的树从形式上看与二叉树很相似,但它的子树是无序的,而二叉树是有序的。即,在一般树中若某结点只有一个孩子,就无需区分其左右次序,而在二叉树中即使是一个孩子也有左右之分。

2.给定二叉树的两种遍历序列,分别是:

前序遍历序列:D,A,C,E,B,H,F,G,I;中序遍历序列:D,C,B,E,H,A,G,I,F,

试画出二叉树B,并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

解:方法是:由前序先确定root,由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合,可继续确定root的左右孩子。将他们分别作为新的root,不断递归,则所有元素都将被唯一确定,问题得解。

D A

F

G

B H I

下面是按先序遍历的思路建立二叉树的两种方法

#include <stdio.h>

#include <stdlib.h>

#define MAX 100

typedef struct node {

char data;

struct node *lchild, *rchild;

} Bitree;

void creatree1( Bitree *&bt)

{ char ch;

if (ch==??) bt=NULL

else

{ bt=(Bitree*)malloc(sizeof(Bitree));

bt-data=ch;

五星文库wxphp.com包含总结汇报、办公文档、IT计算机、考试资料、文档下载、党团工作、资格考试、教程攻略、计划方案、教学研究以及数据结构试题库集及答案等内容。

本文共54页1<<78910111213>>54