山东交通学院数据结构期末考试复习题.docx

《山东交通学院数据结构期末考试复习题.docx》由会员分享，可在线阅读，更多相关《山东交通学院数据结构期末考试复习题.docx（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构（A）复习题一、选择题（每小题2分，共30分）1,计算机算法必须具备输入.输出.（B ）等5个特性。B,可行性.确定性和有穷性D.易读性.安全性和稳定性A.可行性.可移植性和可扩展性C.确定性.有穷性和稳定性.树形结构是数据元素之间存在一种（D ）。A. 一对一关系B.多对多关系 C.多对一关系D. 一对多关系2 .若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂 度（C ）。A.0（log2n）B. 0（1）4 .链表不具有的特点是（A ）。A.可随机访问任一元素C.不必事先估计存储空间5 .栈的操作特点是（C ）oA.随机存取 B.顺序存取6 .队列的

2、删除操作是在（B ）oC.0（n）D.0（n2）B.插入删除不需要移动元素D.所需空间与线性表长度成正比C.先进后出D.先进先出A.队尾B.队头 C.队列任意位置D.队头元素后.下列表示方法中，（A ）不常用来存储稀疏矩阵。A.索引表B.三元组 C.带行指针向量的链接存储D.十字链表.广义表C=（a, （b,c,d）的长度是（A ）oA. 2B. 3C. 4D. 5.在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多（C ）个。A.-1B. 0C. 1D. 2.除第一层外，满二叉树中每一层结点个数是上一层结点个数的（C ）。A. 1/2 倍 B. 1 倍C.2 倍D. 3 倍1L如果求一个

3、连通图中以某个顶点为根的高度最小的生成树，应采用（）。（20 分）A深度优先搜索算法B广度优先搜索算法C求最小生成树的prim算法D拓扑排序算法正确答案:B数据结构-作业4、4.已知图G的邻接矩阵如下所示:oo 66 oo1 55 oooo 300001500005oo3oooo5645oooo26oooo6426oo1）求从顶点1出发的广度优先搜索序列;2）根据prim算法，求图G从顶点1出发的最小生成树，要求表示出其每一步生成过程（用 图的方式表示即可）。（8分）答案：（1）广度优先遍历序列：1； 2, 3, 4; 5;最小生成树（prim算法）12, 65, 43, 20, 58),采用

4、5、5.假定n=8,数组A中8个元素的排序码为（ 36, 25, 48, 直接选择排序，试给出其排序过程。（8分）答案:0)36254812654320581)12254836654320582)12204836654325583)12202536654348584)12202536654348585)12202536436548586)12202536434865587)1220253643485865三、算法设计题(共30分)1.从顺序表中删除其值在给定值S和t之间(要求s小于t)的所有元素。(15分)答：从顺序表中删除其值在给定值s和t之间(要求s小于t)的所有元素。 类型定义：stru

5、ct List EIemType I i st MaxS i ze;int size; 当前线性表长度)；算法：vo i d De I ete3 (L i st& L, EI emType s, EI emType t)从线性表中删除其值在给定值s和t之间的所有元素 (int i=0;wh i I e (i =s)&(L. I isti I eft); 计算右子树的深度i nt dep2=BTreeDepth (BT -r i ght); 返回树的深度i f (dep1dep2)return dep1+1;e I sereturn dep2+1; )数据结构B复习题、选择题（每小题2分，共30

6、分）1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的（B ）和运算的学科。A.结构 D.算法2为了描述n 表不。A.线性表 D.队列3.在一个长度B.关系C.运算23/个人之间的同学关系，可用（C ）结构914/ B.树C,图77个新元素时，需向后移动（B）个元素。A. n-iB. n-i+lC.n-i-1D. i/为n的顺序表中，在第i个元素之前插入一4 .从表中任一结点出发，都能扫描整个表的是（C ）oA.单链表B.顺序表C.循环链表D.静态链表5 .队列的操作特点是（D ）。A.随机存取B.顺序存取C.先进后出D.先进先出6 .一个栈的输入序列为：a, b,

7、 c, d, e,则栈的不可能输出的序列是（C ）。A. a, b, c, d, e B. d, e, c, b, a7 .对稀疏矩阵进行压缩存储目的是（C ）oA.便于进行矩阵运算C.节省存储空间C. d, c, e, a, bD. e, d, c, b, a8 .便于输入和输出I） .降低运算的时间复杂度8 .广义表 0(), (d), (a, (b,c)的长度是(B )oA. 2A. 2B. 3C.4D. 59 . （ A ）的遍历需要先访问根节点，再访问左子树，最后访问右子树。A.前序遍历B.中序遍历C.后序遍历D.层次遍历10 .在一个图中，所有顶点的度数之和等于所有边数的（C ）倍

8、。A. 1/2B. 1C. 2D. 4二、综合分析题（每题8分，共40分）序列。答案： 括号表示法: 前序：A B D 中序：D J G 后序：J G D1、1.已知一棵二叉树如图1所示，写出其括号表示形式，给出其前序.中序.后序遍历A(B(D(,G(J),E(, H),C(,F(I (K, L)(3 分)GJEHCFIKLQ 分)BEHACKL I F (1 分)HEBKLIFCA (1 分)2.由权值为9, 2, 5, 7的四个叶子结点构造一棵哈夫曼树，求该树的带权路径长度。答案:带权路径长度：9*1 +7*2+7*2+2*3+5*3=44.3、3.已知图如下，根据克鲁斯卡尔算法求图G的一

9、棵最小生成树。(要求给出构造过程)答案4、4.假定8个元素的排序码为(36, 25, 48, 12,65,43,20,58),采用气泡排序，试给出其排 序过程。0)36254812654320581)12362548206543582)12203625484365583)12202536434858654)12202536434858655)12202536434858656)12202536434858657)12202536434858655. 5、一个散列存储的数据集合 B=（18, 75, 60, 43, 54, 90, 46, 31, 58, 73, 15, 34）,散列空间 大小为

10、m=13,采用除留余数法。答案：（散列表5分）AAAAAAAAA A0123456789 10 11 1215154A733查找成功时平均查找长度为：=17/12 (3 分)ASL二（8X1+3X2+1 X3） / 12三、算法设计题（共30分）（编写算法前，请给出使用数据结构的类型定义）1.从线性表中删除第i个元素并由函数返回。1、类型定义： struct List EIemType Ii st MaxS i ze;int size; 当前线性表长度1；算法：、i nt Delete I (List& L, int i)(if (iL. size) cerr I ndex i s out r

11、ange! end1 ;ex it (1);ElemType x;x=L. I i st i-1;for (int j=i-1;jI eft)+Count (BT-r i ght)+1; 一、单选题（每题20分，共5道小题，总分值100分）1 .下列表示方法中，（）不常用来存储稀疏矩阵。（20分）A索引表B三元组C带行指针向量的链接存储D十字链表纠错正确答案:A.树形结构是数据元素之间存在一种（）o （20分）A一对一关系B多对多关系C多对一关系D 一对多关系正确答案:D.链表不具有的特点是（）o （20分）A可随机访问任一元素B插入删除不需要移动元素C不必事先估计存储空间D所需空间与线性表长

12、度成正比正确答案:A.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。（20 分）A1/2B1C2D4正确答案:B5,计算机算法必须具备输入.输出.（）等5个特性。（20分）A可行性.可移植性和可扩展性B可行性.确定性和有穷性C确定性.有穷性和稳定性D易读性.安全性和稳定性正确答案:B数据结构-作业一、单选题（每题20分，共5道小题，总分值100分）L广义表C=a（bd）的长度是（）o （20分）A2B3C4D5正确答案:A.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。（20 分）A1/2B1C2D4纠错正确答案:B2 .在长度为n的有序顺序表中，采用二

13、分法查找，在等概率的情况下，查找成功 的平均查找长度是（）o （20分）AO（n2）BO（nlog2n）CO（n）DO（log2n）正确答案:B3 .链表不具有的特点是（）o （20分）A可随机访问任一元素B插入删除不需要移动元素C不必事先估计存储空间D所需空间与线性表长度成正比正确答案:A4 .若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法 的时间复杂度（）o （20分）AO（log2n）BO（1）CO（n）DO（n2）正确答案:C数据结构-作业一、单选题（每题20分，共5道小题，总分值100分）L树形结构是数据元素之间存在一种（）0 （20分）A 一对一关系B多对多关

14、系C多对一关系D 一对多关系正确答案:D2 .若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法 的时间复杂度（）。（20分）AO（log2n）BOCO（n）DO（n2）纠错正确答案:c.在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多（）个。（20 分）A-1B0C1D2正确答案:C4广义表C=（a,（bQd）的长度是（）o （20分）A2B3C4D5正确答案:A5.除第一层外，满二叉树中每一层结点个数是上一层结点个数的（）。（20分）A1/2 倍倍倍倍1 2 3BCD倍倍倍1 2 3BCD正确答案:C 数据结构-作业一、单选题（每题20分，共5道小题，总分值100分

15、）.栈的操作特点是（）o （20分）A随机存取B顺序存取C先进后出D先进先出正确答案:C.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法 的时间复杂度（）o （20分）AO（log2n）BO（1）CO（n）DO（n2）纠错正确答案:C3广义表C=（”b,c,d）的长度是（）o （20分）A2B3C4D5正确答案:A4 .计算机算法必须具备输入.输出.（）等5个特性。（20分）A可行性.可移植性和可扩展性B可行性.确定性和有穷性C确定性.有穷性和稳定性D易读性.安全性和稳定性正确答案:B5 .如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（）o （20 分）A深

16、度优先搜索算法B广度优先搜索算法C求最小生成树的prim算法D拓扑排序算法正确答案:B数据结构-作业一、单选题（每题20分，共5道小题，总分值100分）1 .栈的操作特点是（）o （20分）A随机存取B顺序存取C先进后出D先进先出正确答案:C2 .广义表C=（a,（b,c,d）的长度是（）o （20分）A2B3C4D5纠错正确答案:A3 .如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（）。（20分）A深度优先搜索算法B广度优先搜索算法C求最小生成树的prim算法D拓扑排序算法正确答案:B4 .在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。（20分） A1/2B

17、1C2D4正确答案:B5 .在长度为n的有序顺序表中，采用二分法查找，在等概率的情况下，查找成功的平均查找 长度是()o (20分)AO(n2)BO(nlog2n)CO(n)DO(log2n)正确答案:B数据结构作业一、单选题(每题20分，共5道小题，总分值100分)1 .栈的操作特点是()o (20分)A随机存取B顺序存取C先进后出D先进先出正确答案:C2,若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂 度()。(20 分)AO(log2n)BO(1)CO(n)DO(n2)纠错正确答案:C.堆是一种()排序。(20分)A插入B交换C选择D归并正确答案:C.在长

18、度为n的有序顺序表中，采用二分法查找，在等概率的情况下，查找成功的平均查找 长度是()o (20分)AO(n2)BO(nlog2n)CO(n)DO(log2n)正确答案:B.下列排序算法中，属于不稳定排序的是()o (20分)A气泡排序B快速排序C直接插入排序D归并排序正确答案:B数据结构一作业 一、单选题（每题20分，共5道小题，总分值100分）1 .堆是一种（）排序。（20分）A插入B交换C选择D归并正确答案:C2 .除第一层外，满二叉树中每一层结点个数是上一层结点个数的（）。（20分）A1/2 倍B1倍C2倍D3倍纠错正确答案:C.在长度为n的有序顺序表中，采用二分法查找，在等概率的情况

19、下，查找成功的平均查找 长度是（）o （20分）AO（n2）BO（nlog2n）CO（n）DO（log2n）正确答案:B.广义表C=（a,（b,c,d）的长度是（）。（20分）A2B3C4D5正确答案:A.在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多（）个。（20分）A-1B0C1D2正确答案:C数据结构一作业一、单选题（每题20分，共5道小题，总分值100分）1.队列的删除操作是在（）o （20分）A队尾B队头C队列任意位置D队头元素后正确答案:B2,下列表示方法中，（）不常用来存储稀疏矩阵。（20分）A索引表B三元组C带行指针向量的链接存储D十字链表正确答案:A.计算机算法必须具

20、备输入.输出,（）等5个特性。（20分）A可行性.可移植性和可扩展性B可行性.确定性和有穷性C确定性.有穷性和稳定性D易读性,安全性和稳定性正确答案:B.堆是一种（）排序。（20分）A插入B交换C选择D归并正确答案:C.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂 度（）o （20 分）AO（log2n）BO（1）CO（n）DO（n2）正确答案:C二、综合分析题（每题8分，共40分）1 .已知一棵二叉树的前序序列为：A, B, D, G, J, E, H, C, F, I, K, L中序序列：D, J, G, B, E, H,A, C, K, I,L,Fo画出

21、这棵二叉树。（8分）答案:D E F /G H I/ / J K L2、设某密码电文由8个字母组成，每个字母在电文中出现的频率分别为：7, 19, 2, 6,试为这8个字母设计相应的哈夫曼编码。(8分)答案：8个字母的编码分别为：10 (1011)、32 (11)3、3.画图给出序列(45,啜100/4060/ /)21 28 32/ 1117/ / 56 7 10/ 2319 (00)、21 (01)、2 (10000)、3 (10001). 6 (1001)、7 (1010)、36, 18, 53, 72, 30, 48, 93, 15, 36),构建堆的过程。(8 分)筛72 r良不动o