数据结构习题与解析.doc

第1-3章习题一、选择题1.若进栈序列为a，b，c，d，进栈过程中可以出栈，则 c 不可能是一个出栈序列。A) a,d,c,b B) b,c,d,a C) c,a,d,b D) c,d,b,a6.设用一维数组A1,n来存储一个栈，令An为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。当从栈中弹出一个元素时，变量T将变化为 A 。A) T=T + 1 B) T=T 1 C) T不变 D) T= n7. 一个栈的入栈序列为a，b，c，d，e,则栈不可能的出栈序列是 C 。A) e d c b a B) d e c b a C) d c e a b D) a b c d e8.若语句S的执行时间为O(1),那么下列程序段的时间复杂度为 B 。For(i = 0; i = n ; i+)For(j = 0; j next = P-next-next B) p = P-next; P-next = P-next-next C) delete(P-next) D) p = P-next-next30.在计算递归函数时，如不使用递归过程，则一般情况下必须借助于 A 数据结构。A) 栈 B) 树 C) 双向队列 D) 广义表41.下列叙述中，正确的是 B 。A) 用指针的方式存储一棵有n个结点的二叉树最少需要n+1个指针B) 不使用递归，也可以实现二叉树的前序、中序和后序遍历C) 已知树的前序遍历并不能唯一确定一棵树，因为不知道树的根结点是哪一个D) 任一棵树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间50.以下有关数据结构的叙述，正确的是 C 。A) 线性表的线性存储结构优于链式存储结构 B) 二叉树的第i层上有2i-1个结点，深度为k的二叉树上有2k-1个结点C) 二维数组是其数据元素为线性表的线性表 D) 栈的操作方式是先进先出52.在一个单链表中，若要在指针P所指向的结点之后插入结点q，应执行的操作是 C 。A) P-next=q B) P-next=q; q-next=P-next-next C) q-next = P-next; P-next:=q D)P-next=q; q-next=P-next56.若进栈序列为3,5,7,9,进栈过程中可以出栈，则 B 不可能是一个出栈序列。A) 7,5,3,9 B) 9,5,7,3 C) 9,7,5,3 D) 7,5,9,357.设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈，一个元素出栈后立即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是 C 。A) 4 B) 6 C) 3 D) 259.有6个元素按6,5,4,3,2,1的顺序进栈，以下序列中，不合法的出栈序列是 A 。A) 3,4,6,5,2,1 B) 5,4,3,6,1,2 C) 2,3,1,4,5,6 D) 4,5,3,1,2,661.下面关于线性表的叙述中，错误的是 B 。A) 线性表采用顺序存储，必须占用一片连续的存储单元 B) 线性表采用顺序存储，便于进行插入和删除操作C) 线性表采用链式存储，不必占用一片连续的存储单元 D) 线性表采用链式存储，便于插入和删除操作。62.下述 A 是顺序存储方式的优点。A) 存储密度大 B) 插入运算方便 C) 删除运算方便 D) 可方便地用于各种逻辑结构的存储表示64.向顺序栈中压入元素时，是 A 。A) 先移动栈顶指针，后存入元素 B) 先存入元素，后移动栈顶指针 C) 谁先谁后无关紧要 D) 同时进行65.在一个顺序存储的循环队列中，队首指针指向队首元素的 A 。A) 前一个位置 B) 后一个位置 C) 队首元素位置 D) 任意位置67.栈和队列都是 A 。A) 限制存取点的线性结构 B) 限制存取点的非线性结构 C) 顺序存储的线性结构 D) 链式存储的线性结构68.用链表表示线性表的优点是 C 。A) 便于随机存储 B) 花费的存储空间较顺序存储少 C) 便于插入和删除操作 D) 数据元素的物理顺序与逻辑顺序相同69在一个具有n个单元的顺序栈中，假设以地址高端作为栈顶，以top作为栈顶指针，则当做退栈处理时，top的变化为 D 。A) top不变 B) top = 0 C) top = top - 1 D) top = top + 172.以下 B 不是队列的基本运算。A) 从队尾插入一个新元素 B) 从队列中删除第i个元素 C) 判断一个队列是否为空 D) 读取队头元素的值74.在长度为n的顺序表中，向第i个元素(1 = I NEXT=S;REAR=S 。11.从一个长度为N的顺序表中删除第I(1 = I b D) 总有s pre(y)和post(x)post(y) B) pre(x)pre(y)和post(x)post(y)C) pre(x)post(y) D) pre(x)pre(y)和post(x)post(y)16.如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2结点的 C 。A) 后序 B) 层次序 C) 前序 D) 中序19.在一棵具有5层的完全二叉树中，结点总数最少为 B 。ABCDEFGHIA) 15 B) 16 C) 5 D) 3120.图的广度优先遍历类似于树的 D 。A) 后序遍历 B) 先序遍历 C) 中序遍历 D) 按层遍历22.将下图所示的二叉树存储为对称序线索二叉树，则结点H的左线索指向 B 。A) 结点A B) 结点C C) 结点E D) 结点G25.设有6个结点的无向图，该图至少应有 A 条边，才能确保它是一个连通图。A) 5 B) 6 C) 7 D) 839.在完全二叉树中，如果一个结点是叶结点，则它没有 D 。A) 右子节点 B) 左子节点C) 左子节点、右子节点和兄弟结点 D) 左子节点和右子节点42.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树的结点为n，则二叉树B中另一棵子树的结点个数为 C 。A) m-n+1 B) n+1 C) m-n-1 D) m-n46.已知一棵二叉树结点的先根序列为ABDGCFK，中根序列为DGBAFCK，则结点的后根序列为 B 。A) ACFKBDG B) GDBFKCA C) KCFAGDB D) ABCDFKG47.下列关于树的判断中，错误的是 A 。A) 二叉树是树的特殊情况B) 树和二叉树之间最主要的区别是：二叉树中，结点的子树要区分左子树和右子树，即使在结点中只有一棵树的情况下也要明确指出该子树是左子树还是右子树C) 由树转换成二叉树，其根结点的右子树总是空的D) 二叉树中具有两个子女的父结点，在中序遍历序列中，它的后序结点最多只能有一个子女结点48.如果结点A有3个兄弟结点，而且B是A的双亲结点，则B的度为 C 。A) 2 B) 3 C) 4 D) 549.设A是一个森林，B是由A转换得到的二叉树，A中有n个非终端结点，B中在指针域为空的结点有 C 个。A) n 1 B) n C) n + 1 D) n + 258.如果二叉树中任何一个结点的值都小于它的左子树上所有结点的值，且大于右子树上所有结点的值，要得到个结点值的递增序列，应按下列 B 次序排列结点。A) 先根 B) 中根 C) 后根 D) 层次76.设森林F中有3棵树。第一、第二和第三棵树的结点个数分别是m1,m2和m3，则与森林F对应的二叉树根结点的右子树上的结点个数是 B 。A) m3 B) m2 + m3 C) m1 D) m1 + m286.该二叉树对应的森林结点的层次次序序列为 D 。A) E,G,F,A,C,D,B B) E,A,C,B,D,G,F C) E,A,G,C,F,B,D D) E,G,A,C,D,F,B90.一个满二叉树，共有n个结点，其中m个为树叶，则 B 。A) n = m + 1 B) m = (n + 1)/2 C) n = 2m D) n = 2 * m91.设电文中出现的字母为A,B,C,D和E，每个字母在电文中出现的次数分别为9、27、3、5和11。按霍夫曼编码，则字母C的编码应是 B 。A) 110 B) 1110 C) 10 D) 11193.3个结点可以构造出 D 种不同的二叉树。A) 2 B) 3 C) 4 D) 597.现有一棵度为3的树，它含有两个度为3的结点，一个度为2的结点和两个度为1的结点，由此可知度为0的结点数为 C 。A) 4 B) 5 C) 6 D) 798.假定在一棵二叉树中，双分支结点数为12个，单分支结点数为29个，则叶子结点数为 B 。A) 12 B) 13 C) 14 D) 4199.假定一棵二叉树的结点为97，则它的最小高度为 C 。A) 4 B) 5 C) 6 D) 7100.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A1,n中，结点Ai若有左子女，则左子女结点是 D 。A) A2i 1 B) A2i + 1 C) Ai/2 D) A2i102.由分别带权为9,2,5,7的4个叶子结点构造一棵霍夫曼树，该树的带权路径长度为 C 。A) 23 B) 37 C) 44 D) 46103.下列各项叙述中，正确的是 D 。A) 二叉树中每个结点有两个子结点，而对一般的树则无此限制 B) 用树的前序遍历和中序遍历可以推导出树的后续遍历C) 在二叉树中插入结点，该二叉树便不再是二叉树 D) 用一维数组存储二叉树，总是以前序遍历顺序存储结点104.二叉树的前序遍历和中序遍历如下：前序遍历：EFHIGJK 中序遍历：HFIEJKG 该二叉树根中右子树的根是 C 。A) E B) F C) G D) H107.在下列存储形式中， C 不是树的存储形式。A) 双亲表示法 B) 孩子链表表示法C) 孩子兄弟表示法 D) 顺序存储表示法109-110题基于下面的叙述：某二叉树结点的中序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E。109.该二叉树结点的前序序列为 B 。A) E,G,F,A,C,D,B B) E,A,C,B,D,G,F C) E,A,G,C,F,B,D D) E,G,A,C,D,F,B110.该二叉树对应的森林包括 B 棵树。A) 1 B) 2 C) 3 D) 4二、填空题1.若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为K，则左右子树皆非空的结点个数是 K-1 。2.在树中，一个结点的直接孩子结点的个数称为该结点的 度 。3.如果对于给定的一组权值，说构造出的二叉树的带权路径长度最小，则该树成为 霍夫曼树 。5.设根结店的层次为0，则具有n个结点的完全二叉树的深度为 |LOG2N| 。18.一棵二叉树的结点数为33，则其最大的深度为 33 。19.按后根次序遍历树或森林等同于按 对称序 次序遍历对应的二叉树。第9章 排序 相关习题2.从未排序序列中挑选元素，并将其依次放入已排序序列初始时为空的一端，这种排序方法称为 C 。A) 插入排序 B) 归并排序 C) 选择排序 D) 快速排序3.在对一组记录(60,43,100,30,21,79,65,21,90)进行直接插入排序时，当把它的第七个记录65插入有序表时，为寻找插入位置，需比较 C 次。A) 1 B) 2 C) 3 D) 44.一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为 B 。A) (79,46,56,38,40,84) B) (84,79,56,38,40,46) C) (84,79,56,46,40,38) D) (84,56,79,40,38,46)5.一组记录的排序码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 C 。A) (38,40,46,56,79,84) B) (40,38,46,79,56,84) C) (40,38,46,56,79,84) D) (40,38,46,84,56,79)14.对下列关键字序列用快速排序法进行排序时，速度最快的排序方法是 A 。A) (5,9,17,21,23,25,30) B) (21,9,17,30,25,23,5) C) (21,25,5,17,9,23,30) D) (25,23,30,17,21,5,9)15.在文件局部有序或文件长度较小的情况下，最佳的排序方法是 A 。A) 冒泡排序 B) 直接插入排序 C) 快速排序 D) 简单选择排序26.每次把待排序的区间划分为左、右两个子区间，其中左区间中元素的排序码均不大于基准元素的排序码，右区间中元素的排序码均不小于基准元素的排序码，这种排序方法叫做 B 。A) 堆排序 B) 快速排序 C) 起泡排序 D) 希尔排序27.组记录的排序码为字母序列(Q,D,F,X,A,P,N,B,Y,M,C,W)，按归并排序方法对该序列进行一趟归并后的结果为 D 。A) (D,F,Q,X,A,B,N,P,C,M,W,Y) B) (D,F,Q,A,P,X,B,N,Y,C,M,W) C) (D,Q,F,X,A,P,N,B,Y,M,C,W) D) (D,Q,F,X,A,P,B,N,M,Y,C,W)28.一组序列的关键字为(25,48,16,79,82,23,40,36,72)，其中含有5个长度为2的有序表，按归并排序方法对该序列进行一趟归并后的结果为 A 。A) (16,25,35,48,23,40,79,82,36,72) B) (16,25,35,48,79,82,23,36,40,72)C) (16,25,48,35,79,82,23,36,40,72) D) (16,25,35,48,79,23,36,40,72,82)38.若待排序序列已基本有序，要使它完全有序，则从关键码比较次数和移动次数考虑，应当使用的排序方法是 B 。A) 快速排序 B) 直接选择排序 C) 归并排序 D) 直接插入排序40.在设有关键码序列(16,9,4,25,15,2,13,18,17,5,8,24)，要按关键码值递增的次序排序，采用初始增量为4的希尔排序法，一趟扫描后的结果为 A 。A) (15,2,4,18,16,5,8,24,17,9,13,25) B) (2,9,4,25,15,16,13,18,17,5,8,24)C) (9,4,16,15,2,13,18,17,5,8,24,25) D) (9,16,4,25,2,15,13,18,5,17,8,24)43.设待排序的记录为(20,16,13,14,19)，并经过下列过程将这些记录排序，则所用的排序方法是 D 。 20 16 13 14 19 16 20 13 14 1913 16 20 14 19 13 14 16 20 1913 14 16 19 20 A) 冒泡排序 B) 希尔排序 C) 堆排序 D) 直接插入排序44.对于关键码序列K = 53,30,37,12,45,24,96 ,从空二叉树开始逐个插入每个关键码，建立与集合K对应的二叉排序树（又称二叉查找树）BST，若希望得到的BST高度最小，则应选择的输入序列是 A 。A) 37,24,12,30,53,45,96 B) 30,24,12,37,45,96,53 C) 12,24,30,37,45,53,96 D) 45,24,53,12,37,96,3045.用某种排序方法对线性表(D,I,C,G,A,E,H,F,B)进行关键码升序排列时，结点序列的变化情况如下： D,I,C,A,G,E,H,F,B C,A,B,D,G,E,H,F,I A,B,C,D,F,E,G,H,I A,B,C,D,E,F,G,H,I那么采用的排序方法为 B A) 选择排序 B) 快速排序 C) 希尔排序 D) 合并排序60.设有n个结点进行排序，不稳定的排序方法是 D 。A) 归并排序 B) 直接插入排序 C) 冒泡排序 D) shell排序63.对已建好的初始堆(84,79,56,38,36,40)进行排序，输出堆顶元素后，形成的堆为 D 。A) 79,56,38,46,40 B) 79,56,46,38,40 C) 79,46,38,56,40 D) 79,46,56,38,4066.若关键码序列(k1,k2,kn)是一个堆，序列中元素的关系是 A 。A) ki = k2i且ki = k2i 且ki = k2i+1 B) k1 = K2 = = K2 = = kn D) 元素间没有任何限制70.对n个记录的文件进行堆排序，最坏情况下的执行时间为 C 。A) O(log2n) B) O(n) C) O(nlog2n) D) O(n2)71.用直接插入排序方法对下面4个序列进行由小到大的排序，元素比较次数最少的是 C 。A) 94,32,40,90,80,46,21,69 B) 32,40,21,46,69,94,90,80 C) 21,32,46,40,80,69,90,94 D) 90,69,80,46,21,32,94,4073.已知12个数据元素为(34,76,45,18,26,54,92,60,25,37,03,78)，对该数列按从小到大排序。若采用希尔排序方法排序，设第一趟排序的增量为6，第二趟排序的增量为3，则第二趟排序和的序列为 C 。A) 34,60,25,18,03,54,92,76,45,37,26,78 B) 18,25,03,26,34,37,54,60,45,76,78,92C) 18,03,25,34,26,45,37,60,54,92,76,78 D) 以上都不正确83.下列 C 关键码序列不符合堆的定义。A) A,C,D,G,H,M,P,Q,R,X B) A,C,M,D,H,P,X,G,O,R C) Q,D,P,R,C,Q,X,M,H,G D) A,D,C,M,P,G,H,X,R,Q84.对n个记录的文件进行快速排序，所需的辅助存储空间为 B 。A) O(1) B) O(log2n) C) O(n) D) O(n2)88.下列排序方法中，稳定的排序方法是 B 。A) 快速排序 B) 二分法插入排序 C) 希尔排序 D) 直接选择排序89.用快速排序法对下列关键字序列进行排序，速度最慢的是 A 。A) 7,11,19,23,25,27,32 B) 27,25,32,19,23,7,11 C) 23,11,19,32,27,25,7 D) 23,27,7,19,11,25,3292.下列关键码序列中， C 是一个堆。A) (93,30,52,22,15,71) B) (15,52,22,93,30,71) C) (15,30,22,93,52,71) D) (15,71,30,22,93,52)94.具有12个记录的序列，采用冒泡排序，最少的比较次数是 A 。A) 11 B) 66 C) 1 D) 14495.已知待排序的记录的关键字为50,34,65,76,97,27,13,37,49，采用直接插入排序方法将记录按关键字从小到大排序。当插入37时，需要比较的记录个数为 C 。A) 2 B) 3 C) 4 D) 596.对序列22,86,19,49,12,30,65,35,18进行排序，排序过程如下：(1) 22,86,19,49,12,30,65,35,18 (2) 18,12,19,22,49,30,65,35,86 (3) 15,18,19,22,35,30,49,65,86 (4) 15,18,19,22,30,35,49,65,86 那么，可以认为对其使用的排序方法是 A A) 快速排序 B) 选择排序 C) 插入排序 D) 冒泡排序101.已知8个数据元素为(26,75,15,23,14,62,72,19)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为 B 。A) 3 B) 4 C) 5 D) 6105.排序的重要目的 以后对已排序的数据元素进行 C 。A) 打印输出 B) 分类 C) 查找 D) 合并111.有一组随机数：25,84,21,47,15,27,68