数据结构复习题目1.docx

1、数据结构复习题目1一 是非题(线性结构)4 线性表的链式存储结构具有可直接存取表中任一元素的优点。 错5 线性表的顺序存储结构优于链式存储结构。 错6. 在单链表P指针所指结点之后插入S结点的操作是： 错P-next= S ; S- next = P-next;。7 对于插入、删除而言，线性表的链式存储优于顺序存储。 对 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 错10 线性表的顺序存储结构具有可直接存取表中任一元素的优点。 对11. 栈和队列是操作上受限制的线性表。 对12. 队列是与线性表完全不同的一种数据结构。 错13. 队列是一种操作受限的线性表，凡对数据元素的操

2、作仅限一端进行。错15. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。 错16 队列是一种运算受限的线性表 对(树形结构)1. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所 以，二叉树是树的特殊情形。 错2. 二叉树是一棵结点的度最大为二的树。 错 3. 赫夫曼树中结点个数一定是奇数。 对5. 假设B是一棵树，B是对应的二叉树。则B的后根遍历相当于B的后序遍历 。错6. 通常，二叉树的第i层上有2i-1个结点。 错7. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 对8 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。 对(图形结构)1

3、邻接多重表可以用以表示无向图，也可用以表示有向图。 错2 可从任意有向图中得到关于所有顶点的拓扑次序。 错6. 一个无向图的连通分量是其极大的连通子图。 对7. 连通图的生成树是一个包含图G所有n个顶点和任意n-1条边的子图。 错9. 邻接表可以表示有向图，也可以表示无向图。（ ） 对 （查找)1. 二叉排序树的平均查找长度为O(log)。 对2. 二叉排序树的最大查找长度与（LOG2N）同阶。 错 3 选用好的HASH函数可避免冲突。 错4 折半查找不适用于有序链表的查找。 对5 一般来说，折半查找不适用于有序链表的查找。 对6 二叉排序树的查找和折半查找的时间性能相同。 错（排序)1. 对

4、于目前所知的排序方法，快速排序具有最好的平均性能。 对2 对于任何待排序序列来说，快速排序均快于冒泡排序。错3 在最坏情况下，堆排序的时间性能是O(nlogn),比快速排序好 对选择题。（1-19是线性、树形、图形结构，20-29是查找和排序）1、从逻辑上可以把数据结构分成( C )。 A. 动态结构和静态结构 B. 顺序组织和链接组织C. 线性结构和非线性结构 D. 基本类型和组合类型2、线性表L在( B )情况下适于使用链表结构实现。 A. 不需修改L的结构 B. 需不断对L进行删除、插入 C. 需经常修改L中结点值 D. L中含有大量结点 3、若入栈顺序为A、B、C、D、E，则下列( D

5、 )出栈序列是不可能的。AA、B、C、D、E BB、C、D、A、ECC、D、B、E、A DD、E、C、A、B4、递归程序可借助于(C )转化为非递归程序。 a.线性表 b.队列 c: 栈 d.数组 5、在下列数据结构中( C )具有先进先出（FIFO）特性，( B )具有先进后出(FILO）特性。a线性表 b栈 c队列 d广义表 6、若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,17、假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7, 19, 2

6、2, 6, 32, 14。 若为这6个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右），则频率为7的字符编码是（ g），频率为32的字符编码是（ c ）。a: 00 b: 01 c: 10 d: 11 e: 011 f: 110 g: 1110 h:11118、对二叉排序树（ C ）可得到有序序列。a:按层遍历 b:前序遍历 c:中序遍历 d:后序遍历 9、设一棵二叉树BT的存储结构如下: 1 2 3 4 5 6 7 8 lchild 2 3 0 0 6 0 0 0 data A B C D E F G H rchild 0 5 4 0 8

7、 7 0 0 其中lchild，rchild分别为结点的左、右孩子指针域，data为结点的数据域。则该二叉树的高度为( D )；第3层有( A )个结点（根结点为第1层）。 A2 B. 3 C. 4 D. 510、在有n个结点的二叉树的二叉链表表示中，空指针数 （ B ）。 a.不定 b.n+1 c.n d.n-111、若某二叉树有20个叶子结点，有20个结点仅有一个孩子，则该二叉树的总结点数是( C )。 A40 B. 55 C. 59 D. 6112、已知某二叉树的先序遍历次序为abcdefg中序遍历次序为badcgfe，则该二叉树的后序遍历次序为（ C ）。层次遍历次序为（ a ）。 a

8、: abcdefg b: cdebgfa c: bdgfeca d: edcgfba13、.图示的三棵二叉树中(C )为最优二叉树。 A) B) C) c a 2 7 a b c d d b 7 5 2 4 4 5 a b c d 7 5 2 414、对一棵完全二叉树进行层序编号。则编号为n的结点若存在右孩子,其位序是(d )。编号为n的结点若存在双亲,其位置是( a)。a: n/2 b: 2n c:2n-1 d:2n+1 e:n f: 2(n+1)15、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，则与森林F对应的二叉树根结点的右子树上的结点个数是( d )。A.

9、 m1 B. m1+m2 C. m3 D. m2+m316、下列二叉树中，( a )可用于实现符号不等长高效编码。a:最优二叉树 b:次优查找树 c:二叉平衡树 d:二叉排序树17、设无向图G = (V,E)和G= (V,E)，若G是G的生成树，则下面不正确的说法是( b )。A. G是G的子图 B. G是G的连通分量C. G是G的无环子图 D. G是G的极小连通子图且V= V18、任何一个连通图的最小生成树( b)。 A只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在19、已知某无向图的邻接表如下所示； ( 19 )是其原图。 E ( 20 )是按该邻接表遍历所得深度优先生成

10、树。 C( 21 )是按该邻接表遍历所得广度优先生成树。D 0 a 3 2 1 1 b 3 0 2 c 4 3 0 3 d 5 2 1 0 4 e 5 2 5 f 4 3A. a b B. a b C. a b c d c d c d e f e f e f D. a b E. a b F. a b c d c d c d e f e f e f20、下列查找方法中（ a ）适用于查找单链表。 A）顺序查找 B）折半查找 C）分块查找 D）hash查找21、哈希表的查找效率取决于（ d ）。a: 哈希函数 b:处理冲突的方法。 c:哈希表的装填因子。 d:以上都是22、在Hash函数H(k)=

11、k MOD m中，一般来说，m应取( C )。 A. 奇数 B. 偶数 C. 素数 D. 充分大的数23、在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用 方法。AA.设置监视哨 B.链表存贮 C.二分查找 D.快速查找24、静态查找表和动态查找表的区别在于( B )。 A. 前者是顺序存储，而后者是链式存储B. 前者只能进行查找操作，而后者可进行查找、插入和删除操作 C. 前者只能顺序查找，而后者只能折半查找 D. 前者可被排序，而后者不能被排序25、根据插入次序（80，90，100，110，85，70，75，60，72）建立二叉排序树。图（ a ）是最终变化的结果。

12、80 80 70 90 75 90 60 75 85 100 60 70 85 100 72 110 72 110 a: b: 90 90 75 100 80 100 70 80 110 75 70 85 110 60 72 85 60 72 c: d:26、若有序表中关键字序列为：14，20，25，32，34，45，57，69，77，83，92。对其进行折半查找，则在等概率情况下，查找成功时的平均查找长度是( C )。查找32时需进行( C )次比较。A. 1 B. 2 C. 3 D. 4 27、已知哈希表地址空间为A0.8，哈希函数为H(k)=k mod 7，采用线性探测再散列处理冲突。若

13、依次将数据序列：76,45,88,21,94,77,17存入该散列表中，则元素17存储的下标为( h )；在等概率情况下查找成功的平均查找长度为( C )。 A. 0 B. 1 C. 2 D. 3E. 4 F. 5 G. 6 H. 728、若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，则该二叉树是( C )。A. 二叉排序树 B. 赫夫曼树 C. 堆 D. 平衡二叉树29、已知一组待排序的记录关键字初始排列如下：56,26,86,35,75,19,77,58,48,42下列选择中（ D ）是快速排序一趟排序的结果。（ B ）是归并排序一趟排序的结果。（ A ）是初

14、始堆（大堆顶）。A）86,75,77,58,42,19,56,35,48,26.B）26,56,35,86, 19, 75, 58, 77, 42, 48.C）35,26,19,42,58,48,56,75,86,77.D）42,26,48,35,19,56,77,58,75,86. 三填空题（1-13是线性、树形、图形结构，14-15是查找和排序）1、数据结构通常有下列4类基本结构：集合、 线性结构 、树型结构、图型结构。2、线性表的顺序存储结构是以 物理存储地址 来表示数据元素之间的逻辑关系的。3、递归过程可借助于数据结构 ( 栈 )改写成非递归过程。4、设循环队列存于一维数组中，尾指针r

15、ear指示队尾元素在队列中的当前位置，头指针front指示队列中队头元素的前一个位置，则队列长度( （rear-front +m）%m )。5、在二叉树的第i层上至少有_1_个结点, 至多有_2i-1_个结点 ,深度为k的二叉树至多有_2k_-1_个结点.6、对树的遍历有先序遍历树和后序遍历树。若以二叉链表作树的存储结构,则树的先序遍历可借用二叉树的 先序 遍历算法来实现,而树的后序遍历可借用二叉树的 中序 遍历算法来实现。7、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，则与森林F对应的二叉树根结点的左子树上的结点个数是（m1-1 ），右子树上的结点个数是（ m2

16、+m3 ）。8、若某二叉树有n0个叶子结点，有n1个结点仅有一个孩子，则该二叉树的总结点数是（ 2 n0 + n1-1）。9、如果对完全二叉树中结点从1开始按层进行编号，设最大编号为n；那么，可以断定编号为i (i1)的结点的父结点编号为( i/2 )；所有编号（ n/2 ）的结点为叶子结点。 10、若某二叉树中，有20个结点没有孩子，有20个结点仅有一个孩子，则该二叉树的总结点数是 59 。11、 n个顶点的连通图至少有 n-1 条边，至多有 n(n-1)/2 条边。12、对于图的存储结构有（ 邻接表 ）、（ 邻接矩阵 ）等方法。13、在一个无向图的邻接表中，若表结点的个数是m，则图中边的条

17、数是_m/2_条。14、若有序表中关键字序列为：12，22，33，44，55，66，77，88，99，100，101对其进行折半查找，则在等概率情况下，查找成功时的平均查找长度是（ 3 ）。查找99时需进行（ 2 ）次比较。15、用 中序 遍历对二叉排序树进行访问可得到有序序列。已知Hash函数为 H（K）=K mod 13 ，散列地址为0 -14，用二次探测再散列处理冲突，关键字（23，34，56，24，75，12，49, 52，36，92）的分布如图，则平均成功的查找长度为（ ）。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1452 36925634 23247512

18、49图示结构题（1-4是线性、树形、图形结构，5-6是查找排序）1. 已知在电文中只出现频率为 ( 5,26,7,23,20,19 )的个字符，画出你建的哈夫曼树，并给出其哈夫曼编码。2.已知某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG请画出该二叉树。3将图示森林转换为二叉树，并对该二叉树先序遍历。 4某二叉树的结点数据采用顺序存储表示如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19ABCDEFGHI（1）试画出此二叉树的图形表示。（2）将此二叉树看作森林的二叉树表示，试将它还原为森林。 5 已知Hash函数为 H（K）=K mod 13 ，散列地址为0 -14，用线性探测再散列处理冲突，给出关键字（56，34，68，23，16，70，48，35，83，12，14，57）在散列地址的分布。并指出平均成功的查找长度是多少?0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 6 已知待排序序列为：25,12,9,20,7,31,24,35,17,10，试写出： (1). 堆排序初始建堆(大顶堆)的结果； (2). 以第一个元素为枢轴的快速排序一趟扫描的结果；