内容发布更新时间 : 2024/5/6 13:13:49星期一 下面是文章的全部内容请认真阅读。

习题练习 第一章

1. 算法的计算量的大小称为计算的（ B ）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续

17．以下属于逻辑结构的是（ C ）。 A．效率 B. 复杂性 C. 现实性 A．顺序表 B. 哈希表 C.有序表 D.

D. 难度

2. 算法的时间复杂度取决于（ C）

A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（C），它必须具备（B） 这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法

(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性 D. 易读性、稳定

性、安全性

4．一个算法应该是（ B ）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5、下面属于逻辑结构的是（ C ）

A 顺序表 B哈希表 C 有序表 D 单链表 6、某算法的时间复杂度为O(n2)，表明该算法的（C） A 问题规模是n2 B执行时间等于n2 C 执行时间与n2成正比 D问题规模与n2成正比 7、下面关于算法说法错误的是（ C ）

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

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

8．从逻辑上可以把数据结构分为（ C ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 9．以下与数据的存储结构无关的术语是（ D）。

A．循环队列 B. 链表 C. 哈希表 D. 栈

10．以下数据结构中，哪一个是线性结构（ D ）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串

11．以下那一个术语与数据的存储结构无关？（ A ）

A．栈 B. 哈希表 C. 线索树 D. 双向链表 12．在下面的程序段中，对x的赋值语句的频度为（ C）

FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;

A． O(2n) B．O(n) C．O(n2

) D．O(logn

2) 14．以下数据结构中，（ A）是非线性数据结构

A．树 B．字符串 C．队 D．栈 15. 下列数据中，（ C ）是非线性数据结构。

A．栈 B. 队列 C. 完全二叉树 D. 堆 16．连续存储设计时，存储单元的地址（ A ）。

单链表 二、问答：

1. 数据结构是一门研究什么内容的学科？

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。

2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？

顺序映像、非顺序映像。顺序映像特点：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序映像特点：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。 3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？

数据类型是一个值的集合和定义在这个值集上的一组操作的总称；抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。 4. 回答问题

（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？

数据的逻辑结构反映数据元素之间的逻辑关系，数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关而运算的规则则是依赖于存储结构的。

（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。

逻辑结构相同但存储不同，可以是不同的数据结构。例如，线性表的逻辑结构属于线性结构，采用顺序存储结构为顺序表，而采用链式存储结构称为线性链表。

（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。 栈和队列的逻辑结构相同，其存储表示也可相同，但由于其运算

集合不同而成为不同的数据结构。

5．评价一个好的算法，您是从哪几方面来考虑的？ 正确性、可读性、健壮性、效率与低存储量需求。

第二章

1．下述哪一条是顺序存储结构的优点？（ A ） A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

2．下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ C ）的有限序列（n>0）。 E．信息项

4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

20．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。

AC

．．

p->next=s;s->next=p->next; p->next=s;p->next=s->next;

A．表元素 B．字符 C．数据元素 D．数据项 B． s->next=p->next;p->next=s;

D． p->next=s->next;p->next=s;

25．对于一个头指针为head的带头结点的单链表，判定该表为空A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表

6．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。

A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表

7. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2

) 8. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)

9．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）

A．O（i） B．O（1） C．O（n） D．O（i-1） 16．非空的循环单链表head的尾结点p↑满足（ A ）。 A．p↑.link=head B．p↑.link=NIL C．p=NIL D．p= head

17．循环链表H的尾结点P的特点是（ A ）。 A．P^.NEXT:=H B．P^.NEXT:= H^.NEXT C．P:=H D．P:=H^.NEXT 18．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（）

A. p＾.next=h B. p＾.next=NIL C. p＾.next.＾next=h D. p＾.data=-1

19．在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。

A.

p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；

B.

p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;

C.

q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;

D.

q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

表的条件是（ ）

A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 二、算法设计： 1. 插入算法，在带有头结点的单链表La中第i个元素之前插入e。

2. 删除算法，删除带有头结点的单链表La中第i个元素 3. 将两个有序的带有头结点单链表Ｌａ和Ｌｂ进行合并成一个有序的单链表Ｌｃ算法 4. 将链表Ｌａ进行逆置等操作。

5.

已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。 6.

(6) 有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。 7. 在一个递增有序的线性表中，有数值相同的元素存在。若存

储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分析算法的时间复杂度。

第三章

1. 对于栈操作数据的原则是（ ）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序

2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢

③: A. n-1 B. n C. n+1 D. n/2

④: A. 长度 B. 深度 C. 栈顶 D. 栈底

⑤: A. 两个栈的栈顶同时到达栈空间的中心点.

B. 其中一个栈的栈顶到达栈空间的中心点.

C. 两个栈的栈顶在栈空间的某一位置相遇.

D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈

底.

3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。 存储结构 D. 栈

22. 用链接方式存储的队列，在进行删除运算时（ ）。【

A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都A. 不确定 B. n-i+1 C. i 要修改 D. 头、尾指针可能都要修改

D. n-i

4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。

A. i-j-1 B. i-j C. j-i+1 D. 不确定的

5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( )。

A. i B. n-i C. n-i+1 D. 不确定 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）

A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6

8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。

A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2

13. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）【中山大学 1999 一、8(1分)】

A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop

C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop

14. 若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。

A．top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1

C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1

15. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。 A.

|top[2]-top[1]|=0

B.

top[1]+1=top[2]

C.

top[1]+top[2]=m D. top[1]=top[2]

16. 栈在（ ）中应用。【中山大学 1998 二、3（2分）】 A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ

17. 一个递归算法必须包括（ ）。

A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分

19. 表达式a*(b+c)-d的后缀表达式是( )。

A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 21. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。

A．线性表的顺序存储结构 B. 队列C. 线性表的链式

23. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。

A．仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修

改

24. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。 A．队列 B．多维数组 C．栈

D. 线性表

25. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。

A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m

26. 循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。

A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front

27. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。

A. rear=rear+1 B. rear=(rear+1) mod (m-1)

C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 28. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )

A. 1和 5 B. 2和4 C. 4和2 D. 5和1

31. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。

A. (rear+1) MOD n=front B.

rear=front

C．rear+1=front D. (rear-l) MOD n=front

32. 栈和队列的共同点是（ ）。

A. 都是先进先出 B. 都是先进后出

C. 只允许在端点处插入和删除元素 D. 没有共同点 34. 栈和队都是（ ）

A．顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构

35. 设栈S和队列Q的初始状态为空，元素a1，a2，a3，a4,a5和a6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是a2，a4，a3,a6,a5,a1则栈S的容量至少应该是( )。

A． 6 B. 4 C. 3 D. 2