《数据结构试题和答案》由会员分享，可在线阅读，更多相关《数据结构试题和答案（14页珍藏版）》请在金锄头文库上搜索。
1、数据结构试题和答案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在进行直接插入排序
2、时，其数据比较次数与数据的初始排列_有_关；而在进行直接选择排序时，其数据比较次数与数据的初始排列_无_关。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、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，且进栈和出栈可
4、以穿插进行，则可能出现的出栈序列为（B）A3，2，6，1，4，5 B3，4，2，1，6，5C1，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 的二叉树其结
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必须是
6、不连续的 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则所采
7、用的排序方法是（ 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，1
8、2，7。三、 判断题 （对的打，错的打 共 15 小题，每题 1 分，共计 15 分）1、在线性结构中，每个结点都有一个直接前驱和一个直接后继。 （）.2、在堆中，以任何结点为根的子树仍然为堆。 （ ）3、完全二叉树就是满二叉树。 （ ）4、若将一棵树转换成二叉树，则该二叉树的根结点一定没有右子树（ ） 。5、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。 （ ）6、在 AOE 网中，关键路径是唯一的。( )7、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 ( )8、连通分量是无向图中的极小连通子图。 （ ）9、邻接表只能用于有向图的存储，邻接矩阵
9、对于有向图和无向图的存储都适用。 （ ）10、在散列法中，一个可用散列函数必须保证绝对不产生冲突。 （）11、完全二叉树的某结点若无左孩子，则它必是叶结点。 ( )12、在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。 （）13、栈和队列逻辑上都是线性表。 ()14、快速排序是一种稳定的排序方法。( )15、基数分类只适用于以数字为关键字的情形，不适用以字符串为关键字的情形（ ） 。四、算法填空题： 将折半查找的非递归算法中的空白处进行正确填写。（每空 2 分，共计 10 分）int Search_Bin(SSTable ST,KeyType key) int low=1； hig
10、h=_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 在数据结构的讨论中把数据结构从逻
11、辑上分为 （ 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
12、将一个递归算法改为对应的非递归算法时，通常需要使用（ 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=
13、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 以数组方式存储且结点按关键码
