数据结构推荐习题.doc

第一章 引言1数据结构是一门研究非数值计算的程序设计问题中计算机的_(1)_ 以及它们之间的_(2)_和运算的学科。（1） A. 操作对象 B. 计算方法 C. 逻辑存储 D. 数据映象（2） A. 结构 B. 关系 C. 运算 D. 算法2. 算法的五个要素：有穷性、确定性、 (3) 3算法分析的目的是 (1) ，算法分析考虑哪两方面的问题 (2) （1）A) 找出数据结构的合理性 B) 研究算法中输入和输出关系 C) 分析算法的效率 D) 分析算法的易理解性(2) A) 正确性和空间复杂性B) 易读性和健壮性C) 数据复杂性和程序复杂性D) 时间复杂性和空间复杂性4. 在数据结构中，逻辑上数据结构可分为_ A) 动态结构和静态结构 B)线性结构和非线性结构C)紧凑结构和非紧凑结构 D)内部结构和外部结构第二章 线性表一、填空题1线性表的顺序存储结构，采用 实现，是 （随机/非随机）存取结构。2线性表的链式存储结构中，表中元素的存储位置是 （连续/任意）的，是一种 （随随机/非随机）存取结构。3单链表的头指针为head,带表头附加结点时，表空的条件是 ，不带表头附加结点时，表空的条件是 。4双向循环链表的头指针为head,带表头附加结点时，表空的条件是 或者 ，不带表头附加结点时，表空的条件是 。5 在长为n的顺序表的第i个元素（1=i=n+1）之前插入一个元素时，需向后移动 个元素。在长为n的顺序表中删除第i个元素（1=inext = p-next-next; B). p = p-next; p-next = p-next-next;C). p-next = p-next D). p = p-next-next; 2 写出在双向链表指针P之后插入结点S的操作序列。 3线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_存储方式最节省运算时间。A） 单链表 B）仅有头指针的单循环链表C） 双链表 D）仅有尾指针的单循环链表 4.链表中结点的结构为（data,next）。已知指针q所指结点是指针p所指结点的直接前驱，若在q和p之间插入结点s，则应执行下列哪一个操作？a) s-next=p-next; p-next=s;b) q-next=s; s-next=p;c) p-next=s-next;s-next=p;d) p-next=s; s-next=q ; 5.设单链表中结点的结构为（data,next）。已知指针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;6.设单循环链表中结点的结构为（data,next），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，则应执行下列哪一个操作？a) S=rear; rear=rear-next; free(s);b) rear=rear-next; free(rear);c) rear=rear-next-next; free(rear);d) s=rear-next-next; rear-next-next=s-next; free(s); 7 设双向循环链表中结点的结构为（data,pre,next）,且不带头结点。若在指针p所指结点之后插入结点s，则应执行下列哪一个操作？a) p-next=s; s-pre=p; p-next-pre=s; s-next=p-next;b) p-next=s; p-next-pre=s; s-pre=p; s-next=p-next;c) s-pre=p; s-next=p-next; p-next=s; p-next-pre=s; d) s-pre=p; s-next =p-next=; p-next-pre=s; p-next=s; datanext8.已知一无表头结点的单链表 (结点结构为 ) 以 H 为头指针, 每个结点的 data 域存放的是一个自然数, 请你设计一个算法, 能统计出该链表中结点的值为5的倍数结点的个数.9试述顺序表和链表的定义，各有什么特点？当线性表很少进行插入和删除应采用何种表？为什么？当线性表经常进行插入和删除应采用何种表？为什么？ 10试述数据结构的四种形式，各有什么特点？11在一个递增有序的单链表中，存在重复元素，设计一个算法删除表中的重复元素。第三章 栈和队列一、填空题1栈 的线性表，其运算遵循 的原则。2 是限定仅在表尾进行插入或删除操作的线性表。3队列的特点是 ，采用循环队列的目的是避免 。4，队列的链式存储结构中，进行删除时需修改 指针。5，一个栈的输入序列是：1，2，3,则不可能的栈输出序列是 。二、选择题1队列操作的原则是 。A）先进先出 B）后进先出 C）只能进行插入 D）只能进行删除 2.若已知一个栈的入栈序列是1，2，3，.，n，其输出序列为p1,p2,p3,pn,若p1是n，则pi是 A）i B)n-i C)n-i+1 D)不确定3循环队列A0.m-1存放其元素值，用front和rear分别表示队头及队尾，则当前队列中的元素数是 A）(rear - front + m)%m B)rear - front + 1 C) rear - front - 1 D)rear-front 4在操作序列 push(1),push(2),pop,push(5),push(7),pop ,push(6)之后,栈顶元素和栈底元素分别是什么？ push(k)表示整数k入栈，pop表示栈顶元素出栈。5在操作序列Qinsert(1),Qinsert(2),Qdelete,Qinsert(5),Qinsert(7),Qdelete,Qinsert(9).之后，队头元素和队尾元素分别是什么？Qinsert(k)表示整数k入队列,Qdelete表示元素出队列。 6循环队列A0