一．是非题（共 分，每题 分）

1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系，P是

对D的基本操作集。(F) （D，S）二元就够了

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 对于插入、删除而言，线性表的链式存储优于顺序存储。(T)

8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(F) 链式优点 9. 栈和队列是操作上受限制的线性表。(T)

10. 队列是与线性表完全不同的一种数据结构。(F)

11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(F) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。()F 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。()F 15 二叉树是一棵结点的度最大为二的树。(F) 16 赫夫曼树中结点个数一定是奇数。(T)

17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(T)

18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历 。(F) 19. 通常，二叉树的第i层上有2i-1个结点。(F)最多可以有

20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(T) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(T) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。 (T) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(F)

24 可从任意有向图中得到关于所有顶点的拓扑次序。(F) 有环的不行 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(T) 26 关键路径是AOE网中源点到汇点的最短路径。(F) 长

27 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。(T) 28 一个无向图的连通分量是其极大的连通子图。(T)

29 十字链表可以表示无向图，也可用以表示有向图。(F) 30 邻接表可以表示有向图，也可以表示无向图。（ T） 32. 二叉排序树的最大查找长度与（LOG2N）同阶。(T) 33 选用好的HASH函数可避免冲突。(f) 34 折半查找不适用于有序链表的查找。(T)

35. 对于目前所知的排序方法，快速排序具有最好的平均性能。(T) 36 对于任何待排序序列来说，快速排序均快于冒泡排序。(F)

37 在最坏情况下，堆排序的时间性能是O(nlogn),比快速排序好(T)

选择题。

从逻辑上可以把数据结构分成( )。C

A. 动态结构和静态结构 B. 顺序组织和链接组织

C. 线性结构和非线性结构 D. 基本类型和组合类型 线性表L在( )情况下适于使用链表结构实现。B

A. 不需修改L的结构 B. 需不断对L进行删除、插入 C. 需经常修改L中结点值 D. L中含有大量结点

带头结点的单链表L为空的判断条件是 。B

带头结点的循环链表L为空的判断条件是 。C

A. L==null B. L->next==null

C. L->next==L D. L!=null 递归程序可借助于( )转化为非递归程序。C

a.线性表 b.队列 c: 栈 d.数组

在下列数据结构中( )具有先进先出（FIFO）特性，C

( )具有先进后出(FILO）特性。B

a．线性表 b．栈 c．队列 d．广义表

若对编号为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

在计算递归函数时，如不用递归过程，应借助于( ) 这种数据结构。B

A. 线性表 B. 栈 C. 队列 D. 双向队列

栈和队列的一个共同点是( )。C

A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点

循环队列用数组A[0..m-1]存放其元素值，设头尾指针分别为front和rear，则当前队列中的元素个数是( )。C

A. rear-front-1 B. Rear-front+1 C. (rear-front+m)%m D. Rear-front

4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’)

的结果是 ( ) 。D

a: ‘database’ b: ‘data-base’ c: ‘bas’ d: ‘data-basucture’

5. 设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储，存储器按字节编址.

已知A的起始地址为100。则按行存储时，元素A06的第一个字节的地址是（ ）D 按列存储时，元素A06的第一个字节的地址是（ ）A a: 220 b: 200 c: 140 d: 124

6. 对广义表 A=（（a,(b)）,(c,()),d）执行操作gettail(gethead(gettail(A))) 的结果是：（ ） 。B a:（） b: （（）） c: d d: (d)

假设用于通讯的电文仅由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 对二叉排序树（ ）可得到有序序列。C

a:按层遍历 b:前序遍历 c:中序遍历 d:后序遍历 在有n个结点的二叉树的二叉链表表示中，空指针数 （ ）。B

a.不定 b.n+1 c.n d.n-1

若某二叉树有20个叶子结点，有20个结点仅有一个孩子，则该二叉树的总结点数是

( )。C

A．40 B. 55 C. 59 D. 61

已知某二叉树的先序遍历次序为abcdefg 中序遍历次序为badcgfe，

则该二叉树的后序遍历次序为（ C ）。层次遍历次序为（ a ）。 a: abcdefg b: cdebgfa c: bdgfeca d: edcgfba

.图示的三棵二叉树中( )为最优二叉树。C

A) B) C)

c a 2 7

a b c d d b 7 5 2 4 4 5 a b c d 7 5 2 4

已知某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG。

则其先序遍历次序为（ b），层次遍历次序为（ a ）。

a: abcdefg b: abdcefg c: abcdfeg d: abcdegf 已知某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。

若将该树转换为二叉树,其后序遍历次序为（ d ）。

a: abcdefg b: cdebgfa c: cdegbfa d: edcgfba

设x和y是二叉树中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在

y之后，则x和y的关系是( )。C

A. x是y的左兄弟 B. x是y的右兄弟 C. x是y的祖先 D. x是y的子孙

用三叉链表作二叉树的存储结构，当二叉树中有n个结点时，有( D )个空指针。

A. n-1 B. n C. n+1 D. n+2

设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，则与森

林F对应的二叉树根结点的右子树上的结点个数是( )。D

A. m1 B. m1+m2 C. m3 D. m2+m3 下列二叉树中，( )可用于实现符号不等长高效编码。A

a:最优二叉树 b:次优查找树 c:二叉平衡树 d:二叉排序树 邻接表存储结构下图的深度优先遍历算法类似于二叉树的( )遍历。A A. 先根 B. 中根 C. 后根 D. 层次

设无向图G = (V,E)和G’= (V’,E’)，若G’是G的生成树，则下面不正确的说法是( )。D

A. G’是G的子图 B. G’是G的连通分量

C. G’是G的无环子图 D. G’是G的极小连通子图且V’= V

任何一个连通图的最小生成树( )。B

A．只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在

深度优先遍历图使用了数据结构（b ），而广度优先遍历图使用了数据结构（ C）。

A）数组 B）栈 C）队列 D）线性表

2．下列查找方法中（ ）适用于查找单链表。 A

A）顺序查找 B）折半查找 C）分块查找 D）hash查找

c: d: 哈希表的查找效率取决于（ ）。D

a: 哈希函数 b:处理冲突的方法。 c:哈希表的装填因子。 d:以上都是 在Hash函数H(k)=k MOD m中，一般来说，m应取( )。C+D 充分大的素数 A. 奇数 B. 偶数 C. 素数 D. 充分大的数

在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用 A 方法。 A.设置监视哨 B.链表存贮 C.二分查找 D.快速查找

静态查找表和动态查找表的区别在于( )。B A. 前者是顺序存储，而后者是链式存储

B. 前者只能进行查找操作，而后者可进行查找、插入和删除操作 C. 前者只能顺序查找，而后者只能折半查找 D. 前者可被排序，而后者不能被排序

在一个含有n个元素的有序表上进行折半查找，找到一个元素最多要进行( B )次元素比较。

A．?log2(n)? B. ?log2(n)?+1 C. ?log2(n+1)? D. ?log2(n+1)?+1 若有序表中关键字序列为：14，20，25，32，34，45，57，69，77，83，92。对其进

行折半查找，则在等概率情况下，查找成功时的平均查找长度是( C )。查找32时需进行( C )次比较。

A. 1 B. 2 C. 3 D. 4

已知哈希表地址空间为A[9]，哈希函数为H(k)=k mod 7，采用线性探测再散列处理冲突。

若依次将数据序列：76,45,88,21,94,77,17存入该散列表中，则元素17存储的下标为( H )；在等概率情况下查找成功的平均查找长度为( C )。

A. 0 B. 1 C. 2 D. 3