《数据结构复习题》由会员分享，可在线阅读，更多相关《数据结构复习题（26页珍藏版）》请在金锄头文库上搜索。
1、一是非题（共 分，每 题 分） 1. 数据结构可用三元式表示（D，S，P）。其中：D 是数据对象，S 是 D 上的关系，P 是对 D 的基本操作集。(f) 2 简单 地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表（头指针为 L ）中指 针 p 所指结点是最后一个元素结点 的条件是：p-next=L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线 性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表 P 指针所指结点之后插入 S 结点的操作是： P-next= S ; S- next = P-next; 。(f) 7 对
2、 于插入、删除而言，线 性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、 删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 栈和队列是与 线性表完全不同的一种数据结构。(f) 11. 队列是一种操作受限的线性表，凡 对数据元素的操作仅限一端进行。(f) 12. 栈和队列也是 线性表。如果需要，可对它们中的任一元素进行操作。(f) 13. 栈是限定 仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而 对一般的树，则无此限制，所 以，二叉 树是树的 特殊情形。(f) 15 二叉 树是一棵 结点的
3、度最大 为二的树。(f) 16 赫夫曼 树 中结点个数一定是奇数。(t) 17 在二叉 树 的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) 18 假 设 B 是一棵树，B 是对应 的二叉树。则 B 的后根遍历相当于 B的后序遍历 。(f) 19. 通常，二叉 树的第 i 层上有 2 i-1 个结点。(f) 20. 中序线索二叉 树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉 树的先序遍 历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由 树结点的先根序列和后根序列可以唯一地确定一棵树。 (t) 23 邻 接多重表可以用以表示无向图，也可用以
4、表示有向图。(f) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) 25 有向 图的十字 链表是将 邻接表和逆邻接表合二为一的链表表示形式。(t) 26 关 键路径是 AOE 网中源点到汇点的最短路径。(f) 27 连 通图 G 的生成树是一个包含 G 的所有 n 个顶点和 n-1 条边的子图。(f) 28 一个无向图的连通分量是其极大的连通子图。(t) 29 十字 链表可以表示无向图，也可用以表示有向图。(f) 30 邻 接表可以表示有向图 ，也可以表示无向图。（ t ） 31. 二叉排序 树的平均查找 长度为 O( log) 。(t) 32. 二叉排序 树的最大查找 长度与（lo
5、g n ）同阶。(f) 33 选 用好的 hash 函数可避免冲突。(f) 34 折半 查找不适用于有序链表的查找。(t) 35. 对于目前所知的排序方法，快速排序具有最好的平均性能。(t) 36 对 于任何待排序序列来说，快速排序均快于冒泡排序。(f) 37 在最坏情况下，堆排序的时间性能是 O(nlogn),比快速排序好(t)38 快速排序具有最好的平均 时间性能，它在任何时候的时间复杂度都是 O（n log n）。(f) 39. 字符串是数据 对象特定的 线性表。(t) 40. 空串与空格串是相同的。(f) 41. 对于一棵 m 阶的 B - 树.树中每个结点至多有 m 个关 键字.除根
6、之外的所有非终端结 点至少有m/2个关键字。(f) 42. 当二叉排序 树是一棵平衡二叉 树时，其平均 查找长度为 O(log 2 n)。(t) 43. 广义表的表 头和表尾都是广 义表。(f) 44 二维 数组是其数据元素为线 性表的线性表。(t) 45弗洛伊德算法的基本思想是依最短路径 长度递增的次序求得各条路径。 （f） 选择题。 1. 从逻辑上可以把数据结构分成( c ) 。A. 动态结构和静态结构 B. 顺序组织和链接组织 C. 线性结构和非线性结构 D. 基本类型和组 合类型 2. 线性表 L 在( b ) 情况下适于使用链表结构实现。A. 不需修改 L 的结构 B. 需不断对 L
7、 进行 删除、插入C. 需经常修改 L 中结点值 D. L 中含有大量结点 3. 带头结点的单链表 L 为空的判断条件是 b 。 带头结点的循环链表 L 为空的判断条件是 。 A. L=null B. L-next=null C. L-next=L D. L!=null 4. 若顺序表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率：若找到指定 的结点，将该结点与其后继（若存在） 结点交换位置，使得 经 常被查找的结点逐渐移至 表尾。以下为据此策略编写的算法，请选择适当的内容，完成此功能。 顺序表的存储结构为： typedef structElemType *elem; /数据元素存储
8、空间，0 号单元作监视哨int length; /表长度SSTable; int search_seq(SSTable ST,KeyType key) /在 顺 序表 ST 中顺序查找关键字等于 key 的数据元素。 /若找到，则将该元素与其后 继交换位置，并返回其在表中的位置，否 则为 0。 ST.elem0.key=key; i=ST.length; while(ST.elemi.key!=key) f ; if( g )ST.elemiST.elemi+1；e ； return i; a. i0 b. i=0 c. iST.length d. i=ST.length e. i+ f. i
9、- g. a 和 c 同时满足 h. b 和 d 同时满足5. 递归程序可借助于( c )转化为非递归程序。a.线性表 b.队列 c: 栈 d.数组 6. 在下列数据结构中( c )具有先进先出（FIFO ）特性， ( b )具有先进后出(FILO）特性。 a线性表 b 栈 c 队列 d 广 义表7. 若对编号为 1，2，3 的列车车厢依次通过扳道栈进行 调度，不能得到 ( e ) 的序列。a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 8. 在计算递归函数时，如不用递归过程，应借助于( b ) 这种数据结构。 a. 线性表 b. 栈 c. 队列
10、 d. 双向队列 9. 若带头结点的链表只设尾结点指针。下列 选择中（ c ）最适用于队列。a.单链表 b.双向链表 c. 循环单链表 d.双向循环链表 10. 栈和队列的一个共同点是( c ) 。a. 都是先进先出 b. 都是先进后出c. 只允许在端点处插入和删除元素 d. 没有共同点 11. 循环队列用数组 A0.m-1存放其元素值， 设头尾指针分别为 front 和 rear，则当前 队列中的元素个数是( c )。a. rear-front-1 b. rear-front+1c. (rear-front+m)%m d. rear-front 12. 如下关于串的 陈述中，正确的是( a,
11、 c ) 。 a. 串是数据元素类型特殊的线性表 b. 串中的元素是字母 c. 串中若干个元素构成的子序列称为子串 d. 空串即为空格串 13. 对字符串 s=data-structure 执行操作 replace(s,substring(s,6,8),bas) 的结果是 ( b ) 。 a: database b: data-base c: bas d: data-basucture 14. 对广义表 A= （a,(b) ）,(c,(),d）执行操作 gettail(gethead(gettail(A) 的结果是：（ b ） 。 a:（） b: （） c: d d: (d) 15. 假设用于
12、通 讯的电文仅由 6 个字符组成，字母在 电文中出 现的频率分别为 7, 19, 22, 6, 32, 14 。若 为这 6 个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从 左至右的结合，新生成的二叉 树总是插入在最右）， 则频率 为 7 的字符编码是（ g ）， 频率为 32 的字符 编码是（ c ）。 a: 00 b: 01 c: 10 d: 11 e: 011 f: 110 g: 1110 h:1111 16. 对二叉排序 树（ c ）可得到有序序列。a:按层遍历 b: 前序遍 历 c:中序遍历 d:后序遍历 17. 设一棵二叉 树 BT 的存储结 构如下:1 2 3 4
13、5 6 7 8lchild 2 3 0 0 6 0 0 0data A B C D E F G Hrchild 0 5 4 0 8 7 0 0其中 lchild，rchild 分别为结 点的左、右孩子指 针域，data 为结点的数据域。 则 该二叉树的高度为( d )； 第 3 层有( a )个结点（根结点为第 1 层）。a2 b. 3 c. 4 d. 518. 先序遍历图 示二叉树可得到（ a ）的序列。 a) A B H D E F I C G b) H B E D F I A C G c) H E I F D B G C A (A) (B) (C) (H) (D) (G) (E) (F)(I)19. 在有 n 个结点的二叉树的二叉链表表示中，空指 针数 （ b ）。a.不定 b.n+1 c.n d.n-1 20. 若某二叉树有 20 个叶子 结点，有 20 个结点仅有一个孩子，则该二叉树的总结点数是( c )。a40 b. 55 c. 59 d. 61 21. 已知某二叉 树的先序遍历 次序为 abcdefg 中序遍历次序为 badcgfe， 则该二叉树的后序遍历次序为（ c ）。 层次遍历次序为（ a ）。a: abcdefg b: cdebgfa c: bdgfeca d: edcgfba .22. 图示的三棵二叉树中
