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