淮 阴 工 学 院 课 程 考 试 试 卷
----------------------------装--------------------------订----------------------线----------------------------- 专业： 通信工程 课程名称：数据结构 学分：3.5 试卷编号（A） 课程编号： 1311050 考试方式： 闭卷 考试时间： 100 分钟 拟卷人(签字)： 拟卷日期：2006,12,25 审核人(签字)： 得分统计表： 2. 算法分析的目的是 。 A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 3. 线性表的顺序存储结构是一种 结构。 A.随机存取 B.顺序存取 C.索引存取 D.HASH存取 4. 顺序表和链表均适用于 查找。 A．随机 B．二分法 C．顺序，也能二分法 D．顺序 5. 在一个有向图中，所有顶点的入度之和等于边的条数的 倍。 班级 姓名 学号 题 号 得 分 得分 一 二 三 四 五 六 七 八 九 十 总 分 1. 数据的存储结构种类包括 ① 。 2. 分析以下部分代码的时间复杂度用大O表示法为 ② 。 int i=1; s=0; while(i<=n) { s+=i; i=i*2; } 3. 栈是一种 ③ 的特殊的线性表。 4. 线性表的顺序存储结构是一种 ④ 存取方式。 5. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 ⑤ 的次序来得到最短路径的。 6. 设一棵完全二叉树有100个结点，则共有 ⑥50 个叶子结点。 7. 将一个长度为50的顺序表的第30个元素删除时，需前移 ⑦ 20 个元素。 8. 设数组a[0…8, 0…9]的起始地址为1000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[4,6]的存储地址为 ⑧ 1000+8*2*5+6*2=1092 。 9. 排序方法的稳定性是指 ⑨ 。 10.对有序顺序表（3，8，10，25，29，45，55，77，85，99）采用折半查找，若查找表中元素10，它将依次与表中元素 ⑩ 比较大小。 得分 阅卷人 二、选择题：（每题1分，共20分） 1. 数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的 和运算的学科。 A. 关系 B. 算法 C. 运算 D. 数据 阅卷人 一、填空题：（每空1分，共10分） A．1／2 B． l C． 2 D．4 6. 一组记录的关键字为{18，1，3，8，9，29}，则利用堆排序的方法建立的初始堆(大顶堆)为 。 A．29，18，9，3，8，1 B．29，9，18，8，1，3 C．29，9，18，8，3，1 D．29，18，9，8，3，1 7. 若在线性表中采用折半查找法查找元素，该线性表应该 。 A．元素按值有序 B．元素按值有序，且采用链式存储结构 C．采用顺序存储结构 D．元素按值有序，且采用顺序存储结构 8. 二叉树是非线性数据结构，所以 。 A. 它不能用顺序存储结构存储; B. 顺序存储结构和链式存储结构都能存储; C. 它不能用链式存储结构存储; D. 顺序存储结构和链式存储结构都不能使用 9. 下述几种排序方法中，平均性能最差的是 Ａ. 希尔排序 Ｂ. 快速排序 Ｃ. 归并排序 Ｄ. 简单选择排序 10. 在进行顺序栈入栈运算时，应先判别栈是否 。 A. 空 B. 满 C. 上溢 D. 下溢 11.一个队列的入队序列是a，b，c，d，则队列的输出序列是 。 A.d，c，b，a B.a，b，c，d C.a，d，c，b D.c，b，a，d 12. 一维数组的第一个元素的存储地址是1000，每个元素的长度为2，则第5个元素的地址是1000+2*4 A.1010 B.1008 C.1000 D.1020 13、快速排序是 排序方法中的一种。 Ａ. 插入 Ｂ.选择 Ｃ. 交换 Ｄ. 归并 14、将递归算法转换成对应的非递归算法时，通常需要借助 结构实现。 A.树 B.队列 C.链表 D.栈 15、图是一种 的结构。 A. 一一对应关系 B. 一对多关系 C. 无序关系 D. 多对多关系 16．把一棵树转换为二叉树后，这棵二叉树的形态是 。 A. 有多种 B. 有多种，但根结点都没有左孩子 第 1 页 共 2 页
淮 阴 工 学 院 课 程 考 试 试 卷
----------------------------装--------------------------订----------------------线----------------------------- C. 唯一的 D. 有多种，但根结点都没有右孩子 17．在完全二叉树中，若一个结点没有 ，则它必定是叶结点。 A．右孩子结点 B．左孩子结点 C．左子结点或者没有右子结点 D．兄弟结点 18．在单链表中，指针p指向链表某结点，现将指针s所指结点插到p所指结点之后，则其实现语句应为 A．p->next=s；s->next=p->next； B．s→next=p→next；p→next=s； C．s→next=p→next；p→next=s→next； D．s->next=p+1；p->next=s； 19．对于图1的有向图，以下 是正确的拓扑排序序列。 A．1，2，3，4，5，6 B．6，5，4，3，2，1 2 4 C．3，2，4，5，6，1 3 1 D．3，5，2，4，6，1 5 6 20．若有10个结点的有向图是强连通图，则最少有 条边。 A．8 B．9 C．10 D．11 得分 图1 班级 姓名 学号 0080500005000000000100040006000000600000000000000000000000 000060阅卷人 三、判断题（正确的打√，错误的打╳）（10小题，共10分） （ ）1. 数据结构中，数据的存储结构是与所使用的计算机无关的。 （ 对 ）2. 顺序存储方式也能用于存储非线性结构。 （ ）3. 栈是一种插入、删除操作限于在表的一端进行的线性表，是一种先进先出的结构。 （ 对 ）4. 对一棵非空二叉树，它的根结点是第1层，则它的第i层上最多能有2 i-1个结点。 （ ）5. 图的邻接表存储结构适用于稠密图的情况。 （ ）6. 图的深度优先遍历序列是唯一的。 （ ）7. 拓扑排序就是按照关键字的递增次序进行的排序方法。 （ 对 ）8. 散列查找的平均查找长度ASL与元素个数n无关。 （ ）9. 冒泡排序的时间复杂度为O(nlogn)。 （ 对 ）10. 完全二叉树按自上而下，从左到右给结点编号（从1开始，共n个），则编号最大的分枝结点的编号是n/2。 得分 阅卷人 四、简答题（6小题，共50分） 1．待排关键字序列为{21, 58, 1,29, 17, 43, 99, 33, 12}，请分别给出用快速排序和简单选择排序的过程。 （本题8分） 2．用三元组表表示下列稀疏矩阵： （本题6分） 3．设哈希（Hash）表的地址范围为0～10，哈希函数为：H（K）＝K % 11。 K为关键字，用线性探测法再散列法解决冲突，输入关键字序列： （27，45，53，28，42，91，60，58，37） 造出Hash表，试回答下列问题： （本题10分） （1） 画出哈希表的示意图； 1 （2） 若查找关键字60，需依次与哪些关键字进行比较？ 5 6 （3） 计算查找成功时的平均查找长度ASL。 1 5 5 4 2 3 4．对图2的带权无向图，画出采用Prim算法（从顶点1开始） 6 2 4 构造最小生成树的过程。 （本题10分） 3 6 6 5 5．假设用于通信的电文仅由8个字母组成，字母a,b,c,d,e,f, 图2 G,h在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32， 0.03，0.21，0.10。试构建相应的哈夫曼树（按左子树根结点的权小于等于右子树根结点的权的次序构造），为这8个字母设计哈夫曼编码，并计算平均码长。（本题8分） 6．给定二叉树T的两种遍历序列，分别是： 前序遍历序列： A，D，B， E，C，H，F，G，I 中序遍历序列： A，B，C， E，H，D，G，I，F 试画出二叉树B，并写出二叉树的后序遍历序列。（本题8分） 得分 四、数据结构与算法设计题（10分） 阅卷人 1． 二叉树采用二叉链表结构存储，有创建二叉树、前序遍历二叉树、中序遍历二叉树、后序遍历二叉树等操作，试给出该二叉链表类的描述，并设计前序遍历二叉树的操作算法。（本题6分） 2． 编写折半查找算法。（本题4分） 第 2 页 共 2 页
