级本1数据结构期中试题参考答案.pdfVIP

级本1数据结构期中试题参考答案

一、填空题(每空2分，共32分)

1.按照数据结构中元素逻辑关系的不同，我们将数据结构分成：

线性和

非线性两大类。

2.在一个长度为n的顺序表中删除第pos(0=posn)个位置上的

元素，需移动的元素个数为p=

n-pos-1。

3.Evaluatethepostfixexpression:2431+*+,whereeach

numberrepresentsanoperandandeachsymbolof+or*

representsanoperator,pleasegivetheresultoftheexpression

onthefollowingline18。

4.设以下算法中所用到的栈和队列元素类型一致，类型名为

StackQueue_entry，请问该算法的功能为:栈S元素逆置___。

Error_codealgo1(StackS)

{

StackQueue_entryitem;

QueueQ;

while(!S.empty(){S.top(item);S.pop();Q.append(item);}

while(!Q.empty(){Q.retrieve(item);Q.serve();S.push(item);}

returnsuccess;

}

5.请在下列String类的构造函数中填空：

String::String(Listin_list){

length=in_list.size();

entries=newchar[length+1];

for(inti=0;ilength;i++)p=

in_list.retrieve(i,entry[i]);;

entries[length]=‘\0’;

6.栈中元素的操作原则是LIFO,在出栈算法中需要判断栈是否为空。

7.在线性表和数组这两个概念中，线性表是一个与是否在计算机

中存储无关的逻辑概念。

8.对数据结构进行的抽象数据类型（ADT）定义包含两部分内容，

分别是这种数据结构的逻辑结构定义以及基本操作集定义。

9.在hanoi塔问题中,若要将A塔座上的3个圆盘移动到C塔座上,

其中B塔座作为中间的辅助塔座,则至少需要搬动的次数为7。

10.为了使链式存储的类在使用时不发生错误，我们要为它们配备

析构函数、拷贝构造函数______________、_______赋值重载函数____等

方法。

11.在线性表改进的单链表实现方法中，我们定义了current指针

和current_position分别指示最近访问过的结点的指针和位序号，请

解释这样做的好处：不需要每次都从

头访问链表，在按顺序访问链表结点时效率得到提高。

12.在用于查找的线性表中，线性表中存放了n条Record类型的

记录，Record对象应满

足的要求是：每个Record对象都可以转换为key类型的对象，可

以相互比较大小。

二、应用题(共48分)

1.线性表的顺序存储结构具有三个弱点：其一，在作插入或删除

操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大

的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩

充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨

论之。（9分）

答：

线性表的链式存储结构能够克服上述三个弱点。其一，在作插入

或删除操作时，不需移动元素，当然，此时需要移动指针；其二，链

式结构中的每个结点是动态申请的，只有在需要的时候才要求分配空

间，也因此其三中表的容量是容易扩充的，只要系统堆空间有内存。

当然，由于链式表中指针域也占用空间，链式结构的空间效率也

不一定优于顺序结构。

2.Asentinel,alsocalledhedge,isanextraentry(areextra

en