数据结构习题集含参考答案.pdf

数据结构习题集含答案目录目录 . 1选择题 . 2第一章绪论 . 2第二章线性表 . 4第三章栈和队列 . 6第四章串. 9第五章数组和广义表 . 9第六章树和二叉树 . 10第七章图. 13第八章查找 . 15第九章排序 . 17简答题 . 21第一章绪论 . 21第二章线性表 . 22第三章栈和队列 . 23第四章串. 25第六章树和二叉树 . 25第七章图. 29第八章查找 . 32第九章排序 . 33编程题 . 35第一章绪论 . 35第二章线性表 . 35第三章栈和队列 . 37第四章串. 37第五章数组和广义表 . 37第六章树和二叉树 . 37第七章图. 37第八章查找 . 37第九章排序 . 39选择题第一章绪论1. 数据结构这门学科是针对什么问题而产生的？（A ）A、针对非数值计算的程序设计问题 B 、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对 D、两者都不针对2. 数据结构这门学科的研究内容下面选项最准确的是（D ）A、研究数据对象和数据之间的关系 B 、研究数据对象C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ）A、某班级的学生成绩表是数据元素，90 分是数据项B、某班级的学生成绩表是数据对象，90 分是数据元素C、某班级的学生成绩表是数据对象，90 分是数据项D、某班级的学生成绩表是数据元素，90 分是数据元素4. 数据在计算机存储器内表示时， 物理地址与逻辑地址不相同， 称之为（C ） 。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构5. 算法分析的目的是（ C ）A、找出数据的合理性B 、研究算法中的输入和输出关系C、分析算法效率以求改进D 、分析算法的易懂性和文档型性6. 算法分析的主要方法（ A ） A、空间复杂度和时间复杂度B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性7. 计算机内部处理的基本单元是（B ）A、数据B、数据元素C、数据项D、数据库8. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ B ） A、低B、高C、相同D、不好说9. 算法的时间复杂度取决于（C ）A 、问题的规模B、待处理数据的初始状态C、问题的规模和待处理数据的初始状态D、不好说10. 在数据结构中，从逻辑上可以把数据结构分成（C ）A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构11. 线性表的顺序存储结构是一种( A )的存储结构A、随机存取B、顺序存取C、索引存取D、散列存取12. 线性表的链式存储结构是一种（B ）存储结构A、随机存取B、顺序存取C、索引存取D、散列存取13. 在数据结构中 ,从逻辑上可以把数据结构分成(C )。

A、 动态结构和静态结构B、 紧凑结构和非紧凑结构C、 线性结构和非线性结构D、 内部结构和外部结构14. 在数据结构中 ,从存储结构上可以将之分为(B )A、 动态结构和静态结构B、 顺序存储和非顺序存储C、 紧凑结构和非紧凑结构D、 线性结构和非线性结构15. 某算法的时间复杂度是O(n2),表明该算法的 ( A)A、 执行时间与n2 成正比B、 问题规模是n2 C、 执行时间等于n2 D、 问题规模与n2 成正比16. 在下面的程序段中 ,x=x+1; 的语句频度为 (C )for( i=1;i=n;i+) for( j=1;j=n;j+) x=x+1; A、 O(2n) B、 O(n) C、 O(n2) D、 O(log2n) 17. 以下数据结构中 ,( A)是非线性数据结构A、 树B、 字符串C、 队D、 栈18. 顺序存储 ,存储单元的地址 ( A)A、 一定连续B、 一定不连续C、 不一定连续D、 部分连续 ,部分不连续19. 评价一个算法性能好坏的重要标准是(C )A、 算法的正确性B、 算法易于调试C、 算法的时间和空间复杂度D、 算法易于理解第二章线性表1. 关于线性表的说法不正确的是？（D ）A、存在唯一的一个被称为“第一个”的数据元素（开始结点）B、存在唯一的一个被称为“最后一个”的数据元素（终端结点）C、除第一个之外，集合中的每个数据元素均只有一个前驱D、除第一个之外，集合中的每个数据元素均只有一个后继2. 关于顺序表的说法不正确的是？（D ）A、逻辑关系上相邻的两个元素在物理存储位置上也相邻B、可以随机存取表中任一元素，方便快捷C、性表中插入某一元素时，往往需要移动大量元素D、性表中删除某一元素时，无需移动大量元素3. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用什么存储结构？（A ）A、顺序表B 、单链表C、循环链表 D、双链表4.在一个长度为 n 的顺序表中第 i 个元素（ 1=inext B、 p =null C 、p-next=null D、p-next = p-next-next 9.下述哪一条是顺序存储结构的优点(D) 。

A、 可方便地用于各种逻辑结构的存储表示 B、 插入运算方便C、 删除运算方便 D、 存储密度大10. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算 , 则利用 (A) 存储方式最节省时间A、 顺序表 B、 双链表 C、 带头结点的双循环链表 D、 单循环链表11. 设某顺序表中第一个元素的地址是se( 下标从 1开始), 每个结点占 m个单元 ,则第 i 个结点的地址为 (A) A、 se+(i-1)m B 、 se+(i+1)m C 、 se+i m D、 se-im 12. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素 , 则采用 (B) 存储方式最节省运算时间A、 单链表 B、 仅有尾指针的单循环链表C、 仅有头指针的单循环链表 D、 双链表13. 若长度为 n 的线性表采用顺序存储结构, 在其第 i 个位置插入一个新元素的算法的时间复杂度为 (A) A、 O(n) B、 O(0) C、 O(1) D、 O(n2) 14. 在单链表指针为 p 的结点之后插入指针为s 的结点 , 正确的操作是 (A) A、 s-next=p-next;p-next=s; B、 p-next=s;s-next=p-next; C、 p-next=s;p-next=s-next; D、 p-next=s-next;p-next=s; 15. 对于一个头指针为 head的带头结点的单链表 , 判定该表为空表的条件是 (A) 。

A、 head next=NULL; B、 head=NULL; C、 head next=he; D、 head!=NULL; 第三章栈和队列1.栈、队列通常采用两种存储结构，它们是(B ) A、散列方式和索引方式B、顺序存储结构和链式存储结构C、链表存储结构和数组D、 线性和非线性存储结构2.一个栈入栈序列是a,b,c,d, 则栈输出序列不可能是 (C ) A、d,c,b,a B 、c,d,b,a C、d,c,a,b D、a,b,c,d 3.判断顺序栈（最多结点数为m ）为栈满的条件是（ D ）A、top=0 B、 top!=m C、 top!=0 D、top=m 4.栈存取数据原则（或栈特点）是（B ）A、后进后出 B 、后进先出 C、先进先出 D、随意进出5.一个队列的进队序列为： a，b，c，d，则出队序列是： ( A ) A、a，b，c， d B、 d ，c，b，a C、a，d，c， b D、 c ，b，d，a 6.循环队列为空队列的条件是： （D）A、Q.front=0 B、 Q. （rear+1)%MaxSize=Q.front C、 Q.rear=0 D、 Q.rear=Q.front 7.在存储结构上，如果用带头节点单链表实现队列（假定front和 rear 分别为队首和队尾指针），则删除一个结点的操作为（A ） 。

A、front.next=front.next.next B、rear=rear.next C、rear=front.next D、front= front.next 8.栈和队列共同点是（ C ）A、先进后出B、先进先出C、允许在端点处进行操作线性表D、无共同点9.插入和删除只能在一端进行的线性表是（B ）A、循环队列 B、栈 C、队列 D、循环栈10. 插入和删除分别在两端端进行的线性表是（C ）A、循环队列 B、栈 C、队列 D、循环栈11. 循环队列为满队列的条件是： （B ）A、Q.front=0 B、 Q. （rear+1)%MaxSize=Q.front C、 Q.rear=0 D、 Q.rear=Q.front 12. 栈和队列都是 ( D) A、 限制存取点的非线性结构B、 顺序存储的线性结构C、 链式存储的非线性结构D、 限制存取点的线性结构13. 设栈 S和队列 Q的初始状态为空 , 元素 e1,e2,e3,e4,e5和 e6依次通过栈 S,一个元素出栈后随即进入队列Q,若 6 个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈 S的容量至少应该是 ( A) 。

A、 3 B、 6 C、 4 D、 2 14. 设计一个判别表达式中括号是否匹配出现的算法, 采用(A ) 的数据结构最佳A、 栈B、 顺序表C、 队列D、 单链表15. 表达式 a*(b+c)-d的后缀表达式是 (C ) A、 abc*+d- B、 cb+a*d- C、 abc+*d- D、 abcd+*- 16. 递归过程或函数调用时 , 处理参数及返回地址需要用一种( A) 的数据结构A、 栈B、 队列C、 多维数组D、 线性表17. 最大容量为 n的循环队列 , 队尾指针为 rear, 队头指针为 front,则队空的条件是(A ) A、 rear=front B、 (rear+1)%n=front C、 rear+1=front D、 (rear-l)%n=front 18. 用带头结点的单链表表示队长大于1 的队列时 , 其队头指针指向队头结点, 其队尾指针指向队尾结点 , 则在进行删除操作时 (A ) A、 仅修改队头指针B、 仅修改队尾指针C、 队头、队尾指针都要修改D、 队头 ,队尾指针都可能要修改19. 对于一个具有 n 个结点的单链表 , 在已知的结点 *p 后插入一个新结点的时间复杂度和在给定值为x 的结点后插入一个新结点的时间复杂度分别为( A) 。

A、 O(1),O(n) B、 O(n),O(n) C、 O(1),O(1) D、 O(n),O(1) 第四章串1.关于串的叙述，错误的是： （B ）A串是字符有限序列B空串是由空格构成的串C模式匹配是串的重要运算 D 串有用顺序、链式两种存储方式2.串长度是指（ B ）A串所含不同字母数目 B串所含字符数目C串所含不同字符数目 D串所含非空格字符数目3.设串 S1是串 S子串，则求 S1在 S中定位运算称为（ B ）A求子串 B串匹配 C联接 D求串长4.设有串 s1=”welcome to zdsoft colleage!”和 s2=”so”, 那么 s2 在 s1中的索引位置是（ C ）A12 B14 C13 D10 5.串是一种特殊的线性表 , 其特殊性体现在 (A ) A、 数据元素是字符 B、 顺序存储 C、 链式存储 D、 逻辑结构是线性结构6.设有两个串 p 和 q , 其中 q 是 p 的子串 , 求 q 在 p 中首次出现的位置的算法称为(A ) A、 串的模式匹配 B、 求子串 C、 串联接 D、 求串长第五章数组和广义表1. 假设以行序为主序存储二维数组A=array1.100,1.100,设每个数组元素占 2 个存储单元 , 基地址为 10, 。