48283-软件《数据结构》期中试卷.doc

江西财经大学 15－16第二学期期中考试试卷 试卷代码：48283 授课课时：48 考试用时：90分钟 课程名称：数据结构 适用对象：15级软件工程 试卷命题人 邓庆山 试卷审核人 严军勇 一、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题3分，共24分。） 1. 链式栈与顺序栈相比，一个比较明显的优点是（ B ）。 A．插入操作更加方便 B． 通常不会出现栈满的情况 C．不会出现栈空的情况 D． 删除操作更加方便 2. 在一个链队列中,假定front和rear分别为队首和队后指针,则进行插入S结点的操作时应执行（ C ）。 A．front- next=s； front=s； B．s- next=rear； rear=s； C．rear- next=s； rear=s； D．s- next=front； front=s； 3. 关于算法的描述，不正确的是（　B ）。 A.算法最终必须由计算机程序实现 B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态 D.算法的优劣与算法描述语言无关 4.若算法中语句频度之和为T(n) = 123n + n2/45 + 6nlog2n + 7891，则算法的时间复杂度为（ D ）。 A.O(1) B.O( n ) C.O( nlog2n ) D.O( n2 ) 5. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ C ）。 A.q=p-next；p-data=q-data；p-next=q-next；free(q)； B. q=p-next；q-data=p-data；p-next=q-next；free(q)； C. q=p-next；p-next=q-next；free(q)； D. q=p-next；p-data=q-data；free(q)； 6．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( B ) A.236 B.239 C.242 D.245 7．对于长度为n的顺序表执行删除操作，则其结点的移动次数（　C　　） A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n-1 D.最少为1，最多为n-1 8．栈和队列的共同特点是( A )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 二、填空题（将下列各题横线上的内容补充完整。每小题3分，共18分。） 1. 顺序存储的队列如果不采用循环方式，则会出现 假溢出 问题。 2. 双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句：S→next=P;S→prior=P→prior;P→prior=S;___p-prior-next=s_ ___。 3. 通常程序在调用另一个程序时，都需要使用一个 栈 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 4. 解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个____线性_____ 结构，其主要特点是____先进先出______。 5. 任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的 存储（物理）结构 。 三、简答题（回答要点，并简明扼要作解释。每小题7分，共28分） 1. 画出带头结点的单链表、单循环链表和双向循环链表的示意图，并归纳三者的不同之处。P32 P38 P39 P51表2.3 2. 简述栈和队列的共同点和不同点。它们与线性表有什么关系？P82 3. 设输入序列为a,b,c,d,试写出借助一个栈可得