习题1
1. 填空题
（1）（___________）是指数据之间的相互关系，即数据的组织形式。通常人们认为它包含三个方面的内容，分别为数据的（___________）、（___________）及其运算。
答案：数据结构 逻辑结构 存储结构 （2）（___________）是数据的基本单位，在计算机程序中通常作为一个整体进行处理。 答案：数据元素 （3）数据元素之间的不同逻辑关系代表不同的逻辑结构，常见的逻辑结构有（___________）、（___________）、（___________）和（___________）。
答案：集合 线形结构 树结构 图结构
（4）数据的存储结构考虑的是如何在计算机中存储各个数据元素，并且同时兼顾数据元素间的逻辑关系。基本的存储结构通常有两大类：（___________）和（___________）。 答案：顺序存储结构 链式存储结构
（5）通常一个问题可以有多种不同的算法，但每个算法必须满足5个准则：输入、输出、（___________）、（___________）和（___________）。 答案：有穷性 确定性 可行性
（6）通常通过衡量算法的（___________）复杂度和（___________）复杂度来判定一个算法的好坏。
答案：时间 空间
（7）常见时间复杂性的量级有：常数阶O（___________）、对数阶O（___________）、线性阶O（___________）、线性对数阶O（___________）、平方阶O（___________）、和指数阶O（___________）。通常认为，当问题规模较大时，具有（___________）量级的算法是不可计算的。
答案：1 logn n nlogn n2 2n 指数
（8）STL提供的标准容器有顺序容器、（___________）和（___________）。 答案：排序容器 哈希容器
（9）算法可认为是STL的精髓，所有算法都是采用（___________）的形式提供的。 答案：函数模版
（10）通常认为STL由空间管理器、迭代器、泛函、适配器、（___________）和（___________）等六部分构成，其中前面四部分服务于后面两部分。 答案：容器 算法
2. 选择题
（1）以下结构中，（ ）属于线性结构。 A. 树 B. 图 C. 串 D. 集合 （2）算法描述的方法有很多种，常常将（ ）称为算法语言。 A. 自然语言 B. 流程图 C. 伪代码 D. 程序设计语言 （3）现实生活中的家族谱，可认为是一种（ ）结构。
A. 树 B. 图 C. 集合 D. 线性表 （4）手机中存储的电话号码簿，可认为是一种（ ）结构。 A. 树 B. 图 C. 集合 D. 线性表 （5）NP问题是（ ）。
A. 非多项式时间问题，即非P问题 B. 非确定性多项式时间问题
C. P问题的子集 D. 与P问题不相交的 （6）以下（ ）不属于STL的顺序容器。 A. 向量（vector） B. 列表（list） C. 队列（queue） D.双端队列（deque） （7）下面带有@标记的语句的频度(n>10)是（ ）。
for(int i=0;i for(int j=i+1;j @cout< A. n*(n-1)/2 B. n*n/2 n?2n?1n?2分析：??1??n?1?i?(n?1)n?0j?i?1i?02 i3. 分析以下程序段的时间复杂度。 （1）for (i=l; i<=n; i++) { k++; for (j=1; j<=n; j++) m += k; } （3）i=1; while (i<=n) i *= 2; （5）k=100,i=10; do { if (i i++; }while (i while (y*y*y <= n) y++; （8）int i=0; while(i C. n*(n+1)/2 D. 不确定 （2）for (i=l; i<=n; i++) k++; for (j=1; j<=n; j++) m += k; （4）i=1; while (i<=n) i += 2; （6）for (i=0; i<100; i++) for (j=0; j sum += j; 答案： (1) (2) (3) (4) O(n) O(n) O(logn) O(n) 2 (5) O(1) (6) O(1) (7) O(n1/3) (8) O(n) 4. 将整数设计为一个类，将整数相关的常见数学运算设计为类的接口并进行实现，如求与 给定值的最大公约数、最小公倍数、枚举所有因子等。 解： #include \#include %using std::vector; //定义自然数类 class NaturalNumber{ public: }; //返回欧几里德算法求解最大公约数 unsigned long int NaturalNumber :: EUCLID(NaturalNumber & nn) { } //返回最大公约数 unsigned long int NaturalNumber :: GreatestCommonDivisor(NaturalNumber & nn) unsigned long int m = (num > nn.num) ? num : nn.num; //较大的自然数赋值给m unsigned long int n = (num < nn.num) ? num : nn.num; //较小的自然数赋值给n unsigned long int r = m % n; while (r != 0){ } return n; m = n; n = r; r = m % n; //……其它外部接口 unsigned long int EUCLID(NaturalNumber & n); //欧几里德算法求解最大公约数 unsigned long int num; //存储真正的自然数 NaturalNumber(unsigned long int n=0):num(n){} unsigned long int GreatestCommonDivisor(NaturalNumber & nn);//求解最大公约数 unsigned long int LeaseCommonMultiple(NaturalNumber & nn);//求解最小公约数 int GetFactors(vector //求所有因子，存储在factors 中，函数返回因子个数 private: { } //返回最小公倍数 unsigned long int NaturalNumber :: LeaseCommonMultiple(NaturalNumber & nn) { } int NaturalNumber :: GetFactors( vector void main() { } NaturalNumber p(1); int xx = p.GreatestCommonDivisor(NaturalNumber(120)); int yy = p.LeaseCommonMultiple(NaturalNumber(120)); vector int m = sqrt((double)num); vector if ( m*m == num ) { t++; factors.push_back(m);} vector it--; factors.push_back(*it); if ( 0 == num%i ) {t+=2; factors.push_back(i);bigfactors.push_back(num/i);} unsigned long int temp = EUCLID(nn); return num * nn.GetNumber() / temp; return EUCLID(nn); }while (it!=bigfactors.begin()); return t; 习题2 1. 填空题 （1）在一个单链表中，已知每个结点包含data和next两个域，q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（___________）和（___________）操作。 答案：q->next = s; s->next = p; 或 s->next=q->next; q->next = s; （2）表长为n的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（___________），删除一个元素需要移动元素的平均个数为（___________）。 答案：n/2 (n-1)/2 （3）表长为0的线性表称为（___________）。 答案：空表 （4）动态内存管理是操作系统的基本功能之一，其作用是响应用户程序对内存的（___________）和（___________）请求。 答案：申请 释放 （5）顺序表多采用（___________）实现的，是一种随机存取结构，对表中任意结点存取操作的时间复杂度为（___________）。而查找链表中的结节，需要从头指针起顺着链扫描才能得到，平均时间复杂度为（___________）。因此，若线性表的操作主要是进行查找，很少进行插入或删除操作时，采用（___________）表比较合适。 答案：数组 O(1) O(n) 顺序 （6）在链表某个位置上进行插入和删除操作，只需要修改（___________）即可，而无须移动大量元素，操作的时间复杂度为（___________）。而在顺序表中进行插入和删除操作，往往要移动大量元素，平均移动元素的数目为（___________），平均时间复杂度为（___________）。因此，若对线性表进行频繁的插入和删除操作时，采用（___________）表相对合适。若插入和删除主要发生在表头和表尾，则采用（___________）表更为合适。 答案：指针 O(1) 表长的一半 O(n) 链 循环链 （7）静态链表一般采用（___________）存储的链表结构。 答案：数组 （8）对于32位计算机环境，若单链表中的数据类型为整性，则其存储密度为（___________），而若为双链表，则存储密度为（___________）。若采用顺序表存储数据，则其存储密度为（___________）。 答案：50% 33% 1 （9）向量是最常用的容器，STL中向量使用（___________）实现，因此向量具有（___________）表的所有特点，可以快速随机存取任意元素。 答案：数组 顺序 （10）操作系统在运行之初，有一块很大的连续内存块供用户程序申请，通常称之为内存池或（___________）。 答案：堆 （11）循环链表与单链表的区别仅仅在于其尾结点的链域值不是（___________），而是一个指向（___________）的指针。 答案：NULL(或空指针) 头结点 2. 选择题 （1）线性表的顺序存储结构是一种（ ）的存储结构，线性表的链式存储结构是一种（ ）的存储结构。 A. 随机存取 索引存取 C. 随机存取 顺序存取 B. 顺序存取 随机存取 D. 索引存取 散列存取 （2）在双向链表p所指结点之前插入s所指结点的操作是（ ）。 A. p->left=s; s->right=p; p->left->right =s; s->left=p->left; B. p->right=s; p->right->left=s; s->left=p; s->right=p->right; C. s->right=p; s->left=p->left; p->left=s; p->left->right =s; D. s->right=p; s->left=p->left; p->left->right =s; p->left=s; （3）若链表是利用C++指针来存储结点的地址，结点空间的分配和收回都是由操作符new和delete动态执行的，则称该链表为（ ）链表 A. 单向 B. 双向 C. 静态 D. 动态 （4）将线性表存储到计算机中可以采用多种不同的方法，按顺序存储方法存储的线性表称为（ ），按链式存储方法存储的线性表称为（ ）。 A. 数组 单链表 C. 向量 静态链表 实现。 A. vector 数组 B. 顺序表 链表 D. 静态链表 动态链表 （5）（ ）是STL中线性表的链式存储形式，STL标准库中一般采用（ ） B. list 单链表 C. list 双向循环链表 D. vector 单链表 （6）顺序表的类型定义可经编译转换为机器级。假定每个结点变量占用k(k>=1)个字节，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点ai的存储地址为（ ）。 A. b+ki B. b+k(i-1) C. b+k(i+1) D. b-1+ki （7）在循环链表中，若不使用头指针而改设为尾指针（rear），则头结点和尾结点的存储位置分别是（ ）。 A. real和rear->next->next C. rear->next->next和rear B. rear->next 和rear D. rear和rear->next （8）有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是（ ）。 A. 将“指针型变量”简称为“指针” B. 将“头指针变量”简称为“头指针” C. 将“修改某指针型变量的值” 简称为“修改某指针” D. 将“p中指针所指结点” 简称为“P值” （9）以下说法错误的是（ ）。 A. 对循环链表来说，从表中任一结点出发都能通过向前或向后操作而扫描整个循环链表。 B. 对单链表来说，只有从头结点开始才能扫描表中全部结点。 C. 双链表的特点是找结点的前趋和后继都很容易。 D. 对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。 （10）以下说法正确的是（ ）。 A. 顺序存储方式的优点是存储密度大、且插入、删除运算效率高。 B. 链表的每个结点中都至少包含一个指针。 C. 线性表的顺序存储结构优于链式存储结构。 D. 顺序存储结构属于静态结构，链式结构属于动态结构。 说明:静态链表是链式结构,但属于静态存储结构.链表的每个结点中都至少包含一个指针。原题中,“恰好”改为了”至少”。 （11）单链表中，增加头结点的目的是为了 ( ) A. 使单链表至少有一个结点 C. 方便运算的实现 B. 标示表结点中首结点的位置 D. 说明单链表是线性表的链式存储实现 3. 程序选择题 （1）已知L指向带表头结点的非空单链表的头结点，且P结点既不是首结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列： a.删除P结点的直接后继结点的语句序列是（___________） b.删除P结点的直接前驱结点的语句序列是（___________） c.删除P结点的语句序列是（___________） d.删除首结点的语句序列是（___________） e.删除尾结点的语句序列是（___________） (1) delete Q; (2) Q = P (3) L = L->next (4) P = L (5) Q = P->next (6) P->next = P 答案: a. 5 8 1 b. 2 4 14 5 8 1 c. 2 4 10 8 1 d. 4 5 8 1 e. 4 13 5 8 1 （2）已知p结点是某双向链表的中间结点，试从下面语句((1)～(18))中选择合适的语句序列，完成a～e要求的操作。 a. 在p结点后插入s结点的语句序列是________________________________。 b. 在p结点前插入s结点的语句序列是________________________________。 c. 删除p结点的直接后继结点的语句序列是_____________________________。 d. 删除p结点的直接前驱结点的语句序列是_____________________________。 e. 删除p结点的语句序列是____________________________。 (8) P->next = P->next->next (9) P = P->next (10) while(P->next != Q) P = P->next; (11) while(P != NULL) P = P->next; (12) while(Q->next != NULL) { P = Q ; Q = Q->next;} (13) while(P->next->next != NULL) P = P->next; (7) P = P->next->next (14) while(P->next->next != Q) P = P->next; (1) p->next = p->next->next; (2) p->prior = p->prior->prior; (3) p->next = s; (4) p->prior = s; (5) s->next = p; (6) s->prior = p; (7) s->next = p->next; (8) s->prior = p->prior; (9) p->prior->next = p->next; 答案: a. 7 6 12 3 b. 5 8 13 4 c. 15 1 11 18 d. 16 2 10 18 e. 14 9 17 4．分析以下各程序段的执行结果。 （1）程序段一 vector ivec.insert (ivec.begin (),10); vector ivec.insert(ivec.end(),20); (10) p->prior->next = p; (11) p->next->prior = p; (12) p->next->prior = s; (13) p->prior->next = s; (14)p->next->prior = p->prior; (15) q=p->next; (16) q=p->prior; (17) delete p; (18) delete q; for ( it = ivec.begin (); it != ivec.end(); it++ ) cout << *it <<\; cout << endl; 答案: 10 100 20 分析:开始时容器中有100 100，然后为100 100 3，10 100 100 3，10 100 3，10 100，10 100 20 （2）程序段二 int a[]={1,2,3,4,5}; vector cout << \ << ivec.size() << endl; ivec.resize(100); cout << \ << ivec.size() << endl; for (int j=0; j<95; j++) ivec.insert(ivec.end(),j); cout << \ << ivec.size() << endl; ivec.resize(100); ivec.reserve (20); cout << \ << ivec.size() << endl; 答案：1.size:5 2.size:100 3.size:195 4.size:100 （3）程序段三 int a[]={1,2,3,4,5}; list ilist.pop_back (); //1 2 3 4 ilist.insert (ilist.end(),7); ilist.pop_front (); //2 3 4 7 ilist.front ()=20; //20 3 4 7 ilist.sort(); //3 4 7 20 for ( list cout << *it <<\; cout << endl; //1 2 3 4 7 答案：3 4 7 20 5．算法设计 （1）分别编程实现顺序表类和链表类，并设计完整的测试程序对每个接口进行测试。 （2）设A=（a1,a2,a3,......an）和B=(b1,b2,.. .,bm)是两个线性表（假定所含数据元素均为整数）。若n=m且ai=bi(i=1,.. .,n),则称A=B;若ai=bi(i=1,.. .,j)且aj+1 （3）假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。 （4）试分别以顺序表和单链表作为存储结构，各写一个实现线性表的就地（即使用尽可能少的附加空间）逆置的算法，在原表的存储空间内将线性表（a1，a2,，??，an-1，an)逆置为（an，an-1，??，a2，a1)。 （5）假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。 答案： template void DeletePreNode (Node （6）已知一单链表中的数据元素含有三类字符(即:字 Node //得到s的结点的前一个结点的前一个结点 while (p->next->next != s) p=p->next; //删除p->next指向的结点 Node 母字符、数字字符和其它字符)。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。 （7）Josephus环问题：任给正整数n、k，按下述方法可得排列1，2，??，n的一个置换：将数字1，2，??，n环形排列（如图2-36所示），按顺时针方向从1开始计数，计满k时输出该位置上的数字（并从环中删去该数字），然后从下一个数字开始继续计数，直到环中所有数 n-1n-2n123图2-36 Josephus环 字均被输出为止。例如，n=10，k=3时，输出的置换是3，6，9，2，7，1，8，5，10，4。试编写一算法，对输入的任意正整数n、k，输出相应的置换数字序列。 习题3 1． 填空题 （1）栈的进出原则是（___________），队列的进出原则是（___________）。 答案：后进先出（LIFO） 先进先出（FIFO） （2）设32位计算机系统中，空栈S存储int型数据，栈顶指针为1024H。经过操作序列 push(1)，push(2)，pop，push(5)，push(7)，pop，push(6)之后，栈顶元素为（___________），栈底元素为（___________），栈的高度为（___________），输出序列是（___________），栈顶指针为（___________）H。 答案：6 1 3 2,7 1030 （3）两栈共享存储空间，其数组大小为100，数组下标从0开始。top1和top2分别为栈1和栈2的栈顶元素下标，则栈1为空的条件为（___________），栈2为空的条件为（___________），栈1或栈2满的条件为（___________）。//空栈的条件 答案：top1==-1 top2==100 top1+1==top2 （4）一个队列的入队顺序是1234，则队列的输出顺序是（___________）。 答案：1234 （5）设循环队列数组大小为100，队头指针为front，队尾指针为rear；约定front指向队头元素的前一个位置，该位置永远不存放数据。则入队操作时，修改rear=（___________），出队操作修改front=（___________），队空的判别条件为（___________），队满的判别条件为（___________）。若front=20，rear=60，则队列长度为（___________），若front=60,rear=20，则队列长度为（___________）。 //循环队列 答案：(rear+1)0 (front+1)0 rear==front (rear+1)0=front 40 60 （6）朴素模式匹配算法中，每个串的起始下标均为1，变量i=100，j=10，分别表示主串和模式串当前比较的字符元素下标，若本次比较两字符不同，则i回溯为（___________），j回溯为（___________）。 答案：92 1 （7）用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别为（___________）和（___________）。 答案：O(1) O(n) 2． 选择题 （1）将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。 A. 数组 B. 栈 C. 队列 D. 二叉树 D. 4 3 2 1 （2）四个元素1、2、3、4依次进栈，出栈次序不可能出现（ ）情况。 A. 1 2 3 4 B. 4 1 3 2 C. 1 4 3 2 （3）设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（ ）。 A. r-f B. r-f+1 C. (r-f) mod n +1 D. (r-f+n) mod n 说明：这里的数组不是指C++数组，也就说假定数组长度依然为n，而不是n+1。 （4）10行100列的二维数组A按行优先存储，其元素分别为A[1][1] ~ A[10][100]，每个元素占4字节，已知Loc(A[6][7])=10000H，则Loc(A[4][19])=（ ）。 A. FC11H B. 9248H C. 2F00H D. FD10H （5）设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为（ ）。 A. 连接 B. 模式匹配 C. 求子串 D. 求串长 （6）为了解决计算机主机和键盘输入之间速度不匹配问题，通常设置一个键盘缓冲区，该缓冲区应该是一个（ ）结构。 A. 栈 B. 队列 （7）STL中的双端队列为（ ）。 A. 顺序容器 A. 队列适配器 B. 容器适配器 B. 双端队列 C. 数组 D. 线性表 D. 泛函适配器 C. 迭代器适配器 （8）STL中的（ ）允许用户为队列中的元素设置优先级。 C. 优先级队列适配器 D. 栈适配器 （9）string类型不支持以（ ）的方式操作容器，因此不能使用front、back和pop_back操作。 A. 线性表 B.队列 C. 栈 D. 串 3． 算法设计 （1）设计一个算法判断算数表达式的圆括号是否正确配对。 （2）假定用带头结点的循环链表表示队列，并且只设置一个指针指向队尾元素，试设计该队列类，完成相应的入队、出队、置空队、求队长等操作接口。 （3）设计算法把一个十进制数转换为任意指定进制数。 （4）设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为w1，w2，??，wn。问能否从这n件物品中选择若干件放入此背包，使得放入的重量之和正好为S。如果存在一种符合上述要求的选择，则称此背包问题有解，否则此问题无解，试用递归和非递归两种方法设计解决此背包问题的算法。 背包问题分析： 背包问题是一个经典的NP问题，它既简单形象容易理解，又在某种程度上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例题。本题目是最简单的01背包问题，除此之外，还有许多由此衍生出来的很多复杂的背包问题。 本题中，最容易想到的就是假定背包中已放入了部分物品，现将第i件物品试着放入背包中，如果可以放进去，背包的重量在原来的基础上增加了wi；如果不可以放进去，说明加入后太重了，换下一件物品。如果所有的剩余物品都不能放入，说明以前放入的物品不合适，拿出上一次放入的物品，继续试剩余的物品。 递归解法： 设背包函数为knapsack(int s, int n)，参数 int s 为剩余重量，int n 为剩余物品数，返回值表示背包分配是否成功。 （1） 如果s==0，表示分配成功，返回1； （2） 如果s<0 或者 n<0，表示太重，或者物品分配完毕，返回0； （3） 执行knapsack( s – wi, n-1)，测试当前这件物品放入是否成功。 （3.1） 如果成功，说明当前这件物品放入刚好最终分配成功。 （4） 返回knapsack( s , n-1)，说明当前物品不合适，减小剩余物品数，继续测试。 测试代码： /*简单的背包问题递归解*/ #include\ #define N 6 /*物品数量*/ #define S 8 /*背包大小*/ int W[N+1]={0,1,2,3,4,5,6};/*数据，各物品重量，W[0]不使用*/ /* 背包函数 knapsack() 参数 int s 剩余重量 int n 剩余物品数 返回 int 背包分配是否成功 */ int knapsack(int s,int n) { if(s == 0)/*分配结束，成功*/ return 1; if(s < 0 || (s > 0 && n < 1))/*没有可用空间，或者物品分配完毕*/ return 0; if( knapsack(s - W[n] , n - 1)){/*递归*/ printf(\/*输出*/ return 1; } return knapsack(s , n - 1); } int main() { if(knapsack(S , N))/*递归调用*/ printf(\else printf(\ return 1; }/*main*/ 非递归解法： 一件一件的物品往包（即栈）里放，发现有问题，拿出来，放其他的物品。 （1）i=1 （2）从第i件到第n件测试每件物品，对于第j次循环，测试第j件物品 （2.1）如果该物品可以放，入栈 （2.2）若栈的容量刚好达到要求，成功，打印栈元素。 （2.3）继续测试j+1件物品 （3）若没有成功 （3.1）若栈空，返回失败 （3.2）将栈顶物品（设第k个）出栈 （3.3）令i=k+1，返回（2） 代码： #include\ #define N 6 /*物品数量*/ #define S 8 /*背包大小*/ int W[N+1]={0,1,2,3,4,5,6};/*数据，各物品重量，W[0]不使用*/ int stack[1000]={0}; int value=0; int size=0; knapsackstack() { int i=1; } while (1) { for (int j=i;j<=N;j++) } { if (value+W[j]<=S) {stack[size++]=j; value+=W[j];} if (value==S){ printf(\得到一组解：\ } for (int p=0;p else if (value>S) break; } if (size==0) {printf(\i=stack[--size]+1; value-=W[i-1]; void main() { } knapsackstack(); 习题4 1. 填空题 （1）一般来说，数组不执行（___________）和（___________）操作，所以通常采用 （___________）方法来存储数组。通常有两种存储方式：（___________）和（___________）。 答案：删除 插入 顺序存储 行优先存储 列优先存储 （2）设8行8列的二维数组起始元素为A[0][0]，按行优先存储到起始元素下标为0的一维数组B中，则元素B[23]在原二维数组中为（___________）。若该二维数组为上三角矩阵，按行优先压缩存储上三角元素到起始元素下标为0的一维数组C中，则元素C[23]即为原矩阵中的（___________）元素。 答案：A[2][7] A[3][5] （3）设二维数组A为6行8列，按行优先存储，每个元素占6字节，存储器按字节编址。已知A的起始存储地址为1000H，数组A占用的存储空间大小为（___________）字节，数组A的最后一个元素的下标为（___________），该元素的第一个字节地址为（___________）H，元素A[1][4]的第一个字节的地址为（___________）H。（提示：下标从0开始计） 答案：288 A[5][7] 111AH 1048H （4）设C++中存储三维数组Amnp，则第一个元素为a000，若按行优先存储，则aijk前面共有（___________）个元素；若按列优先存储，则aijk前面共有（___________）个元素。 答案：inp+jp+k i+mj+mnk （5）常见的稀疏矩阵压缩方法有：（___________）和（___________）。 答案：三元组表 十字链表 （6）广义表（（a），（（b，c），d），（e））的长度为（___________），表头为（___________），表尾为（___________）。 答案：3 （a） （（（b，c），d），（e）） （7）设广义表LS＝（（a），（（b，c），d），（e）），若用取表头操作GetHead（）和取表尾操作GetTail（）进行组合操作，则取出元素b的运算为（___________）。 答案：GetHead(GetHead(GetHead(GetTail(LS)))) （8）若广义表A满足GetHead（A）＝GetTail（A），则A＝（___________）。 答案：（（）） 2. 问答题 （1）根据下面的矩阵，写出矩阵转置后的三元组表，起始行列值为1。 ?0??0??3??0?0??15?12000180900130000000005000000140000??0?0?? 0??0?0?? Row 1 1 2 2 3 Col 3 6 1 5 1 Item -3 15 12 18 9 3 5 6 矩阵行数：7 矩阵列数：6 4 2 3 13 5 14 非零元素个数：8 （2）对于如下稀疏矩阵，请写出对应的三元组顺序表，若采用顺序取，直接存的算法进行转置运算，引入辅助数组number[]和position[]，分别表示矩阵各列的非零元素个数和矩阵中各列第一个非零元素在转置矩阵中的位置，请写出数组中的各元素（所有数组起始元素下标为0）。 ?0??3 原矩阵 ?0??0?000020?100??0? 5??0?? Row 0 1 2 2 行数：4 Col 2 0 2 3 Item 2 3 -1 5 Col Number[col] Position[col] 0 1 0 1 0 1 2 2 1 3 1 3 列数：4 非零元素个数：4 （3）对于上题中的稀疏矩阵，写出对应的三元组表和十字链表。 三元组表： Row 0 1 Col 2 0 Item 2 3 2 2 行数：4 列数：4 2 3 -1 5 非零元素个数：4 十字链表： 441001221301022111032222-123530 3. 算法设计 （1）设计上三角矩阵存储类，实现如下接口： ① 对于上三角矩阵A[N][N]，可按行优先压缩存储和按列优先压缩存储。 ② 对于给定的一维数组B[M]，可根据行优先压缩存储或列优先压缩存储还原原始的上三角矩阵。 （2）针对24位真彩色BMP图像文件，编写程序实现如下功能： ① 读取24位真彩色BMP图像文件。 ② 将原图像转换为24位灰度图像，并进行保存。转按公式如下： Grey=0.3*Red+0.59*Blue+0.11*Green ③ 将24位灰度图像转换为8位灰度图像，并进行保存。 ④ 将8位灰度图像分别进行4－邻域和8－邻域平滑，并分别进行保存。 习题5 1. 填空题 （1）已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为（___________）。 答案：129 （2）3个结点可构成（___________）棵不同形态的二叉树。 答案：5 （3） 设树的度为5，其中度为1~5的结点数分别为6、5、4、3、2个，则该树共有（___________） 个叶子。 答案：31 （4）在结点个数为n（n>1）的各棵普通树中，高度最小的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。高度最大的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。 答案：2 n-1 1 n 1 n-1 （5）深度为k的二叉树，至多有（___________）个结点。 答案：2-1 （6）（7）有n个结点并且其高度为n的二叉树的数目是（___________）。 答案：2n-1 （8）设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为（___________），最小结点数为（___________）。 答案：2-1 k+1 （9）将一棵有100个结点的完全二叉树按层编号，则编号为49的结点为X，其双亲PARENT（X）的编号为（）。 答案：24 （10）已知一棵完全二叉树中共有768个结点，则该树中共有（___________）个叶子结点。 答案：384 （11）（12）已知一棵完全二叉树的第8层有8个结点，则其叶子结点数是（___________）。 答案：68 （13）深度为8（根的层次号为1）的满二叉树有（___________）个叶子结点。 答案：128 （14）一棵二叉树的前序遍历是FCABED，中序遍历是ACBFED，则后序遍历是（___________）。 答案：ABCDEF （15）某二叉树结点的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则该二叉树结点的前序遍历序列为（___________），该二叉树对应的树林包括（___________）棵树。 答案：EACBDGF 2 2. 选择题 （1）在一棵度为3的树中，度为3的结点的个数为2，度为2的结点个数为1，则度为0的结点个数为（ ）。 A. 4 B. 5 （2）下列陈述中正确的是（ ）。 A. 二叉树是度为2的有序数 B. 二叉树中结点只有一个孩子时无左右之分 C. 二叉树中必有度为2的结点 D. 二叉树中最多只有两棵子树，并且有左右之分 （3）在K叉树中，如果结点M有3个兄弟，而且N是M的双亲，则N的度是（ ） A. 3 B. 4 C. 5 D. 1 （4）设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ）。 A. 2h B. 2h－1 C. 2h+1 （5）高度为5的完全二叉树至少有（ ）个结点。 D. h+1 C. 6 D. 7 k+1k A. 16 B. 32 C. 31 D. 5 （6）具有65个结点的完全二叉树的高度为（ ）。（根的层次号为0） A. 8 B. 7 C.6 D. 5 （7）对一个满二叉树，m个树叶，n个结点，深度为h，则（ 无 ）。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-1 （8）任一棵二叉树，其叶子结点数为n0，度为2的结点数为n2，则存在关系（ ）。 A. n2 +1=n0 B. n0 +1=n2 C. 2n2 +1=n0 D. n2 =2n0 +1 （9）某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（ ）。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca （10）设m、n为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（ ）。 A. n在m右方 B. n是m祖先 C. n在m左方 D.n是m子孙 （11）一棵二叉树的广义表表示为a（b（c，d），e（f（g））），则得到的层序遍历序列为（ ）。 A. abcdefg B. cbdaegf C. cdbgfea D. abecdfg （12）若二叉树采用二叉链表作为存储结构，要交换其所有分支结点左右子树的位置，利用（ ）遍历方法最合适。 A. 前序 B. 中序 C. 后序 D. 层序 说明：显然，如果按前序或后序遍历，当访问某结点时，交换其左右孩子，则可完成要求。进行层序遍历时，当结点出队时，交换左右孩子，也可以完成题目要求。因此该题有3个答案，谈不上哪个最合适。建议该题目将“最合适”改为“不合适”，这样答案应该是唯一的。 （13）对二叉树进行（ ）遍历，可以得到该二叉树所有结点构成的排序序列。 A. 前序 B. 中序 C. 后序 D. 层序 （14）设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ ）个。 A. n-1 B. n C. n+1 D. n+2 （15）利用3，6，8，12，5，7这6个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（ ）。 A.3 B. 4 C.5 D. 6 （16）若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。 A. n-1 B. [n/m]-1 C. [(n-1)/(m-1)] D. [n/(m-1)]-1 说明：在这里度为m的哈夫曼树是指仅含有度为0和m的结点的m叉树。因此有： (1) Ｎ＝n+nm (2) N = 1 + mnm 3. 试分别画出具有3个结点的树和二叉树的所有不同形态。 答案：树： 二叉树： 4． 试找出分别满足下面条件的所有二叉树： （1）前序序列和中序序列相同； 答案: 右斜树 （2）中序序列和后序序列相同； 答案：左斜树 （3）前序序列和后序序列相同。 答案：只有根结点的树 5．一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从0开始对全部结点进行编号，试问： （1）各层的结点个数是多少？ 答案：n层的结点个数为kn-1 （2）编号为i的结点的父结点（若存在）的编号是多少？ 答案：|(i-1)/k| (|·|表示取下整) （3）编号为i的结点的第m个孩子结点（若存在）的编号是多少？ 答案：k*i+m （4）编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？ 答案：i%k!=0 i+1 （5）叶子结点数n0和非叶子结点数nk之间满足的关系。 答案：nk*(k-1)=n0-1 6．若一棵二叉树的前序序列为abdgcefh，中序序列为dgbaechf，请画出该二叉树，并写出其后序序列。 答案：gdbehfca abcdefgh 7．请将图5－42所示树T转换为二叉树T′。 KAEI答案： BFCGJDH KABEIJFGH 8. 对于图5－43所示的二叉树，该树的三种遍历分别是什么？ CD-+abc答案： /*-d ef前序 -+a*b-cd/ef 中序 a+b*c-d-e/f 后序 abcd-*+ef/- 9. 对于图5－44所示的二叉树，请画出和其对应的森林。 ABCDEFGHIJKM 答案： ABDHKECFIGJM 10. 假设用于通信的电文仅由9个字符组成，并且出现概率为0.07（A）、0.19（B）、0.02（C）、0.06（D）、0.32（E）、0.03（F）、0.21（G）、0.10（H）： （1）画出哈夫曼树； 答案： 10.600.400.28EBG0.110.170.05DAHCF （2）每个字符的哈夫曼编码； 答案： A 0010 B 10 C 00000 D 0001 E 01 F 00001 G 11 H 0011 （3）计算其带权路径长度； 答案：WPL=0.07*4+0.19*2+0.02*5+0.06*4+0.32*2+0.03*5+0.21*2+0.10*4=2.61 （4）如果电文是“ABCDEFGH”压缩前每个字符使用8bit的ASCII编码，则采用上面的哈夫曼编码，其压缩比是多少？ 答案：??4?2?5?4?2?5?2?48?8?0.4375 习题6 1． 填空题 （1）n个顶点的无向图，最多能有（___________）条边。 答案： [n*(n-1)]/2 （2）有n个顶点的强连通图G最多有（___________）条弧。 答案：n*(n-1) （3）有n个顶点的强连通图G至少有（___________）条弧。 答案：n （4）G为无向图，如果从G的某个顶点出发，进行一次广度优先遍历，即可访问图的每个顶点，则该图一定是（___________）图。 答案：连通 （5）若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为（___________）。 答案：O（n） （6）n个顶点的连通图的生成树有（___________）条边。 答案：n-1 （7）图的深度优先遍历类似于树的（___________）遍历；图的广度优先遍历类似于树的（___________）遍历。 答案：前序 层序 （8）对于含有n个顶点e条边的连通图，用普里姆算法求最小生成树的时间复杂度为（___________）。 答案：O（n2） （9）已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（___________）。 答案：O（n+e） （10）一棵具有n个顶点的生成树有且仅有（___________）条边。 答案：n-1 2． 单选题 （1）在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 A. 1/2 B. 1 C. 2 D. 4 （2）在一个具有n个顶点的有向图中，若所有顶点的出度数之和为S，则所有顶点的度数之和为（ ）。 A. S A. n B. S－1 B. n(n-1) C. S+1 D. 2S （3）具有n个顶点的有向图最多有（ ）条边。 C. n(n+1) D. 2n 2 （4）若一个图中包含有k个连通分量，若按照深度优先搜索的方法访问所有顶点，则必须调用（ ）次深度优先搜索遍历的算法。 A. k B. 1 C. k-1 D. k+1 （5）若一个图的边集为{<1，2>，<1，4>，<2，5>，<3，1>，<3，5>，<4，3>}，则从顶点1开始对该图进行深度优先遍历，得到的顶点序列可能为（ ）。 A. 1，2，5，4，3 C. 1，2，5，3，4 B. 1，2，3，4，5 D. 1，4，3，2，5 （6）若一个图的边集为{（A，B），（A，C），（B，D），（C，F），（D，E），（D，F）}，则从顶点A开始对该图进行广度优先遍历，得到的顶点序列可能是（ ）。 A. A，B，C，D，E，F C. A，B，D，C，E，F B. A，B，C，F，D，E D. A，C，B，F，D，E 说明：教材中某结点的邻接点选择次序默认都是自小而大，如果按此进行广度优先遍历，则结果应该为ABCDFE，但题目问可能的序列，则邻接点选择次序可以随便确定，此时，D是正确的。 （7）存储无向图的邻接矩阵是（ A ），存储有向图的邻接矩阵是（ B ）。 A. 对称的 B. 非对称的 （8）采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 （9）设有一个无向图G＝（V，E）和G′＝（V′，E′），如果G′为G的生成树，则下面不正确的说法是（ ）。 A. G′为G的子图 B. G′为G的连通分量 C. G′为G的极小连通子图，且V＝V D. G′为G的一个无环子图 3． 画出图6－32所示的无向图的邻接表（顶点由小到大排列），并根据所得邻接表给出深 度优先和广度优先搜索遍历该图所有的顶点序列。 BCDAGEHF 答案： 01234567ABCDEFGH1012341072345621666673574657深度优先：ABCDEFGH 广度优先：ABHCGFDE 4． 使用普里姆算法构造出图6－33中图G的一棵最小生成树。 161253566346 答案：生成最小树的顺序如下 55241①2④⑤5 43②6 ③习题7 1. 填空题 （1）由10000个结点构成的二叉排序树，在等概率查找的条件下，查找成功时的平均查找长度的最大值可能达到（___________）。 答案：5000.5 （2）长度为11的有序序列：1，12，13，24，35，36，47，58，59，69，71进行等概率查找，如果采用顺序查找，则平均查找长度为（___________），如果采用二分查找，则平均查找长度为（___________），如果采用哈希查找，哈希表长为15，哈希函数为H（key）＝key， 采用线性探测解决地址冲突，即di=(H(key)+i)，则平均查找长度为（保留1位小数）（___________）。 答案：6，3，1.6 （3）在折半查找中，查找终止的条件为（___________）。 答案：找到匹配元素或者low>high? （4）某索引顺序表共有元素275个，平均分成5块。若先对索引表采用顺序查找，再对块元素进行顺序查找，则等概率情况下，分块查找成功的平均查找长度是（___________）。 答案：31 （5）高度为8的平衡二叉树的结点数至少是（___________）。 答案： 54 计算公式：F(n)=F(n-1)+F(n-2)+1 （6）对于这个序列{25，43，62，31，48，56}，采用的散列函数为H(k)=k%7，则元素48的同义词是（___________）。 答案：62 （7）在各种查找方法中，平均查找长度与结点个数无关的查找方法是（___________）。 答案：散列查找 （8）一个按元素值排好的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，平均比较次数分别是s和b，在查找成功的情况下，s和b的关系是（___________）；在查找不成功的情况下，s和b的关系是（___________）。 答案：(1)(2s-1)b=2s([log2(2s-1)]+1)-2[log(2s-1)]+1+1 2 (2)分两种情况考虑，见解答。 解： (1)设所有元素的个数为n，显然有s=n*(n+1)/(2n),则 n=2s-1 设折半查找树高度为k，则前k-1层是满二叉树，最后一层的节点数为 n-(2k-1 -1） 因此，总比较次数 nb=20*1+21*2+22*3+…+2k-2*(k-1)+(n-(2k-1 -1))*k, 而 2*1+2*2+2*3+…+2*(k-1)=2*k-2+1 因此 nb=2*k-2+1+(n-(2-1))*k=(n+1)k-2+1 又k=[log2n]+1,n=2s-1,所以有 (2s-1)b=2s([log2(2s-1)]+1)-2[log(2s-1)]+1+1 (2)查找不成功，对于顺序查找有：s=n。对于折半查找，找不到的情况有n+1种,查找 2 012k-2k-1k k-1kk-1k 到每个叶子节点或度为1的节点后就不再查找，设折半查找树高度为k，则第k-1层的节点数x=2k-2，第k层的节点数y=n-(2k-1 -1） （a）当第k层的节点数y小于等于第k-1层的节点数x时， 则第k-1层有y结点度为1，其余x-y个结点度为0。 则查找次数为：(n+1)b=2yk+2(x-y)(k-1)+y(k-1)=2x(k-1)+yk (n+1)b=2 *(k-1)+(n-(2 -1))*k （b）当第k层的节点数y大于第k-1层的节点数x时， 则第k-1层不存在度为0的结点，有2x-y个结点度为1，其余y-x个结点度为2 则查找次数为：(n+1)b=2yk+(2x-y)(k-1)=2x(k-1)+y(k+1) (n+1)b=2k-1 *(k-1)+(n-(2k-1 -1))*(k+1) k-1 k-1 将k=[log2n]+1，n=s分别代入（a）（b）两个等式即得。 2. 选择题 （1）从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（ ）个结点。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 （2）对一个长度为50的有序表进行折半查找，最多比较（ ）次就能查找出结果。 A. 6 B. 7 C. 8 D. 9 （3）对有18个元素的有序表做折半查找，则查找A[3]（下标从1开始）的比较序列的下标依次为（ ）。 A. 1-2-3 B. 9-5-2-3 C. 9-5-3 D. 9-4-2-3 （4）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为－1，右孩子的平衡因子为0，则做（ ）型调整以使其平衡。 A. LL B. LR C. RL D. RR （5）理论上，散列表的平均比较次数为（ ）次。 A. 1 B. 2 C. 4 D. n （6）二叉排序树中，最小值结点的（ ）。 A. 左指针一定为空 B. 右指针一定为空 C. 左、右指针均为空 D. 左、右指针均不为空 （7）散列技术中的冲突指的是（ ）。 A.两个元素具有相同的序号 B. 两个元素的键值不同，而其他属性相同 C. 数据元素过多 D. 不同键值的元素对应于相同的存储地址 （8）散列表表长m=14，散列函数H(k)=k。表中已有15，38，61，84四个元素，如果用线性探测法处理冲突，则元素49的存储地址是（ ）。 A. 8 B. 3 C. 5 D. 9 （9）采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（ ）。 A. 一定都是同词义词 B. 一定都不是同义词 C. 不一定都是同义词 D. 都相同 （10）静态查找与动态查找的根本区别在于（ ）。 A. 它们的逻辑结构不一样 B. 施加在其上的操作不同 C. 所包含的数据元素的类型不一样 D. 存储实现不一样 3．设一个散列表包含hashSize=13个表项，其下标从0到12，采用线性探查法解决冲突，请按以下要求，将关键码{10，100，32，45，58，126，3，29，200，400，0}散列到表中。 （1）散列函数采用除留余数法，用%hashSize(取余运算)将各关键码映像到表中，请指出每一个产生冲突的关键码可能产生多少次冲突。 答案：如下表， H(key) 0 1 2 3 4 5 6 7 8 9 10 11 12 400 key 0 3 29 200 32 45 58 100 10 126 产生冲突的关键码有：29－1次，45－1次，58－2次，126－2次，400－2次 （2）散列函数采用先将关键码各位数字折叠相加，再用%hashSize将相加的结果映像到表中的办法，请指出每一个产生冲突的关键码可能产生多少次冲突。 答案：如下表， H(key) 0 1 2 3 4 5 6 7 8 9 10 11 12 key 58 10 100 3 200 32 400 0 45 126 29 产生冲突的关键码有：100－1次，200－2次，400－2次，0－7次，126－1次 4．试编写一个函数，完成拉链法解决冲突的散列表上删除一个指定结点的算法。 5．设散列表的长度为13，散列函数为H(k)=k，给定的关键字序列为：19，14，23，01，68，20，84，27，55，11，10，79。试画出分别用拉链法和线性探测查找解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法的查找成功和查找不成功的平均查找长度。 答案：拉链法： 1141277936855671920841011231110 平均查找次数：成功时是21/12=1.75次，不成功时是(4+2+2+1+2+1)/13=12/13=0.92次（在这里查找比较是指元素值的比较。如果指针为空，则不进行查找比较，此时不算查找）。 线性探测法： H(key) 0 key 冲突次数 成功时的比较次数 不成功时的比较次数 1 14 0 1 2 01 1 2 3 68 0 1 4 27 3 4 5 55 2 3 6 19 0 1 7 20 0 1 8 84 2 3 9 79 8 9 10 23 0 1 11 11 0 1 12 10 2 3 0 12 11 10 9 8 7 6 5 4 3 2 1 平均查找次数：成功时是2.5次，不成功时ASL=（0+12+11+10+9+8+7+6+5+4+3+2+1）/13 = 6次。 习题8 1. 填空题 (1) 排序的主要目的是为了以后对已排序的数据元素进行（___________）。 答案：查找 (2) 对n个元素进行起泡排序，在（___________）的情况下比较的次数最少，其比较次数 为（___________）；在（___________）的情况下比较次数最多，其比较次数为（___________）。 答案：原始序列有序 n-1 原始序列逆序 n(n-1)/2 (3) 对一组元素{54,38,96,23,15,72,60,45,83}进行直接插入排序，当第7个元素60插入到有 序表时，寻找插入位置需比较（___________）次。 答案：3 (4) 对一族元素{54,38,96,23,15,72,60,45,83}进行快速排序，在递归调用中使用的栈所能达到的最大深度为（___________） 答案：4 (5) 对n个待排序元素序列进行快速排序，所需最好时间是（___________），最坏时间是 （___________）。 答案：O(nlogn) O(n) (6) 利用简单选择排序对n个元素进行排序，最坏情况下，元素交换的次数为（___________）。 答案：n-1 (7) 如果将序列{50,16,23,68,94,70,73}建成堆，只需把16与（___________）交换。 答案：50 (8) 对于键值序列{12,13,11,18,60,15,7,18,25,100}，用筛选法建堆，必须从键值为（___________）的结点开始。 答案：60 (9) 采用改进的冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递 增，则排序过程中记录的比较次数为（___________）。若A的初始状态为递减排序， 则记录的交换次数为（___________）。 答案：n-1 n(n-1)/2 2. 单选题 (1) 从未排序序列中依此取出一个元素与已排序序列中的元素依此进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。 A.插入排序 B. 选择排序 C. 希尔排序 D. 二路归并排序 (2) 一个对象序列的排序码为{46,79,56,38,40,84}，采用快速排序以位于最左位置的对象为基 准而得到的第一次划分结果为（ ）。 A. {38,46,79,56,40,84} C. {40,38,46,56,79,84} B. {38,79,56,46,40,84} C. {38,46,56,79,40,84} 2 (3) 对二叉排序树进行（ ）遍历，可以得到该二叉树所有节点构成的排序序列。 A. 前序 B. 中序 C. 后序 D. 按层序 (4) 当待排序列基本有序时，下列排序方法中（ ）最好。 A. 直接插入排序 B. 快速排序 C. 堆排序 D. 归并排序 (5) 在下列排序算法中，在待排序的数据表已经为有序时，比较操作花费时间反而最多的是（ ）。 A. 快速排序 B. 希尔排序 C. 冒泡排序 D. 堆排序 (6) 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是 （ ）。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 直接插入排序 (7) 下列排序算法中，时间复杂度为O(nlog2n)且占用额外空间最少的是（ ）。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 希尔排序 (8) 已知数据表A中每个元素距其最终位置不远，则采用（ ）排序算法最节省时 间。 A. 堆排序 B. 插入排序 C. 快速排序 D. 直接选择排序 D. 堆 D. 插入排序 (9) 下面给出的4种排序法中（ ）排序法是不稳定排序法。 A. 插入 B. 冒泡 C. 二路归并 (10) 就平均性能而言，最快的排序方法是（ ）。 A. 冒泡排序 B. 希尔排序 C. 快速排序 3. 判断以下序列是否为小（顶）根堆？若否，则以最少的移动次数将他们调整为小（顶） 根堆。（要求画出最后的堆结构和线性序列） (1) (19,78,32,66,26,58,46,95,89,31)； (2) (113,98,69,35,68,25,43,19,31,55,16,29)。 答案： (1) (19,26,32,66,31,58,46,95,89,78) 19263266315846958978 (2) (16,19,25,31,55,29,43,35,113,98,68,69) 1619253155294335113986869 4. 设有关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要求按照关键码值递增的次序进行排序。 (1) 若采用初时步长为4的Shell（希尔）排序法，写出一趟排序的结果； (2) 若采用以第一个元素为分界元素（枢轴）的快速排序法，写出一趟排序的结果。 答案： (1) (Q,A,C,S,Q,D,F,X,R,H,M,Y) (2) (F,H,C,D,Q,A,M,Q,R,S,Y,X) 5. 试编写一个双向冒泡排序算法，即在排序过程中交替改变扫描方向。 6. 编写算法，实现将整形数组中的元素按照奇数和偶数分开，使奇数在原数组的前面，偶 数在原数组的后面。 7. 利用快速排序算法的思想，编写算法，实现求第k个最小值的功能。 8. 试写一个非递归的快速排序算法。 9. 如果存储结构采用的是带头结点的单链表，编写排序算法使链表中的元素有序排列。