数据结构试题和答案A卷一、填空题(共8 小题,每空 1 分,共计20 分)1.栈和队列都是_线性_结构;对于栈只能在_栈顶_插入和删除元素;对于队列只能在_队尾_插入元素和在_队头_删除元素。
2.一个广义表中的元素分为单元素和表元素两类。
3.对于一个长度为n的顺序存储的线形表,在表头插入元素的时间复杂度为__ O(n)_______,在表尾插入元素的时间复杂度为____ O(1)_______。
5.在一棵具有n个结点的二叉树中,所有结点的空子树个数等于 n+1 。
6.若一个图的顶点集为{a,b,c,d,e,f},边集为{(a,b),(a,c),(b,c),(d,e)},则该图含有___3____个连通分量。
7.在进行直接插入排序时,其数据比较次数与数据的初始排列__有___关;而在进行直接选择排序时,其数据比较次数与数据的初始排列__无___关。
8.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为3的希尔排序,则得到的结果为(15,02,21,24,26,57,43,66,80,48,73)。
9. 在有序表(12,24,36,48,60,72,84)中折半查找关键字72时所需进行的关键字比较次数为__2___。
10.在线形表的散列存储中,处理冲突有开放定址法和链地址法两种方法。
11.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树中有______12______ 个叶子的结点。
12.设二叉树结点的先根序列为ABDECFGH,中根序列为DEBAFCHG,则二叉树中叶子结点是_ E,F,H ___。
13.若由3,6,8,12,10作为叶子结点的值生成一棵哈夫曼树,则该树的高度为 4 ,带权路径长度为 87 。
二、选择题(共15小题,每题 1 分,共计15 分)1.算法指的是( D )A.计算机程序 B.解决问题的计算方法C.排序算法 D.解决问题的有限运算序列2.如下陈述中正确的是(A )A.串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母D.空串就是空白串3.若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为( B )A.3,2,6,1,4,5 B.3,4,2,1,6,5C.1,2,5,3,4,6 D.5,6,4,2,3,14.在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行( B ) A. s->next=p;p->next=s B. s->next=p->next;p->next=sC. s->next=p->next;p=s D. p->next=s;s->next=p5.在按层次遍历二叉树的算法中,需要借助的辅助数据结构是(A)A.队列B.栈C.线性表D.有序表6.图的邻接矩阵表示法适用于表示(C)A.无向图B.有向图C.稠密图D.稀疏图7.深度为5的二叉树其结点数最多为 C 。
A、16;B、30;C、31;D、32。
8.设单循环链表中结点的结构为(data,next),且rear是指向非空的带表头结点的单循环链表的尾结点的指针。
若想删除链表第一个结点,则应执行下列哪一个操作( D )A. s=rear; rear=rear->next; delete s;B. rear=rear->next; delete rear;C. rear=rear->next->next; delete rear;D.s=rear->next->next; rear->next->next=s->next; delete s;9.线性表采用链式存储时,结点的存储地址( B )A.必须是不连续的 B.连续与否均可C.必须是连续的 D.和头结点的存储地址相连续10.线性链表不具有的特点是(A )。
A.随机访问 B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素 D.所需空间与线性表长度成正比11. 含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D )A. e B.2e C.n2-e D.n2-2e12.用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进行排序时,序列的变化情况如下:20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84则所采用的排序方法是( D )A.选择排序B.希尔排序 C.归并排序D.快速排序13. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的 D 。
A.先序遍历; B.中序遍历;C.后序遍历; D.按层遍历。
14. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行深度优先搜索,得到的顶点序列可能为 C 。
A.1,2,5,4,3; B.1,2,3,4,5;C.1,2,5,3,4; D.1,4,3,2,5。
15.假定对元素序列(7,3,5,9,1,12)进行堆排序,并且采用小根堆,则由初始数据构成的初始堆为 B 。
A.1,3,5,7,9,12; B.1,3,5,9,7,12;C.1,5,3,7,9,12; D.1,5,3,9,12,7。
三、判断题(对的打√,错的打×共15 小题,每题 1 分,共计15 分)1、在线性结构中,每个结点都有一个直接前驱和一个直接后继。
(×).2、在堆中,以任何结点为根的子树仍然为堆。
(√)3、完全二叉树就是满二叉树。
(×)4、若将一棵树转换成二叉树,则该二叉树的根结点一定没有右子树(√)。
5、线性的数据结构可以顺序存储,也可以链接存储。
非线性的数据结构只能链接存储。
(×)6、在AOE网中,关键路径是唯一的。
(×)7、哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近。
(√)8、连通分量是无向图中的极小连通子图。
(×)9、邻接表只能用于有向图的存储,邻接矩阵对于有向图和无向图的存储都适用。
(×)10、在散列法中,一个可用散列函数必须保证绝对不产生冲突。
(╳)11、完全二叉树的某结点若无左孩子,则它必是叶结点。
(√)12、在采用线性探测法处理冲突的散列表中,所有的同义词在表中相邻。
(×)13、栈和队列逻辑上都是线性表。
(√)14、快速排序是一种稳定的排序方法。
(×)15、基数分类只适用于以数字为关键字的情形,不适用以字符串为关键字的情形(×)。
四、算法填空题:将折半查找的非递归算法中的空白处进行正确填写。
(每空2分,共计10分)int Search_Bin(SSTable ST,KeyType key){ int low=1;high=_ST.length_________;(1)While (__low<=high _____________) { (2)mid=_(low+high)/2________________;(3)if (EQ(key,ST.elem[mid].key ) return mid;else if (LT(key,ST. elem[mid].key)) _ high=mid-1___________;(4)else __low=mid+1________________;(5) }return 0;}// Search_Bin五、综合应用题(每题10分,共计40 分)1.已知一个连通图的边集为{(1,2)3,(1,3)6,(1,4)8,(2,3)4,出发,求出此图的深度和广度(2,5)10,(3,5)12,(4,5)2},若从顶点V1优先遍历序列,按照普里姆算法求最小生成树并画出,写出依次得到的各条边.1.深度优先:1 2 3 5 4 2分广度优先: 1 2 3 4 5 2分普里姆算法依次得到的各边(1,2)3, (2,3)4, (1,4)8, (4,5)2 2分最小生成树如图所示:4分2.一个待散列存储的数据集合为{32,75,29,63,48,94,25,46,18,70,56},散列地址空间为HT[13],若采用除留余数法构造散列函数和链接法处理冲突,试求出每一元素的散列地址,画出最后得到得到的散列表,求平均查找长度.32 mod 13=6 75 mod 13=10 29 mod 13=3 63 mod 13=11 48 mod 13=9 94 mod 13=325 mod 13=12 46 mod 13=7 18 mod 13=5 70 mod 13=5 56 mod 13=4 2分平均查找长度为:ASL=(9*1+2*2)/10=13/11 2分3.在一个空A VL 树内,依次插入关键字(46,15,20,35,28,58,18,50,54) ,分别画出46,15,20,35插入完和所有关键字都插入完的A VL 树。
,并求出查找成功状态下的平均查找长度 (10分)平均查找长度:(1×1+2×2+4×3+2×4)/9=25/9 2分4. 欲将无序序列(24, 79, 13, 36, 70, 96, 12, 10, 36*, 49, 100, 27)中的关键码按升序重新排列,请写出快速排序第一趟排序的结果序列。
另外请画出堆排序(小根堆)的初始堆和结束堆。
①快速排序第一趟排序的结果序列为:(注意要按振荡式逼近算法实现) 5分② 堆排序的初始堆如下,注意要从排无序堆开始,从最后一个非终端结点开始,自下而上调整,而且要排成小根堆! 初始堆序列为:无序堆 有序初始堆6 分2分4分结束堆1B卷一、填空题(共8 小题,每空 1 分,共计20 分)1.数据的逻辑结构被分为集合、线性结构、树形结构和图状结构4种。
2.链表最后一个结点的指针指向链表的头节点,这样的链表称为_循环_链表;链表的每个结点都有两个指针域,一个指针指向前一结点,另一个指针指向后一结点,这样的链表称为_双向_链表。
3.某二叉树结点的中序遍历序列为A,B,C,D,E,F,G,后序遍历序列为B,D,C,A,F,G,E,则该二叉树结点的前序遍历序列为__ E; A;C;B;D; G; F ___,该二叉树对应的树林包括___ 2 _____棵树。
5.按照锦标赛排序的思想,决出8个选手的名次排列,共需要进行___11___场比赛(考虑最坏的情况)。