二○○五～二○○六学年第一学期期末考试卷。
供 2003 级各系各专业各班使用）
数据结构试题a
总分合计人（签名总分复核人（签名。
复查总分复查人（签名。
一选择题(每空2分，共20分)
1． 设一组权值集合w=，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ ）
(a) 20 (b) 30 (c) 40 (d) 45
2．执行一趟快速排序能够得到的序列是（ ）
(a) [41，12，34，45，27] 55 [72，63]
(b) [45，34，12，41] 55 [72，63，27]
(c) [63，12，34，45，27] 55 [41，72]
(d) [12，27，45，41] 55 [34，63，72]
3．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）
a) head==0 (b) head->next==0
c) head->next==head (d) head!=0
4．时间复杂度不受数据初始状态影响而恒为o(nlog2n)的是（ ）
(a) 堆排序 (b) 冒泡排序 (c) 希尔排序 (d) 快速排序。
5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ）
(a) 空或只有一个结点 (b) 高度等于其结点数。
(c) 任一结点无左孩子 (d) 任一结点无右孩子。
6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）
(a) 堆排序 (b) 冒泡排序 (c) 快速排序 (d) 希尔排序。
7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（ ）
(a) 3 (b) 4 (c) 5 (d) 6
8．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ ）
(a) o(n) (b) o(n2) (c) o(n1/2) (d) o(1og2n)
9．二路归并排序的时间复杂度为（ ）
(a) o(n) (b) o(n2) (c) o(nlog2n) (d) o(1og2n)
10. 深度为k的完全二叉树中最少有（ ）个结点。
(a) 2k-1-1 (b) 2k-1 (c) 2k-1+1 (d) 2k-1
(a) 4 (b) 5 (c) 6 (d) 7
二填空题（每小题3分，共30分）
1．for(i=1，t=1，s=0；i<=n；i++)的时间复杂度为。
2．设指针变量p指向单链表中结点a，指针变量s指向被插入的新结点x，则进行插入操作的语句序列为设结点的指针域为next）。
3．设有向图g的二元组形式表示为g =（d，r），d=，r=，r=，则给出该图的一种拓扑排序序列。
4．设无向图g中有n个顶点，则该无向图中每个顶点的度数最多是。
5．设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有___个结点数。
6．设f和r分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为。
7．设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是。
8．简单选择排序和直接插入排序算法的平均时间复杂度为。
9．快速排序算法的空间复杂度平均情况下为最坏的情况下为。
10.散列表中解决冲突的两种方法是和。
三判断题（每小题2分，共20分）
请在小题括号内打√或×）
1．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（
2．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（
3．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为o(log2n)。（
4．完全二叉树中的叶子结点只可能在最后两层**现。（
5．哈夫曼树中没有度数为1的结点。（
6．对连通图进行深度优先遍历可以访问到该图中的所有顶点。（
7．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（
8．由树转化成二叉树，该二叉树的右子树不一定为空。（
9．线性表中的所有元素都有一个前驱元素和后继元素。（
10.带权无向图的最小生成树是唯一的。（
四算法设计题（每小题10分，共30分）
设计在链式存储结构上合并排序的算法。
2. 设计在二叉排序树上查找结点x的算法。
3. 设计计算二叉树中所有结点值之和的算法。
2019数据结构试卷A
哈尔滨工程大学试卷。考试科目 数据结构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...
2019数据结构
下面我们来解析一下知识点。线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入 删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。栈 队列和数组可以考查的知识点相比链表来说要多一些。最基本的，是栈与...
数据结构2019级数据结构大作业
2011级数据结构大作业。1 公园导游图。给出一张某公园的导游图，用图的顶点表示各个景点 景点个数大于等于30 每个景点有属性值 h，t，c 其中h表示游览完成这个顶点给游客带来的happiness，t表示游览这个景点需要的时间，c表示游览这个景点需要的费用，顶点之间的边表示路径 边具有属性值w，表...