数据结构答案

单选题（共 20 题,每题 2 分）

假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。

标准

1 A: (rear-front+m)%m 答案：B: rear-front+1 A C: (front-rear+m)%m D: (rear-front)%m

串 ababaaababaa 的next数组为（ C ）。 标准

A: 012345678999 2 答案：B: 012121111212

C

C: 011234223456 D: 0123012322345

在一个带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行(D )。

标准

3 A: HL＝p;p->next＝HL; 答案：B: p->next＝HL;HL＝p; D C: p->next＝HL;p＝HL;

D: p->next＝HL->next;HL->next＝p；

递归过程或函数调用时，处理参数及返回地址，要用一种称为（C ）的数据结构。

标准

4 A: 队列 答案：B: 多维数组 C C: 栈

D: 线性表

下面关于线性表的叙述中，错误的是哪一个？（ B ） A: 线性表采用顺序存储，必须占用一片连续的存储单

标准

元。 5 答案：B: 线性表采用顺序存储，便于进行插入和删除操作。

B

C: 线性表采用链接存储，不必占用一片连续的存储单元。

D: 线性表采用链接存储，便于插入和删除操作。 线性表L=（a1,a2,…,an），下列陈述正确的是（ D ） A: 每个元素都有一个直接前驱和一个直接后继 标准6 B: 线性表中至少有一个元素 答案：C: 表中诸元素的排列必须是由小到大或由大到小 D D: 除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和直接后继

当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( B )参数，以节省参数值的传输时间和存储参数的空间。

标准

7 答案：A: 整形 B B: 引用型 C: 指针型

D: 常值引用型

设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。

标准

8 A: 单链表 答案：B: 单循环链表 D C: 带尾指针的单循环链表 D: 带头结点的双循环链表

循环链表H的尾结点P的特点是（ A ）。 A: P->next==H 9

B: P->NEXT==H->NEXT C: P==H

D: P==H->next

串的长度是指（ B）。

标准答案：A

标准

A: 串中所含不同字母的个数 11 答案：B: 串中所含字符的个数

B

C: 串中所含不同字符的个数 D: 串中所含非空格字符的个数

用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( A )。

标准

A: 5 12 答案：B: 6 A C: 8 D: 9

标准

13 在一个长度为 n顺序表中，在第i个元素(1<=i<=n)之后

答案：

插入一个新元素时，需向后移动（ A ）个元素。 A: n-i B: n-i+1 C: n-i-1 D: i

已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( D )

A: -A+B*C/DE 14

B: -A+B*CD/E C: -+*ABC/DE D: -+A*BC/DE

用链接方式存储的队列，在进行删除运算时（ D）。

A

标准答案：D

标准

A: 仅修改头指针 15 答案：B: 仅修改尾指针

D

C: 头、尾指针都要修改

D: 头、尾指针可能都要修改

在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( B )。

标准

A: HL＝p;p->next＝HL; 16 答案：B: p->next＝HL;HL＝p; B C: p->next＝HL;p＝HL;

D: p->next＝HL->next;HL->next＝p；

连续存储设计时，存储单元的地址（ A ）。 A: 一定连续 17

B: 一定不连续 C: 不一定连续

D: 部分连续，部分不连续

在下述结论中，正确的是（ D ）

标准答案：A

①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相标准18 同的满二叉树。 答案：

D

A: ①②③ B: ②③④ C: ②④ D: ①④

下列哪一种图的邻接矩阵是对称矩阵？（B ）

标准

A: 有向图 19 答案：B: 无向图

B

C: AOV网 D: AOE网

当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A[l..n]中时，数组中第i个结点的左孩子为（ D ）

标准

20 答案：A: A[2i](2i=〈n)

D

B: A[2i+1](2i+1=< n) C: A[i/2] D: 无法确定

判断题（共10题,每题2分）

标准答案：N 标准答

2 循环链表不是线性表. ( N )

案：N

健壮的算法不会因非法的输入数据而出现莫名其标准答3

妙的状态。( Y ) 案：Y 数据的逻辑结构是指数据的各数据项之间的逻辑标准答4

关系；( N ) 案：N

标准答

5 有n个顶点的连通图有n-1条边。( N )

案：N

任意一棵非空二叉排序树，删除某结点后又将其

标准答

6 插入，则所得二叉排序树与删除前原二叉排序树

案：N

相同。( N)

在二叉树的第i层上至少有2i-1个结点(i>=1)。标准答7

( N ) 案：N 队列是一种插入与删除操作分别在表的两端进行标准答8

的线性表，是一种先进后出型结构。（ N ） 案：N 线性表的特点是每个元素都有一个前驱和一个后标准答9

继。( N ) 案：N 算法的优劣与算法描述语言无关，但与所用计算标准答10

机有关。( N ) 案：N 1 二叉树是度为2的有序树。( N )

标准答案：

对于给定的n个元素,可以构造出的逻辑结构

集合

有 ___集合_______、______线性结构______、1 线性结构&!@线性____树形结构_____、______图状结构_______

&!@线型

四种。

树形结构&!@树型

结构&!@树型&!@树形

图状结构&!@网状结构&!@图形结构&!@&!@图型&!@图形&!@图状&!@网状 标准答案：

线索二元树的左线索指向其_____前驱_，右线前驱 2

索指向其___后继___。 后继 标准答案：

由空格字符（ASCII

空格串是指_由空格字符（ASCII值32）所组值32）所组成的字3

成的字符串__，其长度等于__空格个数_ 符串

空格个数 每次从无序表中顺序取出一个元素，把这插入标准答案： 到有序表中的适当位置，此种排序方法叫做插入 4

___插入_排序。(从插入、交换、选择、归并、 基数中选择一个)

已知一棵度为3的树有2个度为1的结点，3标准答案： 5 个度为2的结点，4个度为3的结点，则该树12 有___12 _个叶子结点。

标准答案：

带头结点的双循环链表L中只有一个元素结点L->next->next==L 6

的条件是：___L—>next->next==L_____ 有一份电文中共使用 6个字符:a,b,c,d,e,f,它们标准答案： 的出现频率依次为2,3,4,7,8,9，试构造一棵哈80 7

夫曼树，则其加权路径长度WPL为_80_，字001 符c的编码是_001__。

在一棵度为4的树T中，若有20个度为4的标准答案： 结点，10个度为3的结点，1个度为2的结点，82 8

10个度为1的结点，则树T的叶结点个数 是 82 。

每一棵树都能唯一的转换为它所对应的二叉标准答案： 树。若已知一棵二叉树的前序序列是FEGHDCB 9

BEFCGDH，中序序列是FEBGCHD，则它的 后序序列是__FEGHDCB_。

标准答案：

一个有2001个结点的完全二叉树的高度为

11

10 __11_ 。