1、算法与数据结构习题及参考答案算法与数据结构习题及参考答案2单项选择题 1. 文件的基本组织方式有：（）。 A、顺序组织、索引组织、散列组织和链接方式 B、磁盘组织、磁带组织 C、数据库组织 D、关键字与非关键字 答案：A 2. 为了区别循环队列中队满与队空的条件，采用的方法是：（）。 A、不需要特别的方法 B、牺牲一个存贮空间 C、把队头永远放到队尾的前端 D、每次出队后，移动数据 答案：B 3. 通过链表存贮树时，如果给定树中结点的个数，则链域浪费的空间随树的度增加而：（）。 A、增加 B、减少 C、不变 D、无规律 答案：A 4. 两字符串相等的条件是（）。A、两个串的长度相等 B、两个串
2、包含的字符相等 C、两个串的长度相等，并且两个串包含的字符相同 D、两个串的长度相等，并且对应位置上的字符相同 答案：D 5. 在下列有关图的存储结构中说法错误的是（）。A、用邻接矩阵存储一个图时所占用的存储空间大小与图中的顶点个数有关，而与图的边数无关 B、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用 C、邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方） D、存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了答案：B6. 顺序搜索法适合于存储结构为（）的线性表。A、散列存储 B、顺序存储或链接存储
3、C、压缩存储 D、索引存储答案：B多项选择题 1. 下述陈述中哪一项是正确的(): A、文件是由记录组成的集合 B、记录是文件存取的基本单位 C、文件是由数据项组成的 D、数据项有时也被称之为字段 答案：BD 2. 下列排序算法中哪些是不稳定的(): A、昌泡排序 B、选择排序 C、快速排序 D、堆排序 答案：BCD 3. 稀疏矩阵的存贮结构要满足哪些条件？() A、每个非零元素存贮其行号、列号以及值 B、存贮矩阵的行数和列数 C、所有的非零元素以行优先的排列规则存贮 D、只存贮上三角的元素 E、只存贮下三角的元素 答案：ABC 4. 图的邻接矩阵存贮结构包括(): A、表示图中顶点间相邻关系
4、的矩阵 B、对称矩阵 C、表示图中顶点元素的数组 D、表示入度的数组 E、表示出度的数组 答案：AC 5. 假设有三角矩阵ann，对角线及对角线以上的元素非零，对角线以下的元素为0。如果采用压缩存贮，即只存贮矩阵中的上三角元素和既存贮上三角元素又存贮0两种情况下，所需要的存贮空间的分别容量为()和()。 A、n*(n+1)/2, n*(n+1)/2 + 1 B、n*(n+1)/2, n*n C、(n+1)n/2, (n+1)n/2 + 1 D、n(n-1)/2, n*(n-1)/2 + 1 答案：AC 判断题 1. 拓扑排序是图的另一种遍历。 答案：正确 2. 树是一种特殊的图。 答案：正确
5、3. 数据结构中只研究了二叉树，对一般树没有给出解决问题的算法。 答案：错误 4. 在单向链表中，在X指向的结点后插入结点，对应的方法与X是否是头指针无关。 答案：错误 5. 有人采用Haffman树进行编码后，由于每个符号的代码长度不等，当接收方收到编码后的内容后，不能转换为原来的正文。该说法是否正确？ 答案：正确 6. 一棵度为2的树是一棵二叉树。 答案：错误 7. 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。答案：错误8. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。答案：正确9. 两个栈共享一片连续内存空间时，为提高内存利用率，减少
6、溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。答案：正确10. 最优二叉搜索树一定是平衡的二叉搜索树。答案：错误填空题1某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100，则下标为11（第12个）的元素的存储地址为 。答案：1442. 在函数中对引用型形式参数的修改就是对相应 的修改，而对 型形式参数的修改只局限在该函数的内部，不会反映到对应的实际参数上。答案：实际参数的值；传值3. 将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储 个矩阵元素。答案：n(n+1)/2简答题1. 请回答关于链接存储的优缺点。答案：优点：1.插入和删除
7、比较灵活，不需要大量移动结点。 2.动态分配空间比较灵活，不需要预先申请最大的连续空间。 2.检索必须沿链进行，不能随机存取。2. 请写一个递归算法来计算并返回链表的长度，并在程序中做出相应的文字说明。答案： int length(LinkList llist) /*计算单链表list的长度*/ If(llist = = NULL) return(); return1+length(llist-link); 3. 给出栈的最常用的5种操作，并说明它们的功能。答案：(1) void push（ST,x） 将元素x插入栈ST的顶端(2) void pop（ST） 从栈ST顶端删除一个元素(3) D
8、ataType top（ST） 读栈ST顶端的元素(4) int isEmpty（ST） 判断栈ST是否为空栈(5) pStack creatEmptyStack() 创建一个空栈第2章 线性表一、判断题1 线性关系的逻辑结构与存储结构总是一致的。解：错。单链表的逻辑结构与存储结构有可能是不一致的，有可能两个相邻结点的存储地址并不是相邻的。2 每种数据结构都包括插入、删除和查找这三种基本运算。解：错。散列结构无插入与删除运算；栈没有查找，查找须配有另一个栈。3 线性表中的每个结点最多只有一个前驱和一个后继。解：对。线性表的定义为：表中任意一个元素至多有一个前驱，至多有一后继。4 线性的数据结构
9、既可以顺序存储，也可以链接存储；非线性的数据结构则只能链接存储。解：错。对于非线性的数据结构，若对它的数据规定某种次序之后，也可以顺序存储。如，树的前、中、后序遍历之后的存储，一个前驱可能对应多个后继。5 顺序存储方式只能用于存储线性结构。解：错。非线性结构也可采用顺序存储。6 多维数组是向量的推广。解：对。多维向量的存储方式实际上与一维向量是一致的。7 设串s的长度为n，则s的子串个数最多为n (n+1)/2。解：错。s的长度为n，故它含有n个字符，它的子串应包括：1个字符的子串，2个字符的子串，n个字符的子串；这些子串的个数分别为8 单链表从任何一个结点出发，都能访问到所有结点。解：错。单
10、链表仅能从头结点出发去访问所有结点，不能访问前驱。9 线性表的长度是线性表所占用的存储空间的大小。解：错。线性表所占用的存储空间大小为：每个结点所占用的存储字节数乘以线性表的长度。10 双循环链表中，任意一结点的后继指针均指向其逻辑后继。解：错。任意结点的后继结点包含有两个指针llink和rlink，只有rlink指向其逻辑后继，而llink指向其逻辑前驱。11 数据结构、数据元素、数据项在计算机中的映象(或表示)分别称为存储结构、结点、数据域。解：对。12 线性表的顺序存储结构优于链式存储结构。解：错。各有优缺点。顺序存储结构的优点是：（1）存储效率高。（2）可随机访问任意结点，存取速度快。
11、顺序存储结构的缺点是：（1）插入与删除操作麻烦。（2）顺序表的长度扩充麻烦。链式存储结构的优点是：（1）插入与删除方便。（2）顺序表的长度可任意（动态分配内存）。链式存储结构的缺点是：（1）存储效率低。（2）对结点的访问不方便。二、选择题1 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为 C ，元素的移动次数为 F ( 0 i n ) 。(A)O(0) (B)O(1) (C)O(n) (D)O(n2)(E)n-i+1 (F)n-i (G)i (H)i -1 解：选C与E。因为，需要第i个位置至第n个位置的n-i+1个元素向后逐一移动，因此，共做n-i+1次
12、赋值运算，故T(n)=n-i+1，即T(n)=O(n)。2 在长度为n的顺序存储的线性表中，删除第i个元素(0 i n-1)时，需要从前向后依次前移 C 个元素。(A)n-i (B)n-i+1 (C)n-i-1 (D)i解：选C。因为前移元素的个数为n-i。3 从解决问题的需要出发，为实现必要的功能所建立的数据结构，称为 B 。(A)物理结构 (B)逻辑结构 (C)数据类型 (D)数据对象解：选B。4 若长度为n的线性表采用顺序存储结构，在其第i (0 i n )个位置插入一个新元素的平均移动元素移动次数为 C ，在其第i (0 i n-1 )个位置删除一个元素的平均移动元素移动次数为 D 。
13、(A)n (B)(n+1)/2 (C)n/2 (D)(n-1)/2 解：选C。因为，在第0个位置插入新元素应移动n个元素，而在第1个位置插入新元素应移动n-1个元素，一般地，在第i (0 i n )个位置插入一个新元素应移动n-i个元素，而在某个位置上插入新元素的概率为1/（n+1），故平均移动的次数为n/(n+1)+(n-1)/(n+1)+(n-i)/(n+1)+1/(n+1)+0/(n+1)=n/2选D。因为，在第0个位置删除一个元素应移动n-1个元素，而在第1个位置删除元素应移动n-2个元素，一般地，在第i (0 i n-1 )个位置删除一个元素的应移动n-i-1个元素，而在某个位置上删
14、除元素的概率为1/n，故平均移动的次数为(n-1)/n+(n-2)/n+(n-i-1)/n+1/n+0/n=(n-1)/25 若长度为n的无序线性表采用顺序存储结构，在其中查找某个元素的平均比较的次数为 D 。(A)n (B)(n-1)/2 (C)n/2 (D)(n+1)/2解：选D。n个元素的排列方式有n!种，而某个指定元素排在第i个位置的种数为(n-1)!，故某个指定元素恰好排在第i个位置的概率为(n-1)!/n!=1/n。这表明，待查找的元素恰好排在第1个位置、第2个位置、和第n个位置的概率均为1/n。若待查找的元素排在第i个位置，那么查找的次数为i次（1 i n），故平均查找次数为1/
15、n+2/n+i/n+n/n=(n+1)/26 对于只在首、尾两端进行插入操作的线性表，宜采用的存储结构为 。(A)顺序表 (B)带头指针的单链表(C)带尾指针的单循环链表 (D)单链表解：选C。7 在一个单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行 。(A)q-link = p-link；p-link = q； (B)p-link = q-link；q = p；(C)q-link = p-link；p = q； (D)p-link = q-link；q-link = p；解：选D。8 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行 。(A)HL =
16、 p; p-next = HL; (B)p-link = HL; HL = p;(C)p-link = HL; p = HL; (D)p-link = HL-link; HL-link = p; 解：若单链表不带头结点，则应选B。若单链表带头结点，则应选D。9 在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行 。(A)p=q- link ; p-link = q-link; delete p;(B)p = q-link ; q-link = p; delete p;(C)p = q-link ; q-link = p-link; delete p;(D)q-link = q-l
17、ink-link; q-link = q;解：选C。若选D，则链表中没有了q的后继结点，但未删除。仅C选项可使q的后继结点被删除，并按原有结点顺序重新拉链。10 设p为有头结点双向循环链表中某结点的指针，lLink为左链指针，rLink为右链指针，则下述表达式中， 不恒为真。(A)p-rLink-lLink = p (B)p-rLink-lLink=p-lLink-rLink(C)p-lLink-rLink=p (D)p-rLink-rLink=p-lLink-lLink解：选D。因为p-rLink-lLink = p= p-lLink-rLink，故只有D不一定为真。11 若某链表最常用的操
18、作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用 存储方式最节省时间。(A)单链表 (B)双向链表 (C)带头结点的双循环链表 (D)单循环链表解：选C。12 链表不具有的特点是 。(A)可随机访问任一元素 (B)插入删除不需要移动元素(C)不必事先估计存储空间 (D)所需空间与线性表长度成正比解：选A。13 线性表采用链式存储时，其地址 。(A)连续的 (B)部分连续的(C)一定是不连续的 (D)连续与否均可解：选D。14 设有一88下三角矩阵A88，采用按行压缩存储的方式存放在一维数组B 中，则数组B 的容量至少需要 B 个元素空间。(A)32 (B)36 (C)16 (D)6
19、4解：选B。矩阵的第1行有8个非零元素，第2行有7个非零元素，第8行有1个非零元素，故需要存储的非零元素的个数为8+7+6+5+4+3+2+1=8*(1+8)/2=36三、填空题1 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。解：在表头（即第0个位置）插入元素，需移动的元素个数为n，然后再做1次赋值操作，故T(n)=n+1=O(n)。在表尾插入元素无需移动表中已有元素，只需1次赋值操作，故T(n)=1=O(1)。2 在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为 ，若假定p为一个数组a中的下标，则其后继结点的下
20、标为 。解：应填入p-link，p+13 在单循环链表中，最后一个结点的指针指向 结点。解：表头结点。4 在双向链表中每个结点包含有两个指针域，一个指向其 结点，另一个指向 其 结点。解：应填入前驱，后继。5 在双向循环链表中表头结点的左指针域指向 结点，最后一个结点的右指针域指向 结点。解：应填入表尾，表头。6 在以HL为表头指针的带附加表头结点的单链表和单循环链表中，链表为空的条件分别为 和 。解：HL-link=NULL , HL-link=HL7 在双循环链表L中，指针p所指结点为尾结点的条件为 。解：p!=first & p=first-link8 在单链表中，如果要使指针p指向它所
21、指结点的后继结点，其语句是 。解：p =p-link9 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的 、 和 三项。解：为了节省对矩阵的存储空间，稀疏矩阵采用仅存储非零元素的行下标、列下列与非零元素值的方式存储。10 二维数组A45按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A34的存储地址为 。如果其余条件不变，但是数组的存放方式变为列序优先，则元素A34的存储地址变为 。解：行优先方式存储：第0行、第1行、第2行的5个元素依次占据3*5*2=30个存储单元。而第3行的前4个元素占据4*2=8个存储单元，故A34的存储地址为
22、120+30+8=158列优先方式存储：第0列、第1列、第2列、第3列的4个元素依次占据4*4*2=32个存储单元。而第4列的前3个元素占据3*2=6个存储单元，故A34的存储地址为120+32+6=158四、算法设计1 编写算法将以数组表示方式的顺序表原地逆置。解：#includeusing namespace std;#define N 10void Display(int a,int n) for(int i=0;in;i+) coutait; coutendl;/逆置函数1void Invert1(int a,int n) int temp,i,j; for(i=0,j=n-1;ij;
23、i+,j-) temp=ai;ai=aj;aj=temp;/逆置函数2void Invert2(int a,int n) int temp,i; for(i=0;in/2;i+) temp=ai;ai=an-1-i;an-1-i=temp;/主函数void main() int i,aN=0,1,2,3,4,5,6,7,8,9; Display(a,N); Invert1(a,N);Display(a,N); Invert2(a,N);Display(a,N);2 对于带附加头结点的单链表，给出下列算法的代码。(1) 假设单链表中结点的数据域中数据依升序排列，将名为newNode，数据域数据为
24、x的结点插入到该单链表中。(2) 从无序的单链表中查找出所有元素的最大值，该值由函数返回；若单链表为空，则显示出错信息并停止运行。(3) 统计出单链表中结点的值等于给定值x的结点数。解:#includeusing namespace std;/定义结点struct Node int data; struct Node *next;/插入函数void Insert(Node *&head,int x) Node *p,*q,*r,*newnode; newnode=new Node;/创建新结点 newnode-data=x; newnode-next=NULL; if(head-next=NU
25、LL)/如果链表空 head-next=newnode;/头指针指向新结点 else/如果链表非空 /获取链尾指针 p=head; while(p-next!=NULL) p=p-next; r=p; /将新结点插入链表适当位置 if(newnode-datadata)/如果新结点数据小于头结点数据 newnode-next=head; head=newnode;/新结点插入链头 else if(newnode-data=r-data)/如果新结点数据大于或等于链尾结点数据 r-next=newnode;/新结点插入链尾 else /新结点插入链表中间 p=head; while(newnod
26、e-data=p-data) q=p; p=p-next; newnode-next=q-next; q-next=newnode; /求最大值函数void Max(Node *&head,int &maxValue) Node *p=head-next; if(p=NULL)/空表 cout链表为空，退出!data; while(p-next!=NULL) p=p-next; if(p-datamaxValue) maxValue=p-data; /计算值为x的结点个数函数void Count(Node *&head,int x,int &countNum) countNum=0; Node
27、 *p=head-next; if(p=NULL)/空表 cout链表为空，退出!data=x) countNum+; p=p-next; while(p!=NULL);/输出函数void Display(Node *head) Node *p=head-next; if(p=NULL) cout链表空，退出!endl;return; while(p!=NULL) coutdata; p=p-next; coutNULLnext=NULL;/创建带附加头结点的局部指针 int x,maxValue,countNum; int n=5; cout输入n个数,创建升序链表endl; for(int
28、 i=1;ix; Insert(head,x);/调用插入法创建升序链表 Display(head);/调入输出函数 Max(head,maxValue);/求结点值最大者 cout最大值x=xendl; coutx; Count(head,x,countNum);/调用计算结点值为x的结点个数 cout值为x的结点个数为countNumendl;五、阅读算法并描述其功能1 int fun1(int &x) int i=0; while(i=0 & i=last) last-; for(int j=i;j=last;j+) dataj=dataj+1; return 1; return 0; 解：该函数的功能是，如果在全局数组data0last中找到值为x的元素，将它删除并返回1；否则返回0。2 int fun2(
