数据结构考试题

《数据结构考试题》由会员分享，可在线阅读，更多相关《数据结构考试题（25页珍藏版）》请在装配图网上搜索。

1、一、填空题：（1分*10=10分）1）线性结构中元素之间存在1对1关系，树形结构中元素之间存在二对多，图形结构中元素之间存在多对多 关系。2）顺序表中，逻辑上相邻的元素物理位置一定 相邻；单链表中逻辑上相邻的元素位置不一定 相邻。3）线性表、栈和队列都是 线性 结构。对于栈只能在 栈顶 位置插入和删除元素；对于队列只能在 队尾 位置插入和在 对 头位置删除元素。4）由三个结点构成的二叉树，共有 5种不同的结构。5）具有10个顶点的无向图，边的总数最多为10。6）评价算法的优劣通常主要考虑算法的时间复杂度 和空间复杂度 这两方面。7）链式存储的特点是利用指针来表示数据元素之间的逻辑关系。8）线性

2、表常见的存储结构有顺序存储结构和链式 存储结构。9）栈的特点是，队列的特点是先进先出。10）对于二叉树来说，第i层上最多有 2i-i_个节点。11）哈夫曼树是指 J弋权路径长度最短的二叉树。12）构造n个结点的强连通图，至少有 条弧。13）常见的数据结构有集合结构、线性 结构、树形 结构、图形 结构。14）计算机程序中加工处理的基本单位是数据元素，数据中不可再分割最小单位是数据项 。15）链式存储的特点是利用指针来表示数据元素之间的逻辑关系。16）栈的特点是，队列的特点是 先进先出。17）一棵深度为k的满二叉树的结点总数为 2k-i。18）在有n个顶点的有向图中，每个顶点的度最大可达2（n-1

3、）。19）线性结构中元素之间存在1对1关系，树形结构中元素之间存在二对多 关系，图形结构中元素之间存在多对多 关系。20）计算机程序中加工处理的基本单位是数据元素，数据中不可再分割最小单位是数据项 。21）线性表常见的存储结构有顺序 存储结构和链式 存 储结构。22）栈的特点是，队列的特点是先进先出。23）在一颗二叉树中，度为零的结点的个数为n0，度为2的结点的个数为 n2，则有 n0=n2+1。24） n个顶点的连通图至少要有n-1 条边。二、单选题：（2分*10=20分）1、 数据结构中图形结构中元素对应关系为（C ）A. 1对1 B. 1对多 C.多对多 D.无关系2、 数据处理的基本单

4、位是（A ）A. 数据元素C.数据类型3、用链表表示线性表的优点是A.便于进行插入和删除操作B. 数据项D.数据变量（A ）B. 便于随机存取C. 占用的存储空间较顺序表少D.元素的物理顺序与与逻辑顺序一致4、在一个长度为n的顺序表中，若要删除第i （1W忍n）个元素，则需向前移动（C ）个元素。A. n-i+1B. n-i-1 C. n-iD. i5、对具有n个结点的线性表进行插入或删除操作，所需的算法时间复杂度为（D ）A. O（n2）B. O（nlog2n） C. O（log2n）D. O（n）6、对于栈操作数据的原则是（B）A.先进先出B后进先出C后进后出D-不分顺序7、已知一棵完全二

5、叉树的结点总数为9个，则最后一层的结点数为（B ）A.1 B.2C.3D.48、一个n个顶点的连通无向图，其边的个数至少为（A）A. n-1B. nC. n+1D. nlogn；9、要连通具有n个顶点的有向图，至少需要（B ）条边。A. n-lB. nC. n+lD. 2n10、某二又树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则前 序序列遍历为（D）A.ACBEDB.DECAB C.DEABC D.CEDBA11、从逻辑上可以把数据结构分为（C ）两大类。A.动态结构、静态结构B.顺序结构、链式结构C. 线性结构、非线性结构D.初等结构、构造型结构12、数据结构中线性结构中元素对

6、应关系为（A ）A. 1对1 B. 1对多 C.多对多 D.无关系13、数据处理的基本单位是（A ）。A.数据元素B.数据项C.数据类型D.数据变量14、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是: （B ）。A. p-next=s;s-next=p-next; B.s-next=p-next;p-next=s;C. p-next=s;p-next=s-next; D.p-next=s-next;p-next=s;15、在一个长度为n的顺序表中，若要删除第i(1Wn)个元素，则需向前移动（C）个元素。A. n-i+1B. n-i-1 C. n-iD. i16、对具有n个结点的线

7、性表进行插入或删除操作，所需的算法时间复杂度 为（D ）A. O（n2）B. O（nlog2n） C. O（log2n）D. O（n）17、栈和队列的共同点是（C ）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点18、某二又树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则前序序列遍历为（D ）A.ACBEDB.DECAB C.DEABC D.CEDBA19、一个n个顶点的连通无向图，其边的个数至少为（A ）。A. n-1B. nC. n+1D. nlogn；20、用折半查找表的元素的速度比用顺序法（D ）A.必然快 B.必然慢 C.相等 D.不能确定

8、21、数据结构中树型结构中元素对应关系为（B ）A. 1对1B. 1对多 C.多对多 D.无关系22、算法分析的两个主要方面是（D ）。A.正确性和简单性B.可读性和文档性C.数据复杂性和程序复杂性 D.时间复杂度和空间复杂度23、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是: （B ）。A. p-next=s;s-next=p-next; B.C. p-next=s;p-next=s-next; D.24、栈和队列的共同点是（CA.都是先进先出s-next=p-next;p-next=s;p-next=s-next;p-next=s;）。B.都是先进后出D.没有共同点C.只允许

9、在端点处插入和删除元素25、输入序列为ABC，可以变为CBA时，经过的栈操作为（B ）A. push,pop,push,pop,push,popB. push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,pop,push,push,pop,pop26、已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（B ）。A.1 B.2 C.3 D.427、在一棵二叉树上第3层上的结点数最多为（B ）。A.2B.4 C.6 D.88、设无向图的顶点个数为n，则该图最多有（BA. n-1B. n（n-1）/2 C. n（n+1）/

10、229、用折半查找表的元素的速度比用顺序法（ D ）C.相等是稳定的。B.快速排序，D.归并排序，）条边。D.0A. 必然快 B.必然慢30、下列排序算法中，其中（DA.堆排序，冒泡排序C.直接选择排序，归并排序31、线性表若采用链式存储结构时 （D）A、 必须是连续的D.不能确定堆排序冒泡排序要求内存中可用存储单元的地址B、部分地址必须是连续的C、一定是不连续的D、连续不连续都可以32、 判定一个循环队列Q（最多元素为MAX）为满队列的条件是（C ）A、Q-front = = Q-rearB、Q-front != Q-rearC、Q-front = =（Q-rear+1）%MAXD、Q-fr

11、ont != （Q-rear+1）%MAX33、在一个单链表中，已知结点P，若在P结点后插入S结点，则执行（A ）A、s-next = p-next ; p-next=s;B、p-next=s-next ; s-next=p;C、p-next=s ; s-next=p-next;D、以上均不正确34、 按照二叉树的定义，具有3个结点的二叉树有几种（C ）A、3B、4C、5D、635、 深度为 5 的二叉树至多有多少个结点(B)A、16B、31C、32D、4836、图的深度优先搜索算法类似于二叉树的哪种遍历(A)A、先序遍历B、中序遍历C、后序遍历D、按层次遍历37、 在一个图中，所有顶点的度数

12、之和等于所有边数的几倍（C ）A、1/2 B、1C、2 D、438、到目前为止哪种排序是平均速度最大的一种排序方法 （B ）A、直接插入排序B、快速排序C、冒泡排序D、希尔排序39、首先访问该结点，然后访问结点的左子树，最后访问结点的右子树，这 种遍历方式称为（A）A、先序遍历B、后序遍历C、中序遍历D、层次遍历40、一组记录的关键字为46, 79, 56, 38, 40，84，则利用冒泡排序的方法，经第一趟排序后的结果为（B ）A、38，40，46，56，79，84 B、46，56，38，40，79，84C、40，38，46，56，79，84 D、40，38，46，84，56，79三、判断题

13、：（1分*10=10分）1、 线性表中的每个结点最多只有一个前驱和一个后继。（V ）2、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 rear=front（V ）3、 栈操作数据的原则是先进先出。（X ）4、在任意一棵二叉树中，终端结点的个数等于度为2的结点个数加1。）5、一个栈的输入序列是12345,则栈的输出序列不可能是43512。（ V ）6、 串是一个有穷字符序列。（V ）7、 在满二叉树中，存在度为1的结点。（X ）8、 根据任意一种遍历序列即可唯一确定对应的二叉树。（X ）9、 深度为K的二叉树至多有2K-1个结点。（V ）10、 图的拓扑排序是唯一

14、的。（X ）11、 一个算法可以有零个输入或输出。（ X ）12、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（X ）13、 队列操作数据的原则是先进先出。（V ）14、 空串与空格串是一个概念。（X ）15、一个栈的输入序列是12345,则栈的输出序列可以是43512。（ X ）16、在任意一棵二叉树中，终端结点的个数等于度为2的结点个数加1（ V ）17、 由树转化为二叉树，其根结点的右子树总是空的。（V ）18、一个有n个结点的图，最少有1个连通分量，最多有n个连通分量。（V）19、用折半查找表的元素的速度一定比用顺序法快。（X）20、N个顶点的图或网的最小

15、生成树有N-1条边。（V）21、 一个算法可以有零个输入或输出。（ X ）22、队列操作数据的原则是先进先出。（V）23、栈和队列逻辑上都是线性表。（V）24、空串与空格串是一个概念。（X）25、用折半查找表的元素的速度一定比用顺序法快。（X）26、由树转化为二叉树，其根结点的右子树总是空的。（V）27、在满二叉树中，存在度为1的结点。（X）28、根据任意一种遍历序列即可唯一确定对应的二叉树。（X）29、一个n个顶点的连通无向图，其边的个数至少为n-1条。（V）30、图或网的生成树是唯一的。（X）31、线性表中的每个结点最多只有一个前驱和一个后继。（V）32、线性的数据结构可以顺序存储，也可以

16、链接存储。非线性的数据结构只能链接存储。（X）33、栈和队列逻辑上都是线性表。（V）34、空串与空格串是一个概念。（X）35、一个栈的输入序列是12345,则栈的输出序列可以是43512。（ X）36、串是一个有穷字符序列。（V）37、 满二叉树一定是完全二叉树。（V ）38、 希尔排序与直接插入排序都是稳定的排序。（X ）39、 深度为K的二叉树至多有2K-1个结点。（V ）40、 图或网的生成树是唯一的。（X ）五、编程（10分）1. 将下图中的二叉树先序、中序和后序遍历，写出遍历序列，并还原成森林。解：还原后的森林为:先序：ABCEDFGHIJK 中序：BECDAGHFJIK 后序：ED

17、CBHGJKIFA2. 已知一个电文字符集中有6个字符A, B, C, D, E, F,它们使用的 频率为0.06, 0.02, 0.04, 0.03, 0.07, 0.12,设计一个哈夫曼编码。（提示：哈 夫曼树的每个分支左分支设为0,右分支设为1,要求同层中叶子结点权值从左 到右，从小到大）。解：将频率值乘以100得：6,2,4,3,7,12。设哈夫曼树的左分支为0,右 分支为1,则求得的哈夫曼树如下图：所以哈夫曼编码为：字符频率编码A0.0600B0.021010C0.04100D0.031011E0.0701F0.12113. 已知下图G, （1）画出G的邻接矩阵；（2）分别以顶点和为

18、开始，写出G的深度优先遍历序列和广度优先遍历序列。解：（1）该图的邻接矩阵为:0 11110、01 0 0 0 1 0010 0 111010 10 0 011110 0 000 0 1 0 0 010 0 0 1 0 10（2）开始对该图进行深度优先搜索的遍历序列为： 开始对该图进行广度优先搜索的遍历序列为： 开始对该图进行深度优先搜索的遍历序列为：开始对该图进行广度优先搜索的遍历序列为：4. 已知下图为带权图，写出用普里姆算法求该图的最小生成树过程并画出最小生成树。解：最小生成树的求解过程为:5.用迪杰斯特拉算法,求下图中从顶点0到其它各顶点的最短路径。始点终点八、最短路径路径长度01(0

19、,2,1)702(0,2)103(0,4,3)504(0,4)30(0,4,3,5)6.已知一组记录为46, 74, 53, 进行排序时的每一趟排序结果。解：初始状态：4674第一趟排序结果：4653第二趟排序结果：4614第三趟排序结果：1426第四趟排序结果：1426第五趟排序结果：1426第六趟排序结果：14（2614, 26, 38, 65,给出采用冒泡排序法531426386514263865(74)263853(6574)3846(536574)38(46536574)(3846536574)3846536574)7. 将下图中的森林转换成一棵二叉树，并对这棵二叉树进行先序、中序和

20、 后序遍历，写出其遍历序列。中序：BECDAGHFJIK后序：EDCBHGJKIFA8. 已知一个电文字符集中有8个字符A, B, C, D, E, F, G, H,它们 使用的频率为0.04, 0.21, 0.06, 0.07, 0.15, 0.18, 0.12, 0.03,设计一个哈夫 曼编码。（提示：哈夫曼树的每个分支左分支设为0,右分支设为1,要求同层中 叶子结点权值从左到右，从小到大）。解：将频率值乘以100得：4, 21, 6, 7, 15, 18, 12, 3。设哈夫曼树 的左分支为0,右分支为1,则求得的哈夫曼树如下图：所以哈夫曼编码为:字符频率编码A0.040101B0.21

21、10C0.061100D0.071101E0.15111F0.1800G0.12011H0.0301009. 用迪杰斯特拉算法，求下图中从顶点0到其它各顶点的最短路径。解：始点终点八、最短路径路径长度(0,2,1)2(0,2)93(0,4,3)354(0,4)205(0,4,3,5)4710.已知序列35,24,16,78,22,15,29,70,54,31,20,90,77,24,(1) 画出用这个序列生成的二叉排序树。(2) 在原图中如果删除15,有几种情况，将删除后二叉排序树画出。(3) 在原图中如果删除22,有几种情况，将删除后二叉排序树画出。(4) 在原图中如果删除78,有几种情况，

22、将删除后二叉排序树画出。解：（1）生成的二叉排序树为:（2）在原况，直接将15中如果删除15,因为15为叶子结点，删除只有一种情 寸除即可。删除后的二叉排序树如下图：（3）在原图中如果删除22,因为22只有一个左子树，删除只有一种情 况，用它的左子树根结点20替换22即可。删除后的二叉排序树如下图：（4）在原图中如果删除78,因为78有两个子树，删除有两种情况：第 一种是用它左子树中最大值77来替换它；第二种方法是用它右子树中最小 值90来替换它。删除后的二叉排序树如下图：11.假定对有序表3,4,5,7,24,30,42,54,63,72,87,95进行折半查找，试回答下 列问题：(1) 画

23、出描述折半查找过程的判定树；(2) 若查找元素54,需依次与那些元素比较？(3) 若查找元素90,需依次与那些元素比较？解：(1)二叉判定树为：(2) 若查找元素54,则需要与30、63、42、54比较。(3) 若查找元素90,则需要与30、63、87、95比较。12.设有一组关键字9,1,23,14,55,20,80,27,采用哈希函数：H (key) =key % 7，表长为10,用开放地址法的二次探测再散列方法 Hi=(H(key)+di) % 10(di=12,22,32,)解决冲突。解：H(9)=9%7=2H(1)=1%7=1H(23)=23%7=2 (冲突)产生冲突，H= (H(2

24、3)+d ) %10=(2+1)%10=3H(14)=14%7=01H(55)=55%7=6H(20)=20%7=6 (冲突)产生冲突，H = (H(20)+d )%10=(6+1)%10=7H(80)=80%7=3 (冲突)1产生冲突，H = (H(80)+d )%10=(3+1)%10=4H(27)=27%7=6 (冲突)产生冲突，H = (H(27)+d )%10=(6+1)%10=7 (仍冲突)仍有冲突，H1=(H(27)+d1)%14=(6-1)%10=5所以哈希表面下图：201234567891419238027552013.将下图中的二叉树先序、中序和后序遍历，写出遍历序列，并还

25、原成森 林。解：还原后的森林为:先序：ABCEDFGHIJKLMN中序：BECDAGIJHFLMNK 后序：EDCBJIHGNMLKFA14.给定一组权值3, 6, 9，14, 8, 5, 4，19, 25，试设计相应的哈夫曼 树，并求其带权路径长度WPL。解：WPL=268哈夫曼树如下：15.已知下图，画出该图的（1）邻接矩阵和（2）分别以顶点和为起点 进行深度优先遍历。（3）分别以顶点和为起点进行广度优先遍历解：（1）该图的邻接矩阵为:0 10 0 1 10 110 0 10 10 0 110 1 10 0 10 11011（2）开始对该图进行深度优先搜索的遍历序列为：开始对该图进行深度优

26、先搜索的遍历序列为：（3）开始对该图进行广度优先搜索的遍历序列为：开始对该图进行广度优先搜索的遍历序列为：16.已知图下图，（1）写出该图的邻接矩阵；（2）写出全部拓扑排序;解：(1)该图的邻接矩阵为:023MMM/IMM0M5MMMMA=MM0310MMMMMM0M4MMMMMM0M3MMMMM10M6MMMMMM03MMMMMMM0（2）拓扑排序的序列为：V1,V2,V3,V4,V6,V5,V7,V8V1,V3,V2,V4,V6,V5,V7,V817.已知序列32, 45, 16, 7, 28, 40, 30, 19, 7, 56, 43, 78,(1) 画出用这个序列生成的二叉排序树。(

27、2) 在原图中如果删除40,有几种情况，将删除后二叉排序树画出。(3) 在原图中如果删除45,有几种情况，将删除后二叉排序树画出。解：(1)二叉排序树为：(2)删除40时有一种情况，用其子树根结点43代替，如下图:18.已知一组记录为46, 74, 53，14, 26, 38, 65，给出采用直接插入排 序法进行排序时的每一趟排序结果。解：r0r1r2r3r4r5r6r7初始状态：(46)745314263865第趟插入：74(4674)5314263865第二趟插入：53(465374)14263865第三趟插入：14(14465374)263865第四趟插入：26(1426465374)3

28、865第五趟插入：38(142638465374)65第六趟插入：65(14263846536574),用其右子树中的最小值56代替如下右图。如下左图。第二种，,19.将下图中的森林转换成一棵二叉树并对这棵二叉树进行先序、中序和后序遍历，写出遍历序列。先序：ABCEDFGHIJKLMN中序：BECDAGIJHFLMNK后序：EDCBJIHGNMLKFA20.已知一个电文字符集中有8个字符，它们使用的频率为0.04, 0.26, 0.06, 0.09, 0.15, 0.21, 0.12, 0.07,设计一个哈夫曼编码。（提示：哈夫曼树的每个 分支左分支设为0,右分支设为1,要求同层中叶子结点权值

29、从左到右，从小到 大）。解：将频率值乘以 100 得：4, 26, 6, 9, 15, 21, 12, 7）设哈夫曼树的左分支为0,右分支为1,则求得的哈夫曼树如下图：所以哈夫曼编码为： 字符 频率 编码 A0.040100B0.2610C0.060101D0.091111E0.15110F0.2100G0.21011H0.07111021.画出该图的(1)邻接矩阵和(2)邻接表。(3)并根据你画出的邻接表，对该图进行深度优先搜索和广度优先搜索，写出两种搜索的序列。(1)该图的邻接矩阵为:解：(2)该图的邻接表为:0 1 2 3 4(3)对该图进行深度优先搜索的遍历序列为：V1, V2, V3

30、, V4, V5 对该图进行深度优先搜索的遍历序列为：V1, V2, V3, V5, V422.已知下图为带权图，写出用普里姆算法求该图的最小生成树过程并画出 最小生成树。解：最小生成树为:323.已知序列32, 45, 16, 7, 28, 40, 19, 24, 8, 25, 19, 16, 56,(1) 使用这些权值生成一棵二叉排序树。(2) 在原图中删除45时，有几种情况并画出删除之后的二叉排序树。(3) 在原图中删除28时有几种情况并画出删除之后的二叉排序树。解：(1)二叉排序树为：(2)删除45时有两种情况，第一种，用其左子树中最大值代替，如下 左图。第二种，用其右子树中的最小值代

31、替，如下右图。(3) 删除28时有一种情况，用其子树根结点代替，如下图: ；40,56 ：16；24远24.设有一组关键字9, 2, 23, 15, 55, 20, 84, 27, 68, 11, 10, 73, 采用哈希函数为H(key)=key % 13。采用开放地址法的线性探测再散列方法解决 冲突。在014的散列地址方向对该关键字序列构造哈 希表。(提示： di=(H(key)+i) % 14 , i=1,2,3,13)解：由题意计算哈希地址为：H(9)=9%13=9H(2)=2%13=2H(23)=23%13=10H(15)=15%13=2产生冲突，H = (H(15)+d )%14=(2+1)%14=3H(55)=55%13=31产生冲突，H = (H(55)+d )%14=(3+1)%14=4H(20)=20%13=71H(84)=84%13=6H(27)=27%13=1H(68)=68%13=3产生冲突，H = (H(68)+d )%14=(3+1)%14=4仍有冲突，H：=(H(68)+d：)%14=(3+2)%14=5H(10)=10%13=102产生冲突，H = (H(10)+d )%14=(10+1)%14=11H(73)=73%13=81所以哈希表如下图：012345678910 11 12 13