习题1
1.填空题
（1）（___________）是指数据之间的相互关系，即数据的组织形式。通常人们认为它包含三个方面的内容，分别为数据的（___________）、（___________）及其运算。
答案：数据结构逻辑结构存储结构
（2）（___________）是数据的基本单位，在计算机程序中通常作为一个整体进行处理。
答案：数据元素
（3）数据元素之间的不同逻辑关系代表不同的逻辑结构，常见的逻辑结构有（___________）、（___________）、（___________）和（___________）。
答案：集合线形结构树结构图结构
（4）数据的存储结构考虑的是如何在计算机中存储各个数据元素，并且同时兼顾数据元素间的逻辑关系。基本的存储结构通常有两大类：（___________）和（___________）。
答案：顺序存储结构链式存储结构
（5）通常一个问题可以有多种不同的算法，但每个算法必须满足5个准则：输入、输出、（___________）、（___________）和（___________）。
答案：有穷性确定性可行性
（6）通常通过衡量算法的（___________）复杂度和（___________）复杂度来判定一个算法的好坏。
答案：时间空间
（7）常见时间复杂性的量级有：常数阶O（___________）、对数阶O（___________）、线性阶O（___________）、线性对数阶O（___________）、平方阶O（___________）、和指数阶O（___________）。通常认为，当问题规模较大时，具有（___________）量级的算法是不可计算的。
答案：1 log n n n log n 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 C. n*(n+1)/2 D. 不确定 分析：2 1 2 01 (1)112 n n n i j i i n n n i ---==+=-=--= ∑∑∑ 3. 分析以下程序段的时间复杂度。 （1）for (i=l; i<=n; i++) { k++; for (j=1; j<=n; j++) m += k; } （2）for (i=l; i<=n; i++) k++; for (j=1; j<=n; j++) m += k; （3）i=1; while (i<=n) i *= 2; （4）i=1; while (i<=n) i += 2; （5）k=100,i=10; do { if (i i++; }while (i sum += j; （7）y=0; while (y*y*y <= n) y++; （8）int i=0; while(i 答案： (1) O(n2) (2) O(n) (3) O(log n) (4) O(n) (5) O(1) (6) O(1) (7) O(n1/3) (8) O(n) 4.将整数设计为一个类，将整数相关的常见数学运算设计为类的接口并进行实现，如求与 给定值的最大公约数、最小公倍数、枚举所有因子等。 解： #include"math.h" #include"vector" using std::vector; //定义自然数类 class NaturalNumber{ public: NaturalNumber(unsigned long int n=0):num(n){} unsigned long int GreatestCommonDivisor(NaturalNumber & nn);//求解最大公约数 unsigned long int LeaseCommonMultiple(NaturalNumber & nn);//求解最小公约数 int GetFactors(vector unsigned long int GetNumber(){return num;} //……其它外部接口 private: unsigned long int EUCLID(NaturalNumber & n); //欧几里德算法求解最大公约数 unsigned long int num; //存储真正的自然数 }; //返回欧几里德算法求解最大公约数 unsigned long int NaturalNumber :: EUCLID(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){ m = n; n = r; r = m % n; } return n; } //返回最大公约数 unsigned long int NaturalNumber :: GreatestCommonDivisor(NaturalNumber & nn) { return EUCLID(nn); } //返回最小公倍数 unsigned long int NaturalNumber :: LeaseCommonMultiple(NaturalNumber & nn) { unsigned long int temp = EUCLID(nn); return num * nn.GetNumber() / temp; } int NaturalNumber :: GetFactors( vector { int t=0; int m = sqrt((double)num); vector for (unsigned long int i=1;i { if ( 0 == num%i ) {t+=2; factors.push_back(i);bigfactors.push_back(num/i);} } if ( m*m == num ) { t++; factors.push_back(m);} vector if (bigfactors.size()) do { it--; factors.push_back(*it); }while (it!=bigfactors.begin()); return t; } void main() { NaturalNumber p(1); int xx = p.GreatestCommonDivisor(NaturalNumber(120)); int yy = p.LeaseCommonMultiple(NaturalNumber(120)); vector int t = p.GetFactors(f); } 习题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. 随机存取索引存取 B. 顺序存取随机存取 C. 随机存取顺序存取 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. 数组单链表 B. 顺序表链表 C. 向量静态链表 D. 静态链表动态链表 （5）（）是STL中线性表的链式存储形式，STL标准库中一般采用（）实现。 A. vector 数组 B. list 单链表 C. list 双向循环链表 D. vector 单链表 （6）顺序表的类型定义可经编译转换为机器级。假定每个结点变量占用k(k>=1)个字节，b 是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点a i的存储地址为（）。 A. b+ki B. b+k(i-1) C. b+k(i+1) D. b-1+ki （7）在循环链表中，若不使用头指针而改设为尾指针（rear），则头结点和尾结点的存储位置分别是（）。 A. real和rear->next->next B. rear->next 和rear C. rear->next->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.使单链表至少有一个结点 B.标示表结点中首结点的位置 C.方便运算的实现 D.说明单链表是线性表的链式存储实现 3.程序选择题 （1）已知L指向带表头结点的非空单链表的头结点，且P结点既不是首结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列： a.删除P结点的直接后继结点的语句序列是（___________） b.删除P结点的直接前驱结点的语句序列是（___________） c.删除P结点的语句序列是（___________） d.删除首结点的语句序列是（___________） e.删除尾结点的语句序列是（___________） 答案: 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结点的语句序列是____________________________。 答案: 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.push_back (3); ivec.insert (ivec.begin (),10); vector ivec.erase (++it); ivec.pop_back(); ivec.insert(ivec.end(),20); 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 << "1.size: " << ivec.size() << endl; ivec.resize(100); cout << "2.size: " << ivec.size() << endl; for (int j=0; j<95; j++) ivec.insert(ivec.end(),j); cout << "3.size: " << ivec.size() << endl; ivec.resize(100); ivec.reserve (20); cout << "4.size: " << 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.assign(a,a+5); ilist.pop_back (); //1 2 3 4 ilist.insert (ilist.end(),7); //1 2 3 4 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; 答案：3 4 7 20 5．算法设计 （1）分别编程实现顺序表类和链表类，并设计完整的测试程序对每个接口进行测试。（2）设A=（a1,a2,a3,......a n）和B=(b1,b2,.. .,b m)是两个线性表（假定所含数据元素均为整数）。若n=m且a i=b i(i=1,.. .,n),则称A=B;若a i=b i(i=1,.. .,j)且a j+1B。试编写一个比较A和B的算法，当A （3）假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。 （4）试分别以顺序表和单链表作为存储结构，各写一个实现线性表的就地（即使用尽可能少的附加空间）逆置的算法，在原表的存储空间内将线性表（a1，a2,，……，a n-1，a n)逆置为（a n，a n-1，……，a2，a1)。 （5）假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。 答案： template void DeletePreNode (Node { Node //得到s的结点的前一个结点的前一个结点 while (p->next->next != s) p=p->next; //删除p->next指向的结点 Node p->next = s; delete q; } （6）已知一单链表中的数据元素含有三类字符(即:字 循环链表，使每个循环链表中只含同一类的字符，且利 用原表中的结点空间作为这三个表的结点空间(头结点可 另辟空间)。 （7）Josephus环问题：任给正整数n、k，按下述方法可 得排列1，2，……，n的一个置换：将数字1，2，……， n环形排列（如图2-36所示），按顺时针方向从1开始计 数，计满k时输出该位置上的数字（并从环中删去该数 字），然后从下一个数字开始继续计数，直到环中所有数 字均被输出为止。例如，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)%100 (front+1)%100 rear==front (rear+1)%100=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. 二叉树 （2）四个元素1、2、3、4依次进栈，出栈次序不可能出现（）情况。 A. 1 2 3 4 B. 4 1 3 2 C. 1 4 3 2 D. 4 3 2 1 （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. 队列 C. 数组 D. 线性表 （7）STL中的双端队列为（）。 A. 顺序容器 B. 容器适配器 C. 迭代器适配器 D. 泛函适配器 （8）STL中的（）允许用户为队列中的元素设置优先级。 A. 队列适配器 B. 双端队列 C. 优先级队列适配器 D. 栈适配器 （9）string类型不支持以（）的方式操作容器，因此不能使用front、back和pop_back 操作。 A. 线性表 B.队列 C. 栈 D. 串 3．算法设计 （1）设计一个算法判断算数表达式的圆括号是否正确配对。 （2）假定用带头结点的循环链表表示队列，并且只设置一个指针指向队尾元素，试设计该队列类，完成相应的入队、出队、置空队、求队长等操作接口。 （3）设计算法把一个十进制数转换为任意指定进制数。 （4）设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为w1，w2，……，w n。问能否从这n件物品中选择若干件放入此背包，使得放入的重量之和正好为S。如果存在一种符合上述要求的选择，则称此背包问题有解，否则此问题无解，试用递归和非递归两种方法设计解决此背包问题的算法。 背包问题分析： 背包问题是一个经典的NP问题，它既简单形象容易理解，又在某种程度上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例题。本题目是最简单的01背包问题，除此之外，还有许多由此衍生出来的很多复杂的背包问题。 本题中，最容易想到的就是假定背包中已放入了部分物品，现将第i件物品试着放入背包中，如果可以放进去，背包的重量在原来的基础上增加了w i；如果不可以放进去，说明加入后太重了，换下一件物品。如果所有的剩余物品都不能放入，说明以前放入的物品不合适，拿出上一次放入的物品，继续试剩余的物品。 递归解法： 设背包函数为knapsack(int s, int n)，参数 int s 为剩余重量，int n 为剩余物品数，返回值表示背包分配是否成功。 （1）如果s==0，表示分配成功，返回1； （2）如果s<0 或者n<0，表示太重，或者物品分配完毕，返回0； （3）执行knapsack( s – w i, n-1)，测试当前这件物品放入是否成功。 （3.1）如果成功，说明当前这件物品放入刚好最终分配成功。 （4）返回knapsack( s , n-1)，说明当前物品不合适，减小剩余物品数，继续测试。 测试代码： /*简单的背包问题递归解*/ #include"stdio.h" #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("%-4d",W[n]); /*输出*/ return 1; } return knapsack(s , n - 1); } int main() { if(knapsack(S , N))/*递归调用*/ printf("\nOK!\n"); else printf("Failed!"); 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"stdio.h" #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 printf("OK!\n"); break; } else if (value>S) break; } if (size==0) {printf("Finished!");exit(0);} 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++中存储三维数组A mnp ，则第一个元素为a 000，若按行优先存储，则a ijk 前面共有（___________）个元素；若按列优先存储，则a ijk 前面共有（___________）个元素。 答案：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。 ?????? ??? ? ? ?-00 15000001800000130001400003005000000009120 （2）对于如下稀疏矩阵，请写出对应的三元组顺序表，若采用顺序取，直接存的算法进行转置运算，引入辅助数组number[]和position[]，分别表示矩阵各列的非零元素个数和矩阵中各列第一个非零元素在转置矩阵中的位置，请写出数组中的各元素（所有数组起始元素下标为0）。 原矩阵 ?????? ? ? ?-00 051000003 0200 （3）对于上题中的稀疏矩阵，写出对应的三元组表和十字链表。 十字链表： 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的二叉树，至多有（___________）个结点。 答案：2k-1 （6）（7）有n个结点并且其高度为n的二叉树的数目是（___________）。 答案：2n-1 （8）设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为（___________），最小结点数为（___________）。 答案：2k+1-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 C. 6 D. 7 （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 D. h+1 （5）高度为5的完全二叉树至少有（）个结点。 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+n m (2) N = 1 + mn m 3.试分别画出具有3个结点的树和二叉树的所有不同形态。 答案：树： 二叉树： 4．试找出分别满足下面条件的所有二叉树： （1）前序序列和中序序列相同； 答案: 右斜树 （2）中序序列和后序序列相同； 答案：左斜树 （3）前序序列和后序序列相同。 答案：只有根结点的树 5．一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从0开始对全部结点进行编号，试问： （1）各层的结点个数是多少？ 答案：n层的结点个数为k n-1 （2）编号为i的结点的父结点（若存在）的编号是多少？ 答案：|(i-1)/k| (|·|表示取下整) （3）编号为i的结点的第m个孩子结点（若存在）的编号是多少？ 答案：k*i+m （4）编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？ 答案：i%k!=0 i+1 （5）叶子结点数n0和非叶子结点数n k之间满足的关系。 答案：n k*(k-1)=n0-1 6．若一棵二叉树的前序序列为abdgcefh，中序序列为dgbaechf，请画出该二叉树，并写出其后序序列。 答案：gdbehfca 第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 答案： （1）集合结构 数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。 （2）线性结构 数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。 （3）树结构 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■ 第一章绪习题一 1.有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时， 对每个关系画出相应的结构图），并指出它们分别属于何种结构。 ⑴ A=(K,R)其中 K={a1,a2,a3...,an} R={} ⑵ B=(K,R)其中 K={a,b,c,d,e,f,g,h} R={r} r={ 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 作业参考答案 一、（带头结点）多项式乘法C= A×B： void PoｌyAdd ( list &C,liｓｔR) ／／R为单个结 点 { p=C; while(（!p-＞ｎeｘt) &＆(p->nexｔ-＞eｘp>Ｒ->eｘp)) p=p－>ｎｅｘt； ｉf (（p->next) ｜｜(ｐ->neｘt->ｅｘp<Ｒ-＞eｘp)) {R－＞nｅxt=ｐ->ｎeｘｔ;p->neｘｔ=Ｒ;} ｅlse { ｐ-＞nｅxt－＞inf +=R->inｆ;delｅte R; if （！p－>neｘｔ-＞iｎｆ) { R=ｐ-＞nｅxt；p－>next=R->ｎext;deleｔe R; ｝ } } ｖoｉｄPｏlｙMul （lｉst A, lｉst B，lｉst &C ） ｛ C=new sｔｒuct nｏｄe; Ｃ-＞neｘt=ＮUＬL；q=B->next; Wｈｉｌe (q ） { p＝A->neｘｔ; whiｌｅ（p ) { ｒ= new struct node；r->ｅxｐ= p->ｅxp ＋ｑ－>exp； r-＞ｉnf ＝ｐ-＞inf* q－>iｎf; PolyAｄd(C，r）； p=p-＞next; ｝ q=q－>ｎext; ｝ } 二、梵塔的移动次数: 已知移动次数迭代公式为：M ( ｎ)= 2M (n－1 ) + 1 初值为: Ｍ( 0 ) ＝0 则：M （n）＝ 2 （2M （n-2 ) + 1) + 1 =4M( n-2 )+ 3 = 8Ｍ(n－3 )+ 7 =２i M ( n-i ) + 2i– 1 若n＝ｉ，则Ｍ（n-ｎ) ＝0,故：M ( n ) =2ｎM( ｎ-n）+2n–1 =2n– 1 所以,梵塔的移动次数为2ｎ– 1次。 三、简化的背包问题： ｖoid Pacｋ( int ｍ, int i, ｉnt t ）// 初始值为:１１t ｛ for (k=i; k<＝ｎ; k＋＋) { soｌutiｏｎ[m] = ｗeighｔ[k]; if( t == weigｈｔ[k]) ｛ for ( j=1; ｊ<=m；j+＋) cout<＜ｓolutｉon［j]；coｕt< 第1章绪论工程大数电习题答案册工程大数电习题答案 册 2.(1)×(2)×(3)√ 3.（1）A（2）C（3）C 5.计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 6.编写算法，求一元多项式p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法 （1）通过参数表中的参数显式传递 （2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i 1.什么是最小生成树？简述最小生成树的Prime算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想： 从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？ 答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。（1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。 3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。 n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值。 5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？ 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（） 和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的 关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若 为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关 系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数 组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中 的指针表示。 ⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不 能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 1-1什么是数据? 它与信息是什么关系? 【解答】 什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。 什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。 1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为：数据结构= { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容： ①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； ②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构； ③施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、 队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 【解答】 线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构 非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。 1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。 (2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。 (3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。 填空题(10 * 1 '= 10') 一、概念题 22当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 23当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 2.6. 带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 36循环队列的引入，目的是为了克服假溢出。 4.2. 长度为0的字符串称为空串。 4.5. 组成串的数据元素只能是字符。 4.8. 设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 7.2. 为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 5.7. 广义表的深度是广义表中括号的重数 7.8. 有向图G可拓扑排序的判别条件是有无回路。 7.9. 若要求一个稠密图的最小生成树，最好用Prim算法求解。 8.8. 直接定址法法构造的哈希函数肯定不会发生冲突。 9.2. 排序算法所花费的时间，通常用在数据的比较和交换两大操作。 1.1. 通常从正确性、可读性、健壮性、时空效率等几个方面评价算法的(包括程序)的质量。 1.2. 对于给定的n元素，可以构造出的逻辑结构有集合关系、线性关系树形关系、图状关系四种。 1.3. 存储结构主要有顺序存储、链式存储、索引存储、散列存储四种。 1.4. 抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不 变，都不影响其外部使用。 1.5. 一个算法具有五大特性：有穷性、确定性、可行性，有零个或多个输入、有一个或多个输入。 2.8. 在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句： s_>prior= p_>prior; s->next= p; p_>prior- next= s; p_>prior= s;。 2.9. 在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作 (如插入和删除)在各种情况下统一。 3.1. 队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 3.2 .栈是限定尽在表位进行插入或删除操作的线性表。 3.5. 在链式队列中，判定只有一个结点的条件是(Q->rear==Q->fro nt)&&(Q->rear!=NULL) 。 3.7. 已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x;] p_>next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 3.8. 循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt 和(fron t=-1 &&rear+ ^=MAXSIZE) 。 4.3. 串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 4.7. 字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 5.3. 所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀 疏矩阵。 5.4. —维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种?不同的存储 方式。 7.4. 在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第?i列非10元素的个数。 7.10. AOV网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 9.1. 按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序、交换排序、插入排序归并排序等4类。 9.3 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下 排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 9.4. 直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 9.6. 设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 4.9. 下列程序判断字符串s是否对称，对称则返回1,否则返回0;如？(abba”返回1, ? (”abab”)返回0. Int f (char*s) { Int i=0,j=0; 北邮算法与数据结构习题参考答案 作业参考答案 一、（带头结点）多项式乘法 C = A×B： void PolyAdd ( list &C, list R) // R 为单个结点 { p=C; while ((！p->next) && (p->next->exp>R->exp)) p=p->next; if ((p->next) || (p->next->exp 《数据结构简明教程》练习题及参考答案 练习题1 1. 单项选择题 （1）线性结构中数据元素之间是（）关系。 A.一对多 B.多对多 C.多对一 D.一对一 答：D （2）数据结构中与所使用的计算机无关的是数据的（）结构。 A.存储 B.物理 C.逻辑 D.物理和存储 答：C （3）算法分析的目的是（）。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 答：C （4）算法分析的两个主要方面是（）。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 答：A （5）计算机算法指的是（）。 A.计算方法 B. 排序方法 C.求解问题的有限运算序列 D.调度方法 答：C （6）计算机算法必须具备输入、输出和（）等5个特性。 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答：B 2. 填空题 （1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。 答：①逻辑结构②存储结构③运算 （2）数据结构按逻辑结构可分为两大类，它们分别是①和②。 答：①线性结构②非线性结构 （3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。 答：①数据元素 ②关系 （4）在线性结构中，第一个结点 ① 前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点 ② 后继结点，其余每个结点有且只有1个后继结点。 答：①没有 ②没有 （5）在树形结构中，树根结点没有 ① 结点，其余每个结点有且只有 ② 个前驱结点；叶子结点没有 ③ 结点，其余每个结点的后继结点数可以是 ④ 。 答：①前驱 ②1 ③后继 ④任意多个 （6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（ ）。 答：任意多个 （7）数据的存储结构主要有四种，它们分别是 ① 、 ② 、 ③ 和 ④ 存储结构。 答：①顺序 ②链式 ③索引 ④哈希 （8）一个算法的效率可分为 ① 效率和 ② 效率。 答：①时间 ②空间 3. 简答题 （1）数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。 （2）简述线性结构、树形结构和图形结构的不同点。 答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。 （3）设有采用二元组表示的数据逻辑结构S=(D,R)，其中D={a ,b ,…,i }，R={(a ,b ),(a ,c ),(c ,d ),(c ,f ),(f ,h ),(d ,e ),(f ,g ),(h ,i )}，问相对于关系R ，哪些结点是开始结点，哪些结点是终端结点？ 答：该逻辑结构为树形结构，其中a 结点没有前驱结点，称为根结点，b 、e 、g 、i 结点没有后继结点，是终端结点，也称为叶子结点。 （4）以下各函数是算法中语句的执行频度，n 为问题规模，给出对应的时间复杂度： T 1(n )=n log 2n -1000log 2n T 2(n )=3log 2n -1000log 2n T 3(n )=n 2 -1000log 2n T 4(n )=2n log 2n -1000log 2n 答：T 1(n )=O(n log 2n )，T 2(n )=O( )，T 3(n )=O(n 2 )，T 4(n )=O(n log 2n )。 （5）分析下面程序段中循环语句的执行次数。 int j=0,s=0,n=100; do { j=j+1; s=s+10*j; } while (j 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 绪论第1章 √(2)×(3)2.(1)×C ）C（3（1）A（2）3. 的语句频度5.计算下列程序中x=x+1for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 的语句频度为：【解答】x=x+1=n(n+1)(n+2)/6 ）+……+（1+2+……+n）T(n)=1+(1+2)+（1+2+3 并确定算法中每一),p(xx+ax+a+…….+ax的值6.编写算法，求一元多项式p(x)=a n20nn20n1规定算法中不能使用要求时间复杂度尽可能小，语句的执行次数和整个算法的时间复杂度，算法的输入和输出)。n,输出为P(x求幂函数。注意：本题中的输入为a(i=0,1,…n)、x和0in采用下列方法1）通过参数表中的参数显式传递（）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实（2 现输入输出。【解答】1）通过参数表中的参数显式传递（优点：当没有调用函数时，不占用存，调用结束后形参被释放，实参维持，函数通用 性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。 ）通过全局变量隐式传递（2 优点：减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数PolyValue() { int i,n; float x,a[],p; nn=”);printf(“\ scanf(“%f”,&n); nx=”);printf(“\ scanf(“%f”,&x); for(i=0;i O S TEST 1．Fill in the blanks with the proper words.( 10 cents) 1. Operating system is a program that acts as an intermediary between _____ and ______. 2.To prevent user programs from interfering with the proper operation of the system, the hardware has two modes: _________, __________. 3.___________ is the separation of user ______ from physical memory. User would be able to write programs for an extremely large __________ space, simplifying the programming task. 4.The file system consists of two distinct parts: _______, each storing related data and _______, which organizes and provides information about all the files in the system. 5.System call provide the interface between _____ and _____ . 6.________ provide an object-oriented way of implementing file systems, and it allows the same system call interface (the API) to be used for different types of file systems. 7. A process is a program in execution. A process needs certain resources, including ____, ______, files, and ______ to accomplish its task. 8.Disk-scheduling algorithms can improve _________, _________, and ________. 9.The primary distinction between long-term scheduler and short-term scheduler is _______. 10.The device drivers present a uniform device-access interface to ______ , much as system calls provide a standard interface between the application and the operating system. 2. Choose the best answer, and each blank has one answer. (23 cents) 1. Operating system is a kind of(1) , (2) is not the main problem it handles. (1). A. Application software; B. System software; C. Common software; D. Software package; (2). A. managing the bar-machine; B. designing, providing the interface between user program and hardware system; C. managing the information resource of the computer; D. the compiling of the high-level program-designing language. 2. The utilization of the memory can be improved by __(1)___. Its basic task is __(2)_ for each program; and each program can run safely and separately, main by __(3)____. (1), (3): A. memory-allocating B. memory-protecting《数据结构》课后习题答案
数据结构期末考试试题及答案
数据结构实用教程第二版答案_徐孝凯
严蔚敏版数据结构课后习题答案-完整版
北邮算法与数据结构习题参考标准答案
最全数据结构课后习题答案(耿国华版[12bb]
数据结构 期末考试复习题及答案
数据结构(第二版)课后习题答案(王红梅主编)
数据结构课后习题答案清华大学出版社殷人昆
(完整word版)数据结构课后习题及答案
北邮算法与数据结构习题参考答案
数据结构课程 课后习题答案
数据结构课后习题及答案
《数据结构》期末考试题及答案
最全数据结构课后习题答案耿国华版
北邮 计算机学院 数据结构 期末试题
相关主题
文本预览