数据结构的基本概念
选择题
（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 2 线性表的逻辑结构 选择题 （1） 线性表是具有n个（ ）的有限序列。 A．数据 B．字符 C．数据元素 D．数据项 （2） 线性表是（ ）。 A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空 （3） 关于线性表，下列说法中正确的是（ ）。 A．线性表中每个元素都有一个直接前驱和一个直接后继 B．线性表中的数据元素可以具有不同的数据类型 C．线性表中数据元素的类型是确定的 D．线性表中任意一对相邻的数据元素之间存在序偶关系 （4） （ ）是一个线性表。 A．由n个实数组成的集合 B．由所有实数组成的集合 C．由所有整数组成的序列 D．由n个字符组成的序列 6 3 顺序线性表 选择题 （1） 已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元 素的地址为144，则第一个元素的地址是（ ）。 A．108 B．180 C．176 D．112 （2） 在长度为n的线性表中查找值为x的数据元素的时间复杂度为（ ）。 A．○(0) B．○(1) C．○(n) D．○(n2) （3） 在一个长度为n的线性表的第i（1≤i≤n+1）个元素之前插入一个元素，需 向后移动（ ）个元素，删除第i（1≤i≤n）个元素时，需向前移动（ ）个元素。 A．n-i B．n-i+1 C．n-i D．n-i+1 （4） 线性表的顺序存储结构是一种（ ）的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取 （5） 顺序存储结构的优点是（ ）。 A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 （6） n个结点的线性表采用数组实现，算法的时间复杂度是○(1)的操作是（ ）。 A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n） C．删除第i个结点（1≤i≤n） D．以上都不对 （7） 对于顺序存储的线性表，访问某个元素和增加一个元素的时间复杂度为 （ ）。 A．○(n)、○(n) B．○(n)、○(1) C．○(1)、○(n) D．○(1)、○(1) （8） 顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若 申请失败，则说明系统没有（ ）可分配的存储空间。 A．m个 B．m个连续的 C．n+m个 D．n+m个连续的 应用题 （9） 设A是一个线性表（a1，a2，?，an），采用顺序存储结构，则在等概论的前 提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间(1≤i≤n)的概率为（n-i）/（n（n-1）/2），则平均每插入一个元素所移动的元素个数是多少？ （10） 设n表示线性表中的元素个数，E表示存储数据元素所需要的存储单元大小， 7 D表示可以在数组中存储线性表的最大元素个数（D≥n），则使用顺序存储方式存储线性表需要多少存储空间？ （11） 在什么情况下线性表使用顺序存储比较好？ 算法设计题 （12） 试以顺序表作存储结构，实现线性表就地逆置。 （13） 设计算法判断给定字符串是否是回文。所谓回文是正读和反读均相同的字符 串，例如abcba或abba是回文，而abcda不是回文。 （14） 设计一个时间复杂度为○(n)的算法，实现将数组A[n]中所有元素循环左移k 个位置。 （15） 已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有 元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为○(n)。 （16） 假定数组中有多个零元素，设计算法将数组中所有非零元素移到数组的前端。 （17） 顺序存储的线性表A，其数据元素为整型，设计算法将A拆成B和C两个表， 使A中值大于0的元素存入表B，值小于0的元素存入表C，要求B和C不另外设置存储空间而利用A的空间。 （18） 已知顺序表L中的元素递增有序排列，设计算法将元素x插入到表L中并保 持表L仍递增有序。 （19） 设计一个高效算法，在顺序表中删除所有元素值为x的元素，要求空间复杂度 为○(1)。 （20） 设计算法实现从顺序表L中删除所有值在x和y之间的所有元素，要求时间 性能复杂度为○(n)，空间性能为○(1)。 （21） 设计算法删除顺序表中重复的元素，要求算法移动元素的次数较少并使剩余元 素间的相对次序保持不变。 （22） 给定n个记录的有序序列A[n]和m个记录的有序序列B[m]，将它们归并为一 个有序序列，存放在C[n+m]中，试写出这一算法（假设A、B和C均为升序序列）。 8 4 线性链表 选择题 （1） 线性表的链接存储结构是一种（ ）的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取 （2） 线性表采用链接存储时，其（ ）。 A．地址必须是连续的 B．部分地址必须是连续的 C．地址一定是不连续的 D．地址连续与否均可以 （3） 链表不具有的特点是（ ）。 A．可随机访问任一元素 B．插入、删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性表长度成正比 （4） 在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 （ ）。 A．○(1) B．○(n) C．○(n2) D．○(nlog2n1) （5） 对于n个元素组成的线性表，建立一个单链表的时间复杂度是（ ）。 A．○(1) B．○(n) C．○(n2) D．○(nlog2n1) （6） 对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（ ）。 A．○(1) B．○(n) C．○(n2) D．○(nlog2n1) （7） 在单链表中删除指针p所指结点的后续结点，则执行（ ）。 A．p->next=p->next->next B．p->next=p->next C．p=p->next->next D．p=p->next; p->next=p->next->next （8） 在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间 插入s所指结点，则执行（ ）操作。 A．s->next=p->next; p->next=s; B．q->next=s; s->next=p; C．p->next=s->next; s->next=p; D．p->next=s; s->next=q （9） 在一个长度为n（n>1）的带头结点的单链表h上，另设有尾指针r指向尾结 点，执行（ ）操作与链表的长度有关。 A．删除单链表中的第一个元素 B．删除单链表中的最后一个元素 C．在单链表第一个元素前插入一个新元素 D．在单链表的最后一个元素后插入一个新元素 （10） 在单链表中附加头结点的目的是为了（ ）。 A．保证单链表中至少有一个结点 B．标识单链表中首结点的位置 C．方便运算的实现 D．说明单链表是线性表的链式存储 9 （11） 将长度为n个单链表链接在长度为m的单链表之后的算法，其时间复杂度是 （ ）。 A．○(1) B．○(n) C．○(m) D．○(n+m) （12） 循环单链表的主要优点是（ ）。 A．不再需要头指针了 B．从表中任一结点出发都能扫描到整个链表 C．已知某个结点的位置后，能够容易找到它的直接前驱 D．在进行插入、删除操作时，能更好地保证链表不断开 （13） 将线性表（a1，a2，?，an）组织为一个带头结点的循环单链表，设H为链表 的头指针，则链表中最后一个结点的指针域中存放的是（ ）。 A．变量H的地址 B．变量H的值 C．元素a1的地址 D．空指针 （14） 非空的循环单链表L的尾结点p满足（ ）。 A．p=NULL B．p->next=NULL C．p->next=L D．p=L （15） 若要在○(1)的时间内实现两个循环单链表的首尾相接，则两个循环单链表应 各设一个指针，分别指向（ ）。 A．各自的头结点 B．各自的尾结点 C．各自的第一个元素结点 D．一个表的头结点，一个表的尾结点 （16） 设线性表非空，（ ）可以在○(1)的时间内在表尾插入一个新结点。 A．带头结点的单链表，有一个链表指针指向头结点 B．带头结点的循环单链表，有一个链表指针指向头结点 C．不带头结点的单链表，有一个链表指针指向表的第一个结点 D．不带头结点的循环单链表，有一个链表指针指向表中某个结点（除第一个结点外） （17） 设指针rear指向带头结点的循环单链表的尾指针，若要删除链表的第一个元 素结点，正确的操作是（ ）。 A．s=rear; rear=rear->next; B．rear=rear->next; C．rear=rear->next->next; D．s=rear->next->next; rear->next->next=s->next; （18） 设有两个长度为n个单链表，以h1为头指针的链表是非循环的，以h2为尾指 针的链表是循环的，则（ ）。 A．在两个链表上删除第一个结点的操作，其时间复杂度均为○(1) B．在两个链表的表尾插入一个结点的操作，其时间复杂度均为○(n) C．循环链表要比非循环链表占用更多的存储空间 D．循环链表要比非循环链表占用更少的存储空间 （19） 使用双链表存储线性表，其优点是可以（ ）。 10 A．提高查找速度 B．更方便数据的插入和删除 C．节约存储空间 D．很快回收存储空间 （20） 与单链表相比，双链表的优点之一是（ ）。 A．插入和删除操作更简单 B．可以进行随机访问 C．可以省略表头指针或表尾指针 D．访问其后相邻结点更灵活 （21） 带头结点的循环双链表L为空表的条件是（ ）。 A．L->next->prior=NULL B．L->prior=L C．L->next=L D．B和C都对 （22） 在循环双链表的p所指结点后插入s所指结点的操作是（ ）。 A．p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B．p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; C．s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; D．s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; （23） 在双链表中指针pa所指结点后面插入pb所指结点，执行的语句序列是（ ）。 ①pb->next=pa->next; ②pb->prior=pa; ③pa->next=pb; ④pa->next->prior=pb; A．①②③④ B．④③②① C．③④①② D．①④③② （24） 在一个双链表中，删除结点p的操作是（ ）。 A．p->prior->next=p->next; p->next->prior=p->prior; B．p->prior=p->prior->prior; p->prior->prior=p; C．p->next->prior=p; p->next=p->next->next; D．p->next=p->prior->prior; p->prior=p->prior->prior; 应用题 （25） 单链表设置头结点的作用是什么？ （26） 线性表的顺序存储结构具有三个弱点：其一，插入或删除操作需要移动大量元 素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。试问，线性表的链接存储结构是否能够克服上述三个弱点？ （27） 若频繁地对一个线性表进行插入和删除操作，该线性表采用什么存储结构比较 好？ （28） 设n表示线性表中的元素个数，P表示指针所需的存储单元大小，E表示存储 数据元素所需的存储单元大小，则使用单链表存储方式存储该线性表需要多少存储空间（不考虑头结点）？ 算法设计题 11 （29） 设计算法依次打印单链表中每个结点的数据信息。 （30） 求单链表的长度。 （31） 设计算法将值为x的结点插入到不带头结点的单链表L中值为k的结点之前， 若找不到值为k的结点，则将x插入到链表的末尾。 （32） 判断非空单链表是否递增有序。 （33） 已知非空线性链表由list指出，结点结构为（data，link）。请编写算法，将链 表中数据域最小的结点移到链表的最前面。要求：不得额外申请新的结点。 （34） 给定一个带头结点的单链表，设head为头指针，设计算法按递增次序输出单 链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作辅助空间）。 （35） 已知非空线性链表由list指出，设计算法交换p所指结点与其后续结点在链表中的位置（设p所指结点不是链表的最后一个结点）。 （36） 设计算法实现将单链表就地逆置。 （37） 头插法建立单链表。 （38） 尾插法建立单链表 （39） 复制一个单链表。 （40） 设计算法实现将单链表就地逆置。 （41） 在一个有序单链表（假设从小到大排列）中插入一个元素值为x的结点，使得插入后单链表仍然有序。 （42） 设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结 点。 （43） 已知单链表中各结点的元素值为整型且递增有序，设计算法删除表中大于 mink且小于maxk的所有元素，并释放被删结点的存储空间。 （44） 有两个整数序列A=(a1，a2，?，am)和B=(b1，b2，?，bn)已经存入两个单链 表中，设计算法判断序列B是否是序列A的子序列。 （45） 设线性表C=(a1，b1，a2，b2，?，an，bn)采用带头结点的单链表存储，设计算 法将表C拆分为两个线性表A和B，使得A=(a1，a2，?，an)，B=(b1，b2，?，bn)。 12 （46） 有两个递增有序的单链表la和lb，设计算法将这两个单链表合并为一个有序 链表。 （47） 有两个有序的单链表，一个表为升序，另一个表为降序，设计算法将这两个链 表合并为一个有序链表。 （48） 已知单链表A和B的数据（设为整型）递增有序，设计算法利用原有结点， 将表A中与表B具有相同值的结点删除，将表B中与原表A不同值的结点存入表A中，并保持表A的递增有序。 （49） 设计算法将循环单链表就地逆置。 （50） 已知L为单链表的头结点地址，表中共有m（m＞3）个结点，从表中第i个（1 ＜i＜m）结点起到第m个结点构成一个部分循环链表。设计算法将这部分循环链表中所有结点顺序完全倒置。 （51） 假设在长度大于1的循环单链表中，即无头结点也无头指针，s为指向链表中 某个结点的指针，试编写算法删除结点s的前驱结点。 （52） 设循环单链表L1，对其遍历的结果是：x1，x2，x3，?，xn-1，xn。请将该循 环链表拆成两个循环单链表L1和L2，使得L1中含有原L1表中序号为奇数的结点且遍历结果为：x1，x3，?；L2中含有原L1表中序号为偶数的结且遍历结果为：?，x4，x2。 （53） 已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。试编写算 法，构造三个循环单链表，使每个循环链表中只含同一类字符。 （54） 有两个循环链表tail1和tail2（tail1和tail2分别指向循环链表的尾指针），编 写算法将循环链表tail2链接到循环链表tail1之后，并使链接后的链表仍是循环链表。 （55） 已知p指向循环单链表最后一个结点的指针，试编写只包含一个循环的算法， 将线性表（a1，a2，?，an-1，an，）改造成（a1，a2，?，an-1，an，an-1，?，a2，a1）。 （56） 判断带头结点的循环双链表是否对称。 （57） 设计算法实现双链表中第i个结点的前面插入一个值为x的结点。 （58） 已知非空循环双链表head的存储结构为： Struct DNode { TElem info; Struct DNode *left; Struct DNode *right; 13 }; 设计算法实现从链表中删除指针p所指结点的前驱结点（假设该结点存在）。 （59） 已知非空双链表由d指出，结点结构为（priordatanext），请设计算法将链表中 数据值最大（假定唯一）的那个结点移至链表的最前面。要求不得额外申请新的双链表结点。 （60） 设计算法实现将双链表中结点p与其后继结点互换位置。 （61） 设有一个双链表，每个结点中除了有prior、data和next三个域外，还有一个 访问频度域freq，在链表被起用之前，其值均初始化为零，每当在双链表上进行一次LOCATE运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。编写算法实现符合上述要求的LOCATE算法。 14 5 静态链表 选择题 （1） 静态链表中指针表示的是（ ）。 A．下一结点在内存中的地址 B．下一元素在数组中的下标 C．左、右孩子的存储位置 D．左、右孩子的地址 （2） 以下说法错误的是（ ）。 ①静态链表既有顺序存储的优点又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关 ②静态链表中能容纳的元素个数在定义表时必须是确定的 ③静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动 A．①，② B．① C．①，②，③ D．② （3） 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中某结点， 使j沿链移动的操作为（ ）。 A．j=r[j].next B．j=j+1 C．j=j->next D．j=r[j]->next （4） 线性表的静态链表存储与顺序存储相比，优点是（ ）。 A．所有基本操作的算法实现简单 B．便于随机存取 C．便于插入和删除 D．便于利用零散的存储空间 （5） 下图所示数组中以静态链表形式存储了一个线性表，设头指针为a[0].link，则 该线性表的元素依次为（ ）。 下标 0 1 2 3 4 5 6 7 8 data link 4 60 63 40 45 3 7 6 2 74 25 0 1 A．60，63，40，45，74，25 C．74，25，45，60，40，63 B．45，63，25，60，40，74 D．25，45，60，40，63，74 15 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 8 顺序栈 选择题 （1） 在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为 栈底，以top作为栈顶指针，当出栈时，top的变化为（ ）。 A．不变 B．top=0 C．top-1 D．top=top+1 （2） 设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满 时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（ ）。 A．S1的栈底位置为0，S2的栈底位置为n-1 B．S1的栈底位置为0，S2的栈底位置为n/2 C．S1的栈底位置为0，S2的栈底位置为n D．S1的栈底位置为0，S2的栈底位置为1 （3） 为了增加内存空间的利用率和减少溢出的可能性，两个栈共享一片连续的内存 空间时，应将两栈的栈底分别设在这片内存空间的两端，这样，当（ ）时才产生上溢。 A．两个栈的栈顶同时到达栈空间的中心点 B．其中一个栈的栈顶到达栈空间的中心点 C．两个栈的栈顶在栈空间的某一位置相遇 D．两个栈均不空，且一个栈的栈顶到达另一个栈的栈底 （4） 两个栈共享一个数组空间的好处是（ ）。 A．减少存取时间，降低发生上溢的可能性 B．节省存储空间，降低发生上溢的可能性 C．减少存取时间，降低发生下溢的可能性 D．节省存储空间，降低发生下溢的可能性 算法设计题 （5） 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出 栈的操作序列可表示为仅有I和O组成的序列，称可以操作的序列为合法序列，否则称为非合法序列。 ①下面所示的序列中哪些是合法的？ ②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。 （6） 下面的算法将一个整数e压入到堆栈S，请在空格处填上适当的语句实现该操 作。 Typedef struct { int *base; int top; int stacksize; }SqStack; 21 int Push(SqStack S,int e) { if ( ① ) { S.base=(int *)realloc(S.base,(S.stacksize+1)*sizeof(int)); if ( ② ) { printf (“Not Enough Memory!\\n”); retuan 0; } S.top= ③ ; S.stacksize= ④ ; } ⑤ ; retuan 1; } 22 9 链栈 选择题 （1） 向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行 （ ）。 A．h->next=s; B．s->next=h; C．s->next=h; h->next=s; D．s->next=h->next; h->next=s; （2） 从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行 （ ）。 A．x=top; top=top->next; B．x=top->data; C．top=top->next; x=top->data; D．x=top->data; top=top->next; 23 10 队列的基本概念 选择题 （1） 队列的“先进先出”特性是指（ ）。 A．最后插入队列中的元素总是最后被删除 B．当同时进行插入、删除操作时，总是插入操作优先 C．每当有删除操作时，总要先做一次插入操作 D．每次从队列中删除的总是最早插入的元素 （2） 允许对队列进行的操作有（ ）。 A．对队列中的元素排序 B．取出最近入队的元素 C．在队头元素之前插入元素 D．删除队头元素 （3） 一个队列的入队顺序是1、2、3、4，则队列的输出顺序是（ ）。A．4321 B．1234 C．1432 D．3241 24 11 顺序队列 选择题 （1） 循环队列存储在数组A[0?m]中，则入队时的操作为（ ）。 A．rear=rear+1 B．rear=(rear+1) mod (m-1) C．rear=(rear+1) mod m D．rear=(rear+1) mod (m+1) （2） 若用一个长度为6的数组来实现循环队列，且当前rear和front的值分别为0 和3，则从队列中删除一个元素，再增加两个元素后，rear和front的值分别为（ ）。 A．1和5 B．2和4 C．4和2 D．5和1 （3） 已知循环队列的存储空间为数组A[21]，front指向队头元素的前一个位置，rear 指向队尾元素，假设当前front和rear的值分别是8和3，则该队列的长度为（ ）。 A．5 B．6 C．16 D．17 （4） 如图所示为一个元素类型为字符型的环形队列，如果front指向队头元素的前 一个位置，rear指向队尾元素，则所表示的队列为（ ）。 0 1 2 3 4 5 6 7 f l ↑rear 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 I s b e a u T i f u l ↑front T h e o w e R A．The f B．beautiful The f C．flower is D．eautiful The f 应用题 （5） 举例说明顺序队列的“假溢出”现象。 （6） 简述顺序队列假溢出的避免方法及队列满或空的判定条件。 （7） 在操作序列EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、 DeQueue、EnQueue(9)之后，队头元素和队尾元素分别是什么？（EnQueue(k)表示整数k入队，DeQueue表示队头元素出队。） 算法设计题 （8） 在循环队列中设置一个标志flag，当front=rear且flag=0时为队空，当front=rear且flag=1时为队满。编写相应的入队和出队算法。 （9） 如果设置一个计数器count累计队列的长度，则当count=0时队列为空，当 count=QueueSize时队列为满。试设计相应的入队和出队算法。 （10） 25 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 19 散列查找 选择题 （1） 散列技术中的冲突指的是（ ）。 A．两个元素具有相同的序号 B．两个元素的键值不同，而其他属性相同 C．数据元素过多 D．不同键值的元素对应于相同的存储地址 （2） 设散列表表长为m=14，散列函数H(k)=k mod 11。表中已有15、38、61、84 四个元素，如果用线性探测法处理冲突，则元素49的存储地址是（ ）。 A．8 B．3 C．5 D．9 （3） 为一组关键码{87，73，25，55，90，28，31，17，101，22，3，62}构造散列 表，设散列函数为H(key)=key mod 11，在用链地址法处理后位于同一链表中的是（ ）。 A．81，90 B．31，101 C．3，78 D．62，73 （4） 在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位 置，在查找成功的情况下，所探测的这些位置的键值（ ）。 A．一定都是同义词 B．一定都不是同义词 C．不一定都是同义词 D．都相同 （5） 在散列函数H(key)=key mod m中，一般来讲，m应取（ ）。 A．奇数 B．偶数 C．素数 D．充分大的数 （6） 下面关于散列查找的说法正确的是（ ）。 A．散列函数越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有散列函数中最好的 C．不存在特别好和特别坏的散列函数，要视情况而定 D．若在散列表中删去一个元素，只要简单地将该元素删去即可 （7） 关于散列查找说法不正确的有几个（ ）。 ①采用链地址法解决冲突，查找一个元素的时间是相同的 ②采用链地址法解决冲突，若插入总是在链首，则插入任一个元素的时间是相同的 ③采用链地址法解决冲突易引起聚集现象 ④再散列法易引起聚集现象 A．1 B．2 C．3 D．4 （8） 关于散列查找，下面说法正确的是（ ）。 A．再散列法处理冲突不会产生聚集 B．散列表的装填因子越大说明空间利用率越高，因此应使装填因子尽可能大 C．散列函数选择得好可以减少冲突现象 D．对任何关键码集合都无法找到不产生冲突的散列函数 36 （9） 散列函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。 A．最大概率 B．最小概率 C．平均概率 D．同等概率 （10） 散列函数方法一般适用于（ ）情况下的查找。 A．查找表为链表 B．查找表为有序表 C．关键码集合比地址集合大得多 D．关键码集合与地址集合存在对应关系 （11） 设哈希表长m=15，哈希函数H(key)=key mod 13，关键码集合为{53，17，12， 61，89，70，87，25，64，46}，采用二次探测再散列方法处理冲突，则查找成功的平均比较长度为（ ）。 A．1.4 B．1.6 C．1.8 D．2.0 （12） 假设有10个关键码，它们具有相同的散列函数值，用线性探测法把这10个关 键码存入散列表中至少需要做（ ）次探测。 A．110 B．100 C．55 D．45 （13） 采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是（ ）。 A．数据元素过多 B．装填因子过大 C．散列函数选择不当 D．解决冲突的算法不好 （14） 对具有n个关键码的散列表进行查找，平均查找长度是（ ）。 A．○(log2n) B．○(n) C．○(nlog2n) D．与n无关 应用题 （15） 已知关键码序列为（Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct， Nov，Dec），散列表的地址空间为0~16，设散列函数为H(x)=[i/2]，其中i为关键码中第一个字母在字母表中的序号，采用线性探测法和链地址法处理冲突，试分别构造散列表，并求等概率情况下查找成功的平均查找长度。 （16） 设散列表为T[0..12]，散列函数为H(key)=key mod 13，采用再散列法处理冲突， 再散列函数为Hi(key)=(Hi-1+REV(key+1) mod 11+1) mod 13，其中REV(key)表示颠倒10进制数key的各位，如REV(73)=37，REV(7)=7等。将关键码集合{2，8，31，20，19，18，53，27}插入到散列表中，画出最后的散列表，并计算查找成功的平均查找长度。 （17） 给定关键码序列{26，25，20，34，28，24，45，64，42}，设定装填因子为 0.6，请给出除留余数法的散列函数，画出采用线性探测法处理冲突构造的散列表。 37 20 排序的基本概念 选择题 （1） 排序算法的稳定性是指（ ）。 A．经过排序之后，能使值相同的数据保持原顺序中的相对位置不变 B．经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变 C．排序算法的性能与被排序元素的数量关系不大 D．排序算法的性能与被排序元素的数量关系密切 （2） 对任意的7个关键码进行排序，至少要进行（ ）次关键码之间的比较。 A．13 B．14 C．15 D．16 （3） 一个待排序的n个记录可分为n/k组，每组包含k个记录，且任一组内的各记 录分别大于前一组内的所有记录且小于后一组内的所有记录，若采用基于比较的排序方法，其时间下界为（ ）。 A．○(klog2k) B．○(klog2n) C．○(nlog2k) D．○(nlog2n) （4） 关于排序，下列说法中正确的是（ ）。 A．稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率较高 B．对同一个线性表使用不同的排序方法进行排序，得到的排序结果可能不同 C．排序方法都是在顺序表上实现的，在链表上无法实现排序方法 D．在顺序表上实现的排序方法在链表上也可以实现 （5） 下列不属于内部排序方法的是（ ）。 A．归并排序 B．拓扑排序 C．堆排序 D．插入排序 38 21 插入排序 选择题 （1） 用直接插入排序对下面四个序列进行由小到大排序，元素比较次数最小的是 （ ）。 A．94，32，40，90，80，46，21，69 B．21，32，46，40，80，69，90，94 C．32，40，21，46，69，94，90，80 D．90，69，80，46，21，32，94，40 （2） 当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（ ）。 A．起泡排序 B．直接插入排序 C．快速排序 D．简单选择排序 （3） 数据序列{8，9，10，4，5，6，20，1，2}只能是（ ）的两趟排序后的结 果。 A．选择排序 B．冒泡排序 C．插入排序 D．堆排序 （4） 对数据序列{15，9，7，8，20，-1，4}进行排序，一趟后数据序列变为{9，15， 7，8，20，-1，4}，则采用的是（ ）。 A．选择排序 B．冒泡排序 C．插入排序 D．堆排序 （5） 下列排序算法中，（ ）可能会出现下面情况：在最后一趟开始之前，所有 元素都不在最终位置上。 A．起泡排序 B．插入排序 C．快速排序 D．堆排序 （6） 对有n个记录的线性表进行直接插入排序，在最好情况下需比较（ ）次。 A．n-1 B．n+1 C．n/2 D．n(n-1)/2 39 22 希尔排序 选择题 （1） 以下排序算法中，（ ）不能保证每趟至少能将一个元素放到其最终位置上。 A．快速排序 B．希尔排序 C．起泡排序 D．堆排序 （2） 对数据序列{98，36，-9，0，47，23，1，8，10，7}采用希尔排序，下列（ ） 是增量为4的排序结果。 A．{10，7，-9，0，47，23，1，8，98，36} B．{-9，0，36，98，1，8，23，47，7，10} C．{36，98，-9，0，23，47，1，8，7，10} D．以上都不对 40 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