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

《数据结构习题集含参考答案.pdf》由会员分享，可在线阅读，更多相关《数据结构习题集含参考答案.pdf（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构习题集含答案目录目录 . 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

2、第九章排序 . 39选择题第一章绪论1. 数据结构这门学科是针对什么问题而产生的？（A ）A、针对非数值计算的程序设计问题 B 、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对 D、两者都不针对2. 数据结构这门学科的研究内容下面选项最准确的是（D ）A、研究数据对象和数据之间的关系 B 、研究数据对象C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ）A、某班级的学生成绩表是数据元素，90 分是数据项B、某班级的学生成绩表是数

3、据对象，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、数据

4、项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

5、、索引存取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;

6、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、存在唯一的一个

7、被称为“最后一个”的数据元素（终端结点）C、除第一个之外，集合中的每个数据元素均只有一个前驱D、除第一个之外，集合中的每个数据元素均只有一个后继2. 关于顺序表的说法不正确的是？（D ）A、逻辑关系上相邻的两个元素在物理存储位置上也相邻B、可以随机存取表中任一元素，方便快捷C、在线性表中插入某一元素时，往往需要移动大量元素D、在线性表中删除某一元素时，无需移动大量元素3. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用什么存储结构？（A ）A、顺序表B 、单链表C、循环链表 D、双链表4.在一个长度为 n 的顺序表中第 i 个元素（ 1=i

8、next 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 、

9、 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

10、-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, 则栈输出序列不可能是

11、(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.fro

12、nt 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

13、 ）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的容量至少应该是 (

14、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、 (

15、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

16、),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 ) 。

17、A、 数据元素是字符 B、 顺序存储 C、 链式存储 D、 逻辑结构是线性结构6.设有两个串 p 和 q , 其中 q 是 p 的子串 , 求 q 在 p 中首次出现的位置的算法称为(A ) 。A、 串的模式匹配 B、 求子串 C、 串联接 D、 求串长第五章数组和广义表1. 假设以行序为主序存储二维数组A=array1.100,1.100,设每个数组元素占 2 个存储单元 , 基地址为 10, 则 LOC5,5=( A) 。A、 818 B、 B 808 C、 1010 D、 1020 2. 在稀疏矩阵的三元组顺序表中, 每个三元组表示 (D ) 。A、 矩阵中数据元素的行号、列号和数据值B

18、、 矩阵中非零元素的数据值C、 矩阵中数据元素的行号和列号D、 矩阵中非零元素的行号、列号和数据值第六章树和二叉树1.假设在一棵二叉树中，双分支结点数为15，单分支结点数为 30 个，则叶子结点数为（ B ）个。A. 15 B. 16 C. 17 D. 47 2. 假定一棵三叉树的结点数为50，则它的最小高度为（ C ） 。A. 3 B. 4 C. 5 D. 6 3. 在一棵二叉树上第4 层的结点数最多为（ D ） 。A. 2 B. 4 C. 6 D. 8 4. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R1.n， 结点 Ri若有左孩子，其左孩子的编号为结点（B ） 。A. R2

19、i+1 B. R2i C. Ri/2 D. R2i-1 5. 设 n , m 为一棵二叉树上的两个结点，在中序遍历序列中n 在 m 前的条件是（B ） 。A. n 在 m 右方B. n 在 m 左方C. n 是 m 的祖先D. n 是 m 的子孙6. 下面叙述正确的是（ D ） 。A. 二叉树是特殊的树B. 二叉树等价于度为2 的树C. 完全二叉树必为满二叉树D. 二叉树的左右子树有次序之分7. 现有一深度为 5 的二叉树，请问其最多有（D ）个结点。A. 32 B. 5 C.30 D. 31 8. 现有一深度为 4 的二叉树，请问其最多有（A ）个结点。A. 15 B. 16 C.17 D.

20、6 9. 在一棵二叉排序树上按（B ）遍历得到的结点序列是一个有序序列。A. 先序B. 中序C.后序D.头序10. 在一棵二叉树中，度为 0 的结点数为 n0， 度为 2 的结点数为 n2， 则 n0= （ C ）A. n+1 B. n+2 C.n2+1 D.2n+1 11. 由三个结点构成的二叉树，共有（B ）种不同的形态。A. 4 B. 5 C.6 D.7 12. 一棵含有 n 个结点的树，（ A ）形态达到最大深度。A. 单支树B. 二叉树C.三 叉树D.n 叉树13. 不含任何结点的空树（C ） 。.是一棵树 ; .是一棵二叉树 ; .是一棵树也是一棵二叉树; .既不是树也不是二叉树1

21、4. 二叉树是非线性数据结构，所以( C ) 。.它不能用顺序存储结构存储; .它不能用链式存储结构存储; .顺序存储结构和链式存储结构都能存储; .顺序存储结构和链式存储结构都不能使用15. 具有 n(n0)个结点的完全二叉树的深度为(C )。.log2(n) . log2(n) . log2(n) +1 .log2(n)+116. 在一棵三元树中度为3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1的结点数为 2 个，则度为 0 的结点数为（ D ）个。A. 4 B. 5 C.6 D.7 17. 有关二叉树下列说法正确的是（B ）A二叉树的度为2 B 一棵二叉树的度可以小于2

22、C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2 18. 在完全二叉树中，若一个结点是叶结点，则它没（C ） 。A左子结点B右子结点C左子结点和右子结点D左子结点，右子结点和兄弟结点19. 在下列情况中，可称为二叉树的是（B ） A每个结点至多有两棵子树的树B. 哈夫曼树 C每个结点至多有两棵子树的有序树D. 每个结点只有一棵右子树20. 树最适合用来表示的结构是(A )。A、 元素间具有分支及层次关系的结构B、 元素间的有序结构C、 元素间的无序结构D、 元素间无联系的结构21. 任意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对位置( B)。A、 肯定发生变化B、

23、肯定不发生变化C、 有时发生变化D、 无法确定22. 判断线索二叉树中某结点P 有左孩子的条件是 (D )。A、 p-LTag=1 B、 p!=NULL C、 p-lchild!=NULL D、 p-LTag=0 23. 设森林 T 中有 4 棵树,其结点个数分别为n1,n2,n3,n4, 那么当森林 T 转换成一棵二叉树后 ,则根结点的右子树上有 (A )个结点。A、 n2+n3+n4 B、 n1-1 C、 n1 D、 n1+n2+n3 24. 以数据集 4,5,6,7,10,12,18 为叶结点权值所构造的哈夫曼树,其带权路径长度为(C )。A、 155 B、 160 C、 165 D、

24、170 25. 以下属于前缀编码的是 ( A)。A、 0,1101,1110,1100,1111 B、 0,1,01,010,110 C、 00,01,10,11,101 D、 01,00,10,001,110,101 26. 一棵具有 N 个结点的二叉树采用二叉链表进行存储,其中空指针域有 ( A )个。A、 N+1 B、 N C、 N-1 D、 不确定27. 已知一棵度为 3 的树有 2 个度为 1 的结点 ,3 个度为 2 的结点 ,4 个度为 3 的结点,则该树中有 (C )个叶子结点。A、 10 B、 11 C、 12 D、 13 第七章图1. 图的深度优先遍历类似于二叉树的（A ）

25、 。A先序遍历B中序遍历C后序遍历D层次遍历2. 已知一个图如图所示，若从顶点a 出发按深度优先遍历，则可能得到的一种顶点序列为（ D ）Aabecdf Bacfebd Caebcfd Daedfcb 3. 若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（B ）图。A非连通B连通C强连通D有向4. 在一个图中，所有顶点的度数之和等于所有边数的（C ）倍。A 1/2 B 1 C 2 D 3 5. 在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（B ）倍。A 1/2 B 1 C 2 D 3 6. 一个有 N 个顶点的有向图最多有（B ）条边。A N

26、B N(N-1) C N(N -1)/2 D 2N 7. 具有 4 个顶点的无向完全图有（A ）条边。A 6 B 12 C 18 D 20 8. 具有 6 个顶点的无向图至少有（A ）条边才能确保是一个连通图。A 5 B 6 C 7 D 8 9. 对于一个具有 N 个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是（D ）A N B (N-1)2 C N-1 D N*N 10. 一个具有 N 个顶点的无向图中，要连通全部顶点至少要（C ）条边A N B N+1 C N-1 D N/2 11. 一个具有 n 个顶点的无向图最多有 (A )边。A、 n(n-1)/2 B、 n(n-1) C、 n

27、D、 2n 12. 对于一个具有 n 个顶点和 e 条边的无向图 ,若采用邻接表表示 ,则占用的存储空间为 ( D )。A、 n+e B、 e C、 2e D、 n+2e 13. 如果含有 n 个顶点的图形成一个环 ,则它有 ( A )棵生成树。A、 n B、 n-1 C、 n+1 D、 不确定14. 任何一个无向连通网的最小生成树( A)。A、 有一棵或多棵B、 只有 1 棵C、 一定有多棵D、 可能不存在15. 判断一个有向图是否存在回路,可以用 (D )。A、 广度优先遍历算法B、 求关键路径的方法C、 Dijkstra 方法D、 深度优先遍历算法16. 深度优先遍历类似于二叉树的( A

28、)。A、 先序遍历B、 中序遍历C、 后序遍历D、 层次遍历17. 广度优先遍历类似于二叉树的(D )。A、 先序遍历B、 中序遍历C、 后序遍历D、 层次遍历第八章查找1. 顺序查找法适合于存储结构为（B ）的线性表。A散列存储B顺序存储或链式存储C压缩存储D索引存储2. 在查找过程中，若同时还要增、删工作，这种查找称为（B ） 。A、 静态查找B、 动态查找C、 内查找D、 外查找3. 索引顺序表的特点是顺序表中的数据（A ） 。A、 有序B、 无序C、 块间有序D、 散列4. 采用顺序查找方法查找长度为n 的线性表时，每个元素的平均查找长度为（C）A、 n B、n/2 C、(n+1)/2

29、 D 、(n-1)/2 5. 设有序表的关键字序列为 1,3,9,12,32,41,45,62,75,77,82,95,100， 当采用二分查找法查找值为82 的节点时，经（D ）次比较后查找成功。A、 1 B、 2 C、 3 D、 4 6. 设有 100 个元素，用折半查找法进行查找时，最大、最小比较次数分别时（ A ）A、 7,1 B、6,1 C、5,1 D、8,1 7. 当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（C ） 。A必定快B不一定C在大部分情况下要快D取决于表递增还是递减8. 折半查找有序表（ 4，6，10，12，20，30，5

30、0，70，88，100） 。若查找表中元素 58，则它将依次与表中（A ）比较大小，查找结果是失败。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50 9. 如果要求用线性表既能较快地查找,又能适应动态变化的要求 ,则可采用 (A )查找方法。A、 分块查找B、 顺序查找C、 折半查找D、 基于属性10. 已知一如下 10 个记录的表 ,其关键字序列为 (2,15,19,25,30,34,44,55,58,80),用折半查找法查找关键字为55 的记录 ,比较次数是 (B )。A、 1 次B、 2 次C、 3 次D、 4 次11. 如果按关键码值递增的顺序依次将

31、99 个关键码值插入到二叉排序树中,则对这样的二叉排序树检索时 ,在等概率情况下查找成功时的平均查找长度ASL为( A)。A、 50 B、 48 C、 45 D、 47 12. 对包含 n 个元素的散列表进行查找 ,平均查找长度为 (A )。A、 不直接依赖于n B、 O(n2) C、 O(log2n) D、 O(n) 13. 衡量查找算法效率的主要标准是(A )。A、 平均查找长度B、 元素个数C、 所需的存储量D、 算法难易程度第九章排序1. 用冒泡排序方法对n 个记录按排序码值从小到大排序时，当初始序列是按排序码值从大到小排列时，与码值总比较次数是（D）。An-1 Bn Cn+1 Dn(

32、n-1) 2 2.下列排序方法中， 与排序码值总比较次数与待排序记录的初始序列排列状态无关的是(D) 。A直接插入排序 B冒泡排序 C快速排序 D直接选择排序3. 将 6 个不同的整数进行排序，至少需要比较(A) 次。A5 B6 C 15 D21 4. 将 6 个不同的整数进行排序，至多需要比较(C) 次。A5 B6 C 15 D21 5. 当待排序的整数是有序序列时，采用(B) 方法比较好，其时间复杂度为O(n)。A快速排序 B冒泡排序 C归并排序 D直接选择排序6. 当待排序的整数是有序序列时，采用（A）方法比较差，达到最坏情况下时间复杂度为 O(n2)。A快速排序 B冒泡排序 C归并排序

33、 D直接选择排序7. 当待排序的整数是有序序列时，无论待排序序列排列是否有序，采用（D）方法的时间复杂度都是O(n2)。A快速排序 B冒泡排序 C归并排序 D直接选择排序8. 若一组记录的排序码值序列为50，80，30，40，70，60利用快速排序方法，以第一个记录为基准，得到一趟快速排序的结果为（B ） 。A30， 40，50，60， 70，80 B 40，30，50，80，70，60 C50， 30，40，70， 60，80 D 40，50，30，70，60，80 9. 已知 Am中每个数组元素距其最终位置不远，采用下列(A) 排序方法最节省时间。A直接插入 B堆 C快速 D直接选择10.

34、 给定排序码值序列为 F，B，J，C，E，A，I，D，C，H，对其按字母的字典序列的次序进行排列，冒泡排序(大数下沉 )的第一趟排序结果应为（C ） 。AB， F，C，J，A， E，D，I ，C ，H BC， B，D，A，E， F，I ，C，J，H CB， F，C，E，A， I ，D，C，H ，J DA， B，D，C，E， F，I ，J，C ，H 11. 给定排序码值序列为 F，B，J，C，E，A，I，D，C，H，对其按字母的字典序列的次序进行排列，快速排序的第一趟排序结果为（B ） 。AB， F，C，J，A， E，D，I ，C ，H BC， B，D，C，E， A，F，I ，J，H CB， F

35、，C，E，A， I ，D，C，H ，J DA， B，D，C，E， F，I ，J，C ，H 12. * 给定排序码值序列为 F，B，J，C，E，A，I，D，C，H，对其按字母的字典序列的次序进行排列，二路归并排序的第一趟排序结果是（A ） 。AB， F，C，J，A， E，D，I ，C ，H BC， B，D，A，E， F，I ，C，J，H CB， F，C，E，A， I ，D，C，H ，J DA， B，D，C，E， F，I ，J，C ，H 13. 对序列 15,9,7,8,20,-1,4 进行排序 ,进行一趟后数据的排列变为9,15,7,8,20,-1,4, 则采用的排序方法是 ( A)。A、 直接

36、插入排序 B 、 选择排序 C 、 堆排序 D、 希尔排序14. 评价排序算法好坏的标准主要是(A )。A、 执行时间和所需的辅助空间 B 、 执行时间 C 、 辅助空间 D、 算法本身的复杂度15. 对 n 个不同的排序码进行冒泡(递增)排序,在下列 ( A )情况比较的次数最多。A、 从大到小排列好的 B 、 从小到大排列好的 C 、 元素无序 D 、 元素基本有序判断题1顺序存储方式的优点是存储密度大, 且插入、删除运算效率高。（）2数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。（）3静态链表与动态链表在元素的插入、删除上类似, 不需做元素的移动。（ ）4顺序表适宜于顺

37、序存取, 而链表适宜于随机存取。（）5线性表的链式存储结构中, 逻辑上相邻的两个元素在物理位置上并不一定相邻。（ ）6 两顺序栈共享空间, 也存在空间溢出问题。（）7 在对不带头结点的链队列作出队操作时, 不会改变头指针的值。（）8. KMP 算法的特点是在模式匹配时指示主串的指针不会回溯。（ ）9. 子串的定位运算称为串的模式匹配。（）10. 串student和Student相等。（）11 多维数组可以看作是一种特殊的线性表。（ ）12. 一个稀疏矩阵Am,n 采用三元组顺序表形式表示, 若把三元组中有关行下标与列下标的值互换 ,并把 m和 n 的值互换 , 则就完成了Am,n 的转置运算。

38、（）13. 稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。（）14. 满二叉树一定完全是二叉树。（ ）15. 二叉树的遍历结果不是唯一的。（ ）16. Hash 表的平均查找长度与处理冲突的方法无关。（）17. 在二叉树排序树中插入一个新结点,总是插入到叶结点下面。（）18. 哈希表是一种将关键字转换为存储地址的存储方法。（）19. 在二叉排序树上删除一个结点时, 不必移动其它结点, 只要将该结点的父结点的相应的指针域置空即可。（）20. 程序与算法没有区别。（）21. 一个算法可以没有输入，但不能没有输出。（）22. 顺序存储结构通过数据元素的地址直接反映数据元素的逻辑关系。（）23. 链

39、式存储结构通过指针间接反映数据元素之间的逻辑关系。（）24. 数据的存储结构通常只有顺序存储结构和链式存储结构两种。（）25. 逻辑结构不同的数据应该采用不同的存储结构。（）26 算法分析的前提是算法的时空效率高。（）27. 数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算个方面。（）28. 数据是计算机加工处理的对象。（）29. 算法可以用任意的符号来描述。（）30. 栈是一种后进先出的线性表。（）31. 在 n 个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反。（）32. 栈是线性表的特例，是指元素先进后出。（）33. 用链式存储结构保存的线性表，称为链表。（）34

40、. 顺序表与顺序栈没有区别，它们都是顺序存储结构。（）35. 队列的特点是先进先出。（）36. 将插入和删除限定在表的同一端进行的线性表是队列。（）37. 队列是一种对进队列、出队列操作的次序做了限制的线性表。（）38. 栈和队列没有区别，都是受限的线性表。（）39. 链栈与链队没有区别，都是用链式存储结构保存数据的线性表。（）40. 二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。（）41. 二叉树的前序遍历中，任意结点均处在其子女结点之前。（）42. 线索二叉树是一种逻辑结构。（）43. 哈夫曼树的总结点个数（多于1 时）不能为偶数。（）44. 由二叉树的先序序列和后序序列可以唯

41、一确定一棵二叉树。（）45. 树的后序遍历与其对应的二叉树的后序遍历序列相同。（）46. 根据任意一种遍历序列即可唯一确定对应的二叉树。（）47. 满二叉树也是完全二叉树。（）48. 哈夫曼树一定是完全二叉树。（）49. 树的子树是无序的。（）简答题第一章绪论1. 请分别给出数据、 数据对象、数据元素、 数据项的含义， 并说明四者的关系。数据 (Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并能被计算机程序处理的符号的总称。（1 分）数据元素 (Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，相当于表中的一条记录。（1 分

42、）数据项：相当于记录的“域”, 是数据的不可分割的最小单位, 如学号 . （ 1 分）数据对象：性质相同的数据元素的集合，是数据的一个子集. 例如 : 同一个班的所有学生记录集合。 （1 分）关系：包含关系：数据泛指所有。数据对象是数据的一个子集，由数据元素组成，数据元素是由数据项组成。（1 分）评分标准，总共5 个得分点，每段话一个得分。2. 简述算法的设计要求1、正确性、 2、可读性、 3、健壮性、 4、通用性、 5、效率与存储的要求（执行算法所耗费的存储空间、执行算法所耗费的时间）评分标准，本题共5 个得分点，每个要点一分。3. 请简述数据结构所研究的三种基本结构，以及数据元素间的关系。

43、线性结构：数据元素之间一对一的关系。（2 分）树形结构：数据元素之间一对多的关系。（1.5 分）图形结构：数据元素之间多对多的关系。（1.5 分）4. 请问算法的分析和评价的两个标准，以及各自作用。时间复杂度：评估算法运行所需时间。（1.5+1 分）空间复杂度：评估算法运行时所需最大存储空间。（1.5+1 分）5. 数据结构研究数据元素的哪些方面，每方面又具体包括什么。（5 分）研究数据元素间的：（1）逻辑关系，即逻辑结构，包括线性、树、图的结构类型（2）存储方式，即存储结构，包括有顺序存储和链式存储（3）数据处理，即运算，包括有插入、删除、查找、排序等。第二章线性表1. 请问如果要插入一个数

44、据到一个线性表中，顺序表和链表哪个的效率高？为什么？链表的效率高（2 分） ，因为顺序表要移动插入位置后的每一个元素的位置给新数据腾位置（ 1.5 分） 。链表只需要将前一个数据的指针指向新数据并将新数据的指针指向后一个数据即可（1.5 分） 。2. 线性表有哪些特点？1）除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素；（ 2 分）2）第一个数据元素没有前驱数据元素；（1.5 分）3）最后一个数据元素没有后继数据元素。（1.5 分）3. 顺序存储结构的优缺点有哪些? (中等) 顺序存储结构的优点:（2.5 分） 1）存储空间连续2）逻辑相邻，物理相邻3）可随机

45、存取任一元素缺点 :（2.5 分） 1）插入、删除操作需要移动大量的元素2）预先分配空间需按最大空间分配，利用不充分3）表容量难以扩充4. 单链表优缺点有哪些 ? (中等) 单链式存储结构的优点:（2.5 分） 1）不需预先分配空间，空间利用充分2）插入、删除操作简单 , 无需移动大量的元素3）表容量易于扩充缺点 :（2.5 分） 1）每个数据元素，除存储本身信息外，还需空间存储其直接后继的信息2）逻辑相邻，物理不一定相邻3）不可随机存取任一元素, 只能从链表头依次查找. 5. 请描述在顺序表中第i 个位置插入新的数据x 操作过程。根据顺序表的存储特点，要在表中某位置i 插入一新数据元素，则要

46、进行如下两步操作：（1）从位置 i 到表尾位置的所有数据元素均要从后至前依次向后移一个存储位置，为新插入结点腾出第i 个位置；（2 分）（2）将新数据x 插入到空余位置i 处。 （2分）（3）表长度加1. （1 分）6. 请描述在一个单链表中插入一个数据q 的插入过程。（1）找到将插入数据位置的前一个结点p; （1 分）（2）q 的 next 值等于 p 的 next 值;（ 2 分）（3）p 的 next 值等于 q； （2 分）7. 请描述从一个单链表中删除一个数据的删除过程。（1）找到将被删除数据的前一个结点p; （2 分）（2）p 的 next 指针指向被删除数据的后一个结点；（2 分

47、）（3）将被删除数据原来的next 指针指向null; （1 分）第三章栈和队列1. 请简述线性表、栈和队列三者之间的联系。（简单）（1）线性表、栈和队列都属于线性结构。（2 分）（2）栈和队列都是特殊的线性表，并且都有顺序存储、链式存储两种存储方式。 （1 分）（3）栈是一种先进后出的线性表，队列是一种先进先出的线性表（2 分）2. 在计算机进行运算时，需要把十进制转换为二进制。请问答：这种数制转换可以借助于哪种数据结构实现、及原因。答:栈。 （2 分）原因： （ 3 分）在进行数值转换时，其实质是求余的过程，并且余数的倒序序列正是所求结果。栈是一种先进后出的线性结构，能够满足这种操作。3.

48、 有一字符序列 abcde 依次按照某一线性结构存储，请回答以下问题：（1） 、如果该线性结构是队列，那么，写出出队序列。（2） 、如果该线性结构是栈，那么，输出序列可能是d,c,e,a,b 吗，为什么？（3） 、如果该线性结构是栈，且输出序列是abcde。请写出操作过程。 （push (x)：表示把 x 压入栈内； pop (x)：表示把 x 弹出栈）答：（1） 、abcde（1 分）（2） 、不可能，因为：d 是第一出栈字符，说明a,b 已别压入栈内；并且压入栈的次序为 abcde； 由以上得出： ab 出栈的顺序只能是b、 a， 而不是 a、 b。 所以，出栈序列d,c,e,a,b是不可

49、能的。 （2 分）（3） 、 （2 分）push ( a) ，pop ( a) push ( b) ，pop ( b) push ( c) ，pop ( c) push ( d) ，pop ( d) push ( e) ，pop ( e)4. 简述栈和队列的异同点。相同点：栈和队列都是只允许在表的端点处进行插入、删除操作的线性表。（2 分）不同点：栈的特点是先进后出，队列的特点是后进先出。（3 分）5. 若依次读入数据元素序列1、2、3，进栈的过程中允许出栈，试写出各种可能的出栈序列。答:123、 132、 213、231、321（各 1 分）6. 如果入栈序列有组成, 请问输出序列可能有哪些

50、? (较难) 输出序列有5 种：C B A, B C A, B A C, A C B , A B C（各 1 分）7. 设将整数 1 ，2，3，4 依次进栈，能否得到1423 出栈序列和 1432?并说明为什么不能得到或者如何得到。 （中等）不能得到1423，但可以得到1432（2 分）因为要得到4 必须将所有数据入栈，这样将只能依次获取到1432 不能获得1423。采用push、pop、 push、push、push、pop、pop、 pop 可以获得 1432。 （3 分）8.循环队列的优点是什么？如何判断的空和满。优点：可以克服队列假溢出现象。2 分队满： (rear+1)%M=fron