经典题目： 第1章 数据结构与算法

《经典题目： 第1章 数据结构与算法》由会员分享，可在线阅读，更多相关《经典题目： 第1章 数据结构与算法（11页珍藏版）》请在金锄头文库上搜索。

1、Comment A1: 为神魔Comment A2: 栈 先进后出Comment A3: 从上到下，偏左优先第第 1 章章 数据结构与算法数据结构与算法 经典题（经典题（13%-15%）一、选择题一、选择题 1、下列叙述中正确的是、下列叙述中正确的是_。 （2007，9） A）程序执行的效率与数据的存储结构密切相关程序执行的效率与数据的存储结构密切相关 B）程序执行的效率只取决于程序的控制结构）程序执行的效率只取决于程序的控制结构 C）程序执行的效率只取决于所处理的数据量）程序执行的效率只取决于所处理的数据量 D）以上）以上 3 种说法都不对种说法都不对 2、下列叙述中正确的是、下列叙述中正确

2、的是_。 （2007，9） A）数据的逻辑结构与存储结构必定是一一对应的）数据的逻辑结构与存储结构必定是一一对应的 B）由于计算机存储空间是向量式的存储结构，因此数据的存）由于计算机存储空间是向量式的存储结构，因此数据的存 储结构一定是线性结构储结构一定是线性结构 C）程序设计语言中的数组一般是顺序存储结构，因此利用数）程序设计语言中的数组一般是顺序存储结构，因此利用数 组只能处理线性结构组只能处理线性结构 D）以上以上 3 种说法都不对种说法都不对 3、冒泡排序在最坏情况下的比较次数是、冒泡排序在最坏情况下的比较次数是_。 （2007，9） A）n(n+1)/2 B）nlog2n C）n(n

3、-1)/2 D）n/2 4、一棵二叉树中共有、一棵二叉树中共有 70 个叶子结点与个叶子结点与 80 个度为个度为 1 的结点，则的结点，则 该二叉树中的总结点数为该二叉树中的总结点数为_。 （2007，9） A）219 B）221 C）229 D）231 5、下列叙述中正确的是、下列叙述中正确的是_。 （2007，4） A）算法的效率只与问题的规模有关，而与数据的存储结构无）算法的效率只与问题的规模有关，而与数据的存储结构无 关关 B）算法的时间复杂度是指执行算法所需要的计算工作量算法的时间复杂度是指执行算法所需要的计算工作量 C）数据的逻辑结构与存储结构是一一对应的）数据的逻辑结构与存储结

4、构是一一对应的 D）算法的时间复杂度与空间复杂度一定相关）算法的时间复杂度与空间复杂度一定相关 6、下列队列的叙述正确的是、下列队列的叙述正确的是_。 （2007，4） A）队列属于非线性表）队列属于非线性表 B）队列按）队列按“先进后出先进后出”的原则组织数据的原则组织数据 C）队列在队尾删除数据）队列在队尾删除数据 D）队列按队列按“先进先出先进先出”的原则组织数据的原则组织数据 7、对下图所示的二叉树进行、对下图所示的二叉树进行前序遍历前序遍历的结果为的结果为 _c_。 （2007，4） A）DYBEAFCZX B）YDEBFZXCA Comment A4: ？Comment A5: ？

5、偏左，偏下的优先， 必须沿路径移动Comment A6: 各个选项的原则？C）ABDYECFXZ D）ABCDEFXYZ8、某二叉枝中有某二叉枝中有 n 个度为个度为 2 的结点，则该二叉树中的叶子结点的结点，则该二叉树中的叶子结点 数为数为_a_。 （2007，4） A）n+1 B）n-1 C）2n D）n/2 9、下列叙述中正确的是、下列叙述中正确的是_d_。 （2006，9） A）一个算法的空间复杂度大，则其时间复杂度也必定大）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度必定小）一个算法的空间复杂度大，则其时间复杂度必定小 C）一个算法的时间

6、复杂度大，则其空间复杂度必定小）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述）上述 3 种说法都不对种说法都不对 10、在长度为、在长度为 64 的有序线性表中进行顺序查找，最坏情况下需的有序线性表中进行顺序查找，最坏情况下需 要比较的次数为要比较的次数为_。 （2006，9） A）63 B）64 C）6 D）7 11、对下图所示的二叉树进行中、对下图所示的二叉树进行中序遍历序遍历的结果为的结果为_a_。 （2006，9） A）ACBDFEG B）ACBDFGE C）ABDCGEF D）FCADBEG 12、按照按照“后进先出后进先出”原则组织数据的数据结构是原则组织数据的数据结构是

7、 _a_。 （2006，4） A）队列）队列 B）栈）栈 C）双向链表）双向链表 D）二叉树）二叉树 13、下列叙述中正确的是、下列叙述中正确的是_。 （2006，4）Comment A7: ？Comment A8: 怎么计算？A）线性链表是线性表的链式存储结构线性链表是线性表的链式存储结构 B）栈与队列是非线性结构）栈与队列是非线性结构 C）双向链表是非线性结构）双向链表是非线性结构 D）只有根结点的二叉树是线性结构）只有根结点的二叉树是线性结构 14、对如下图所示的二叉树进行、对如下图所示的二叉树进行后序遍历后序遍历的结果为的结果为 _d_。 （2006，4） A）ABCDEF B）DBE

8、AFC C）ABDECF D） DEBFCA15、在深度为、在深度为 7 的满二叉树中，叶子结点的个数为的满二叉树中，叶子结点的个数为 _。 （2006，4） A）32 B）31 C）64 D）63 16、下列数据结构中，能用、下列数据结构中，能用二分法二分法进行查找的是进行查找的是 _。 （2005，9） A）顺序存储的有序线性表顺序存储的有序线性表 B）线性链表）线性链表 C）二叉链表）二叉链表 D）有序线性链表）有序线性链表 17、下列关于栈的描述正确的是、下列关于栈的描述正确的是_。 （2005，9） A）在栈中只能插入元素而不能删除元素）在栈中只能插入元素而不能删除元素 B）在栈中只

9、能删除元素而不能插入元素）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入或删除元素栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入，而在另一端删除元）栈是特殊的线性表，只能在一端插入，而在另一端删除元 素素 18、下列叙述中正确的是、下列叙述中正确的是_。 （2005，9） A）一个逻辑数据结构只能有一种存储结构）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构）一个逻辑数据结构可以有多种存

10、储结构，且各种存储结构 不影响数据处理的效率不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构一个逻辑数据结构可以有多种存储结构，且各种存储结构 影响数据处理的效率影响数据处理的效率 19、算法的时间复杂度是指、算法的时间复杂度是指_。 A）执行算法程序所需要的时间）执行算法程序所需要的时间 B）算法程序的长度）算法程序的长度 C）算法执行过程中所需要的基本运算次数）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数）算法程序中的指令条数 20、算法的空间复杂度是指、算法的空间复杂度是指_。 A）算法程序的长度）算法程序的长度 B）算法程序中的指令条数）算法

11、程序中的指令条数 C）算法程序所占的存储空间）算法程序所占的存储空间 D）算法执行过程中所需要的存储空间）算法执行过程中所需要的存储空间 21、数据存储结构是指、数据存储结构是指_。 （2005，4） A）存储在外存中的数据）存储在外存中的数据 B）数据所占的存储空间量）数据所占的存储空间量 C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示 22、下列叙述中，错误的是、下列叙述中，错误的是_。 A）数据的存储结构与数据处理的效率密切相关）数据的存储结构与数据处理的效率密切相关 B）数据的存储结构与数据处理的效率无关

12、）数据的存储结构与数据处理的效率无关 C）数据的存储结构在计算机中所占的空间不一定是连续的）数据的存储结构在计算机中所占的空间不一定是连续的 D）一种数据的逻辑结构可以有多种存储结构）一种数据的逻辑结构可以有多种存储结构 23、在稍微复杂的线性表中，一个、在稍微复杂的线性表中，一个数据元素数据元素可以由若干个可以由若干个数据数据 项项组成，在这种情况下，常把数据元素称为组成，在这种情况下，常把数据元素称为_。 A）数据单元）数据单元 B）记录记录 C）记录项）记录项 D）数据项）数据项 24、下列关于栈的描述中错误的是、下列关于栈的描述中错误的是_。 （2005，4） A）栈是先进后出的线性表

13、）栈是先进后出的线性表 B）栈只能顺序存储）栈只能顺序存储 C）栈具有记忆作用）栈具有记忆作用 D）对栈的插入与删除操作中，不需要改变栈底指针对栈的插入与删除操作中，不需要改变栈底指针 25、下列关于队列的叙述中正确的是、下列关于队列的叙述中正确的是_。 A）在队列中只能插入数据）在队列中只能插入数据 B）在队列中只能删除数据）在队列中只能删除数据 C）队列是先进先出的队列是先进先出的线性表线性表 D）队列是先进后出的线性）队列是先进后出的线性 表表 26、下列对于线性链表的描述中正确的是、下列对于线性链表的描述中正确的是_。 （2005，4） A）存储空间不一定连续，且各元素的存储顺序是任意

14、的存储空间不一定连续，且各元素的存储顺序是任意的 B）存储空间不一定连续，且前件元素一定存储在后件元素的）存储空间不一定连续，且前件元素一定存储在后件元素的 前面前面 C）存储空间必须连续，且前件元素一定存储在后件元素的前）存储空间必须连续，且前件元素一定存储在后件元素的前Comment A9: 和 32 题有什么区别？面面 D）存储空间必须连续，且各元素的存储顺序是任意的）存储空间必须连续，且各元素的存储顺序是任意的 27、与单向链表相比，双向链表的优点之一是、与单向链表相比，双向链表的优点之一是_。 A）更节省存储空间）更节省存储空间 B）便于进行随机访问）便于进行随机访问 C）更容易访问相邻结点更容易访问相邻结点 D）可以省略头指针和尾指针）可以省略头指针和尾指针 28、在线性链表中删除一个元素后，只需改变被删除元素所在、在线性链表中删除一个元素后，只需改变被删除元素所在 结点的前一个结点的结点的前一个结点的_即可。即可。 A）指针域指针域