《数据结构》复习题及答案(2)

《数据结构》复习题及答案（2）

一、判断题

1．在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。√

2． 线性表的逻辑顺序和存储顺序总是一致的。（×）

3．链表的每个结点都恰好包含一个指针域。（×）

4．有向图的邻接表和逆邻接表中表结点的个数不一定相等。（×）

5．对连通图进行深度优先遍历可以访问到该图中的所有顶点。（ √ ）

6．当装填因子小于1时，向散列表中存储元素时不会引起冲突。（×）

7．用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。（×）

8．数据的存储结构是数据的逻辑结构的存储映像。（ √ ）

9．当装填因子小于1时，向散列表中存储元素时不会引起冲突。（×）

10．散列技术的查找效率主要取决于散列函数和处理冲突的方法。（×）

11．非空的双向循环链表中任何结点的前驱指针均不为空。（ √ ）

12．子串“ABC”在主串“AABCABCD”中的位置为2。（ √ ）

13．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。（×）

14．线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。（ㄨ ）

15．稀疏矩阵压缩存储后，必会失去随机存取功能。（√ ）

16．对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。（ ㄨ ）

17．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（√ ）

18．数据的逻辑结构和数据的存储结构是相同的。（ ㄨ）

二、单向选择题

1．已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（ A ）。

A． B+(i-1)*m B．B+i*m C． B-i*m D． B+(i+1)*m

2．数据结构中，与所使用的计算机无关的是数据的（C ）

A．存储结构 B．物理结构 C．逻辑结构 D．物理和存储结构

3．若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（D ）存储方法最节省时间。

A 单链表 B 带头指针的单循环链表

C 双链表 D 带尾指针的单循环链表

4．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（ B ）结构。

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

5．用链接方式存储的队列，在进行插入运算时( D ).

A. 仅修改头指针 B. 头、尾指针都要修改

C. 仅修改尾指针 D.头、尾指针可能都要修改

6．以下论述正确的是（ C ）。

A．空串与空格串是相同的 B．\"tel\"是\"Teleptone\"的子串

C．空串是零个字符的串 D. 空串的长度等于1

7．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（C ）。

A h B h+1 C h或h+1 D 任意

8．数据的基本单位是（ B ）。

A.数据结构 B.数据元素 C.数据项 D.文件

9．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B ）个空指针域。

A 2m-1 B 2m C 2m+1 D 4m

10．设某有向图中有n个顶点，则该有向图对应的邻接表中有（ B ）个表头结点。

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

11．二叉排序树中左子树上所有结点的值均（ A ）根结点的值。

A < B > C = D !=

12．静态查找与动态查找的根本区别在于（B ）。

A 它们的逻辑结构不一样 B 施加在其上的操作不同

C 所包含的数据元素的类型不一样 D 存储实现不一样

13．散列技术中的冲突指的是（ D）。

14．A 两个元素具有相同的序号

B 两个元素的键值不同，而其他属性相同

C.数据元素过多

D 不同键值的元素对应于相同的存储地址

14．一组记录的关键码为{46, 79, 56, 38, 40, 84}，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ A ）。

A {40, 38, 46, 56, 79, 84} B {40, 38, 46, 79, 56, 84}

C {40, 38, 46, 84, 56, 79} D {84, 79, 56, 46, 40, 38}

15．对一个算法的评价，不包括如下（ B ）方面的内容。

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度

三、算法设计题

1．设计在顺序存储结构上实现求子串算法。

void substring(char s[ ], long start, long count, char t[ ])

{

long i,j,length=strlen(s);

if (start<1 || start>length) printf(\"The copy position is wrong\");

else if (start+count-1>length) printf(\"Too characters to be copied\");

else { for(i=start-1,j=0; it[j]=s[i]; t[j]= '\\0';

}

}

2．编写算法，要求输出二叉树后序遍历序列的逆序。

void Postordern(BiTree *H)

{ if (H)

{ visit(H->data);

Postordern(H->rchild);

Postordern(H->lchild);

}

}