数据结构期末考试（题集）

数据结构的基本概念

选择题

（1） 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构

中的数据元素之间的逻辑关系是由（ ）表示的。 A．线性结构 B．非线性结构 C．存储位置 D．指针

（2） 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲

或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A．树 B．图 C．线性表 D．集合

（3） 计算机所处理的数据一般具有某种内在联系，这是指（ ）。 A．数据和数据之间存在某种关系 B．元素和元素之间存在某种关系 C．元素内部具有某种结构 D．数据项和数据项之间存在某种关系

（4） 在数据结构中，与所使用的计算机无关的是数据的（ ）。 A．树 B．图 C．线性表 D．集合

（5） 在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）。 A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法

（6） 在链接存储结构中，要求（ ）。

A．每个结点占用一片连续的存储区域 B．所有结点占用一片连续的存储区域 C．结点的最后一个域是指针类型 D．每个结点有多少个后继就设多少个指针

（7） 下列说法不正确的是（ ）。 A．数据元素是数据的基本单位 B．数据项是数据中不可分割的最小单位 C．数据可由若干个数据项构成 D．数据元素可由若干个数据项构成

（8） 以下与数据的存储结构无关的术语是（ ）。 A．循环队列 B．链表 C．散列表 D．栈

（9） 以下术语属于逻辑结构的是（ ）。 A．顺序表 B．哈希表 C．有序表 D．单链表

（10） 可以用（ ）定义一个完整的数据结构。 A．数据元素 B．数据对象 C．数据关系 D．抽象数据类型

（11） 对于数据结构的描述，下列说法中不正确的是（ ）。 A．相同的逻辑结构对应的存储结构也必相同

B．数据结构由逻辑结构、存储结构和基本操作三方面组成

1

C．数据结构基本操作的实现与存储结构有关

D．数据的存储结构是数据的逻辑结构的机内实现

（12） 以下关于链接存储结构的叙述中，（ ）是不正确的。

A．结点除数据信息外还包括指针域，因此存储密度小于顺序存储结构 B．逻辑上相邻的结点物理上不一定相邻 C．可以通过计算得到第i个结点的存储地址 D．插入和删除操作方便，不必移动结点

（13） 可以用（ ）、数据关系和基本操作定义一个完整的抽象数据类型。 A．数据元素 B．数据对象 C．原子类型 D．存储结构

应用题

（14） 设有数据结构（D，R），其中D={1，2，3，4，5，6}，R={(1，2)，(2，3)，

(2，4)，(3，4)，(3，5)，(3，6)，(4，5)，(4，6)}。试画出其逻辑结构图并指出属于何种结构。

（15） 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区

别。

（16） 说明数据的逻辑结构和存储结构之间的关系。

（17） 抽象数据类型的主要特点是什么？数据类型和抽象数据类型的关系如何？使

用抽象数据类型的主要好处是什么？

2

1 算法和算法分析

选择题

（1） 算法指的是（ ）。

A．对特定问题求解步骤的一种描述，是指令的有限序列 B．计算机程序

C．解决问题的计算方法 D．数据处理

（2） 下面（ ）不是算法所必须具备的特性。 A．有穷性 B．确切性 C．高效性 D．可行性

（3） 算法必须具备输入、输出和（ ）等特性。 A．可行性、可移植性和可扩充性 B．可行性、确定性和有穷性 C．确定性、稳定性和有穷性 D．易读性、稳定性和健壮性

（4） 算法应该具有确定性、可行性和有穷性，其中有穷性是指（ ）。 A．算法在有穷的时间内终止 B．输入是有穷的 C．输出是有穷的 D．描述步骤是有穷的

（5） 当输入非法错误时，一个“好”的算法会进行适当处理，而不会产生难以理解

的输出结果，这称为算法的（ ）。 A．可读性 B．健壮性 C．正确性 D．有穷性

（6） 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A．找出数据结构的合理性 B．研究算法中输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易读性和文档性 E．空间性能和时间性能 F．正确性和简明性 G．可读性和文档性 H．数据复杂性和程序复杂性

（7） 算法的时间复杂度与（ ）有关。 A．问题规模 B．计算机硬件性能 C．编译程序的质量 D．程序设计语言

（8） 算法的时间复杂度与（ ）有关。 A．问题规模 B．待处理数据的初态 C．算法的易读性 D．A和B

（9） 某算法的时间复杂度是○(n2)，表明该算法（ ）。 A．问题规模是n2 B．执行时间等于n2 C．执行时间与n2成正比 D．问题规模与n2成正比

（10） 下面说法错误的是（ ）。

3

①算法原地工作的含义是指示不需要如何额外的辅助空间

②在相同的规模n下，复杂度○(n)的算法在时间上总是优于复杂度○(2n)的算法 ③所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 ④同一个算法，实现语言的级别越高，执行效率就越低

（11） 算法

for (i=n-1; i>=1; i--) for (j=1; j<=i; j++) if (a[j]>a[j+1]) a[j]与a[j+1]交换；

其中n为正整数，则最后一行语句的频度（执行次数）在最坏情况下是（ ）。

32

A．○(n) B．○(nlog2n) C．○(n) D．○(n)

（12） 算法的时间复杂度属于一种（ ）。 A．事前统计的方法 B．事先分析估算的方法 C．事后统计的方法 D．事后分析估算的方法

（13） 设某算法完成对n个元素进行处理，所需的时间是T(n)=100 nlog2n+200n+500，

则该算法的时间复杂度是（ ）。 A．○(1) B．○(n) C．○(nlog2n) D．○(nlog2n+n)

（14） 假设时间复杂度为○(n2)的算法在有200个元素的数组上运行需要3.1ms，则

在有400个元素的数组上运行需要（ ）ms。 A．3.1 B．6.2 C．12.4 D．x（无法确定）

（15） 下列程序段加下划线的语句执行（ ）次。 for (m=0,i=1; i<=1; i++) for (j=1; j<=2*i; j++) m=m+1； A．n2 B．3n C．n(n+1) D．n3

应用题

（16） 将下列函数按它们的n→∞时的无穷大阶数，从小到大排列。 n，n-n3-7n5，nlog2n，2n/2，n3，log2n，n1/2+log2n，(3/2)n，n!，n2+log2n

（17） 分析以下程序段，并用大○记号表示其执行时间。 ① i=1;k=0; else i++;

while (i

while (i+j<=n) { if (i>j) j++; k=k+10*i;

4

i++; } while (i<=n) ⑥ for (i=0;i

while ((y+1)*(y+1)<=n) a[i][j]=0; y=y+1

（18） 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为T1=○(2n)，

A2的时间复杂度为T2=○(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。

综合应用题

（19） 设n是偶数，且有程序段： for (i=1;i<=n;i++) if (2*i<=n) for (j=2*I;j<=n;j++) y=y+i*j;

则语句y=y+i*j的执行次数是多少？要求列出计算公式。

（20） 斐波那契数列Fn定义如下：

F0=0，F1=1，?，Fn=Fn-1+Fn-2 n=2，3，? 请就此斐波那契数列，回答下列问题。

① 在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，?，F1，F0精确计算多少次？ ② 用大○表示法给出递归计算时递归函数的时间复杂度是多少？

（21） 运算是数据结构的一个重要方面。举例说明两个数据结构的逻辑结构和存储方

式完全相同，只是对于运算的定义不同，因而具有不同的特性，则这两个数据结构是不同的。

（22） 针对给定的实际问题建立数据结构时，应从哪些方面考虑。

5

6 线性表综合

选择题

（1） 下面关于线性表的叙述中，错误的是（ ）。 A．线性表采用顺序存储，必须占用一片连续的存储单元 B．线性表采用顺序存储，便于进行插入和删除操作 C．线性表采用链接存储，不必占用一片连续的存储单元 D．线性表采用链接存储，便于插入和删除操作

（2） 若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用

（ ）存储方法最节约时间。 A．顺序表 B．单链表 C．双链表 D．循环单链表

（3） 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结

点，则采用（ ）存储方法最节约时间。 A．单链表 B．循环双链表 C．循环单链表 D．带尾指针的循环单链表

（4） 设线性表有n个元素，以下操作中，（ ）在顺序表上实现比在链表上实现

的效率更高。

A．输出第i（1≤i≤n）个元素值 B．交换第1个和第2个元素的值 C．顺序输出所有n个元素

D．查找与给定值x相等的元素在线性表中的序号

（5） 如果对于具有n（n＞1）个元素的线性表的基本操作有4种：删除第一个元素；

删除最后一个元素；在第一个元素前插入新元素；在最后一个元素的后面插入新元素。则最好使用（ ）。 A．只设尾指针的循环单链表 B．只设尾指针的非循环单链表 C．只设头指针的循环双链表

D．同时设置头指针和尾指针的循环单链表

应用题

（6） 请比较线性表的两种基本的存储结构——顺序表和单链表。

（7） 举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，算法的效

率不同。

（8） 如果某线性表中数据元素的类型不一致，但是希望能根据下标随机存取每个元

素，请为这个线性表设计一个合适的存储结构。

（9） 线性链表有哪几种常见的变形？各有何特点？

16

算法设计题

（10） 用顺序表表示集合，设计算法实现集合的求交集运算。

（11） 用顺序表表示集合，设计算法实现集合的求并集运算。

（12） 用顺序表表示集合，设计算法实现集合的求差集运算，要求不另外开辟空间。

（13） 假定以有序表表示集合，设计算法判断两个给定集合是否相等。

（14） 设两个单链表L1和L2分别表示两个集合，设计算法判断L1是否是L2的子

集。

（15） 已知两个不带头结点的单链表A和B分别表示两个集合，并且其元素值递增

有序，求A、B的交集C，并以同样的递增形式存储，要求尽可能节省时间。

（16） 在某商店的仓库中，对电视机按其价格从低到高建立一个单链表，链表的每个

结点指出同样价格的电视机的台数。现有m台价格为n元的电视机入库，请编写算法完成仓库的进货管理。

（17） 从键盘输入n个英语单词，输入格式为n，w1，w2，?，wn，其中n表示随后

输入英语单词个数，试编写算法建立一个单链表，要求： ①如果单词重复出现，则只在链表上只保留一个；

②统计单词重复出现的次数，然后输出次数最多的前k（k＜n）个单词。

（18） 一元稀疏多项式可以采用单链表形式存储，设计算法完成A(x)+B(x)，其中A(x)

和B(x)均为稀疏的一元多项式，要求利用原表的存储空间。

（19） 假设用不带头结点的单链表表示八进制数，例如，八进制数536可以表示成三

个结点的链表。要求写一个函数Add，该函数有两个参数P和Q，分别指向表示八进制数的链表，执行函数调用Add(P,Q)后，将返回表示八进制数P加八进制数Q所得结果数的链表。

（20） 约瑟夫环问题：设有编号为1，2，?，n的n（n＞0）个人围成一个圈，每个

人持有一个密码m（m≠1），从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，?，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。

（21） 编写算法，完成下述要求：

①建立一个链表用于存放输入的二进制数，链表中的每个结点的data域存放一个二进制位。

②在此链表上实现对二进制数加1的运算，并输出运算结果。

（22） 有一个不带头结点的单链表h，通过遍历链表将链表中所有的链接方向逆转，

17

算法如下，请在空格处填写正确的语句。 void Inverse(&h) { if ( ① ) return; p=h->next; pr=NULL; while ( ② ) { h->next=pr;pr=h; h=p; ③ } }

（23） 设两个带头结点的单链表A和B，表中结点的数据为整型，下面算法产生表A

和表B的并集并以表C存储，请填写算法中空白处的语句，完成其功能。

18

7 栈的基本概念

选择题

（1） 经过以下栈运算后，x的值是（ ）。

InitStack(s)，Push(s,a)，Push(s,b)，Pop(s,x)，GetTop(s,x) A．a B．b C．1 D．0

（2） 经过以下栈运算后，StackEmpty(s)的值是（ ）。 InitStack(s)，Push(s,a)，Push(s,b)，Pop(s,x)，Pop(s,y) A．a B．b C．1 D．0

（3） （ ）不是栈的基本运算。 A．删除栈顶元素 B．删除栈底元素 C．判断栈是否为空 D．将栈置为空栈

（4） 设有一个空栈，栈顶指针为1000H（十六进制，下同），每个元素需要1个单

位的存储空间，则执行PUSH，PUSH，POP，PUSH，POP，PUSH，POP，PUSH操作后，栈顶指针值为（ ）。 A．1002H B．1003H C．1004H D．1005H

（5） 一个栈的入栈序列是{1，2，3，4，5}，则栈的不可能的输出序列是（ ）。 A．{5，4，3，2，1} B．{4，5，3，2，1} C．{4，3，5，1，2} D．{1，2，3，4，5}

（6） 若一个栈的输入序列是1，2，3，?，n，输出序列的第一个元素是n，则第i

个输出元素是（ ）。 A．不确定 B．n-i C．n-i-1 D．n-i+1

（7） 若一个栈的输入序列是1，2，3，?，n，其输出序列是p1，p2，?，pn，若

p1=3，则p2的值（ ）。 A．一定是2 B．一定是1 C．不可能是1 D．以上都不对

（8） 若一个栈的输入序列是p1，p2，?，pn，其输出序列是1，2，3，?，n，若

p3=1，则p1的值（ ）。 A．可能是2 B．一定是2 C．不可能是2 D．不可能是3

（9） 当字符序列t3_依次通过栈，输出长度为3且可用作C语言标识符的序列有

（ ）。 A．4个 B．5个 C．3个 D．6个

应用题

（10） 设有一个栈，元素进栈的次序为A，B，C，D，E，能否得到如下出栈序列，

若能，请写出操作序列，若不能，请说明原因。

19

①C，E，A，B，D ②C，B，A，D，E

（11） 在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，栈

顶元素和栈底元素分别是什么？（push(k)表示整数k入栈，pop表示栈顶元素出栈。）

（12） 设元素1、2、3、P、A依次经过一个栈，进栈次序为123PA，在栈的输出序

列中，有哪些序列可作为C++程序设计语言的变量名。

（13） 如果进栈序列为A、B、C、D，则可能的出栈序列是什么？

算法设计题

（14） 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出

栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

① 下面所示的序列中哪些是合法的？ A．IOIIOIOO B．IOOIOIIO C．IIIOIOIO D．IIIOOIOO ② 通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，

否则返回false（假定被判定的操作序列已存入一维数组中）。

20

12 链队列

选择题

（1） 用不带头结点的单链表存储队列时，其队头指针指向队头结点，队尾指针指向

队尾结点，则执行删除操作时，（ ）。 A．仅修改队首指针 B．仅修改队尾指针 C．队首指针和队尾指针都需要修改 D．队首指针和队尾指针可能都需要修改

（2） 在链队列中，设指针f和r分别指向队首和队尾，则插入s所指结点的操作是

（ ）。 A．f->next=s; f=s; B．r->next=s; r=s; C．s->next=r; r=s; D．s->next=f; f=s;

（3） 设循环单链表表示的队列长度为n，若只设头指针，则进队操作的时间性能为

（ ）。 A．○(n) B．○(1) C．○(n2) D．○(nlog2n)

（4） 最不适合用作链队列的链表是（ ）。 A．只带队首指针的非循环双链表 B．只带队首指针的循环双链表 C．只带队尾指针的循环双链表 D．只带队尾指针的循环单链表

算法设计题

（5） 假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但

不设头指针。试设计相应的入队和出队算法。

26

13 栈和队列的应用

选择题

（1） 设计一个判别表达式中左右括号是否配对的算法，采用（ ）数据结构最佳。 A．顺序表 B．栈 C．队列 D．链表

（2） 如果数据是在程序的运行过程中逐步产生的，并且要求先产生的数据后处理，

后产生的数据先处理，则最合适的数据结构是（ ）。 A．顺序表 B．顺序栈 C．顺序队列 D．堆

（3） 在解决计算机主机和打印机之间速度不匹配问题时通常设置一个打印缓冲区，

该缓冲区应该是一个（ ）结构。 A．栈 B．队列 C．数组 D．线性表

（4） 执行（ ）操作时，需要使用队列作为辅助数据结构。 A．深度优先遍历图 B．广度优先遍历图 C．散列查找 D．遍历二叉树

（5） 表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为

（ ），其中^表示乘幂。 A．3,2,4,1,1；#*^(+*- B．3,2,8；#*^- C．3,2,4,2,2；#*^(- D．3,2,8；#*^(-

（6） 利用栈计算表达式的值时，设置操作数栈OPND，设OPND只有存储单元，

计算下列表达式是不发生上溢的是（ ）。 A．a-b*(c-d) B．(a-b)*c-d C．(a-b*c)-d D．(a-b)*（c-d）

（7） 与中缀表达式a*b+c/d-e等价的前缀表达式是（ ）。 A．-+*ab/cde B．*+/-abcde C．+*ab-/cde D．*ab+cd/-e

（8） 解决hanoi塔问题的递归算法，其时间复杂度是（ ）。 A．○(n) B．○(n2) C．○(2n) D．○(n!)

（9） 4个圆盘的汉诺塔，总的移动次数为（ ）。 A．7 B．8 C．15 D．16

（10） 一个递归的求解过程可以用递归函数求解，也可以用非递归函数求解，从运行

时间上看，通常递归函数要比非递归函数（ ）。 A．快一些 B．慢一些 C．相同 D．无法比较

（11） 栈和队列的主要区别在于（ ）。 A．它们的逻辑结构不一样 B．它们的存储结构不一样 C．所包含的运算不一样 D．插入、删除运算的限定不一样

27

（12） 栈和队列的共同点是（ ）。 A．都是先进先出 B．都是先进后出 C．只允许在端点处插入和删除元素 D．没有共同点

（13） 栈和队列具有相同的（ ）。 A．逻辑结构 B．抽象数据类型 C．存储结构 D．运算

（14） 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈

S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。 A．6 B．4 C．3 D．2

算法设计题

（15） 假设一个算术表达式中可以包含三中括号：园括号“（”和“）”，方括号“[”

和“]”以及花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用。编写算法判断表达式中所含括号是否配对出现。

（16） 设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出。

（17） 设计递归算法求解在n元集合A={1，2，?，n}中选取k（k≤n）个元素的所

有组合。例如，从集合{1，2，3，4}中选取2个元素的所有组合为：{1，2}，{1，3}，{1，4}，{2，3}，{2，4}，{3，4}。

（18） 已知Q是一个循环队列，S是一个顺序栈，设计算法实现将队列中所有元素逆

转。

（19） 设栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，?，a2，a1，

要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，?，a2，a2n-1，a2n-3，?，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为○(n)。

（20） 利用两个栈S1和S2模拟一个队列，已知栈的三个运算定义如下：PUSH(ST,x)

元素x入ST；POP(ST,x)ST栈顶元素出栈，赋给变量x；Sempty(ST)判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue插入一个元素入队列；dequeue删除一个元素出队列；queue_empty判断队列是否为空。

（21） 一个双端队列Q是限定在线性表的两端（LEFT端和RIGHT端）都可以进行

插入和删除操作的线性表，队列为空的条件是LEFT=RIGHT。若采用顺序存储结构存储双端队列，要求： ①定义双端队列的存储结构；

②给出在指定端L（表示左端）和R（表示右端）进行插入（QueueInsert）和删除（QueueDelete）操作的算法。

28

14 数组

选择题

（1） 数组通常具有的两种基本操作是（ ）。 A．查找和修改 B．查找和索引 C．索引和修改 D．建立和删除

（2） 将数组称为随机存取结构是因为（ ）。 A．数组元素是随机的 B．对数组任一元素的存取时间是相等的 C．随时可以对数组进行访问 D．数组的存储结构是不定的

（3） 下面说法中，不正确的是（ ）。 A．数组是一种线性结构

B．数组是一种定长的线性结构

C．除了插入和删除操作外，数组的基本操作还有存取、修改、检索和排序等 D．数组的基本操作有存取、修改、检索和排序等，没有插入和删除操作

（4） 二维数组SZ[-3..5，0..10]含有的元素个数是（ ）。 A．88 B．99 C．80 D．90

（5） 数组A[0..5，0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址

为1000的内存单元中，则元素A[5，5]的地址是（ ）。 A．1175 B．1180 C．1205 D．1210

（6） C语言中定义的整数一维数组a[50]和二维数组b[10][5]具有相同的首元素地

址，即&(a[0])=&(b[0][0])，在以列序为主序时，a[18]的地址和（ ）的地址相同。 A．b[1][7] B．b[1][8] C．b[8][1] D．b[7][1]

（7） 二维数组A的每个元素是由6个字符组成的串，行下标的范围从0～8，列下

标的范围是0～9，则存放A至少需要（ ）个字节，A的第8列和第5行共占（ ）个字节，若A按行序优先方式存储，元素A[8][5]的起始地址与当A按列优先存储时的（ ）元素的起始地址一致。 A．90 B．180 C．240 D．540 E．108 F．114 G．54 H．A[8][5] I．A[3][10] J．A[5][8] K．A[4][9]

（8） 三维数组A[8,8,10]采用行序为主的方式从地址A[0，0，0]开始存放，假设每

个元素占用存储空间大小为L，则元素A[3，2，8]的存放位置是（ ）。 A．A[0，0，0]+198*L B．A[0，0，0]+108*L C．A[0，0，0]+268*L D．A[0，0，0]+13*L

算法设计题

（9） 若在矩阵A中存放一个元素ai,j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元

素中最小值且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A，试设计一个求矩阵所有马鞍点的算法，并分析最坏情况下

29

的时间复杂度。

（10） 给定n×m矩阵A[a..b，c..d]满足A[i，j]≤A[i，j+1]（a≤i≤b，c≤j≤d-1）和

A[i，j]≤A[i+1，j]（a≤i≤b-1，c≤j≤d）。设计算法判定x是否在A中，要求时间复杂度为○(m+n)。

30

15 特殊矩阵

选择题

（1） 对特殊矩阵采用压缩存储的目的主要是为了（ ）。 A．表达变得简单 B．对矩阵元素的存取变得简单 C．去除矩阵中的多余元素 D．减少不必要的存储空间

（2） 下面（ ）不属于特殊矩阵。 A．对角矩阵 B．三角矩阵 C．稀疏矩阵 D．对称矩阵

（3） 一个n×n的对称矩阵，如果以行或列为主序放入内存，则需要（ ）个存

储单元。 A．n(n+1)/2 B．n(n-1)/2 C．n2 D．n2/2

（4） 设A[n，n]是对称矩阵，将其下三角（包括对角线）按行序存储到一维数组

T[n(n+1)/2]中，则上三角元素A[i][j]对应T[k]的下标k是（ ）。 A．i(i-1)/2+j B．j(j-1)/2+i C．i(j-i)/2+1 D．j(i-1)/2+1

（5） 设有一个n行n列的对称矩阵A将其下三角部分按行存放在一维数组B中，

A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（ ）处。 A．(i+3)*i/2 B．(i+1)*i/2 C．(2n-i+1)*i/2 D．(2n-i-1)*i/2

（6） 若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中。

则存放到B[k]中的非零元素ai,j（1≤i，j≤n）的下标i，j与k的对应关系是（ ）。 A．(i+1)*i/2+j B．(i+1)*i/2+j-1 C．(j+1)*j/2+i D．(j-1)*j/2+i-1

（7） 若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中。

则存放到B[k]中的非零元素ai,j（1≤i，j≤n）的下标i，j与k的对应关系是（ ）。 A．(j-1)(2n-j+1)/2+i-j B．(j-1)(2n-j+2)/2+i-j+1 C．(j-1)(2n-j+2)/2+i-j D．(j-1)(2n-j+2)/2+i-j+1

（8） 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，

则A中元素A66,65在B数组中的位置k为（ ）。 A．198 B．195 C．197 D．196

应用题

（9） 对于一个n行m列的上三角矩阵A，如果以行优先的方式用一维数组B从0

号位置开始存储，求元素ai,j（1≤i≤n，1≤j≤m）在数组B中的存储位置。

（10） 设有三对角矩阵An×n（行、列下标均从0开始），将其三条对角线上的元素逐

行存于数组B[3n-2]中，使得B[k]=ai,j，求： ①用i，j表示k的下标变换公式； ②用k表示i，j的下标变换公式。

31

（11） 设有五对角矩阵B=(ai,j)20×20，按特殊矩阵压缩存储的方式将其五条对角线上的

元素存于数组A[-10..m]中，计算元素B[15][16]在数组A中的存储位置。

挑战题

（12） 对于给定的数组a[n][2n-1]，将3个顶点分别为a[0][n-1]、a[n-1][0]和a[n-1][2n-2]

的三角形上的所有元素按行序存放在一维数组B[n×n]中，且元素a[0][n-1]存放在B[0]中。例如当n=3时，数组a[3][5]中三角形如图所示。如果位于三角形上的元素a[i][j]存放于B[k]中，请给出元素a[i][j]的下标i，j和k的对应关系。 a00 a10

a01

a20

a11 a21

a02 a12 a22

a03 a13 a04 a14

a23 a24

（13） 设A和B均为n阶下三角矩阵，另有一个n行n+1列的二维数组C，设计一

个方案将两个矩阵A和B压缩存储于同一个数组C中，并给出A的矩阵元素ai,j和B的矩阵元素bi,j在数组C中的存放位置。

32

16 查找的基本概念

选择题

（1） 静态查找与动态查找的根本区别在于（ ）。 A．它们的逻辑结构不一样 B．施加在其上的操作不同 C．所包含的数据元素的类型不一样 D．存储实现不一样

（2） 以下（ ）方法适合动态查找。 A．顺序查找 B．折半查找 C．散列查找 D．随机查找

（3） 能够实现动态查找的数据结构是（ ）。 A．有序表 B．双链表 C．循环链表 D．二叉排序树

（4） 平均查找长度与查找集合中记录个数n无关的查找方法是（ ）。A．折半查找 B．平衡二叉树的查找 C．散列查找 D．不存在

（5） 在以下数据结构中，（ ）查找效率最低。 A．有序顺序表 B．二叉排序树 C．堆 D．散列表

33

17 顺序查找

选择题

（1） 对线性表进行顺序查找，要求线性表的存储结构为（ ）。 A．散列存储 B．顺序存储 C．链接存储 D．顺序存储或链接存储

（2） 用顺序查找方法在长度为n的线性表中进行查找，在等概率情况下，查找成功

的平均查找长度为（ ）。 A．n B．n/2 C．(n-1)/2 D．(n+1)/2

（3） 假定查找成功与不成功的可能性相同，在查找成功的情况下每个记录的查找概

率相同，则顺序查找的平均查找长度为（ ）。 A．0.5(n+1) B．0.25(n+1) C．0.5(n-1) D．0.75n+0.25

34

18 折半查找

选择题

（1） 有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找

与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（ ）；在查找不成功的情况下，s和b的关系是（ ）。 A．s=b B．s>b C．s

（2） 长度为12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，

查找成功的平均长度是（ ），查找失败时的平均查找长度是（ ）。 A．37/12 B．62/13 C．39/12 D．49/13

（3） 已知一个有序表为{12，18，24，35，47，50，62，83，90，115，134}，当折

半查找值为90的元素时，经过（ ）次比较后查找成功。 A．2 B．3 C．4 D．5

（4） 折半查找判定树不属于（ ）。 A．平衡二叉树 B．二叉排序树 C．完全二叉树 D．二叉树

（5） 当n足够大时，在有序顺序表中进行折半查找，假设顺序表中每个元素的查找

概率相同，则查找成功的平均查找长度为（ ）。 A．(n+1)/2 B．n/2 C．log2(n+1)-1 D．log2(n+1)

（6） 对表长为n的有序表进行折半查找，其判定树的高度为（ ）。 A．log2(n+1) B．log2(n+1)-1 C．log2n D．log2(n-1)

（7） 对100个元素进行折半查找，在查找成功的情况下，比较次数最多是（ ）。 A．25 B．50 C．10 D．7

（8） 对具有14个元素的有序表R[]14]进行折半查找，查找R[3]时比较需要比较

（ ）。

A．R[0]R[1]R[2]R[3] B．R[6]R[2]R[4]R[3] C．R[0]R[13]R[2]R[3] D．R[6]R[4]R[2]R[3]

（9） 对有序表A[1..17]进行折半查找，则查找长度为5的元素下标依次是（ ）。 A．8，17 B．5，10，12 C．9，16 D．9，17

应用题

（10） 画出长度为10的折半查找判定树，并求等概率时查找成功和不成功的平均查

找长度。

（11） 对长度为2k-1的有序表进行折半查找，查找成功的情况下最多需要比较多少

次？查找失败的情况下需要比较多少次？

35

23 起泡排序

选择题

（1） 以下（ ）在数据序列基本有序时效率最高。 A．快速排序 B．起泡排序 C．堆排序 D．希尔排序

（2） 将记录序列{8，9，10，4，5，6，20}采用起泡排序排成升序序列，需要进行

（ ）趟（假设采用从前向后的扫描方式）。 A．3 B．4 C．5 D．8

41

24 快速排序

选择题

（1） 下列序列中，（ ）是执行一趟快速排序的结果。 A．[da，ax，eb，de，bb] ff [ha，gc] B．[cd，eb，ax，da] ff [ha，gc，bb] C．[gc，ax，eb，cd，bb] ff [da，ha] D．[ax，bb，cd，da] ff [eb，gc，ha]

（2） 快速排序在（ ）情况下最不利于发挥其长处。 A．待排序的数据量太大 B．待排序的数据中含有多个相同值 C．待排序的数据已基本有序 D．待排序的数据数量为奇数

（3） 对数列{25，84，21，47，15，27，68，35，20}进行排序，元素序列的变化情

况如下：

①25，84，21，47，15，27，68，35，20 ②20，15，21，25，47，27，68，35，84 ③15，20，21，25，35，27，47，68，84 ④15，20，21，25，27，35，47，68，84 则采用的排序方法是（ ）。 A．希尔排序 B．简单选择排序 C．快速排序 D．归并排序

（4） 一组记录的关键码为{46，79，56，38，40，84}，则利用快速排序的方法，以

第一个记录为基准得到的一次划分结果为（ ）。 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}

（5） 就平均时间而言，（ ）最佳。 A．起泡排序 B．直接插入排序 C．快速排序 D．简单选择排序

（6） 快速排序的最大递归深度是（ ），最小递归深度是（ ）。 A．○(1) B．○(log2n) C．○(n) D．○(nlog2n)

（7） 对以下数据序列利用快速排序进行排序，速度最快的是（ ）。 A．{21，25，5，17，9，23，30} B．{25，23，30，17，21，5，9} C．{21，9，17，30，25，23，5} D．{5，9，17，21，23，25，30}

（8） 对8个元素的线性表进行快速排序，最好情况下的比较次数为（ ）次。 A．7 B．8 C．12 D．13

应用题

（9） 对n=7，给出快速排序一个最好情况和最坏情况的初始排列的实例。

（10） 快速排序在什么情况下退化成起泡排序？如何改进？

（11） 对50个整数进行快速排序需进行的关键码之间的比较次数可能达到的最大值

和最小值分别是多少？

42

算法设计题

（12） 写出快速排序的非递归算法。

（13） 一个数组中的元素为正整数或负整数。设计算法将正整数和负整数分开，使线

性表的前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少比较次数。

（14） 设计算法将数组A[n]中所有的偶数移到奇数之前，要求不增加存储空间，且

时间复杂度为O(n)。

（15） 对给定序号j（1≤j≤n），要求在无序记录A[1]～A[n]中找到按关键码从小到

大排在第j位上的记录，试利用快速排序的划分思想设计算法实现上述查找。

（16） 荷兰国旗问题。要求重新排列一个由字符R、W、B（R代表红色，W代表白

色，B代表蓝色，这都是荷兰国旗的颜色）构成的数组，使得所有的R都排在最前面，W排在其次，B排在最后。为荷兰国旗问题设计一个算法，其时间性能是O(n)。

43

25 简单选择排序

选择题

（1） （ ）方法是从未排序序列中挑选元素，并将其放入排列序列的一端。 A．归并排序 B．插入排序 C．快速排序 D．选择排序

（2） 对数据序列{84，47，25，15，21}进行排序，数据序列的变化为：{84，47，

25，15，21}→{15，47，25，84，21}→{15，21，25，84，47}→{15，21，25，47，84}，则采用的排序方法是（ ）。 A．快速排序 B．简单选择排序 C．起泡排序 D．直接插入排序

（3） 简单选择排序的比较次数和移动次数分别为（ ）。 A．O(n)，O(log2n) B．O(log2n)，O(n2) C．O(n2)，O(n) D．O(nlog2n)，O(n)

44

26 二路归并排序

选择题

（1） 将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（ ）。 A．n B．2n-1 C．2n D．n-1

（2） 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选

择的排序方法是（ ）。 A．快速排序 B．堆排序 C．归并排序 D．希尔排序

（3） 二路归并的趟数是（ ）。 A．n B．log2n C．nlog2n D．n2

（4） （ ）在某趟排序结束后不一定能选出一个元素放到其最终位置上。 A．选择排序 B．堆排序 C．归并排序 D．起泡排序

（5） 下列排序算法中，（ ）在最坏情况下的时间复杂度不高于○（nlog2n）。 A．希尔排序 B．快速排序 C．归并排序 D．起泡排序

27 基数排序

选择题

（1） 以下排序方法中，（ ）不需要进行关键码的比较。 A．快速排序 B．归并排序 C．基数排序 D．堆排序

（2） 以下排序方法中，稳定的排序方法是（ ）。 A．快速排序 B．希尔排序 C．基数排序 D．堆排序

（3） 已知关键码序列{78，19，63，30，89，84，55，69，28，83}采用基数排序，

第一趟排序后的关键码序列为（ ）。

A．{19，28，30，55，63，69，78，83，84，89} B．{28，78，19，69，89，63，83，30，84，55} C．{30，63，83，84，55，78，28，19，89，69} D．{30，63，83，84，55，28，78，19，69，89}

（4） 将1000个英文单词进行排序，采用（ ）排序方法时间性能最好。 A．插入排序 B．快速排序 C．基数排序 D．堆排序

（5） 假设线性表中每个记录有两个数据项K1和K2，现对线性表按如下规则进行

排序：先按数据项K1由小到大排序，在K1值相同的情况下，K2值小的在前面，大的在后面，则应该采用的排序方法是（ ）。

A．先按K1值进行直接插入排序，再按K2的值进行简单选择排序 B．先按K2值进行直接插入排序，再按K1的值进行简单选择排序

45

C．先按K1值进行简单选择排序，再按K2的值进行直接插入排序 D．先按K2值进行简单选择排序，再按K1的值进行直接插入排序

46