《数据结构1-4章习题》由会员分享，可在线阅读，更多相关《数据结构1-4章习题（22页珍藏版）》请在金锄头文库上搜索。
1、1习题习题 1 绪论绪论1.1 单项选择题单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的 、数 据信息在计算机中的 以及一组相关的运算等的课程。 A操作对象 计算方法 逻辑结构 数据映象 A存储结构 关系 运算 算法2. 数据结构 DS 可以被形式地定义为 DS=D，R） ，其中 D 是 的有限集 合，R 是 D 上的 有限集合。 A算法 数据元素 数据操作 数据对象 A操作 映象 存储 关系3. 在数据结构中，从逻辑上可以把数据结构分成 。 A动态结构和静态结构 紧凑结构和非紧凑结构 线性结构和非线性结构 内部结构和外部结构 4. 算法分析的目的是 ，算法分析的两个
2、主要方面是 。 A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是 ，它必具备输入、输出和 等五个特性。 A. 计算方法 B. 排序方法C. 解决问题的有限运算序列 D. 调度方法 A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性1.2 填空题（将正确的答案填在相应的空中）填空题（将正确的答案填在相应的空中）1. 数据逻辑结构
3、包括 、 和 三种类型，树形结构和图 形结构合称为 。 2. 在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 2个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个 后续结点。 3. 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个直接前驱结点，叶子结点没有 结点，其余每个结点的直接后续结点可 以 。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。 5. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。 6. 算法的五个重要特性是_ _ , _ _ , _ _ , _ _ , _ _。 7. 分析下面算法（程序
4、段） ，给出最大语句频度 ，该算法的时间复 杂度是_ _。 for (i=0;inext= =NULL C. head-next= =head D. head!=NULL 8. 带头结点的单链表 head 为空的判定条件是_。 A. head= =NULL B. head-next= =NULL C. head-next= =head D. head!=NULL 9. 非空的循环单链表 head 的尾结点（由 p 所指向）满足_。 A. p-next= =NULL B. p= =NULL C. p-next= =head D. p= =head 10. 在双向循环链表的 p 所指结点之后插入
5、s 所指结点的操作是_。 A. p-nextt=s; s-prior=p; p-next- prior =s; s-next=p-next; B. p-next=s; p-next- prior =s; s- prior =p; s-next=p-next; C. s- prior =p; s-next=p-next; p-next=s; p-next- prior =s; D. s- prior =p; s-next=p-next; p-next- prior =s; p-next=s; 11. 在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 s 结
6、点，则执行_。4A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p; B. q-next=s; s-next=p; C. p-next=s; s-next=q; 12. 在一个单链表中，若 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; C. p-next=s; s-next=p; 13. 在一个单链表中，若删除 p 所指结点的后续结点，则执行_。 A. p-next
7、= p-next-next； B. p= p-next; p-next= p-next-next； C. p-next= p-next; D. p= p-next-next；2.2 填空题（将正确的答案填在相应的空中）填空题（将正确的答案填在相应的空中）1. 单链表可以做_ _的链接存储表示。 2. 在双链表中，每个结点有两个指针域，一个指向_ _，另一个指向 _。 3. 在一个单链表中 p 所指结点之前插入一个 s (值为 e)所指结点时，可执 行如下操作：q=head; while (q-next!=p) q=q-next; s= new Node/*生成新结点*/; s-data=e;
8、q-next= ; /填空 s-next= ; /填空 4. 在一个单链表中删除 p 所指结点的后继结点时，应执行以下操作： q= p-next; p-next= _ _; /填空 free( ); /填空 5. 在一个单链表中 p 所指结点之后插入一个 s 所指结点时，应执行 s- next=_ _和 p-next=_的操作。2.3 算法设计题算法设计题:1.设顺序表 va 中的数据元数递增有序。试写一算法，将 x 插入到顺序表 的适当位置上，以保持该表的有序性。 2.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表 （a1, a2,. an）逆置为(an, an-1,., a
9、1)。 3. 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试 写一算法，删除表中所有大于 x 且小于 y 的元素（若表中存在这样的元素）同 时释放被删除结点空间。 4. 试写一算法，实现单链表的就地逆置(要求在原链表上进行)。习题答案习题答案2.1 1. B 2. A, C 3. B 4. D 5. C 6. A 7. A8. B 9. C 10. D 11.B 12.B 13.A 2.2 1. 线性结表 2. 前驱结点、后继结点53. s, p 4. q-next, q 5. p-next, s 习题习题 3 栈和队列栈和队列3.1 单项选择题单项选择题1. 一个栈的入栈序列
10、a，b，c，d，e，则栈的不可能的输出序列是_。 A. edcba B. decba C. dceab D. abcde 2. 若已知一个栈的入栈序列是 1，2，3，n，其输出序列为 p1，p2，p3，pn，若 p1=n，则 pi 为_。 A. i B. n=i C. n-i+1 D. 不确定 3. 栈结构通常采用的两种存储结构是_。 A. 顺序存储结构和链式存储结构 B.散列方式和索引方式 C.链表存储结构和数组 D.线性存储结构和非线性存储结构 4. 判定一个顺序栈 S（最多元素为 m）为空的条件是_。 A. S.top !=0 B.S. top= =0 C. S.top !=m D. S
11、.top= =m-1 5. 判定一个顺序栈 S（最多元素为 m）为栈满的条件是_。 A. S.top！=0 B. S.top= =0 C. S.top！=m D. S.top= =m-1 6. 栈的特点是_，队列的特点是_。 A. 先进先出 B. 先进后出 7. 向一个栈顶指针为 HS 的链栈中插入一个 s 所指结点时，则执行_。 (不带空的头结点)A.HSnext=s;B. snext= HSnext; HSnext=s;C. snext= HS; HS=s;D. snext= HS; HS= HSnext;8. 从一个栈顶指针为 HS 的链栈中删除一个结点时，用 x 保存被删结点的值， 则
12、执行_。(不带空的头结点) A. x=HS; HS= HSnext; B. x=HSdata;C. HS= HSnext; x=HSdata; D. x=HSdata; HS= HSnext;9. 一个队列的数据入列序列是 1，2，3，4，则队列的出队时输出序列是_ 6。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，1 10. 判定一个循环队列 Q（最多元素为 m）为空的条件是_。 A. rear - front= =m B. rear-front-1= =m C. front= = rear D. front= = rear+1 11. 判定一个循环队
13、列 Q(最多元素为 m, m=Maxsize-1)为满的条件是_。 A. (rear- front)+ Maxsize)% Maxsize = =m B. rear-front-1= =m C. front= =rear D. front= = rear+1 12. 循环队列用数组 A0，m-1存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列中的元素个数是_。 A. (rear-front+m)%m B.rear-front+1 C.rear-front-1 D. rear-front 13. 栈和队列的共同点是_。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点3.2 填空题（将正确的答案填在相应的空中）填空题（将正确的答案填在相应的空中）1. 向量、栈和队列都是_结构，可以在向量的_位置插入和删除元 素；对于栈只能在_插入和删除元素；对于队列只能在_插入元素和_ 删除元素。 2. 向一个长度为 n 的向量的第 i 个元素（1in+1）之前插入一个元素 时，需向后移动_个
