浙江工商大学数据结构期末复习题2.doc

《浙江工商大学数据结构期末复习题2.doc》由会员分享，可在线阅读，更多相关《浙江工商大学数据结构期末复习题2.doc（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流浙江工商大学数据结构期末复习题2.精品文档.数 据 结 构 习 题 集 一、选择题 .在一个长度为n的顺序表中，向第i个元素(1in+1)之前插入一个新元素时，需向后移动 B 个元素。 A. n-1 B. n-i+1 C. n-i-1 D. i .在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为 C 。 A. top不变 . top -n C. toptop-1 D. top=top+1 .向顺序栈中压入元素时，是 A 。 A. 先存入元素，后移动栈顶指针 B.先移动栈顶指针，后存入

2、元素 .在一个顺序存储的循环队列中，队首指针指向队首元素的 A 。 A. 前一个位置 B. 后一个位置 C. 队首元素位置 D. 队尾元素位置 .若进栈序列为1,2,3,4,进栈过程中可以出栈，则 C 不可能是一个出栈序列。 A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4 .在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是 C 。 A. front= =rear+1 B. front+1= =rear C. front= =rear D. front= =0 .在具有n个单元的顺序存储的循环队列中

3、，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是 D 。 A. rear % n= =front B. (rear-1) % n= =front C. (rear-1) % n= =rear D. (rear+1) % n= =front .从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需 平均比较 D 个结点。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 .在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点， 则执行 C 。 A. s-next=p-next; p-next=s; B. p-n

4、ext=s-next; s-next=p; C. q-next=s; s-next=p; D. p-next=s; s-next=q; 10.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行 C 。 A. hs-next=s; B. s-next=hs-next; hs-next=s; C. s-next=hs；hs=s; D. s-next=hs; hs=hs-next; 11.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行 B 。 A. front-next=s; front=s; B. rear-next=s; rear=s; C

5、. front=front-next; D. front=rear-next; 12.线性表是 A 。 A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空 13.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的， 删除一个元素时大约要移动表中的 C 个元素。 A. n+1 B. n-1 C. (n-1)/2 D. n 14.线性表采用链式存储时，其地址 D 。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续与否均可以 15.设单链表中指针p指着结点(数据域为m)，指针f

6、指着将要插入的新结点(数据域为x)，当x插在结点m之后时，只要先修改 B 后修改p-link=f即可。 A. f-link=p; B. f-link=p-link; C. p-link=f-link; D. f=nil; 16.在双向链表存储结构中，删除p所指的结点时需修改指针 B 。 A. (p-rlink) -rlink) -link=p; p-rlink=(p-rlink) -rlink; B. (p-llink) -rlink=p-rlink; (p-rlink) -llink=p-llink; C. p-llink=(p-llink) -llink; (p-llink) -llink

7、) -rlink=p; D. (p-llink) -llink) -rlink=p; p-llink=(p-llink) -llink; 17.在双向链表存储结构中，删除p所指的结点的前趋结点（若存在）时需修改指针 A 。 A. (p-llink) -llink) -rlink=p; p-llink=(p-llink) -llink; B. (p-rlink) -rlink) -llink=p; p-rlink=(p-rlink) -rlink; C. (p-llink) -rlink=p-rlink; (p-rlink) -llink=p-llink; D. p-llink=(p-llink

8、) -llink; (p-llink) -llink) -rlink=p; 18.根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和 B 。 A. 循环链表 B. 多重链表 C. 普通链表 D. 无头结点链表 19.在数据结构中，与所使用的计算机无关的数据叫 C 结构。 A. 存储 B. 物理 C. 逻辑 D. 物理和存储 20.二分法查找 A 存储结构。 A. 只适用于顺序 B. 只适用于链式 C. 既适用于顺序也适用于链式 D. 既不适合于顺序也不适合于链式 21.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上 B 。 A. 一定相邻 B. 不一定相邻 C. 有时相

9、邻 23.假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点 数为 B 。 A. 15 B. 16 C. 17 D. 47 24.假定一棵二叉树的结点数为18个，则它的最小高度 B 。 性质2 A. 4 B. 5 C. 6 D. 18 25.在一棵二叉树中第五层上的结点数最多为 C 。 性质1 A. 8 B. 15 C. 16 D. 32 26.在一棵具有五层的满二叉树中，结点总数为 A 。 性质3 A. 31 B. 32 C. 33 D. 16 27.已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后

10、两层上的结点总数为 B 。 不理解？ A. 1 B. 2 C. 3 D. 4 28.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 C 。 A. 23 B. 37 C. 44 D. 46 为什么不是46？ 29.在树中除根结点外，其余结点分成m (m0)个 A 的集合T1,T2,T3.Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1im)。 A. 互不相交 B. 可以相交 C. 叶结点可以相交 D. 树枝结点可以相交 30.下面答案 D 是查找二叉树（又称二叉排序树）。 A. 二叉树中的每个结点的两棵子树的高度差的绝对值不大于 B. 二

11、叉树中的每个结点的两棵子树的高度差等于 C. 二叉树中的每个结点的两棵子树是有序的 D. 二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值， 且小于其右子树（如果存在）所有结点的关键字值。 31.如果结点A有三个兄弟，而且B是A的双亲，则B的出度是 B 。 A. 3 B. 4 C. 5 D. 1 32.一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。如果按层次顺序从开始对全部结点编号，编号为n的有右兄弟的条件是 B 。 A. (n-1) % k= =0 B. (n-1) % k!=0 C. n % k= =0 D. n %

12、k!=0 33.在完全二叉树中，当i为奇数且不等于时，结点i的左兄弟是结点 D ，否则没有左兄弟。 A. 2i-1 B. i+1 C. 2i+1 D. i-1 34.某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,n且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树 的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按 B 编号。 A. 中序遍历序列 B. 前序遍历序列 C. 后序遍历序列 D. 层次遍历序列 35.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。 A. 1/2 B. 1 C. 2 D. 4

13、36.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小 为 A 。 A. n B. n+1 C. n-1 D. n+e 37.具有n个顶点的无向完全图，边的总数为 D 条。 A. n-1 B. n C. n+1 D. n*(n-1)/2 38.设图G有n个顶点和e条边，当G是非孤立顶点的连通图时有2e=n,故可推得深度优先搜索的时间复杂度为 A 。 A. O(e) B. O(n) C. O(ne) D. O(n+e) 39.最小代价生成树 D 。 A.是唯一的 B.不是唯一的 C.唯一性不确定 D.唯一性与原因的边的权数有关 40.在无向图G的邻接矩阵A中，若Ai,j等

14、于1，则Aj,i等于 C 。 A. i+j B. i-j C. 1 D. 0 41.图的深度优先或广度优先遍历的空间复杂性均为 A 。(访问标志位数组空间) A. O(n) B. O(e) C. O(n-e) D. O(n+e) 42.已知一个有序表为(12、18、24、35、47、50、62、83、90、115、134)，当二分查找值为90的元素时， B 次比较后查找成功；当二分查找值为47的元素时， D 次比较后查找成功。 A. 1 B. 2 C. 3 D. 4 43.散列函数有一个共同性质，即函数值应当以 D 取其值域的每个值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等

15、概率 44.设散列地址空间为0m1,k为关键字，用p去除k，将所得的余数作为k的散列地址，即H(k)k % p。为了减少发生冲突的频率，一般取p为 D 。 A. 小于m的最大奇数 B. 小于m的最大偶数 C. m D. 小于m的最大素数 45.目前以比较为基础的内部排序时间复杂度T(n)的范围是 A ；其比较次数与待 排序的记录的初始排列状态无关的是 B 。 A. O(log2 n)O(n) O(lon2 n)O(n2 ) O(nlog2 n)O(n2 ) O(n)O(n2 ) O(n)O(nlog2 n) B. 插入排序 先用二分法查找，找到后插入排序 快速排序 冒泡排序 46.设关键字序列

16、为：3,7,6,9,8,1,4,5,2。进行排序的最小交换次数是 A 。 A. 6 B. 7 C. 8 D. 20 47.在归并排序过程中，需归并的趟数为 C 。 A. n B. n C. log2 n向上取整 D. log2 n向下取整 48.一组记录排序码为(46、79、56、38、40、84)，则利用堆排序的方法建立的初始堆为 B 。 A. (79、46、56、38、40、80) B. (84、79、56、38、40、46) C. (84、79、56、46、40、38) D. (84、56、79、40、46、38) 49.一组记录的关键码为(46、79、56、38、40、84)，则利用快

17、速排序的方法，以第一个记录为基准得到的一次划分结果为 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) 50.在平均情况下快速排序的时间复杂性为 C ，空间复杂性为 B ；在最坏情况下（如初始记录已有序），快速排序的时间复杂性为 D ，空间复杂性为 A 。 A. O(n) B. O(log2 n) C. O(nlog2 n) D. O(n2 ) 选择题参考答案： .B .C .A .A .C .C .D .D .C 10.C 11.B 12.A 13.C

18、 14.D 15.B 16.B 17.A 18.B 19.C 20.A 21.B 22.D 23.B 24.B 25.C 26.A 27.B 28.C 29.A 30.D 31.B 32.B 33.D 34.B 35.B 36.A 37.D 38.A 39.D 40.C 41.A 42.B,D 43.D 44.D 45.A: B: 46.A 采用选择排序对给定的关键字序列进行排序，只需次。 47.C 48.B 49.C 50.C B D A 二、填空题 1.在线性结构中第一结点 1 无 前驱结点，其余每个结点有且只有 2 一 个前驱结点；最后一个结点 3 无 后继结点，其余每个结点有且只有 4

19、 一 个后继结点。 2.在树型结构中，树根结点没有 1 前趋 结点，其余每个结点有且仅有 2 一 个前驱结点；树叶结点没有 3 后继 结点，其余每个结点的 4 后继 结点数不受限制。 3.一个数据结构用二元组表示时，它包括 1 数据元素 的集合K和K上 2二元关系 的集合R。 4.对于一个二维数组A1.m,1.n，若按行序为主序存储，则任一元素Ai,j的相对地址（即偏移地址）为 1 (i-1)*n+j-1 。 5.对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长 1 一半 的元素。 6.对于长度为n的顺序表，插入或删除元素的时间复杂性为 1 O(n) ；对于顺序栈或队列，插入

20、或删除元素的时间复杂性为 2 O(1) 。 7.在具有n个单元、顺序存储的循环队列中，队满时共有 1 n-1 个元素。 8.从顺序表中删除第i个元素时，首先把第i个元素赋给 1 变参或函数名 带回，接着从 2 链接指针 开始向后的所有元素均 3 前移 一个位置，最后使线性表的长度 4 减1 。 9.在线性表的顺序存储中，元素之间的逻辑关系是通过 1 相邻位置 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 2 链接指针 决定的。 10.一个单链表中删除*p结点时，应执行如下操作: (1)q=p-next; (2)p-data=p-next-data; (3)p-next= 1 q-ne

21、xt或p-next-next ; (4)free(q); 11.若要在一个单链表中的*p结点之前插入一个*s结点时，可执行如下操作: (1)s-next= 1 p-next ; (2)p-next=s; (3)t=p-data; (4)p-data= 2 s-data ; (5)s-data= 3 t ; 12.对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空间的 1 浪费 ，若分配太少又容易在算法中造成 2 溢出 ，因此适应于数据量变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要 3 预先分配 存储空间，存储器中的整个 4 动态存储区 都可供使用，分配

22、和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑 5 溢出 的发生，因此适应数据量变化较大的情况。 13.无论对于顺序存储还是链接存储的栈和队列来说，进行插入或删除运算的时间复 杂性均相同，则为 1 O(1) 。 0 0 2 0 *14.一个稀疏矩阵为 3 0 0 0，则对应的三元组线性表为 0 0 -1 5 (1,3,2),(2,1,3),(3,3,-1),(3,4,5)。 0 0 0 0 15.对于一棵具有n个结点的树，则该树中所有结点的度之和为 n-1 。 16.在一棵二叉树中，度为0的结点的个数为n0 ，度为2的结点的个数为n2 ，则：n0 = n2 +1 。 17.在二

23、叉树的顺序存储中，对于下标为5的结点，它的双亲结点的下标为 1 2 ， 若它存在左孩子，则左孩子结点的下标为 2 10 ，若它存在右孩子，则右孩子结点的下标为 3 11 。 18.假定一棵二叉树的广义表表示为A(B(，D)，C(E(G)，F)，则该树的深度为 14 ， 度为0的结点数为 23 ，度为1的结点数为 3 2 ，度为2的结点数为 42 ；C结点是A 结点的 5 右 孩子，E结点是C结点的 6 左 孩子。 19.在一棵二叉排序树中，按 中序 遍历得到的结点序列是一个有序序列。 20.由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为 55 。 21.假定在

24、二叉树的链接存储中，每个结点的结构为leftdataright ，其中 data为值域，left和right分别为链接左、右孩子结点的指针域，请在下面中序遍历算法 中画有横线的地方填写合适的语句。 void inorder(bt); if bt!=nil (1) 1 inorder(bt-left) ； (2) 2 printf(bt-data) ； (3) 3 inorder(bt-right) ； 22.在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该 顶点的 1 度数 ，对于有向图来说等于该顶点的 2 出度数 。 23.假定一个图具有n个顶点和e条边，则采用邻接矩

25、阵表示的空间复杂性为 1 O(n2 ) ， 采用邻接表表示的空间复杂性为 2 O(n+e) 。 24.已知一个无向图的邻接矩阵如下所示，则从顶点A出发按深度优先搜索遍历得到的 顶点序列为 1 ABCDFE ，按广度优先搜索遍历得到的顶点序列为 2 ABCEFD 。 A B C D E F 0 1 1 0 1 0A 1 0 1 0 1 1B 1 1 0 1 0 0C 0 0 1 0 0 1D 1 1 0 0 0 1E 0 1 0 1 1 0F 25.已知一个图如下所示，在该图的最小生成树中，各边的权值之和为 20 。 10 15 5 2 8 12 3 26.假定在有序表A1.20上进行二分查找，

26、则比较一次查找成功的结点数为 11 ， 比较两次查找成功的结点数为 22 ，比较三次查找成功的结点数为 34 ，比较四次查找成功结点数为 48 ，比较五次查找成功的结点数为 55 ，平均查找长度为 63.7 。 27.在索引查找或分块查找中，首先查找 1 索引表 ，然后再查找相应的 2 子表或块 ，整个索引查找的平均查找长度等于查找索引表的平均查找长度与查找相应子表的平均查找长度之 3 和 。 28.在散列存储中，装填因子的值越大，存取元素时发生冲突的可能性就 1 越大，当的值越小，存取元素时发生冲突的可能性就 2 越小 。 29.给定线性表(18,25,63,50,42,32,90)，用散列

27、方式存储，若选用h(K)=K % 9作为散列函数，则元素18的同义词元素共有 12 个，元素25的同义词元素共有 20 个，元素50的同义词元素共有 31 个。 30.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接选择排序时，第四次选择和交换后，未排序记录(即无序表)为 (54,72,60,96,83) 。 31.在对一组记录(54,38,96,23,15,72,60,45,38)进行冒泡排序时，第一趟需进行相邻记录交换的次数为 17 ，在整个冒泡排序过程中共需进行 25 趟后才能完成。 32.在归并排序中，若待排序记录的个数为20，则共需要进行 15 趟归并，在

28、第三趟归并中，是把长度为 24 的有序表归并为长度为 38 的有序表。 33.在直接插入和直接选择排序中，若初始数据基本正序，则选用 1 直接插入排序 ，若初始数据基本反序，则选用 2 直接选择排序 。 34.在堆排序、快速排序和归并排序中，若只从节省空间考虑，则应首先选取 1 堆排序 方法，其次选取 2 快速排序 方法，最后选取 3 归并排序 方法；若只从排序结果的稳定性考虑，则应选取 4 归并排序 ；若只从平均情况下排序最快考虑，则应选取 5 快速排序 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 6 堆排序 方法。 填空题参考答案 1. 1无 2一 3无 4一 2. 1前趋

29、 2一 3后继 4后继 3. 1数据元素 2二元关系 4. 1(i-1)*n+j-1 5. 1一半 6. 1O(n) 2O(1) 7. 1n-1 预先 8. 1变参或函数名 2第i+1个元素 3前移 4减1 9. 1相邻位置 2链接指针 10.1q-next或p-next-next 11.1p-next 2s-data 3t 12.1浪费 2溢出 3 预先分配 4动态存储区 5溢出 13.1O(1) 14.1(1,3,2),(2,1,3),(3,3,-1),(3,4,5) 15.1n-1 16.1n2 +1 17.12 210 311 18.14 23 32 42 5右 6左 19.1中序 2

30、0.155 21.1inorder(bt-left) 2printf(bt-data) 3inorder(bt-right) 22.1度数 2出度数 23.1O(n2 ) 2O(n+e) 24.1ABCDFE 2ABCEFD 25.120 26.11 22 34 48 55 63.7 27.1索引表 2子表或块 3和 28.1越大 2越小 29.12 20 31 30.1(54,72,60,96,83) 31.17 25 32.15 24 38 33.1直接插入排序 2直接选择排序 34.1堆排序 2快速排序 3归并排序 4归并排序 5快速排序 6堆排序 三、判断题 1数据元素是数据的最小单位

31、（ ）。 2数据项是数据的基本单位（ ）。 3顺序存储的线性表可以随机存取（ ）。 4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性， 因此，是属于同一数据对象（ ）。 5在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素（ ）。 6在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构（ ）。 7链表的每个结点中，都恰好包含一个指针（ ）。 *8数组是同类型值的集合（ ）。 /不是集合/ *9使用三元组表示稀疏矩阵的元素，有时并不能节省存储时间（ ）。 *10.线性表可以看成是广义表的特例，如果广义表

32、中的每个元素都是原子，则广义表便成为线性表（ ）。 11.由树转换成二叉树，其根结点的右子树总是空的（ ）。 12.后序遍历树和中序遍历与该树对应的二叉树，其结果不同（ ）。 13.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子 树的前序遍历序列中的最后一个结点（ ）。 14.若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序 遍历序列中的最后一个结点（ ）。 15.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树 的根结点是哪一个（ ）。 16.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理

33、（ ）。 17.有回路的图不能进行拓扑排序（ ）。 18.连通分量是无向图中的极小连通子图（ ）。 /极大/ 19.散列法存储的基本思想是由关键码的值决定数据的存储地址（ ）。 20.散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法（ ）。 21.m阶B-树每一个结点的子树个数都小于或等于m（ ）。 22.中序遍历二叉排序树的结点就可以得到排好序的结点序列（ ）。 23.在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针， 由空变为非空即可（ ）。 24.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素（ ）。 25.对于n个记录的集合进行快速排序，所需要的平均时间是O(nlog2 n)（ ）。 26.对于n个记录的集合进行归并排序，所需要的平均时