数据结构期末考试试题A卷

2010– 2011学年度第 一 期

考试班级 09级计应 完卷时间 　100分钟 考试科目 《数据结构》 命 题 人 杨 华 使用教材 　 教研室主任签字 系教学副主任签字_____ _____　 总

一二三四五六七八九十分

《数据结构》期末考试试卷（A卷）第Ｉ卷 选择题（共30分）

一、选择题（本大题共15小题，每小题2分，共30分。在每小题给出的四个选项中，只有一个是正确的，选对得2分，选错或不选得0分）。

1、在数据结构中，与所使用的计算机无关的是数据的（ ）结构。

A、 逻辑 B、 存贮 C、 逻辑与存贮 D、 物理2、下列算法的时间复杂度的量级为（ ）。for( int i=0； iA、 O（m3） B、 O（n2） C、 O（m*n） D、 O（m+n）

3、线性表是（ ）。

A、一个有限序列，可以为空；　　　B、一个有限序列，不能为空；

　　 C、一个无限序列，可以为空；　　　D、一个无限序列，不能为空；

4、上溢现象通常出现在（　　　）

A、顺序栈的入栈操作过程中 B、顺序栈的出栈操作过程中C、链栈的入栈操作过程中 D、链栈的出栈操作过程中5、队和栈的主要区别是( )

A、逻辑结构不同 B、存储结构不同

C、所包含的运算个数不同 D、限定插入和删除的位置不同6、一个栈的入栈序列是a，b，c，d，e，则不可能的出栈序列是（ ）。

　 A、 edcba 　 B、dceab　 C、 decba 　 D、 abcde

7、设有两个串P和Q，求P在Q中首次出现的位置的运算称为（ ）。

A、 连接运算 B、 模式匹配运算 C、 求子串 D、 求串长

8、王先生有一对双胞胎儿女，他和他双胞胎儿女的关系属于（ ）。

A、 集合结构 B、线形结构 C、树型结构 D、图形结构9、下面关于算法说法错误的是（ ）。

A、算法最终必须由计算机程序实现

B、为解决某问题的算法同为该问题编写的程序含义是相同的C、 算法的可行性是指指令不能有二义性 D、以上几个都是错误的

10、在一个单链表中，若q所指结点是p所指结点的前驱结点，若在q与p之间插入一个s所指结点，则执行（ ）。

A、 snext=pnext；pnext=s； B、pnext=s；snext=q；C、pnext= snext；snext=p； D、qnext=s；snext=p；11、下列表述中，（ ）不是算法的基本特征。A、正确性 B、长度有限 C、在规定的时间完成 D、确定性

12、在初始为空的栈S中依次插入元素fedcba后，连续进行了三次POP（S）操作，此时求top（S）=（ ）。

A、 c B、dC、b D、e

13、串是一种特殊的线性表，其特殊性体现在（ ）。A、唯一可以顺序存贮 B、数据元素是一个字符C、可以链接存贮 D、数据元素可以是多个字符14、循环队列S为满的条件是（ ）。

A、S rear== Sfront B、（S rear+1）%maxsize== SfrontC、S rear==0 D、Sfront==0

15、设单链表中指针p所指结点a，若要删除p之后的结点（若存在），则需要进行的操作为（ ）。

A、p next= p next next B、p= p next

C、p= p nextnext D、next =p

南充职业技术学院2010-2011第一期期末考试

数 据 结 构 答 题 卷

（考试时间100分钟，满分100分）

第Ｉ卷 选择题（共30分）

一、选择题（本大题共15小题，每小题2分，共30分。在每小题给出的四个选项中，只有一个是正确的，选对得2分，选错或不选得0分）。

题号答案题号答案

1B9D

2C10D

3A11B

4A12B

5D13D

6B14B

7B15A

8C

第Ⅱ卷 非选择题（共70分）

注意事项：

1．考生要将第II卷的答案用钢笔或圆珠笔答在答题卷指定的位置上。2．答题前应将答卷上密封线内的项目填写清楚。

二、简答题（共5小题，每题8分，共40分）

16、什么叫算法，它有哪些特征。

答：算法是对特定问题求解步骤的一种描述，是指令

的有限序列，其中每一条指令表示一个或多个操作。算法具有有穷性、确定性、可行性、输入和输出5个特性。

17、在链表的设计中，为什么通常采用带头结点的链表结构？

答：头指针是链表的一个标识，它用来指向带头结点的链表中的头结点。头结点是在链表的第一个数据元素之前附加的一个结点，它的作用是使对第一个结点的操作和其它结点一致，表空与非空时处理一致，不需要特殊处理，简化了操作。

18、在顺序队列中，什么叫溢出？什么叫假溢出？如何避免假溢出产生？

答：当front0，rear=M时，再有元素入队发生溢出，称之为“假溢出”，存储空间还有剩余。为了改进这种状况，可以将顺序队列想象为一个首尾相接的环状空间，称之为循环队列。

19、字符串连接运算concat（S1，S2）一般不满足交换律运算，但当S1，S2满

足一定条件的时候，concat（S1，S2）= concat（S2，S1）可以成立；请写出使得concat（S1，S2）= concat（S2，S1）成立的条件，并举例说明。

1、s1和s2为空串；2、s1和s2之一为空串；3、s1和s2为相同的串；

4、若两串长度不等，则长串s1由整数个s2短串组成

20、在如图1所示的链表中，若在指针p所指的结点之后插入数据域值相继为a

和b的两个结点，请写出实现该操作的语句。

图1

P→next=s s→next=p→next→next

三、计算、程序分析和画图题（3小题，每题10分，共30分）

21、设有一个顺序栈S，元素s1， s2， s3， s4， s5， s6依次进栈，如果6个元

素的出栈顺序为s2， s3， s4， s6， s5， s1，则顺序栈的容量至少应为多大？（要求写出栈的状态变化过程）

容量为3

22、算法分析（10分）void conversion( ) { setnull( s )；

scanf (“%d”, n)； while(n)

{ push(s , n%8)； n=n / 8； }

while(! empty(s))

{ pop(s , e)； printf(“%d”, e)； } }

分析上面的算法，当我们输入n=100时，其结果是___144__________。23、请画出下列二元组表示的数据结构对应的逻辑结构图，并指出它属于何

种结构。

三元组：A=（K，R），其中：

K={a，b，c，d，e，f，g，h}；R={ r }

r={，，，，，，}

它是一种线性结构

abcdefgh