哈尔滨工程大学试卷。
考试科目： 数据结构a 卷。
一、 单项选择题（每空1分，共15分）
1、以下数据结构中，从逻辑结构看，（ 和其他数据结构不同。
a．树b．顺序表 c．链队列d．循环队列。
2、对于链式存储的线性表，查找结点和删除结点的时间复杂度为（ ）
a．o(n) o(n) b．o(n) o(1) c．o(1) o(n) d．o(1) o(1)
3、有六个元素1，2，3，4，5，6的顺序进栈，如果第一个出栈的元素是4，则第三个出栈的元素不可能是（ ）
a．3b．2c．1d．6
4、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）
a．数据的处理方法b．数据元素的类型
c．数据元素之间的关系d．数据的存储方法。
5、顺序表中删除一个元素，需要平均移动的元素个数为（ ）
a．(n-1)/2b．n/2c．(n+1)/2d．n-1
6、在程序实现递归调用的时候，一般要对临时变量和地址要进行保存，这通常是一个（ ）结构。
a．堆栈b．队列 c．数组d．线性表。
7、有n个叶子的哈夫曼树的结点总数为（ ）
a．不确定b．2nc．2n+1d．2n-1
8、设用链表作为栈的存储结构，则出栈操作（ ）
a．必须判别栈是否为满b．必须判别栈是否为空
c．判别栈元素的类型d．对栈不作任何判别。
9、已知一算术表达式的中缀形式为a+b*c-d/e，后缀形式为abc*+de/-，其前缀形式为。
a．-a+b*c/deb．-a+b*cd/e
c．-+abc/ded．-+a*bc/de
10、设树t的度为3，其中度为的结点个数分别为，则t中的叶子数为（ ）
a．11b．12c．13d．14
11、有一个长度为15的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为（ ）
a．43/15b．45/15 c．47/15 d．49/15
12、设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）
a．40，50，20，95b．15，40，60，20
c．15，20，40，45d．45，40，15，20
13、在有向图的邻接表存储结构中，结点的个数是图中边个数的（ ）倍。
a．1b．2c．3d．4
14、下列关于aoe网的叙述中，不正确的是（ ）
a．关键活动不按期完成就会影响整个工程的完成时间。
b．任何一个关键活动提前完成，那么整个工程将会提前完成。
c．所有的关键活动提前完成，那么整个工程将会提前完成。
d．某些关键活动提前完成，那么整个工程将会提前完成。
15、当初始关键字基本有序的情况下，下列哪种排序方法的时间复杂度受到了影响（ ）
a．起泡排序 b．简单选择排序 c．归并排序 d．堆排序。
二、 判断题（每空1分，共10分）
1、利用prim算法构造最小生成树，较适用于稀疏图的求解。
2、数据项是数据处理的最小单位。
3、顺序存储结构中，删除数据元素的操作比较容易。
4、两个串相等，当且仅当其长度相等。
5、中序线索二叉树中，任意一个结点都只有一个前驱和后继。
6、在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。
7、有向无环图的拓扑序列是唯一的。
8、hash表的平均查找长度与处理冲突的方法无关。
9、图的广度优先遍历要借助于队列来实现。
10、在初始有序的前提下，快速排序的性能更优了。
三、 填空题（每空1分，共10分）
1、字符串“abcdef”的子串有___个。
2、循环队列存储在数组a[0..m]中，则入队时的尾指针操作为___
3、由9个顶点构成的无向非连通图，边的数量最多为___
4、在5阶5层b树中，最少的关键字的个数为___
5、广义表a((a,b),(c,d),(e)),f)，取出原子e的操作是___
6、在图的存储结构里面，图的存储结构相对来说，更适合于稀疏图的存储。
7、有一个8阶对称阵a[0..7][0..7]，采用压缩存储方式进行存储 (以行序为主序)，首地址为100，每个元素所占的单元个数为3，则a[6][6]的地址是___
8、一棵完全二叉树有521个结点，则其叶子结点个数为___
9、在一个aoe网中，可以通过___方法判断图中是否有环。
10、如果按关键码值递减的顺序依次将n个关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为___
四、 应用题（每题7分，共35分）
1、若一棵二叉树的先序序列为abchidefgklj，中序序列为bhciaefdlkgj。请画出这棵二叉树，并将其转换为对应的森林。
2、对以下关键字序列建立哈希表：(12, 32, 16, 19, 24, 27, 56, 67, 34)，哈希表的表长为12，用二次探测再散列法处理冲突；请给出哈希函数，画出此哈希表，并计算在等概率情况下查找成功的平均查找长度。
3、给出一组关键字(45, 27, 22, 17, 19, 30, 52, 50)，写出建大顶堆过程（包括每个元素的筛选过程）。
4、给出一组关键字：(25，18，17，30，12，29，16，20，26)分别写出按快速排序方法进行排序时的变化过程。
5、对给定的一组关键字序列(5, 6, 10, 8, 9, 7, 4, 2)，构造一棵平衡二叉树并画图。
五、算法设计题（每题15分，共30分）
1、在一个单链表l中，设计算法用指针p返回单链表中数据域最大的结点，并删除该结点。
2、请设计算法求元素x所在结点的深度。
2019数据结构
下面我们来解析一下知识点。线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入 删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。栈 队列和数组可以考查的知识点相比链表来说要多一些。最基本的，是栈与...
数据结构2019级数据结构大作业
2011级数据结构大作业。1 公园导游图。给出一张某公园的导游图，用图的顶点表示各个景点 景点个数大于等于30 每个景点有属性值 h，t，c 其中h表示游览完成这个顶点给游客带来的happiness，t表示游览这个景点需要的时间，c表示游览这个景点需要的费用，顶点之间的边表示路径 边具有属性值w，表...
数据结构2019辅导
一 简单题 1 在单链表中，头结点是必不可少的？2 链队列q为空的条件是什么？3 如果一个二叉树中没有度为1的结点，它是不是完全二叉树？4 具有n个顶点和n 1条边的无向连通图是否存在环路？5 判断一个有向图是否存在回路的方法有哪些？6 在一棵二叉排序树t中，先插入结点n，然后再删除结点n，得到的新...