《严蔚敏数据结构各章习题及答案》由会员分享，可在线阅读，更多相关《严蔚敏数据结构各章习题及答案（68页珍藏版）》请在金锄头文库上搜索。
1、数据结构习题及解答第1章 概述习题1一、单项选择题1. 数据结构是指（1. A ）。A.数据元素的组织形式B.数据类型C.数据存储结构 D.数据定义2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。A.存储结构B.逻辑结构 C.链式存储结构D.顺序存储结构3. 树形结构是数据元素之间存在一种（3. D ）。A.一对一关系B.多对多关系 C.多对一关系D.一对多关系4. 设语句x+的时间是单位时间，则以下语句的时间复杂度为（4. B）。for(i=1; i=n; i+)for(j=i; j=n; j+)x+;A.O(1)B.O()C.O(n)D.O()7. 数据
2、在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ 7. B）。A.低 B.高 C.相同D.不好说8. 数据结构作为一门独立的课程出现是在（ 8. D）年。A.1946B.1953 C.1964 D.19689. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（9. B ）。A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10. 计算机内部数据处理的基本单位是（10. B ）。A.数据 B.数据元素C.数据项D.数据库二、填空题 1. 数据结构按逻辑结构可分为两大类，分别是_和_。1. 线性结构，非线性结构2. 数据的逻辑结构有四种基本形态，分
3、别是_、_、_和_。2. 集合，线性，树，图3. 线性结构反映结点间的逻辑关系是_的，非线性结构反映结点间的逻辑关系是_的。3. 一对一，一对多或多对多4. 一个算法的效率可分为_效率和_效率。4. 时间，空间5. 在树型结构中，树根结点没有_结点，其余每个结点的有且只有_个前趋驱结点；叶子结点没有_结点；其余每个结点的后续结点可以_。5. 前趋，一，后继，多6. 在图型结构中，每个结点的前趋结点数和后续结点数可以_。6. 有多个7. 线性结构中元素之间存在_关系；树型结构中元素之间存在_关系；图型结构中元素之间存在_关系。7. 一对一，一对多，多对多8. 下面程序段的时间复杂度是_。8. O
4、()for(i=0;in;i+)for(j=0;jn;j+)Aij=0;9. 下面程序段的时间复杂度是_。9. O()i=s=0;while(sn) i+; s+=i;10. 下面程序段的时间复杂度是_。10. O()s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=Bij;sum=s;11. 下面程序段的时间复杂度是_。11. O(logn)i=1;while(i=n)i=i*3;12. 衡量算法正确性的标准通常是_。12. 程序对于精心设计的典型合法数据输入能得出符合要求的结果。13. 算法时间复杂度的分析通常有两种方法，即_和_的方法，通常我们对算法求时间复杂度时，采
5、用后一种方法。13. 事后统计，事前估计三、求下列程序段的时间复杂度。1. x=0;for(i=1;in;i+)for(j=i+1;j=n;j+)x+;1. O() 2. x=0;for(i=1;in;i+)for(j=1;j=n-i;j+) x+;2. O()3. int i,j,k;for(i=0;in;i+)for(j=0;j=n;j+) cij=0;for(k=0;k=0)&Ai!=k)j-;return (i); 4. O(n)5. fact(n) if(n=1) return (1); else return (n*fact(n-1);5. O(n)第2章 线性表习题2一、单项选择
6、题 1. 线性表是_。1A A一个有限序列，可以为空B一个有限序列，不可以为空C一个无限序列，可以为空D一个无限序列，不可以为空2. 在一个长度为n的顺序表中删除第i个元素(0=inext=s; s-prior=p; p-next-prior=s; s-next=p-next;B s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;C p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;D s-prior=p; s-next=p-next; p-next-prior=s; p-next=s; 6
7、. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为_。6A Ap-next=p-next-next;Bp=p-next;Cp=p-next-next; Dp-next=p; 7. 在一个长度为n的顺序表中向第i个元素(0 inext=p-next; p-next=sBq-next=s; s-next=pCp-next=s-next; s-next=pDp-next=s; s-next=q9. 以下关于线性表的说法不正确的是_。9C A线性表中的数据元素可以是数字、字符、记录等不同类型。B线性表中包含的数据元素个数不是任意的。C线性表中的每个结点都有且只有一个直
8、接前趋和直接后继。D存在这样的线性表：表中各结点都没有直接前趋和直接后继。10. 线性表的顺序存储结构是一种_的存储结构。 10A A随机存取B顺序存取C索引存取D散列存取11. 在顺序表中，只要知道_，就可在相同时间内求出任一结点的存储地址。11D A基地址B结点大小 C向量大小 D基地址和结点大小12. 在等概率情况下，顺序表的插入操作要移动_结点。 12B A全部 B一半 C三分之一 D四分之一13. 在_运算中，使用顺序表比链表好。 13C A插入 B删除 C根据序号查找 D根据元素值查找14. 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_。 14B A
9、O(1) BO(n) CO(n2) DO(log2n)15. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列_。15C AA, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A 16. 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为_。16C Atop不变 Btop=0 Ctop- Dtop+17. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行_。17B Ahs-next=s; Bs-next=hs; hs=s;Cs-next
10、=hs-next;hs-next=s; Ds-next=hs; hs=hs-next; 18. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为_。18D Arearn= = front B（front+l）n= = rearCrearn -1= = front D(rear+l)n= = front 19. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为_。19CArearn= = front Bfront+l= rearCrear= = front D(rear+l)n= front20. 在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为_。20AAfront=front-next Brear=rear-nextCrear=front-next Dfront=rear-
