《数据结构全部测试题》由会员分享，可在线阅读，更多相关《数据结构全部测试题（20页珍藏版）》请在金锄头文库上搜索。
1、数据结构测试题 卫信 06第 1 页 共 20 页1第一章概论 自测题答案 一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。2. 数据结构被形式地定义为（D, R） ，其中 D 是 数据元素 的有限集合，R 是 D 上的 关系 有限集合。3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。6 在线性结构中
2、，第一个结点 没有 前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有 1 个后续结点。7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。9数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。10. 数据的运算最常用的有 5 种，它们分别是插入 、 删除、修改、 查找 、排序。11. 一个算法的效率可分为 时间 效率和 空间 效率。二、单项选
3、择题（ B ）1. 非线性结构是数据元素之间存在一种：A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系（ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构；A) 存储 B) 物理 C) 逻辑 D) 物理和存储（ C ）3. 算法分析的目的是：A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性（ A ）4. 算法分析的两个主要方面是：A) 空间复杂性和时间复杂性 B) 正确性和简明性C) 可读性和文档性 D) 数据复杂性和程序复杂性（ C ）5. 计算机算法指的是：A) 计算方法 B) 排序方法 C
4、) 解决问题的有限运算序列 D) 调度方法（ B ）6. 计算机算法必须具备 输入、输出和 等 5 个特性。A) 可行性、可移植性和可扩充性 B) 可行性、确定性 和有穷性C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性三、简答题2.【严题集 1.2】数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。数据结构测试题 卫信 06第 2 页 共 20 页23. 简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关
5、系是多对多的。四、 【严题集 1.8】分析下面各程序段的时间复杂度五、设有数据逻辑结构 S=（D,R） ，试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系 R，哪些结点是开始结点，哪些结点是终端结点？ 1. 【严蔚敏习题集 P7 1.3】D=d1,d2,d3,d4 R=(d1,d2),(d2,d3),(d3,d4) 答： d1d2d3d4 d1无直接前驱，是首结点 d4无直接后继是尾结点2。D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 答： 此图为树形结构 d1无直接前驱，是
6、根结点 d2,d5,d7,d9无直接后继是叶子结点3D=d1,d2,d9 R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)答： 此图为图形结构 d1，d2无直接前驱，是开始结点 d6,d7无直接后继是终端结点(2) (3)2. s=0;for i=0; itop0 ST-top=0 ST-topm0 ST-top=m0（ A ）4. 李春葆判定一个队列 QU（最多元素为 m0）为满队列的条件是QU-rear QU-front = = m0 QU-rear QU
7、-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1解：队满条件是元素个数为 m0。由于约定满队时队首指针与队尾指针相差 1，所以不必再减 1 了，应当选 A。当然，更正确的答案应该取模，即： QU-front = = (QU-rear+1)% m0（ D ）5数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为（）rf; （） （n fr）% n; （）nrf; （） （nr f）% n6. 【 98 初程 P71】 从供选择的答案中，选出应填入下面叙述 ？ 内
8、的最确切的解答，把相应编号写在答卷的对应栏内。设有 4 个数据元素 a1、a2 、a3 和 a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4 次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B 是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C ，第二次出队得到的元素是 D 。经操作后，最后在栈中或队中的元素还有 E 个。供选择的答案：AD：a1 a2 a3 a4E： 1
9、2 3 0答：ABCDE2, 4, 1, 2, 2数据结构测试题 卫信 06第 7 页 共 20 页77. 【 94 初程 P75】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。栈是一种线性表，它的特点是 A 。设用一维数组 A1,n来表示一个栈，An 为栈底，用整型变量 T 指示当前栈顶位置，AT 为栈顶元素。往栈中推入（ PUSH）一个新元素时，变量 T 的值 B ；从栈中弹出（POP）一个元素时，变量 T 的值 C 。设栈空时，有输入序列 a，b，c，经过PUSH， POP， PUSH，PUSH ，POP 操作后，从栈中弹出的元素的序列是 D
10、 ，变量 T 的值是 E 。供选择的答案：A： 先进先出 后进先出 进优于出 出优于进 随机进出B，C： 加 1 减 1 不变 清 0 加 2 减 2D： a,b b,c c,a b,a c,b a,cE： n+1 n+2 n n-1 n-2答案：ABCDE= 2, 2, 1, 6, 4注意，向地址的高端生长，称为向上生成堆栈；向地址低端生长叫向下生成堆栈，本题中底部为 n，向地址的低端递减生成，称为向下生成堆栈。8. 【 91 初程 P77】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。在做进栈运算时，应先判别栈是否 A ；在做退栈运算时，应先判
11、别栈是否 B 。当栈中元素为 n 个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 D 分别设在这片内存空间的两端，这样，只有当 E 时，才产生上溢。供选择的答案：A，B：空 满 上溢 下溢C： n-1 n n+1 n/2D： 长度 深度 栈顶 栈底E：两个栈的栈顶同时到达栈空间的中心点 其中一个栈的栈顶到达栈空间的中心点 两个栈的栈顶在达栈空间的某一位置相遇 两个栈均不空，且一个栈的栈顶到达另一个栈的栈底答案：ABCDE2, 1, 2, 4, 3四、简答题（每小题 4 分，共 20 分）1. 【严
12、题集 3.2和 3.11】说明线性表、栈与队的异同点。刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表 LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表 FIFO。 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。2. 【统考书 P60 4-11，难于严题集 3.1】设有编号为 1，2，3，4 的四辆列车，顺序进入一个栈式结构的车站，具体写
13、出这四辆列车开出车站的所有可能的顺序。刘答：至少有 14 种。 全进之后再出情况，只有 1 种：4，3，2，1 进 3 个之后再出的情况，有 3 种，3,4,2,1 3,2,4,1 3,2,1,4 进 2 个之后再出的情况，有 5 种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 进 1 个之后再出的情况，有 5 种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,33. 【刘自编】假设正读和反读都相同的字符序列为“回文” ，例如， abba和abcba 是回文，数据结构测试题 卫信 06第 8 页 共 20 页8abcde 和
14、ababab则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？答：线性表是随机存储，可以实现，靠循环变量（j-）从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用 POP 动作实现。 （但堆栈是先减后压还是）若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。4. 【统考书 P60 4-13】顺序队的“假溢出”是怎样产生的？如何知道循环队
