数据结构试题库集及答案

导读:考虑对这四个数据元素进行的队操作是进队两次,供选择的答案:,7.从供选择的答案中,C:①加1②减1③不变④清0⑤加2⑥减2D:①a,b②b,c③c,a④b,a⑤c,8.从供选择的答案中,且一个栈的栈顶到达另一个栈的栈底答案:ABCDE=2,1,2,4,3,刘答:相同点:都是线性结构,都是逻辑结构的概念,顺序进入一个栈式结构的车站,第4~5章串和数组自测卷答案,它包含有三个数据项,A.可以顺序存

数据结构试题库集及答案

现要进行的栈操作是进栈两次,出栈一次,再进栈两次,出栈一次;这时,第一次出栈得到的元素是 A ,第二次出栈得到的元素是 B 是;类似地,考虑对这四个数据元素进行的队操作是进队两次,出队一次,再进队两次,出队一次;这时,第一次出队得到的元素是 C ,第二次出队得到的元素是 D 。经操作后,最后在栈中或队中的元素还有 E个。 供选择的答案:

A~D:①a1②a2③a3④a4 E:①1 ②2 ③3 ④0

答:ABCDE=2, 4, 1, 2, 2

7.从供选择的答案中,选出应填入下面叙述?内的最确切的解答,把相应编号写在答卷的对应栏内。

栈是一种线性表,它的特点是 A 。设用一维数组A[1,…,n]来表示一个栈,A[n]为栈底,用整型变量T指示当前栈顶位置,A[T]为栈顶元素。往栈中推入(PUSH)一个新元素时,变量T的值 B ;从栈中弹出(POP)一个元素时,变量T的值 C 。设栈空时,有输入序列a,b,c,经过PUSH,POP,PUSH,PUSH,POP操作后,从栈中弹出的元素的序列是 D ,变量T的值是 E 。 供选择的答案:

A:①先进先出②后进先出 ③进优于出 ④出优于进 ⑤随机进出 B,C: ①加1 ②减1 ③不变 ④清0 ⑤加2 ⑥减2 D:①a,b②b,c ③c,a ④b,a ⑤ c,b ⑥ a,c E:① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 答案:ABCDE=2,2,1,6,4

注意,向地址的高端生长,称为向上生成堆栈;向地址低端生长叫向下生成堆栈,本题中底部为n,向地址的低端递减生成,称为向下生成堆栈。

8.从供选择的答案中,选出应填入下面叙述?内的最确切的解答,把相应编号写在答卷的对应栏内。

在做进栈运算时,应先判别栈是否 A ;在做退栈运算时,应先判别栈是否 B 。当栈中元素为n个,做进栈运算时发生上溢,则说明该栈的最大容量为 C 。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 D 分别设在这片内存空间的两端,这样,只有当 E 时,才产生上溢。 供选择的答案:

A,B:①空②满③上溢④下溢 C: ①n-1②n③n+1④n/2 D:①长度②深度③栈顶④栈底

E:①两个栈的栈顶同时到达栈空间的中心点②其中一个栈的栈顶到达栈空间的中心点

③两个栈的栈顶在达栈空间的某一位置相遇④两个栈均不空,且一个栈的栈顶到达另一个栈的栈底 答案:ABCDE=2, 1, 2, 4, 3

四、简答题

1.说明线性表、栈与队的异同点。

刘答:相同点:都是线性结构,都是逻辑结构的概念。都可以用顺序存储或链表存储;栈和队列是两种特殊的线性表,即受限的线性表,只是对插入、删除运算加以限制。

不同点:①运算规则不同,线性表为随机存取,而栈是只允许在一端进行插入、删除运算,因而是后进先出表LIFO;队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表FIFO。

②用途不同,堆栈用于子程调用和保护现场,队列用于多道作业处理、指令寄存及其他运算等等。

2.设有编号为1,2,3,4的四辆列车,顺序进入一个栈式结构的车站,具体写出这四辆列车开出车站的所有可能的顺序。

刘答:至少有14种。

①全进之后再出情况,只有1种:4,3,2,1

②进3个之后再出的情况,有3种,3,4,2,1 3,2,4,1 3,2,1,4

③进2个之后再出的情况,有5种,2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 ④进1个之后再出的情况,有5种,1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3

3.顺序队的“假溢出”是怎样产生的?如何知道循环队列是空还是满?

答:一般的一维数组队列的尾指针已经到了数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫“假溢出”。 采用循环队列是解决假溢出的途径。 另外,解决队满队空的办法有三:

① 设置一个布尔变量以区别队满还是队空;

② 浪费一个元素的空间,用于区别队满还是队空。 ③ 使用一个计数器记录队列中元素个数(即队列长度)。

我们常采用法②,即队头指针、队尾指针中有一个指向实元素,而另一个指向空闲元素。 判断循环队列队空标志是: f=rear 队满标志是:f=(r+1)%N

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. 不包含任何字符(长度为0)的串称为空串;由一个或多个空格(仅由空格符)组成的串称为空白串。 (对应严题集4.1①,简答题:简述空串和空格串的区别)

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

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

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

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

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

(注:数组是从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 解:注意B的下标要求从1开始。 先用第一个元素去套用,可能有B和C; 再用第二个元素去套用B和C,B=2而C=3(不符); 所以选B ?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]的第一个字节的地址分别是 B 和 C 。若按列存储,则A[7,1]和A[2,4]的第一个字节的地址分别是 D 和 E 。 供选择的答案:

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]的第一个字节的地址是 D 。 供选择的答案

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个结点所构成的二叉树有5种形态。

2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31个分支结点和26-1=32个叶子。 注:满二叉树没有度为1的结点,所以分支结点数就是二度结点数。

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

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

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

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

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

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

6.一棵含有n个结点的k叉树,可能达到的最大深度为n,最小深度为2。 答:当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 B。解:法1:先由已知条件画图,再后序遍历得到结果;

法2:不画图也能快速得出后序序列,只要找到根的位置特征。由前序先确定root,由中序先确定左子树。例如,前序遍历BEFCGDH中,根结点在最前面,是B;则后序遍历中B一定在最后面。

法3:递归计算。如B在前序序列中第一,中序中在中间(可知左右子树上有哪些元素),则在后序中必为最后。如法对B的左右子树同样处理,则问题得解。

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

答:即递归最大嵌套层数,即栈的占用单元数。精确值应为树的深度k+1,包括叶子的空域也递归了一次。

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

解:先构造哈夫曼树,得到各叶子的路径长度之后便可求出WPL=(4+5+3)×2+(1+2)×3=33 (15) (9) (6) (注:两个合并值先后不同会导致编码不同,即哈夫曼编码不唯一) 4 5 3 (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

C F

E G

B H I

下面是按先序遍历的思路建立二叉树的两种方法 #include #include #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计算机、考试资料、文档下载、党团工作、资格考试、教程攻略、计划方案、教学研究以及数据结构试题库集及答案等内容。

本文共10页1<<5678910