发布时间 : 星期一 文章数据结构期末试卷(A) - 图文更新完毕开始阅读d64c2b969b89680202d82543
座位号：
杭州电子科技大学学生考试卷（ A ）卷 考试课程 数据结构 课程号 考生姓名 教师号 学号（8位） 考试日期 2013 年 月 日 成 绩 任课教师姓名 年级 专业 10. 就平均查找速度而言，下列几种查找速度从慢至快的关系是（ ）。 A. 顺序 折半 哈希 分块 B. 顺序 分块 折半 哈希 C. 分块 折半 哈希 顺序 D. 顺序 哈希 分块 折半 三．填空题：（每空2分，共20分） 1. n个元素的顺序表，第i个元素之前插入一个新元素，需要向后移动( )个元素。 2. 一个队列的入队序列是1，2，3，4，则队列的输出序列是（ ）。 特别提醒：答案写在答题纸中，并请尽量写在一张纸中。 一．判断题：（每小题2分，共20分） 1. 线性表中所有结点的类型必须相同。 （ ） 2. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （ ） 3. 线性表的顺序存储结构是一种顺序存取的存储结构。 （ ） 4. 数组元素的下标值越大，存取时间越长。 （ ） 5. 长度为1的串等价于一个字符型常量。 （ ） 6. 若已知一棵二叉树的前序遍历序列和后序遍历序列，则可以确定该二叉树。 （ ） 7. n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。 （ ） 8. 任何一个关键活动延迟，那么整个工程将会延迟。 （ ） 9. 直接选择排序算法在最好情况下的时间复杂度为O（n）。 （ ） 10. 在散列法中，一个可用散列函数必须保证绝对不产生冲突。 （ ） 3. 由一棵二叉树的前序序列和（ ）可唯一确定这棵二叉树。 4. 已知完全二叉树的第8层有8个结点，则其叶子结点数是（ ）。 5. 若完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是（ ）。 6. 在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 7. 在插入和选择排序中，若初始数据基本正序，则选择（ ）。 8. 在插入和选择排序中，若初始数据基本反序，则最好选择（ ）。 9. 在快速排序、堆排序、归并排序中，（ ）排序是稳定的。 10. 顺序表 10, 20, 30, 40, 50, 60, 70，采用折半搜索时，搜索成功的平均搜索长度是（ ）。 四．结构问答题：（每小题6分，共30分） 1. 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ，求其后序遍历序列。画出这棵二叉树的后序线索化图。 2. 设哈希表长13，哈希函数为 H (key) = key % 13。用线性探测再散列法解决冲突，对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。画出该哈希表，并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 3. 假设用于通信的电文由A-H的8个字符组成，各字符在电文中出现的次数分别为5，29，7，8，14，23，3，11，设计各字符的赫夫曼编码。 4. 顺序表序列为：32，33，6，27，37，10，64，14，36，19。求： (1) 快速排序第一趟划分的结果，以第一个元素为枢轴。 (2) 堆排序初始建小顶堆的结果。 (3) 在增量为3时，希尔排序第一趟排序的结果。 (4) 归并排序第一趟排序的结果。 5. 右图是一个无向图，要求： (1) 画出该图的邻接矩阵存储结构。 (2) 画出该图的邻接表存储结构。 (3) 根据邻接表，给出DFS及BFS次序。 (4) 给出该图的最小生成树。 二．选择题：（每小题2分，共20分） 1. 在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A．逻辑 B．存储 C．逻辑和存储 D．物理 2. 进栈序列是1，2，3，…，n，出栈序列为p1，p2，p3，…，pn，若p1＝n，则pi为（ ）。 A．i B．n－i C．n－i＋1 D．不确定 3. 判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ ）。 A．求关键路径的方法 B．求最短路径的Dijkstra方法 C．深度优先遍历算法 D．广度优先遍历算法 4. 一个具有n个顶点的连通图的生成树，它含有图中的全部顶点，且有（ ）条边。 A． n B．n-1 C．n+1 D．2n 5. 设有广义表D(a,b,D)，其长度为（ ），深度为（ ）。 A．∞ B．3 C．2 D．5 6. 某二叉树的前序和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A．空或只有一个结点 B．高度等于其结点数 C．任一结点无左孩子 D．任一结点无右孩子 7. 将一棵森林F转换为孩子兄弟链表表示的二叉树T，则F的后根遍历是T 的（ ）。 A．前序遍历 B．中序遍历 C．后序遍历 D．层序遍历 8. AOV网是一种（ ）。 A．无向图 B．无向无环图 C．有向无环图 D．有向有环图 9. 设有5000个无序记录，希望得到前10个最小元素，用（ ）方法最快。 A．冒泡排序 B．快速排序 C．堆排序 D．简单选择排序
五．算法设计：（10分） 设计在带头结点的单链表中删除值相同的重复结点的算法。写出算法思路，并给出C或C++实现。 第 1 页 共 2 页
座位号：
请在此处答题： 一、 判断题（每题2分，共20分） 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 4. 6. 7. 8. 9. 10. 二、 选择题（每题2分，共20分） 1. 2. 3. 4. 5. 5. 三、 填空题（每空2分，共20分） 1. 6. 2. 7. 3. 8. 4. 9. 5. 10. 五、 算法设计题（10分） 四、 问答题（每题6分，共30分） 1. 2. 3.
第 2 页 共 2 页