讯享网

 <p>数据结构基础及深入及考试</p><p>复习资料</p><p>习题及实验参考答案见附录</p><p>结论</p><p>1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。</p><p>2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列</p><p>3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。</p><p>4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。</p><p>5、在数据结构中，从逻辑上可以把数据结构分成（ C ）</p><p>A、动态结构和表态结构</p><p>B、紧凑结构和非紧凑结构</p><p>C、线性结构和非线性结构</p><p>D、内部结构和外部结构</p><p>6、算法的时间复杂度取决于（ A ）</p><p>A、问题的规模</p><p>B、待处理数据的初态</p><p>C、问题的规模和待处理数据的初态</p><p>线性表</p><p>1、线性表的存储结构包括顺序存储结构和链式存储结构两种。</p><p>2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。</p><p>A、(n-1)/2</p><p>B、n</p><p>C、n+1</p><p>D、n-1</p><p>E、n/2</p><p>F、(n+1)/2</p><p>G、(n-2)/2</p><p>3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ）</p><p>A、正确的</p><p>B、错误的</p><p>C、不一定，与具体的结构有关</p><p>4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ）</p><p>A、必须是连续的</p><p>B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以</p><p>5、带头结点的单链表为空的判定条件是（ B ）</p><p>A、head==NULL</p><p>B、head->next==NULL</p><p>C、head->next=head</p><p>D、head!=NULL</p><p>6、不带头结点的单链表head为空的判定条件是（ A ）</p><p>A、head==NULL</p><p>B、head->next==NULL</p><p>C、head->next=head</p><p>D、head!=NULL</p><p>7、非空的循环单链表head的尾结点P满足（ C ）</p><p>A、p->next==NULL</p><p>B、p==NULL</p><p>C、p->next==head</p><p>D、p==head</p><p>8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ）</p><p>A、O(1)</p><p>B、O(n)</p><p>C、O(n2)</p><p>D、O(nlog2n)</p><p>9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ）</p><p>A、p->next=p->next->next;</p><p>B、p=p->next;p->next=p->next->next;</p><p>C、p->next=p->next;</p><p>D、p= p->next->next;</p><p>10、在一个单链表中，若在p所指结点之后插入s所指结点，则执行（ B ）</p><p>A、s->next=p;p->next=s;</p><p>B、s->next=p->next;p->next=s;</p><p>C、s->next=p->next;p=s;</p><p>D、p->next=s;s->next=p;</p><p>11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点s，则执行（ C ）</p><p>A、s->next=p->next;p->next=s;</p><p>B、p->next=s->next;s->next=p;</p><p>C、q->next=s;s->next=p;</p><p>D、p->next=s;s->next=q;</p><p>12、在线性结构中，第一个结点没有前趋结点，其余每个结点有且只有 1 个前趋结点。</p><p>栈和队列</p><p>1、在栈操作中，输入序列为（A，B，C，D），不可能得到的输出数列是（ D ）</p><p>A、（A，B，C，D）</p><p>B、（D，C，B，A）</p><p>C、（A，C，D，B）</p><p>D、（C，A，D，B）</p><p>2、设栈ST用顺序存储结构表示，则栈ST为空的条件（ B ）</p><p>A、ST.top=ST.base<>0</p><p>B、ST.top=ST.base==0</p><p>C、ST.top=ST.base<>n</p><p>D、ST.top=ST.base==n</p><p>3、向一个栈顶指针为HS的链栈中插入一个s结点时，执行（ C ）</p><p>A、HS->next=s;</p><p>B、s->next=HS->next;HS->next=s;</p><p>C、s->next=HS;HS=S;</p><p>D、s->next=HS;HS=HS->next;</p><p>4、从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删结点的值，则执行（ C ）</p><p>A、x=HS;HS=HS->next;</p><p>B、HS=HS->next;x=HS->data;</p><p>C、x=HS->data;HS=HS->next;</p><p>D、s->next=HS;HS=HS->next;</p><p>5、用单链表表示的链示队列的队头在链表的（ A ）位置。</p><p>A、链头</p><p>B、链尾</p><p>C、链中</p><p>6、判定一个链队列Ｑ（最多元素个数为n）为空的条件是（A）</p><p>Ａ、Ｑ.front==Q.rear B、Q.front!=Q.rear</p><p>C、Q.front==(Q.rear+1)%n</p><p>D、Q.front!=(Q.rear+1)%n</p><p>7、在链队列Ｑ中，插入要所指结点需顺序执行的指令是（B）</p><p>A、Q.front->next=s;f=s;</p><p>B、Q.rear->next=s;Q.rear=s;</p><p>C、s->next=Q.rear;Q.rear=s;</p><p>D、s->next=Q.front;Q.front=s;</p><p>8、在一个链队列Q中，删除一个结点需要执行的指令是（ C ）</p><p>A、Q.rear=Q.front->next;</p>