数据结构试题和答案.doc

数据结构试题和答案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） A3，2，6，1，4，5 B3，4，2，1，6，5 C1，2，5，3，4，6 D5，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；Ds=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)Ae B2e Cn2e Dn22e12. 用某种排序方法对关键字序列（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开始对该图进行深度优先搜索，得到的顶点序列可能为 C 。A1，2，5，4，3； B1，2，3，4，5； C1，2，5，3，4； D1，4，3，2，5。15.假定对元素序列（7，3，5，9，1，12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为 B 。A1，3，5，7，9，12； B1，3，5，9，7，12； C1，5，3，7，9，12； D1，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 (_lownext =s _；r=s; r-next=null;。9. 在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为_2_。10.在线形表的散列存储中，处理冲突有 开放定址法 和 链地址法 两种方法。11. 在一棵二叉树中，第五层的结点数最多为 16 个。12. 用冒泡法对n 个关键码排序，在最好情况下，只需做_n-1_次比较和_0_次移动；在最坏的情况下要做_ n(n-1)/2 _次比较。二、选择题 （共 15小题，每题 1 分，共计 15 分）1在数据结构的讨论中把数据结构从逻辑上分为 （ C） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构2算法分析的两个主要方面是（ A）。A空间复杂性和时间复杂性 B正确性和简明性 C可读性和文档性 D数据复杂性和程序复杂性3一个非空广义表的表头（D） A不可能是子表B只能是子表 C只能是原子D可以是子表或原子4在一个单链表中，若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；Ds=rear-next-next； rear-next-next=s-next； delete s；9线性表采用链式存储时，结点的存储地址（B ） A必须是不连续的 B连续与否均可 C必须是连续的 D和头结点的存储地址相连续10根据集合25，30，16，48，按照依次插入结点的方法生成一棵二叉搜索树，在等概率情况下成功查找一个元素的平均查找长度为（ A ）A 2 B 2.5 C3 D 411. 含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为(D)Ae B2e Cn2e Dn22e12. 对线性表进行折半搜索时，要求线性表必须（ C ）A 以链接方式存储且结点按关键码有序排列 B 以数组方式存储 C 以数组方式存储且结点按关键码有序排列 D以链接方式存储A选择排序B希尔排序 C归并排序D快速排序13. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为(D )排序法。A二路归并 B选择 Cshell D插入14. 若一个图的边集为,则从顶点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. 在以下的叙述中，正确的是(B)。A线性表的线性存储结构优于链表存储结构B二维数组是其数据元素为线性表的线性表C栈的操作方式是先进先出D队列的操作方式是先进后出三、 判断题 （对的打，错的打 共 15 小题，每题 1 分，共计 15 分）1、单链表从任何一个结点出发，都能访问到所有结点。()2、将一棵树转换成二叉树后，根结点没有左子树。 ( )3、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 ( )4、在树结构里，有且仅有一个结点没有前驱；非根结点有且仅有一个双亲，且存在一条从根到该结点的路径（ ）。5、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（ ）6、在AOE网中，关键路径是唯一的。()7、向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。 ( )8、对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。（ ）9、在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧。（ ）10、在散列法中，一个可用散列函数必须保证绝对不产生冲突。（） 11、完全二叉树的某结点若无左孩子，则它必是叶结点。 ( )12、所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。（）13、AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。 ()14、若一个栈的输入序列为123n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai =n-i+1。(i=1,2,.,n)。( )15、在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。（ ）。四、算法填空题： 将折半查找的非递归算法中的空白处进行正确填写。（每空2分，共计 10分） int Search_Bin(SSTable ST,KeyType key) int low=_； high=ST.length； （1） While (low=high) (2) mid=_； (3) if (EQ(key,ST.elemmid.key ) return _； else if (LT(key,ST. elemmid.key) _； (4) else _； (5) return 0；/ Search_Bin五、 综合应用题 （每题10分，共计 40 分）下图为某无向图的邻接表，分别写出从A出发深度优先搜索和广度优先搜索的结果，并画出该无向图的逻辑结构图。12345678910A5B 37C267DE1F3G23H910I8J8深度优先搜索（DFS）结果为：AEBCFGDHIJ广度优先搜索（BFS）结果为：AEBCGFDHIJ这是有着4个连通分量的非连通图。A EB C FG H ID J已知哈希表地址空间为0.14，哈希函数为H(k)=k mod 13，采用线性探测法处理冲突。将下面各数依次存入该散列表中，并求出在等概率下的平均查找长度和失败的查找长度。 240, 29, 345, 189, 100, 20, 21, 35, 3, 208, 78, 99, 45, 350 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14208783502932403451891002021359945 240 mod 13=6 29 mod 13 =3 345 mod 13 =6 (冲突，地址7) 189 mod 13 =7 (冲突，地址8)100 mod 13 =920 mod 13 = 7 (冲突，地址10)21 mod 13 =8 (冲突，地址11)35 mod 13 =123 mod 13 =3 (冲突，地址4)208 mod 13 =078 mod 13 = 0 (冲突，地址1)99 mod 13 = 8 (冲突，地址13)45 mod 13 = 6 (冲突，地址14)350 mod 13 =12