完美WORD格式.整理

一、选择题

（1）数据结构通常是研究数据的（ A ）及它们之间的相互联系。

A. 存储结构和逻辑结构 B. 存储和抽象 C. 联系和抽象 D. 联系与逻辑 （2）在逻辑上可以把数据结构分成：（ C ）。

A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构

（3）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（ C ）。

A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结 （4）算法分析的两个主要方面是（ A ）。

A. 空间复杂性和时间复杂性 B. 正确性和简明性

C. 可读性和文档性 D. 数据复杂性和程序复杂性 （5）下列时间复杂度中最坏的是（ D ）。

2

A. O（1） B. O（ n） C. O（log2n） D. O（n） （6）等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（ C ）。

A．n

B．(n-1)/2 C． n/2 D．(n+1)/2

（7）设有编号为1，2，3，4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为 ( D )

A．1234 B．1243 C．1324 D．1423 （8）如果以链表作为栈的存储结构，则出栈操作时（ B ） A．必须判别栈是否满 B．必须判别栈是否空 C．必须判别栈元素类型 D．队栈可不做任何判别 （9）链栈与顺序栈相比，有一个比较明显的优点是（ B ）。

A．插入操作更加方便 B．通常不会出现栈满的情况。 C．不会出现栈空的情况 D．删除操作根加方便 （10）插入和删除只能在一端进行的线性表，称为( C )。 A．队列 B．循环队列 C．栈 D．循环栈 （11）若进队的序列为：A，B，C，D，则出队的序列是（ C ）。 A．B，C，D，A C．A，B，C，D

B．A，C，B，D D．C，B，D，A

（12）若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( B )。 A．5和1

A．\ 为( A )。

A．\

B．\

C．\ D．\

. 专业资料分享 .

B．4和2 C．2和4 D．1和5

C．\ D．\

（13）S=\，执行求子串函数SubStr(S,2,2)后的结果为( B )。

B．\

（14）S1=\，S2=\，执行串连接函数ConcatStr(S1,S2)后的结果

完美WORD格式.整理

（15）S1=\，S2=\，执行函数SubStr(S2,4,LenStr(S1))后的结果为( B )。 A．\

B．\

C．\ D．\（16）设串S1=\，S2=\

则ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的结果串为( D )。

A．BCDEF B．BCDEFG C．BCPQRST D. BCDEFEF (17)已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a[3][5]的存储地址是1000，则a[0][0]的存储地址是（ B ）。

A．872

B．860

C．868

D．864

（18）在一棵具有五层的满二叉树中，结点的总数为（ B ）

A．16 B．31 C．32 D．33 （19）具有64个结点的完全二叉树的深度为（ C ）

A．5 B．6 C．7

（20）具有n（n>1）个结点的完全二叉树中，结点i（2i>n）的左孩子结点是（ D ）。

A．2i

B．2i+1

C．2i-1

D．不存在

（若2i<=n，则答案为A）

（21）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为（ B ）。 A．46

B．47

C．90

D．91

（22）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的右孩子编号为（ B ）。 A．98

B．99

C．50

D．100

（23）用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是（ B ）。

Ａ．32 Ｂ．33 Ｃ．34 Ｄ．15 （ 先构造哈夫曼树，WPL=（1+2）*3+（3+4+5）*2=33 ） （24）二叉树的叶结点个数比度为2的结点的个数（ C ）。 A．无关 A．n A．n （ C ）。 A．n-1

B．n+1

C．n

D．n+e

（28）在图的表示法中，表示形式唯一的是（ A ）。

A．邻接矩阵表示法 B．邻接表表示法

B．相等

C．多一个 D．少一个

C．n(n-1)/2 D．2n

D．n/2

（25）对于一个具有n个顶点的有向图的边数最多有（ B ）。

B．n(n-1) B．n+1

（26）在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。

C． n-1

（27）对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为

. 专业资料分享 .

完美WORD格式.整理

C．逆邻接表表示法 D．邻接表和逆邻接表表示法 （29）对有14个元素的有序表A[1..14]作二分查找，查找元素A[4]时的被比较元素依次为（ C ）。

A．A[1]，A[2]，A[3]，A[4] C．A[7]，A[3]，A[5]，A[4] A． 4 5 3 1 2

B．A[1]，A[14]，A[7]，A[4] D．A[7]，A[5]，A[3]，A[4] C．4 5 2 1 3

D．4 2 3 1 5

（30）不可能生成下图二叉排序树的关键字的序列是（ A ）。

B．4 2 5 3 1

4 21 3 5

（31）排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为 ( D )。

A．希尔排序 B．归并排序 C．插入排序 D. 选择排序 （32）每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做（ C ）。

A．冒泡排序 B．堆排序 C．快速排序 D. 归并排序 （33）直接插入排序的方法是从第（ B ）个元素开始，插入到前边适当位置的排序方法。 A．1 B．2 C．3 D．n （34）堆的形状是一棵（ C ）。

A．二叉排序树 B．满二叉树 C．完全二叉树 D．平衡二叉树 （35）一组记录的排序码为(25，48，16，35，79，82，23，40)，其中含有4个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为：（ A ）。 A，16 25 35 48 23 40 79 82 36 72 B．16 25 35 48 79 82 23 36 40 72 C．16 25 48 35 79 82 23 36 40 72 D．16 25 35 48 79 23 36 40 72 82 （36）一个数据序列的关键字为：（46，79，56，38，40，84），采用快速排序，并以第一个数为基准得到第一次划分的结果为：（ C ）

A．（38，40，46，56，79，84） C．（40，38，46，56，79，84）

二、填空题

（1） 若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为 O

（nlog2n） 。

（2） 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存

取线性表中的元素时，应采用 顺序 存储结构。

（3） 对一个需要经常进行插入和删除操作的线性表，采用 链式 存储结构为宜。 （4） 双链表中，设p是指向其中待删除的结点，则需要执行的操作为：

B．（40，38，46，79，56，84） D．（40，38，46，79，56，84）

. 专业资料分享 .

完美WORD格式.整理

p->prior->next=p->next 。

（5） A+B/C-D*E的后缀表达式是： ABC/+DE*- 。 （6） 解决顺序队列“假溢出”的方法是采用 循环队列 。

（7） 循环队列的队首指针为front，队尾指针为rear，则队空的条件为 front ==

rear 。

（8） 设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一

个空闲元素，队列的最大空间为MAXLEN，则队满标志为： front==(rear+1)%MAXLEN 。

（9） 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有

front=11，rear=19，则循环队列中还有 8 个元素。（L= (N＋rear－front)% N=（40＋19－11）% 40=8）

（10） 设S=\，则LenStr(s)= _ 8 。

（11） 两个字符串分别为：S1=\is\，S2=\

July,2005\的结果是： Today is 30 July,2005 。

（12） 求子串函数SubStr(\的结果是：

July 。

（13） 在串的运算中，EqualStr(aaa,aab)的返回值为 <0 。

（14） 多维数组的顺序存储方式有按行优先顺序存储和 按列优先顺序存储 两

种。

（15） 在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所

以多维数组是一种 随机 存取结构。

（16）tail(head((a,b),(c,d))= b 。

（17） 设广义表((a,b,c))，则将c分离出来的运算是 head(tail(tail(head(L)))) （18） 广义表LS=（a,(b),((c,(d)))）的长度是 3 。 （19） 广义表LS=（a,(b),((c,(d)))）的深度是 4 。

（21） 广义表LS=（a,(b),((c,(d)))）的表尾是 ((b),((c,(d)))) 。 (22)数组元素a[0..2][0..3]的实际地址上2000，元素长度是4，则LOC[1,2]= 2024 。

（23） n阶下三角矩阵，因为对角线的上方是同一个常数，需要 n（n-1）/2+1 个存储单元。

（24）稀疏矩阵的三元组有 3 列。

（25）稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的 行数 。 （26）n阶对称矩阵，如果只存储下三角元素，只需要 n（n-1）/2 个存储单元。 (27)哈夫曼树是带权路径长度 最小 的二叉树。

(28)由二叉树的后序和 中序 遍历序列，可以唯一确定一棵二叉树。

（29）某二叉树的中序遍历序列为: DEBAC，后序遍历序列为：EBCAD。则前序遍历序列为：DABEC 。

. 专业资料分享 .