数据结构作业及答案汇总.docx
- 文档编号:16026404
- 上传时间:2023-07-10
- 格式:DOCX
- 页数:26
- 大小:79.98KB
数据结构作业及答案汇总.docx
《数据结构作业及答案汇总.docx》由会员分享,可在线阅读,更多相关《数据结构作业及答案汇总.docx(26页珍藏版)》请在冰点文库上搜索。
数据结构作业及答案汇总
第一章绪论
一、选择题
1.数据结构是一门研究非数值计算的程序设计问题中计算机的 1 以及它们之间的 2 和运算等的学科。
1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像
2 A.结构 B.关系 C.运算 D.算法
2.数据结构被形式地定义为(K,R),其中K是 1 的有限集,R是K上的 2 有限集。
1 A.算法 B.数据元素 C.数据操作 D.逻辑结构
2 A.操作 B.映像 C.存储 D.关系
3.在数据结构中,从逻辑上可以把数据结构分成 。
A.动态结构和静态结构 B.紧凑结构和非紧凑结构
C.线性结构和非线性结构 D.内部结构和外部结构
4.线性结构的顺序存储结构是一种 1 的存储结构,线性表的链式存储结构是一种 2 的存储结构。
A.随机存取 B.顺序存取 C.索引存取 D.散列存取
5.算法分析的目的是 1 ,算法分析的两个主要方面其一是指 2 ,其二是指正确性和简单性。
1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进 D.分析算法的易懂性和文档性
2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系
C.可读性和文档性 D.数据复杂性和程序复杂性k
6.计算机算法指的是 1 ,它必须具备输入、输出和 2 等 5个特性。
1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法
2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性
C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性
7.线性表的逻辑顺序与存储顺序总是一致的,这种说法 。
A.正确 B.不正确
8线性表若采用链式存储结构时,要求内存中可用存储单元的地址 。
A.必须连续的B.部分地址必须连续的 C.一定是不续的 D连续不连续都可以
9.以下的叙述中,正确的是 。
A.线性表的存储结构优于链式存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出
10.每种数据结构都具备三个基本运算:
插入、删除和查找,这种说法 。
A.正确B.不正确
二、填空题1.数据逻辑结构包括三种类型 、 和 ,树形结构和图形结构合称为 。
2.在线性结构中,第一个结点 前驱结点,其余每个结点有且只有 个前驱结点;最后一个结点 后续结点,其余每个结点有且只有 个后续结点。
3.算法的五个重要特性是 、 、 、 、 。
4.下面程序段的时间复杂度是 。
for(i=0;i for(j=0;j A[i][j]=0; 5.下面程序段的时间复杂度是 。 i=s=0; while(s { i++;/*i=i+1*/ s+=i;/*s=s+i*/ } 6.下面程序段的时间复杂度是 。 s=0; for(i=0;i for(j=0;j s+=B[i][j]; sum=s; 7.下面程序段的时间复杂度是 。 i=1; while(i<=n) i=i*3; 第一章绪论(参考答案) 一、选择题: 1. A.B。 2. B.D。 3. C。 4. A. B。 (顺序存储结构的地址在内存中是连续的所以可以通过计算地址的相对变化而实现随机存取,而链式存储结构的存储地址不一定连续,只能通过结点的指针按次序顺序存取) 5. C. A。 6. C. B。 7. B。 8. D。 9. B。 10. B。 二、填空题: 1. 线性结构,树形结构,图形结构,非线性结构。 2. 没有,1,没有,1。 3. 有穷性,确定性,可行性,输入,输出。 4. O(m*n)。 5. O( )。 6. O(n2)。 7. O(log3n)。 5.O( )。 解: 设基本语句频度为N。 N=1,i=1,s=1;N=2,i=2,s=1+2;N=1,i=1,s=1;N=3,i=3,s=1+2+3;… 当频度为N时,i=N,s=1+2+3…+N。 则根据循环条件,s=1+2+3+…+N 所以,时间复杂度为 7. O(log3n)。 解: 设基本语句的频度为N。 (注意此题没有限制语句频度) N=1,i=3;N=2,i=9;N=3,i=27;… 当频度为N时,i=3N所以3N 所以时间复杂度T(n)=O(log3n) 第二章线性表 单项选择题 1.一个顺序表的第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是 。 A.110 B.108 C.100 D.120 2.一个栈的入栈序列是a、b、c、d、e,则栈的不可能输出序列是 。 A.edcba B.decba C.dceab D.abcde 3.若一个栈的入栈序列是1、2、3、…、n,其输出序列为p1、p2、p3、…、pn,若p1=n,则pi为 。 A.i B.n=iC.n-i+1 D.不确定 4.栈结构通常采用的两种存储结构是 。 A.顺序存储结构和链表存储结构 B.散列方式和索引方式 C.链表存储结构和数组 D.线性存储结构和非线性存储结构 5.判断一个栈ST(最多元素为m)为空的条件是 。 A.ST->top! =0 B.ST->top==NULLC.ST->top! =mD.ST->top==m 6.判断一个栈ST(最多元素为m)为满栈的条件是 。 A.ST->top! =0 B.ST->top==0C.ST->top! =m-1D.ST->top==m 7.栈的特点是 1 ,队列的特点是 2 。 A.先进先出 B.先进后出 8.一个队列的入队序列是1、2、3、4,则队列输出序列是 。 A.4、3、2、1 B.1、2、3、4 C.1、4、3、2D.3、2、4、1 9.判断一个队列QU(最多元素为m)为空的条件是 。 A.QU->rear-QU->front==m B.QU->rear-QU->front-1==m C.QU->front==QU->rearD.QU->front-QU->rear+1 10.判断一个队列QU(最多元素为m)为满队列的条件是 。 A.QU->rear-QU->front==m B.QU->rear-QU->front-1==m C.QU->front==QU->rearD.QU->front-QU->rear+1 11.判断一个循环队列QU(最多元素为m)为空的条件是 。 A.QU->front==QU->rear B.QU->front! =QU->rear C.QU->front==(QU->rear+1)%mD.QU->front! =(QU->rear+1)%m 12.判断一个循环队列QU(最多元素为m)为满队列的条件是 。 A.QU->front==QU->rear B.QU->front! =QU->rear C.QU->front==(QU->rear+1)%mD.QU->front! =(QU->rear+1)%m 13循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear,则当前队列中的元素个数是 。 A.(rear-front+m)%mB.rear-front+1 C.rear-front-1 D.rear-front 14.栈和队列的共同点是 。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入、删除元素D.没有共同点 填空题 1.线性表、栈和队列都是 结构,可以在线性表的 位置插入和删除元素;对于栈只能在 插入和删除元素;对于队列只能在 插入元素和 删除元素。 2.在一个长度为n的线性表的第i个元素(1≤i≤n)之前插入一个元素时,需向后移动 个元素。 3.在一个长度为n的向量中的删除第i个元素(1≤i≤n)时,需要向前移动 个元素。 4.若栈顶指针指向栈顶的空位,向栈中压入元素的操作是 。 5.若栈顶指针指向栈顶元素,则对栈进行退栈时的操作是 。 6.在一个循环队列中,队首指针指向队首元素的 。 7.从循环队列中删除一个元素时,其队头指针 。 8.在具有n个单元的循环队列中,队满时共有 个元素的。 9.一个栈的输入序列是12345,则栈的输出序列43512是 。 (填写“可能”或“不可能”) 10.一个栈的输入序列是12345,则栈的输出序列12345是 。 (填写“可能”或“不可能”) 第二章线性表(参考答案) 选择题: 1. B。 2. C。 3. C。 4. A。 5. B。 6. D。 7. B,A。 8. B。 9. C。 10. A。 11. A。 12. C。 13. A。 14. C。 (2. C。 堆栈讲究先进后出,后进先出选项1是abcde先入栈,然后依次出栈,正好是edcba 选项2是abcd先依次入栈,然后d出栈,e再入栈,e出栈。 选项c是错误的,不可能a先出栈。 选项4是a入栈,然后a出栈;b再入栈,b出栈……依此类推。 所以选c。 ) (13. A。 因为rear有可能会转一圈到front的后面,所以需要加一下m) 填空题: 1. 线性,任何,栈顶,队尾,队首。 2. n-i+1。 3. n-i。 4. 先移动栈顶指针,后存入元素。 5. 先取出元素,后移动栈顶指针。 6. 前一个位置。 7. 要加1 8. n-1。 9. 不可能的。 10. 可能的。 第三章链表 单项选择题 1.不带头结点的单链表head为空的判定条件是 。 A.head==NULL B.head->next==NULL C.head->next==head D.head! =NULL 2.带头结点的单链表head为空的判定条件是 。 A.head==NULL B.head->next==NULL C.head->next==head D.head! =NULL 3.非空的循环单链表head的尾结点(由指针p所指向)满足 。 A.p->next==NULL B.p==NULL C.p->next==head D.p==head 4.在循环双链表的p所指结点之后插入s所指结点的操作是 。 A.p->right=s;s->left=p;p->right->left=s;s->right=p->right; B.p->right=s;p->right->left=s;s->left=p;s->right=p->right; C.s->left=p;s->right=p->right;p->right=s;p->right->left=s; D.s->left=p;s->right=p->right;p->right->left=s;p->right=s; 5.在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入s结点, 则执行 。 A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C.q->next=s;s->next=p; D.p->next=s;s->next=q; 6.在一个单链表中,已知p所指结点不是最后结点,在p之后插入s所指结点,则执行 。 A.s->next=p;p->next=s; B.s->next=p->next;p->next=s; C.s->next=p->next;p=s; D.p->next=s;s->next=p; 7.在一个单链表中,若删除p所指结点的后续结点,则执行 。 A.p->next=p->next->next; B.p=p->next;p->next=p->next->next; C.p->next=p->next; D.p=p->next->next; 8.从一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较 个结点。 A.n B.n/2C.(n-1)/2D.(n+1)/2 9.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 。 A.O (1) B.O(n)C.O(n2)D.O(nlog2n) 10.给定有n个元素的向量,建立一个有序单链表的时间复杂度是 。 A.O (1) B.O(n)C.O(n2)D.O(nlog2n) 11.向一个栈顶指针为HS的链栈中插入s所指结点,则执行 。 A.HS->next=s; B.s->next=HS->next;HS->next=s; C.s->next=HS;HS=s; D.s->next=HS;HS=HS->next; 12.从一个栈顶指针为HS的链栈中删除一个结点,用x保存被删除结点的值,则执行 。 A.x=HS;HS=HS->next;B.x=HS->data; C.HS=HS->next;x=HS->data;D.x=HS->data;HS=HS->next; 13.在一个链队中,假设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; 14.在一个链队中,假设f和r分别为队首和队尾指针,删除一个结点,则执行 。 A.r=f->next; B.r=r->next; C.f=f->next; D.f=r->next; 填空题 1.单链表是 的链接存储表示。 2.在双链表中,每个结点有两个指针域,一个指向 ,另一个指向 。 3.在一个单链表中,p所指结点之前插入s所指向结点,可执行如下操作: (1)s->next=p->next; (2)p->next=s; (3)t=p->data; (4)p->data= ; (5)s->data= ; 4.在一单链表中,删除p所指结点时,应执行以下操作: (1)q=p->next; (2)p->data=p->next->data; (3)p->next=; (4)free(q); 5.带头结点(head)的单链表为空的条件是 。 6.在一个单链表中,p所指结点之后插入s所指向结点,应执行s->next= 和 p->next=的操作。 7.非空的单循环链表head的尾结点(由p所指向),满足 。 8.在栈顶指针为HS的链栈中,判定栈空的条件是 。 9.在带头结点的链队列HQ中,判定只有一个头结点的条件是 。 编程题 1.已知有一栈顶指针为HS的链栈,请编写一计算该链栈中结点个数的函数。 2.已知有一带头结点的链队列HQ中,请编写求该链队列中结点个数的函数。 第三章链表(参考答案) 选择题: 1. A。 2. B。 3. C。 4. D。 5. C。 6. B。 7. A。 8. D。 9. B。 10. C。 11. C。 12. D。 13. B。 14. C。 (8. D。 说明: 可能查找的次数从1到n次不等,这样的话,总的查找次数是(n+1)n/2,除以n为平均查找次数,即为D.(n+1)/2 10. C。 说明: 这本质上是一个排序问题,要写双重循环来排序,根据已经学习过的程序知识,比如起泡法排序等,其时间复杂度是C.O(n2)。 11. C。 说明: 注意这是一个栈顶指针,而非栈顶结点,所以选C不选B。 填空题: 1. 线性表。 2. 前驱结点,后续结点。 3. s->data,t。 4. p->next->next或q->next。 5. head->next==NULL。 6. p->next,s。 7. p->next==head。 8. HS==NULL。 9. HQ->front==HQ->rear。 (3. s->data,t。 这道题实质上是在p后面插入了s结点,然后将p和s结点中的数据作了交换,结果就如同是“真正”在p前面插入了一个s结点一样。 其中的t是一个数据域变量。 4. p->next->next或q->next。 其实是把被删结点之后的结点做了前移。 ) 编程题 1. intcount(node*HS) {node*p; intn=0; p=HS; while(p! =NULL) {n++; p=p->next; } return(n); } 2.intcount(strructlinkqueue*HQ) {strructlinkqueue*p; intn; p=HQ->first; if(p==NULL)return(0); n=1; while(p! =HQ->rear) {n++; p=p->next; } return(n); } 第四章串 单项选择题 1.空串与空格串是相同的,这种说法 。 A.正确 B.不正确 2.串是一种特殊的线性表,其特殊性体现在 。 A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个字符 3.设两个字符串p和q,求q在p中首次出现的位置的运算称作 。 A.连接 B.模式匹配 C.求子串 D.求串长 4.设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x与y串的连接串,函数subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串,函数len(s)返回串s的长度,则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是 。 A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF 填空题 1.串的两种最基本的存储方式是 。 2.两个串相等的充分必要条件是 。 3.空串是 ,其长度等于 。 4.空格串是 ,其长度等于 。 5.设s=“IAMATEACHER”,其长度是 。 第四章串(参考答案) 单项选择题: 1. B。 2. B。 3. B。 4. D。 填空题: 1. 顺序存储方式和链接存储方式。 2. 两个串的长度相等且对应位置的字符相同。 3. 零个字符的串,0。 4. 由一个或多个空格字符组成的串,其包含的空格个数。 5. 14。 第六章树形结构 单项选择题 1.如图所示的4棵二叉树中, 不是完全二叉树。 2.在线索化二叉树中,t所指结点没有左子树的充要条件是 。 A.t->left==NULL B.t->ltag==1C.t->ltag==1且t->left==NULLD.以上都不对 3.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法 。 A.正确 B.错误 4.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法 。 A.正确 B.错误 5.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法 。 A.正确 B.错误 6.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少 为 。 A.2h B.2h-1 C.2h+1 D.h+1 7.如图所示二叉树的中序遍历序列是 。 A.abcdgef B.dfebagc C.dbaefcg D.defbagc 8.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,前序遍历序列是 。 A.acbed B.decab C.deabc D.cedba 9.如果T2是由树T转换而来的二叉树,那么T中结点的前序就是T2中结点的 。 A.前序B.中序 C.后序D.层次序 10.如果T2是由树T转换而来的二叉树,那么T中结点的后序就是T2中结点的 。 A.前序B.中序 C.后序D.层次序 11.某二叉树的先序遍历结点访问顺序是abdgcefh,中序遍历结点访问顺序是dgbaechf,则其后序遍历结点访问顺序是 。 A.bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca 12.二叉树为二叉排序树的充分必要条件是任一结点的值均大于其左孩子的值、小于其右孩子的值,这种说法 。 A.正确 B.错误 13.按照二叉树的定义,具有3个结点的二叉树有 种。 A.3B.4 C.5D.6 14.如图所示二叉树的中序遍历序列是 。 A.abdgcefh B.dgbaechf C.gdbehfca D.abcdefgh 15.树的基本遍历策略可分为先根遍历和后根遍历;二叉树基本遍历策略可分为先序遍历、 中序遍历和后序遍历。 这时,我们把由树转化得到的二叉树叫做这棵树对应的二叉树。 结论 是正确的。 A.树的先根遍历序列与二叉树的先序遍历序列相同 B.树的后根遍历序列与二叉树的后序遍历序列相同 C.树的先根遍历序列与二叉树的中序遍历序列相同 D.以上都不对 16.深度为5的二叉树至多有 个结点。 A.16 B.32 C.31 D.10 17.在一非空二叉树的中序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 作业 答案 汇总