肇慶学院工程学院数据结构复习题.doc

试题型：(每小题分值*数量)选择 15*2=30判断 10*1=10填空 10*3=30应用 4*5=20算法 10*1=10一、复习以PPT讲述内容和作业为主。注：平衡二叉树，B-树，B+树，哈希表只考简单概念。二、要求会定义的数据结构：1、单链表2、双向链表3、顺序栈4、二叉链表三、要求掌握的算法：1、查找：折半查找，二叉排序树查找2、排序：直接插入排序，冒泡排序，简单选择排序四、要求掌握的应用：1、线性表应用于一元多项式的表示及相加2、栈应用于表达式求值，表达式转换3、队列(循环队列)存储数据的变化4、串的模式匹配KMP算法5、二叉树的性质的证明6、根据树/二叉树的遍历结果求树结构(参考作业)7、赫夫曼树的构造(过程)8、图的邻接矩阵，邻接表，逆邻接表的表示法9、图的深度优先生成树，广度优先生成树的生成10、图用普里姆算法构造最小生成树11、图用Dijkstra算法求最短路径(注意要有过程)12、AOE网络求关键路径的问题13、二叉排序树的构造 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的① 、数据信息在计算机中的② 以及一组相关的运算等的课程。 ① A．操作对象　　　Ｂ．计算方法　　Ｃ．逻辑结构　　Ｄ．数据映象 ② A．存储结构 Ｂ．关系 Ｃ．运算 Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是① 的有限集合，R是D上的② 有限集合。 ① A．算法 Ｂ．数据元素 Ｃ．数据操作 Ｄ．数据对象 ② A．操作 Ｂ．映象 Ｃ．存储 Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成 。 A．动态结构和静态结构 Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构 Ｄ．内部结构和外部结构 4. 算法分析的目的是① ，算法分析的两个主要方面是② 。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是① ，它必具备输入、输出和② 等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括 、 和 三种类型，树形结构和图形结构合称为 。 2. 在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。 3. 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个直接前驱结点，叶子结点没有 结点，其余每个结点的直接后续结点可以 。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。 5. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是__ __。 for (i=0;in;i++) for (j=0;jn; j++) A[i][j]=0; 8. 分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是__ __。 for (i=0;in;i++) for (j=0; ji; j++) A[i][j]=0; 9. 分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是__ __。 s=0; for (i=0;in