大连东软信息学院数据结构期末试卷(本科)

1、东软信息学院0708学年第二学期数据结构期中试题班级：_ 姓名：_ 学号：_学生层次：嵌入式系统工程系 07级 电子信息工程（集成电路设计与系统） 本科嵌入式系统工程系 07级 电子信息工程（嵌入式系统工程） 本科题 号一二三四总 分分 数一、 选择题（每小题1分，共20分）1. 从逻辑上可以把数据结构分为（ ）。A动态结构和静态结构 B. 线性结构和非线性结构C紧凑结构和非紧凑结构 D. 逻辑结构和物理结构2. 线性表的链表存储结构与顺序存储结构相比优点是（ ）A. 所有的操作算法实现简单 B 便于随机存取C 便于插入和删除 D便于利用零散的存储器空间3.将下图所示的s所指结点加到p所指结点

2、之后，其语句应为：（ ）p sA s->next=p+1;p->next=s; B (*p).next=s;(*s).next=(*p).next; C s->next=p->next;p->next=s->next; D s->next=p->next;p->next=s;4. 不带头结点的单链表head为空的判定条件是（ ）A head= =NULL B head->next= =NULL C head->next= =head D head!=NULL5. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s结点，则应

3、执行语句（ ）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. 在一个单链表中，若删除p所指结点的后续结点，则应执行语句（ ）A p->next=p->next->next; B p=p->next;p->next=p->next->next;C p->next=p->next; D p=p->next->next;7. 一个向量

4、第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是( )A. 110 B. 108 C. 100 D. 1208. 在一个长度为n的顺序表中,在第i个元素( 1 <= i <=n+1)之前插入一个新元素时须向后移动( )个元素.A. n-1B. n-i+1C. n-i-1D. i9. 在一个单链表中，已知q所指的结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行( )。A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s-&g

5、t;next=p;D.p->next=s;s->next=q;10. 线性表L=(a1,a2,an),下列说法正确的是( )A. 每个元素都有一个直接前驱和一个直接后继B. 线性表中至少要有一个元素C. 表中诸元素的排列顺序必须是由小到大或由大到小D. 除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继11. 循环队列用数组Amaxsize 表示，下面哪个选项表示该循环队列队满（ ）(A) rear=maxsize-1 (B) front=(rear+1)%maxsize(C) rear-front=maxsize (D) rear-front=maxsiz

6、e-112元素的入栈序列是a,b,c,d，则栈的不可能的输出序列是（ ）(A) dcba (B)abcd (C) dcab (D) cbad13链表仿真堆栈时，栈空的条件是（ ）(A) top<maxsize-1 (B) top=NULL (C) 没有限制 (D) top<014在用数组queuemaxsize仿真队列时(temp为int型变量)，假设队列中至少有一个元素，出队列操作应执行以下（ ）(A) temp=queuerear；rear-； (B) rear+； temp=queuerear；(C) temp=queuefront；front-； (D) front+； t

7、emp=queuefront；15在用链表仿真堆栈时(假设stack为栈顶指针)，将new指针指向的节点执行入栈操作应执行( ) (A) new->next=stack->next； stack=new； (B) new->next=stack； stack=new；(C)new->next=stack；stack=new->next；(D) stack=new；stack->next=new->next；16链表仿真堆栈时，栈满的条件( )(A) top<maxsize-1 (B) top=NULL (C) 没有限制 (D) top<01

8、7下列哪种数据结构常用于函数调用( )(A) 堆栈 (B) 队列 (C) 链表 (D) 数组18编译器中通常以哪种数据结构处理递归程序调用( )（A）队列（B）数组（C）堆栈（D）记录19. 若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。当从队列中删除2个元素，再加入1个元素后，rear和front的值分别为多少( )？A 1和5 B 2和4 C 4和2 D 5和120. 字符串是一种特殊的线性表，其特殊性体现在（ ） A可以顺序存储 B. 数据元素是一个字符 C. 可以链式存储 D. 数据元素可以是多个字符二、 填空题(每空1分，共24分)1. 数据的最常用

9、的两种存储结构为_ 和 _。2. 根据数据结构中各数据元素之间逻辑关系的不同，可以将数据结构分为_、_ 和_三类。3. 在一个单链表中删除p所指结点时，应执行以下操作： q=p->next; p->data=p->next->data; p->next=_; free(q);4. 在一个单链表中p所指结点之后插入一个s所指结点，应执行s->next=_和p->next=_的操作.5. 顺序表中逻辑上相邻的元素的物理位置 _相邻。单链表中逻辑上相邻的元素的物理位置 _相邻。6判断一个队列QU（最多元素为m0）为空的条件是 _。7. 判断一个循环队列QU(

10、最多元素为m0)为满队列的条件是 _。8栈和队列都是线性结构，对于栈只能在 _位置插入和删除元素，对于队列只能在 _ 位置插入元素和 _位置删除元素。9用大小为MaxSize的数组仿真一个循环队列，front和rear分别记录该队列前后端的索引值，则该循环队列在某一状态下，队列中的元素个数为 。10在具有n个单元的环状队列中，队满时共有 个元素。11. 已知字符串char string =”student”，其有效长度为 _，占用内存空间为 字节。12.已知数组int a65以行为主序进行存储，起始位置为1000，则a23的存储地址为 。（int占2个字节）13、有5个元素，其入栈顺序为：A、

11、B、C、D、E，在各种可能的出栈顺序中，以元素C第一个出栈且D第二个出栈的次序有_、_、_。三、 14算法题（7小题，共38分）1(本题6分)假设本测试中使用的链表结点定义如下：struct List int data; struct List *next;typedef struct List Node;typedef Node *Link;Link P,Q,R,S,head;Link pointer,back,new;对以下单链表分别执行下列程序段，要求分别画出结果图（1）Q=head->next->next;（2）R->data=P->next->data;

12、（3）S=P; while(S->next!=NULL) S->data=S->data*3; S=S->next;2有一链表如下图所示，阅读程序给出程序的输出结果。（本题5分）P = head;while(P ->next!= NULL) printf(“n data=%d”, P -> data);P = P->next；if( P != NULL) P = P ->next; 3（本题4分）设有一个二维数组Amn，假设A00存放位置在644（10），A22存放位置在676（10），每个元素占一个地址空间，求A33（10）存放在什么位置？4、

13、（本题6分）在什么情况下用顺序表比链表好？在什么情况下用链表比顺序表好？5（本题5分）将以下稀疏矩阵进行压缩，请写出压缩后的数组内容(即三元组表)。 0 0 1 0 0 0 0 0 0 0 8 0 0 0 0 3 0 0 6 0 0 0 1 0 0 0 0 0 0 4 0 5 0 0 0 0 0 0 0 0 0 06（本题6分）试画出执行函数之后的结果。注：此为环状队列，且每次执行以上一次执行的结果为基础addqueue（）结果包含“队列数据内容”、“front”、“rear”及边界情况的输出delqueue（）结果包含“队列数据内容”、“front”、“rear”及输出数据值和边界情况的输出 28 16 10 3rearfront 2 1 0（1） addqueue（30）（2） delqueue（）（3） addqueue(24)7（本题6分）试画出执行函数之后的结果。注：此为堆栈，且每次执行以上一次执行的结果为基础push（）结果包含“堆栈数据内容”、“top”及边界情况的输出po