数据结构复习题.docx

1、数据结构复习题考试说明考试内容：一、绪论数据结构的基本概念和分类、数据结构的逻辑结构、存储结构、算法、数据结构的选择和评价二、线性表线性表的类型定义、线性表的顺序表示和实现、线性表的链式表示和实现三、栈和队列 栈和队列的结构特性、两种存储结构上实现栈和队列的基本操作、栈和队列在程序设计中的应用六、树和二叉树树、二叉树的定义、性质和存储结构、二叉树的遍历和线索化、二叉树和森林转换、最优树和哈夫曼编码。七、图图的定义和术语、图的存储结构、图的遍历、最小生成树、拓扑排序、最短路径问题。九、内部排序插入排序、交换排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程、时间复杂度分析及其应用。

2、试题类型及分值：选择题30分 15题应用题 40分 5题算法设计题 30分 3题一 选择题1.计算机算法指的是（1），它必须具备（2） 这三个特性。(1) A计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 答案：CB2. 下面说法错误的是（ ） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4

3、）同一个算法，实现语言的级别越高，执行效率就越低 A(1) B.(1),(2) C.(1),(4) D.(3)答案 C3从逻辑上可以把数据结构分为（ ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构答案 C4以下与数据的存储结构无关的术语是（ ）。A循环队列 B. 链表 C. 哈希表 D. 栈答案 D5连续存储设计时，存储单元的地址（ ）。A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续答案 A6下面关于线性表的叙述中，错误的是哪一个？（ ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删

4、除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。答案 B7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。A单链表 B双链表 C单循环链表 D带头结点的双循环链表答案：D8. 下面的叙述不正确的是（ ）A线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关答案 BC10. 对于顺序存储的线性表，访问结点和增

5、加、删除结点的时间复杂度为（ ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)答案： C11. 循环链表H的尾结点P的特点是（ ）。 AP.NEXT:=H BP.NEXT:= H.NEXT CP:=H DP:=H.NEXT答案：A12完成在双循环链表结点p之后插入s的操作是（ ）A p.next:=s ; s.priou:=p; p.next.priou:=s ; s.next:=p.next;B p.next.priou:=s; p.next:=s; s.priou:=p; s.next:=p.next;C s.priou:=p; s.n

6、ext:=p.next; p.next:=s; p.next.priou:=s ;D s.priou:=p; s.next:=p.next; p.next.priou:=s ; p.next:=s;答案 D13在非空双向循环链表中q所指的结点前插入一个由p所指的链结点的过程依次为:rlink(p) q; llink(p) llink(q); llink(q) p; （ ） Arlink(q) p Brlink(llink(q) p Crlink(llink(p) p Drlink(rlink(p) p答案 B14在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。A. p-Llink=q

7、;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;答案 C15 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。Ap-next=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-n

8、ext=s-next; D p-next=s-next;p-next=s;答案 B16. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2答案：B17. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ ）。A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4答案：D18. 若一个栈以向量V1.n存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。Atop:=to

9、p+1; V top:=x B. V top:=x; top:=top+1 C. top:=top-1; V top:=x D. V top:=x; top:=top-1答案：C19. 若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈( i =1,2)栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条件是（ ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top2答案：B20. 用链接方式存储的队列，在进行删除运算时（ ）。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能

10、都要修改答案 D21. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。A仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改答案 D22. 循环队列存储在数组A0.m中，则入队时的操作为（ ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 答案：D23. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素

11、，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 答案：B25若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定答案B26在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个A4 B5 C6 D7 答案 C27. 有关二叉树下列说法正确的是（ ）A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2答案B28. 有n个叶子的哈夫曼树的结点总数为（ ）。A

12、不确定 B2n C2n+1 D2n-1答案 D29. 利用二叉链表存储树，则根结点的右指针是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空答案C30对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。A先序 B. 中序 C. 后序 D. 从根开始按层次遍历答案C32若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。A前序 B中序 C后序 D按层次答案D33在下列存储形式中，哪一个不是树的存储形式？（ ）A双亲表示法 B孩子链表表示法

13、 C孩子兄弟表示法 D顺序存储表示法答案D34一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）ACABDEFG BABCDEFG CDACEFBG DADCFEG 答案B35已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。ACBEFDA B FEDCBA C CBEDFA D不定 答案A36已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。Aacbed Bdecab Cdeabc Dcedba 答案D39下述编码中哪一个不是前缀码（ ）。A（00，01，10，11） B（0，1，

14、00，11） C（0，10，110，111） D（1，01，000，001）答案 B40. 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 Al.n中时，数组中第i个结点的左孩子为（ ）AA2i(2i=n) B. A2i+1(2i+1=0)个结点的d度树, 若用多重链表表示, 树中每个结点都有d个链域, 则在表示该树的多重链表中有多少个空链域? 为什么? 答案：n（n0）个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nd-(n-1)=n(d-1)+1个。7. 一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其

15、中n0是度为0的结点的个数。答案：证明：设二叉树度为0和2的结点数及总的结点数分别为n0，n2 和n，则n=n0+n2 (1)再设二叉树的分支数为B,除根结点外，每个结点都有一个分支所指，则 n=B+1 (2)度为零的结点是叶子，没有分支，而度为2的结点有两个分支，因此（2）式可写为n=2*n2+1 (3)由（1）、（3）得n2=n0-1,代入（1），并由（1）和（2）得B=2*(n0-1)。 证毕。9设一棵二叉树的先序、中序遍历序列分别为先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C（1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。 （3

16、）将这棵二叉树转换成对应的树（或森林）。答案：略10.设某二叉树的前序遍历序列为:ABCDEFGGI，中序遍历序列为:BCAEDGHFI：（1）试画出该二叉树；（2）写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。（3）设具有四个结点的二叉树的前序遍历序列为；为长度等于四的由，排列构成的字符序列，若任取作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出具有四个结点二叉树的全部形态及相应的中序遍历序列。答案： （1）略（2）设二叉树的前序遍历序列为P1，P2，Pm，中序遍历序列为S1,S2,，Sm。因为前序遍历是“根左右”，中序遍历是“左根右”，则前

17、序遍历序列中第一个结点是根结点（P1）。到中序序列中查询到Si=P1,根据中序遍历时根结点将中序序列分成两部分的原则，有： 若i=1，即S1=P1，则这时的二叉树没有左子树; 否则，S1,S2,Si-1是左子树的中序遍历序列,用该序列和前序序列P2,P3，Pi去构造该二叉树的左子树。 若i=m,即Sm=P1,则这时的二叉树没有右子树; 否则,Si+1,Si+2,，Sm是右子树的中序遍历序列，用该序列和前序序列中Pi+1,Pi+2,Pm,去构造该二叉树的右子树。（3）若前序序列是abcd，并非由这四个字母的任意组合（4!=24）都能构造出二叉树。因为以abcd为输入序列，通过栈只能得到1/(n+1)*2n!/(n!*n!)=14 种，即以abcd为前序序列的二叉树的数目是14。任取以abcd作为中序遍历序列，并不全能与前序的abcd序列构成二叉树。例如：若取中序列dcab就不能。该14棵二叉树的形态及中序序列略。11用一维数组存放的一棵完全二叉树如下图所示：ABCDEFGHIJKL写出后序遍历该二叉树时访问结点的顺序。答案：HIDJKEBLFGCA12. 已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成？请简述原因。答案：