商学院专业课数据结构商大

1、综合练习一课堂练习设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ ）。A) a，b，c，e，d B) b，c，a，e，d C) a，e，c，b，d D) d，c，e，b，a一.单选题1. 数据的逻辑结构可以分为_。A) 静态结构和动态结构 B) 物理结构和存储结构C) 线性结构和非线性结构 D) 虚拟结构和抽象结构一.单选题2. 顺序存储方式的优点是_。A) 存储密度大B) 插入、删除运算方便C) 可进行动态存储分配D) 可方便地用于各种逻辑结构的存储表示一.单选题3. 下面关于线性表的叙述中，错误的是 _。A) 线性表采用顺序存储，必须占用一片连

2、续的存储单元B) 线性表采用顺序存储，便于进行插入和删除操作C) 线性表采用链接存储，不必占用一片连续的存储单元D) 线性表采用链接存储，可以动态分配存储空间一.单选题4. 用数组存储线性表的优点是_。A) 便于插入和删除操作 B) 便于随机存取C) 可以方便地改变表的长度D) 不需要占用一片连续的存储空间一.单选题5. 线性表中各元素之间呈_关系。A) 层次B) 网状 C) 有序 D) 集合一.单选题6. 一维数组和线性表的区别是_。A) 前者长度固定，后者长度可变 B) 后者长度固定，前者长度可变C) 两者长度均固定 D) 两者长度均可变一.单选题7.单链表L中，P所指结点为尾结点的条件为

3、 _ 。A) PL B) P-next=NULLC) P.next:L D) Pnil一.单选题8.与数据元素本身的形式、内容、相对位置及个数无关的是数据的 _ 。A) 存储结构B) 存储实现 C) 逻辑结构D) 运算实现一.单选题9.单链表中，增加头结点的目的是 _ 。A) 使单链表至少有一个结点B) 表示单链表中首结点的位置C) 方便运算的实现 D) 说明单链表是线性表的链式存储结构一.单选题10. 数据结构是一门研究非数值计算的程序设计问题中计算机的_以及它们之间的关系和运算等的学科。 A）操作对象 B）计算方法 C）逻辑存储 D）数据映像一.单选题11.算法分析的目的是_。 A）找出数

4、据结构的合理性 B）分析算法的效率以求改进 C）研究算法中的输入和输出的关系 D）分析算法的易懂性和文档性一.单选题12.在长度为n的顺序表的第i（1in+1）个位置上插入一个元素，元素的移动次数为_。A）n-i+1 B）n - i C）i D）i-1一.单选题13. 不带头结点的单链表 head为空的判断条件为_。 A）head =Null B） head -next = Null C） head -next = head D） head ! = Null 一.单选题14. 数据结构被形式地定义为(D，S)，其中D是数据元素的有限集合，S是D上_的有限结合。A）操作 B）关系 C）存储D）映

5、像一.单选题15.线性结构的顺序存储结构是一种 的存储结构。A）随机存取B）顺序存取C）索引存取D）散列存取一.单选题16.组成数据的基本单位是_。 A）数据项B）数据类型C）数据元素D）数据变量一.单选题17. 双循环链表的*p结点之后插入*s结点的操作是 A）p-next=s，s-prior=p，p-next-prior=s，s-next=p-next；B）p-next=s，p-next-prior=s，s-prior=p，s-next=p-next；C）s-prior=p，s-next=p-next，p-next=s，p-next-prior=s；D）s-prior=p，s-next=p

6、-next，p-next-prior=s，p-next=s；一.单选题18.一维数组和线性表的共同点是 。两者都是相同类型数据的集合两者都允许不同类型数据共存两者长度均固定两者长度均可变一.单选题19. 线性链表中各链接结点之间的地址_。A）连续与否都可以 B）必须连续C）一定不连续D）部分地址必须连续一.单选题20. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为 。A）单链表B）用头指针表示的单循环链表 C）用带尾指针表示的单循环链表D）顺序表二.多选题1. 下列关于链式存储结构的叙述中，正确的是_。 A) 结点除自身信息外还包括指针域，因此存储密度小于 顺序存储结构 B)

7、 可以通过计算直接确定第i个结点的存储地址 C) 逻辑上相邻的结点物理上不必相邻 D) 插入、删除操作方便，不必移动结点ACD二.多选题2. 下面的叙述正确的是_。(06)A）线性表在链式存储时，查找第i个元素的时间同i的值成正比B）线性表在链式存储时，查找第i个元素的时间同i的值无关C）线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D）线性表在顺序存储时，查找第i个元素的时间同i的值无关AD二.多选题3. 链表具有的特点是_。A）插入、删除不需要移动元素B）不必事先估计存储空间C）可随机访问任一元素D）所需空间与链表长度成正比ABD二.多选题4. 下列关于链式存储结构的叙述中，正确

8、的是_。A) 结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B) 可以通过计算可以直接确定第i个结点的存储地址C) 逻辑上相邻的结点物理上必须相邻D) 插入、删除操作方便，不必移动结点AD二.多选题5. 数据元素之间的关系在计算机中的表示方法有_。 A）顺序映像 B）线性结构 C）非线性结构D) 非顺序映像AD三、判断题1. 数据结构中与所使用的计算机无关的是数据的逻辑结构。2. 线性表是一个有序序列，其中可包含相同的元素，也允许各个元素可以是不同的数据类型。3. 链表的每个结点都含有两个指针。4.线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个后继。5.线性表中各元素类型

9、必须是相同的。 6.数据结构的操作一定是定义在逻辑结构上，实现在存储结构上。 7.数据的逻辑结构指的是数据元素之间的逻辑关系的整体。正确 1 5 6 7四、填空题1. 数据结构包括的三个方面的内容是 、 和 。2. 通常衡量算法效率的一般标准为 和 。3. 算法是对特定问题求解步骤的一种描述，它具有有穷性、确定性、可行性、_及一个或多个输出等重要特征。4. 数据结构是相互之间存在一种或多种关系的_集合。5. 线性结构中元素的关系是_的关系。 答案：1 逻辑结构、存储结构、运算 2 时间复杂度、空间复杂度 3 具有零个或多个输入 4 数据元素 5 一对一四、填空题6. 用一维数组表示线性表L=(

10、a1,a2,an)，假定删除表中任一元素的概率相同（都为1/n），则删除一个元素平均需移动的元素个数为_ 。(n-1)/2 7.当线性表采用顺序存储结构进行存储时，其主要特点是 _ 。逻辑结构相邻的结点存储结构也相邻8.链式存储结构最显著的优点是 _。 方便插入、删除操作四、填空题9.单循环链表的最显著的优点是 _ 。答：从任意结点出发都可以访问链表中的每个元素10.一个线性表第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的地址是_ 。答：110五、简答题1解释数据结构、逻辑结构、存储结构的概念，并讨论他们之间的关系；参考答案：数据结构：相互之间存在一种或多种特定关系的数据元素

11、的集合。逻辑结构：逻辑结构描述数据之间的逻辑关系。包括集合、线性、树形和网状结构。存储结构：数据结构在计算机中的表示称存储结构。包括顺序、索引、链式和散列。三者关系：在数据结构中，数据的逻辑结构和存储结构密切相关的；存储结构不仅存储数据元素，还要存储数据元素的逻辑关系；逻辑结构与计算机无关；逻辑结构相同但存储结构不同，可以是不同的数据结构。五、简答题2线性表的顺序存储具有如下缺点：(1).在进行插入或删除操作时，需要移动大量元素；(2).由于难以估计其大小，必须预先分配较大的存储空间，往往使存储空间得不到充分利用；(3).表的容量难以扩充。试问线性表的链式存储结构是否一定能克服上述缺点？试做简

12、要讨论。参考答案：链式存储结构一般克服的顺序结构的三个弱点： 首先，链式存储结构插入、删除不需要移动元素，只需修改指针，时间复杂度为O(1)；其二，不需要预先分配存储空间，可根据需要动态申请；其三，表容量只受内存空间的限制；缺点：因指针增加了内存空间开销，当空间不允许时，就不能克服顺序存储的优点。六、编程题1已知两个带头结点的单链表La和Lb中的元素按非递减顺序排列，试用C语言编写一个函数将这两个有序表合并成一个有序单链表保存在La中，而不改变其排序性。设带头结点的单链表的结点结构说明及函数名如下：typedef struct node /*定义结点结构*/ datatype data; st

13、ruct node next; lklist;typedef struct node *pointer;函数首部为：pointer mergelklist(lklist ha,lklist hb)pointer mergelklist(lklist ha,lklist hb) pointer *h, *pa, *pb ; pa=ha-next, pb=hb-next； h= r = ha； while(pa & pb) If(pa-data data) /*移动ha, hb头指针, 修改r指向 r-next =pa; r=pa; pa= pa-next ； else r-next =pb; r

14、=pb; pb= pb-next ； if(pa=NULL) r-next=pb; if(pb=NULL) r-next=pa; return h； 1题参考答案六、编程题2 设计算法求两个递增有序的顺序表L1和L2中的公共元素，并将其置入顺序表L3中，用C语言实现。设顺序表存储结构说明如下：typedef struct ElemType *elem; Int length ;sqlist;sqlist L1,L2,L3;函数首部为： status complist(sqlist L1, sqlist L2, sqlist L3)status complist(sqlist L1, sqlist L2, sql