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

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结点，则应执行语句（ ）A s-next=p:p-next=s; B s-next=p-next;

3、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. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是( )A. 110 B. 108 C. 100 D. 1208. 在一个长度为n的顺序表中,在第i个元素( 1 = i next=p-next;p-next=s;B.p-next

4、=s-next;s-next=p;C.q-next=s;s-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 (

5、D) rear-front=maxsize-112元素的入栈序列是a,b,c,d，则栈的不可能的输出序列是（ ）(A) dcba (B)abcd (C) dcab (D) cbad13链表仿真堆栈时，栈空的条件是（ ）(A) topmaxsize-1 (B) top=NULL (C) 没有限制 (D) topnext=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

6、) topmaxsize-1 (B) top=NULL (C) 没有限制 (D) topnext; p-data=p-next-data; p-next=_; free(q);4. 在一个单链表中p所指结点之后插入一个s所指结点，应执行s-next=_和p-next=_的操作.5. 顺序表中逻辑上相邻的元素的物理位置 _相邻。单链表中逻辑上相邻的元素的物理位置 _相邻。6判断一个队列QU（最多元素为m0）为空的条件是 _。7. 判断一个循环队列QU(最多元素为m0)为满队列的条件是 _。8栈和队列都是线性结构，对于栈只能在 _位置插入和删除元素，对于队列只能在 _ 位置插入元素和 _位置删除元

7、素。9用大小为MaxSize的数组仿真一个循环队列，front和rear分别记录该队列前后端的索引值，则该循环队列在某一状态下，队列中的元素个数为 。10在具有n个单元的环状队列中，队满时共有 个元素。11. 已知字符串char string =”student”，其有效长度为 _，占用内存空间为 字节。12.已知数组int a65以行为主序进行存储，起始位置为1000，则a23的存储地址为 。（int占2个字节）13、有5个元素，其入栈顺序为：A、B、C、D、E，在各种可能的出栈顺序中，以元素C第一个出栈且D第二个出栈的次序有_、_、_。三、 14算法题（7小题，共38分）1(本题6分)假设

8、本测试中使用的链表结点定义如下：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;（3）S=P; while(S-next!=NULL) S-data=S-data*3; S=S-next;2有一链表如下图所示，阅读程序给出程序的输出结果。（本题5分）P = head

9、;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、（本题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

10、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”及边界情况的输出pop（）结果包含“堆栈数据内容”、“top”及输出数据值和边界情况的输出24 16 10 3top 2 1