数据结构 23679 10章 单章题目1

第二章 线性表

10.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。 Void insert_sqlist(sqlist L，datatype x，int i)

/*将X插入到顺序表L的第i-1个位置*/ { if( L.last == maxsize) error(“表满”)； if((i<1)||(i>L.last+1))error(“非法位置”); for(j=L.last;j>=i;j--)______; L.data[i-1]=x; L.last=L.last+1; }

12.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。

void delete_sqlist(sqlist L,int i) /*删除顺序表L中的第i-1个位置上的结点*/

{if((i<1)||(i>L.last))error(“非法位置”)； for(j=i+1;j=L.last;j++)________; L.last=L.last-1; }

13.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时间复杂性及其量级分别是________和________,其平均时间复杂性及其量级分别为________和________。

14.以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。 int locate_sqlist(sqlist L,datatype X)

/*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号；否则回传0*/ {________;

while((i≤L.last)&&(L.data[i-1]!=X))i++; if(________)return(i); else return(0); }

23.INITIATE()的功能是建立一个空表。请在________处填上正确的语句。 lklist initiate_lklist() /*建立一个空表*/

{________________; ________________; return(t); }

24.以下为求单链表表长的运算，分析算法，请在 ________处填上正确的语句。 int length_lklist(lklist head) /*求表head的长度*/ {________;

j=0;

while(p->next!=NULL) {________________; j++;

}

return(j); /*回传表长*/ }

1

25.以下为单链表按序号查找的运算，分析算法，请在____处填上正确的语句。 pointer find_lklist(lklist head,int i) { p=head;j=0;

while(________________) { p=p->next; j++; } if(i==j) return(p); else return(NULL);

}

26.以下为单链表的定位运算，分析算法，请在____处填上正确的语句。 int locate_lklist(lklist head,datatype x)

/*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ { p=head;j=0;

while(________________________________){p=p->next;j++;} if (p->data==x) return(j); else return(0); }

27.以下为单链表的删除运算，分析算法，请在____处填上正确的语句。 void delete_lklist(lklist head,int i)

{ p=find_lklist(head,i-1);

if(____________________________) { q=________________; p->next=p->next; free(q); }

else error(“不存在第i个结点”) }

28.以下为单链表的插入运算，分析算法，请在____处填上正确的语句。 void insert_lklist(lklist head,datatype x,int i) /*在表head的第i个位置上插入一个以x为值的新结点*/ { p=find_lklist(head,i-1);

if(p==NULL)error(“不存在第i个位置”)； else {s=________________;s->data=x; s->next=________________; p->next=s; } }

29.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 lklist create_lklist1()

/*通过调用initiate_lklist和insert_lklist算法实现的建表算法。假定$是结束标志*/

{ ininiate_lklist(head);

i=1;

scanf(“%f”,&x); while(x!=’$’)

{________________; ________________;

2

scanf(“%f”,&x); }

return(head); }

该建表算法的时间复杂性约等于____________，其量级为____________。

30.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 lklist create_lklist2() /*直接实现的建表算法。*/

{ head=malloc(size); p=head;

scanf(“%f”,&x); while(x!=’$’) { q=malloc(size); q->data=x; p->next=q;

________________; scanf(“%f”,&x); }

________________; return(head); }

此算法的量级为________________。 三、单向选择题

1．对于线性表基本运算，以下结果是正确的是 ( ) ①初始化INITIATE(L)，引用型运算，其作用是建立一个空表L=Ф . ② 求表长LENGTH(L)，引用型运算，其结果是线性表L的长度

③读表元GET(L,i), 引用型运算。若1<=i<=LENGTH(L),其结果是线性表L的第i个结点；

否则，结果为0

④定位LOCATE(L,X), 引用型运算.若L中存在一个或多个值与X相等的结点，运算结果为这些结点的序号的最大值；否则运算结果为0

⑤插入INSERT(L,X,i),加工型运算。其作用是在线性表L的第i+1个位置上增加一个以X为值的新结点

⑥删除DELETE(L,i), 引用型运算.其作用是撤销线性表L的第i个结点Ai 2.线性结构中的一个结点代表一个 （ ） ① 数据元素 ② 数据项 ③ 数据 ④ 数据结构

3．顺序表的一个存储结点仅仅存储线性表的一个 （ ） ① 数据元素 ② 数据项 ③ 数据 ④ 数据结构 4．顺序表是线性表的 （ ） ①链式存储结构 ②顺序存储结构 ③ 索引存储结构 ④ 散列存储结构

5.对于顺序表，以下说法错误的是 （ ）

①顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 ②顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 ③顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻

④顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中

6.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ ）为标准操作

3

①条件判断 ②结点移动 ③算术表达式 ④赋值语句

7.对于顺序表的优缺点，以下说法错误的是 （ ） ①无需为表示结点间的逻辑关系而增加额外的存储空间 ②可以方便地随机存取表中的任一结点 ③插人和删除运算较方便

④由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配) ⑤容易造成一部分空间长期闲置而得不到充分利用

8.指针的全部作用就是 （ ） ①指向某常量 ② 指向某变量 ③指向某结点 ④存储某数据

9.除了( ) ，其它任何指针都不能在算法中作为常量出现，也无法显示。 ①头指针 ②尾指针 ③指针型变量 ④空指针

10.单链表表示法的基本思想是指针P表示结点间的逻辑关系，以下说法错误（ ） ①任何指针都不能用打印语句输出一个指针型变量的值

②果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可

③若想修改变量p的值(比如让P指向另一个结点)，则应直接对p赋值 ④对于一个指针型变量P的值。只需知道它指的是哪个结点

⑤结点*ｐ是由两个域组成的记录，p->data是一个数据元素，p->next的值是一个指针

11.单链表的一个存储结点包含 （ ） ①数据域或指针域 ②指针域或链域 ③指针域和链域 ④数据域和链域

12.对于单链表表示法，以下说法错误的是 （ ） ①数据域用于存储线性表的一个数据元素

②指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 ③所有数据通过指针的链接而组织成单链表

④NULL称为空指针，它不指向任何结点，只起标志作用

13.对于单链表表示法，以下说法错误的是 （ ） ①指向链表的第一个结点的指针，称为头指针 ②单链表的每一个结点都被一个指针所指 ③任何结点只能通过指向它的指针才能引用 ④终端结点的指针域就为NULL

⑤尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表

14．有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是 （ ） ①将“指针型变量”简称为“指针”②将“头指针变量”称为“头指针” ③将“修改某指针型变量的值”称为“修改某指针” ④将“p中指针所指结点”称为“P值”

15．设指针P指向双链表的某一结点，则双链表结构的对称性可用（ ）式来刻画 ① p->prior->next->==p->next->next ② p->prior->prior->==p->next->prior ③ p->prior->next->==p->next->prior ④ p->next->next==p->prior->prior

4

16.以下说法错误的是 （ ）

①对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表 ②对单链表来说，只有从头结点开始才能扫描表中全部结点 ③双链表的特点是找结点的前趋和后继都很容易

④对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。

17．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是 （ ）

①real和rear->next->next ②rear->next 和real ③rear->next->next和rear ④rear和rear->next 18.以下说错误的是 ( )

①对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n）

②读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构

③在链表上实现读表元运算的平均时间复杂性为O（1） ④链入、摘除操作在链表上的实现可在O（1）时间内完成

⑤链入、摘除操作在顺序表上的实现，平均时间复杂性为O（n） 19．在串的基本运算中，属于加工型运算的有 （ ）

①EQAL(S,T) ②LENGTH(S)

③CONCAT(S,T) ④REPLACE(S,T,R) ⑤INDEX(S,T) 20. 在串的基本运算中，属于引用型运算的有 （ ）

①ASSIGN(S,T) ②INSERT(S1,i,S2)

③DELETE(S,i,j) ④SUBSTR(S,i,j) ⑤REPLACE(S,T,R) 21．循环链表主要优点是 （ ）

①不再需要头指针了

②已知某个结点的位置后，能够容易找到它的直接前趋 ③在进行插入、删除运算时，能更好地保证链表不断开 ④从表中任一结点出发都能扫描到整个链表

22，每种数据结构都具备三个基本操作:插入、删除和查找，这种说法 （ ）

①正确 ②错误 23．以下说法错误的是 （ ）

①数据的物理结构是指数据在计算机内实际的存储形式 ②算法和程序没有区别，所以在数据结构中二者是通用的 ③对链表进行插人和删除操作时，不必移动结点 ④双链表中至多只有一个结点的后继指针为空 24．以下说法正确的是

①线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继

②线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效

率要低

③在线性表的顺序存储结构中，插人和删除元素时，移动元素的个数与该元素位置有关

④顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动 25．以下说法错误的是 （ ）

①求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

5

②顺序存储的线性表可以随机存取

③由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 ④线性表的链式存储结构优于顺序存储结构 26．以下说法错误的是 （ ）

①线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻 ②在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻 ③在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻 ④线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 27．以下说法正确的是（ ）

①在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素

②在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构

③顺序存储结构属于静态结构，链式结构属于动态结构 ④顺序存储方式只能用于存储线性结构 28.以下说法正确的是（ ）

①顺序存储方式的优点是存储密度大、且插入、删除运算效率高 ②链表的每个结点中都恰好包含一个指针 ③线性表的顺序存储结构优于链式存储结构

④顺序存储结构属于静态结构，链式结构属于动态结构 29.下面关于线性表的叙述正确的是( )

①线性表采用顺序存储，必须占用一片连续的存储单元 ②线性表采用顺序存储，便于进行插人和删除操作

③线性表采用链接存储，不必占用一片连续的存储单元 ④线性表采用链接存储，不便于插人和删除操作

30.线性表L=(a1,a2,...,ai,...,an),下列说法正确的是( )

①每个元素都有一个直接前驱和直接后继 ②线性表中至少要有一个元素

③表中诸元素的排列顺序必须是由小到大或由大到小的

④除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继

31.线性表的逻辑顺序与存储顺序总是一致的，这种说法( )

①正确 ②不正确

32.设p,q是指针,若p=q,则*p=*q ,这种说法( )

①正确 ②不正确

33.线性表若采用链表存储结构时，要求内存中可用存储单元的地址( )

①必需是联系的 ②部分地址必须是连续的 ③一定是不连续的 ④连续不连续都可以

34.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为( )

①p=rear; ②rear=rear->next; rear=rear->next; free(rear); free(p)

③rear=rear->next->next; ④ p=rear->next->next; free(rear); rear->next->next=p->next; free(p);

6

35. 单链表中，增加头结点的目的是为了 ( )

①使单链表至少有一个结点 ②标示表结点中首结点的位置

③方便运算的实现 ④说明单链表是线性表的链式存储实现 36线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着

① 每个结点所代表的数据元素都一样。

② 每个结点所代表的数据元素包含的数据项的个数要相等

③ 不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 ④ 结点所代表的数据元素有同一特点

37．带头结点的单链表Head为空的判定条件是

①Head=Null ②Head->next=NULL ③Head->next=Head 38.非空的单循环链表L的尾结点*P,满足

P->next=NULL P=NULL P->next=L P=L. 39.双向链表结点结构如下： LLink data RLink 其中：LLink是指向前驱结点的指针域： data是存放数据元素的数据域； Rlink是指向后继结点的指针域。

下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双向链表中。不能正确完成要求的算法段是

①Q->LLink=P->LLink; ②P->LLink=Q; Q->Rlink=P; Q->Rlink=P;

P->LLink=Q; P->LLink->Rlink=Q; P->LLink->Rlink=Q; Q->LLink=P->LLink; ③Q->LLink=P->LLink; Q->Rlink=P;

P->LLink->Rlink=Q; P->LLink=Q;

40.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。

①顺序表 ②单链表 ③双链表 ④单循环链表 41．串是任意有限个

①符号构成的集合 ②符号构成的序列 ③字符构成的集合 ④字符构成的序列 五、算法设计

1． 设A=（a1,a2,a3,......an）和B=(b1,b2,.. .,bm)是两个线性表（假定所含数据元素均为整数）。若n=m且ai=bi(i=1,.. .,n),则称A=B;若ai=bi(i=1,.. .,j)且aj+1B。是编写一个比较A和B的算法，当AB是分别输出-1，0或者1。

2，试编写在无头结点的单链表上实现线性表基本运算LOCATE(L,X)、INSERT(L,X，i)和DELETE(L,i)的算法，并和在带头结点的单链表上实现相的算法进行比较。 3．试编写在不带头结点的单链表上实现线性表基本运算LENGTH(L)的算法。

4．假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。

5．设有线性表A=(a1,a2,.. .,am)和B=(b1,b2,.. .,bn).试写合并A、B为线性表C的算

7

法，使得：

?(a1,b1,...,am,bm,bm?1,bn)当m??n;C=? ?(a1,b1,...,an,bn,an?1,...,am)当m?n;假设A、B均以单链表为存储结构(并且m、n显示保存)。要求C也以单链表为存储结构并利用单链表A、B的结点空间。

6，设线性表存放在向量A[arrsize]的前elenum分量中，且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂性。 7．已知单链表L中的结点是按值非递减有序排列的，试写一算法将值为x的结点插入表L中，使得L仍然有序。

8，试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2,.. .,an)逆置为(an,.. .,a2,a1)。

9．假设分别以两个元素值递增有序的线性表A、B表示两个集合(即同一线性表中的元素各不相同)，现要求构成一个新的线性表C，C表示集合A与B的交，且C中元素也递增有序。试分别以顺序表和单链表为存储结构，填写实现上述运算的算法。

10，已知A、B和C为三个元素值递增有序的线性表，现要求对表A作如下运算： 删去那些既在表B中出现又在表C中出现的元素。试分别以两种存储结构(一处种顺序结构，一种链式的)编写实现上述运算的算法。

11．假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的前趋结点。

12．已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。

13.(Josephus环)任给正整数n、k，按下述方法可得排列1，2，??,n的一个置换:将数字1，2，.. .,n环形排列(如图算法设计题13.所示)，按顺时针方向从1开始 计数；计满K时输出该为之上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10,k=3时，输出的置换是3，6，9，2，7，

1，8，5，10，

4。试编写一算法，对输人的任意正整数n、k，输出相应的置换

14·在双链表上实现线性表的下列基本运算(a)初始化； (b)定位(c)插入(d)删除。 15·设有一双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在双链表上进行一次LOCATEL，X)运算时，令元素值为X的结点中freq域的值增1，并使此链表中结点保持按访问频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。试编写实现符合上述要求的LOCATE运算的算法。

16·若X和Y是用结点大小为1单链表表示的串，设计一个算法找出X中第一个不在y中出现的字符。

17．在顺序串上实现串的判等运算EQUAL(S,T)。

8

18．在链串上实现判等运算EQUAL(S,T)。

19．若S和T是用结点大小为1的单链表存储的两个串（S、T为头指针），设计一个算法将串S中首次与串T匹配的子串逆值。

20．用串的其他运算构造串的子串定位运算index。

第三章 栈、队列和数组

6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。 7 以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。 int InitStack(SqStackTp *sq) { ________;

return(1);}

8 以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。 Int Push(SqStackTp *sq,DataType x)

{ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{________________: ________________=x;

return(1);}

}

9 以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。 Int Pop(SqStackTp *sq,DataType *x)

{if(sp->top==0){error(“下溢”);return(0);} else{*x=________________; ________________; return(1);} }

10. 以下运算实现在顺序栈上判栈空，请在________________处用适当句子予以填充。

Int EmptyStack(SqStackTp *sq)

{if(________________) return(1); else return(0); }

11.以下运算实现在顺序栈上取栈顶元素，请在________________处用适当句子予以填充。

Int GetTop(SqStackTp *sq,DataType *x) {if(________________) return(0); else{*x=________________; return(1);} }

12. 以下运算实现在链栈上的初始化，请在________________处用请适当句子予以填充。

Void InitStacl(LstackTp *ls){ ________________;}

13.` 以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。 Void Push（LStackTp *ls,DataType x）

9

{ LstackTp *p;p=malloc(sizeof(LstackTp)); ________________; p->next=ls;

________________; }

14．以下运算实现在链栈上的退栈，请在________________处用请适当句子予以填充。

Int Pop(LstackTp *ls,DataType *x) {LstackTp *p; if(ls!=NULL) { p=ls;

*x=________________; ls=ls->next;

________________; return(1)； }else return(0); }

15. 以下运算实现在链栈上读栈顶元素，请在________________处用请适当句子予以填充。

Int Get Top(LstackTp *ls,DataType *x)

{ if(ls!=NULL){ ________________;return(1);} else return(0); }

20．以下运算实现在循环队上的初始化，请在________________处用适当句子予以填充。

Void InitCycQueue(CycqueueTp *sq) { ________________;sq->rear=0;}

21. 以下运算实现在循环队上的入队列，请在________________处用请适当句子予以填充。

Int EnCycQueue(CycquereTp *sq,DataType x)

{ if((sq->rear+1)%maxsize== ________________) {error(“队满”);return(0); else{ ________________;

________________ ________________; return(1); }

22. 以下运算实现在循环队上的出队列，请在________________处用适当句子予以填充。

Int OutCycQueue(CycquereTp *sq,DataType *x)

{if(sq->front== ________________){error(“队空”);return(0)；} else{ ________________; ________________; return(1); } }

23. 以下运算实现在循环队上判队空，请在________________处用适当句子予以填

10

充。

Int EmptyCycQueue(CycqueueTp sq)

{if(________________) return(1); else return(0); }

24. 以下运算实现在循环队上取队头，请在________________处用适当句子予以填充。

Int GetHead(CycqueueTp sq,DataType *x)

{ if(sq.rear== ________________return(0); else{ *x=sq.data[________________ ]; return(1); }

25.链队在一定范围内不会出现________________的情况。当lq.front==lq.rear试，队中无元素，此时________________。

26．以下运算实现在链队上的初始化，请在________________处用适当句子予以填充。

void InitQueue(QueptrTp *lp) { LqueueTp *p;

p=(LqueueTp *)malloc(sizeof(LqueueTp))； ________________； lq->rear=p;

(lq->front)->next=________________; }

27. 以下运算实现在链队上的入队列，请在________________处用适当句子予以填充。

Void EnQueue(QueptrTp *lq,DataType x) { LqueueTp *p;

p=(LqueueTp *)malloc(sizeof(LqueueTp)); ________________=x; p->next=NULL;

(lq->rear)->next=________________; ________________;

}

28. 以下运算实现在链队上的出队列，请在________________处用适当句子予以填充。

int OutQueue(QuetrTp *lq,DataType *x) { LqueueTp *s;

if(lq->front==lq->rear){erroe(“队空”)；return(0);} else { s=(lq->front)->next;

________________=s->data;

(lq->front)->next=________________； if(s->next==NULL) lq->rear=lq->front; free(s); return(1); } }

11

29. 以下运算实现在链队上判队空，请在________________处用适当句子予以填充 int EmptyQueue(QueptrTp *lq)

{ if(________________) return(1)； else return(0); }

30. 以下运算实现在链队上读队头元素，请在________________处用适当句子予以填充。

Int GetHead(QueptrTp lq,DataType *x) { LqueueTp *p;

if(lq.rear==lq.front) return(0); else{________________;

________________ =p->data; return(1); } }

38．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在___________处用适当的句子用以填充。

Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b)

{ (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu; if(a.tu) { q=1;

for(col=1; ___________;col++) for(p=1;p<=a.tu;p++) if(___________==col)

{(*b).data[q].i=a.data[p].j; (*b).data[q].j=a.data[p].i; (*b).data[q].v=a.data[p].v; ___________; } }

39．基于三元组的稀疏矩阵转置的处理方法有两种，以下计算按照矩阵A的三元

组a.data的次序进行转置，请在___________处用适当的句子用以填充。

Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b) { (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu=a.tu; if(a.tu)

{for(col=1;___________;col++) num[col]=0; for(t=1;t<=a,tu;t++) num[a.data[t].j]++; cpot[1]=1;

for(col=2;col<=a.nu;col++) cpot[col]=___________; for(p=1;p<=a.tu;p++) { col=a.data[p].j; q=cpot[col];

(*b).data[q].i=a.data[p].j; (*b).data[q].j=a.data[p].i; (*b).data[q].v=a.data[p].v; __________________________;

12

} } }

三、单项选择题

1．在以下栈的基本运算中，不是加工型运算的是 （ ）

①lnitStack(S) ②Push(S,X) ③Pop(S) ④empty(S) 2.以下说法正确的是 ( )

①因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ②因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ③对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢” ④对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。 3．在以下队列的基本运算中，不是加工型运算的是 （ ）

①InitQueue(Q) ②EnQueue(Q,X) ③OutQueu(Q,X) ④GetHead(Q,x) 4.顺序队列的人队操作应为 ( )

①sq.rear=sq.rear+1 sq.data[sq.rear]=x ②sq.data[sq.rear]=x sq.rear=sq.rear+1 ③sq.rear=(sq.rear+1)% maxsize; sq.data[sq.rear]=x

④sq.data[sqrear]=x sq.rear=(sq.rear+1)% maxsize 5.循环队列的人队操作应为 ( )

①sq.rear=sq.rear+1 sq.data[sq.rear]=x ②sq.data[sq.rear]=x sq.rear=sq.rear+1 ③sq.rear=(sq.rear+1)% maxsize sq.data[sq.rear]=x

④sq.data[sq.rear]=x sq.rear=(sq.rear+1)% maxsize 6. 顺序队列的出队操作为 ( )

①sq.front=(sq.front+1)% maxsize ②sq.front=sq.front+1

③sq.rear=(sq.rear+1)% maxsize ④sq.rear=sq.rear+1

7. 循环队列的出队操作为 ( )

①sq.front=(sq.ftont+1)% maxsize ②sq.front=sq.front+1

③sq.rear=(sq.rear+)% maxsize ④sq.rear=sq.rear+1

8.循环队列的队满条件为 ( )

①(sq.rear+1) % mazsize ==(sq.front+1) % maxsize; ②(sq.rear+1 % maxsize ==sq.front+1 ③sq.(rear+1) % maxsize ==sq.front ④sq.rear ==sq.front 9.循环队列的队空条件为 ( )

①(sq.rear+1) % maxsize ==(sq.front+1) % maxsize ②(sq.rear+) % maxsize ==sq.front+1 ③(sp.rear+1) % maxsize ==sq.front ④sq.rear == sq.front

10.数组的数据元素类型DataType可根据实际需要而定义。以下说法完全正确的是 ( )

①数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分

13

②数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体 ③数组的读、写运算只能读取或修改一个数据元素的一部分 ④数组的读、写运算只能读取或修改一个数据元素整体 11．对于以行序为主序的存储结构来说，在数组A[c1···d1，c2···d2]中，c1和d1分别为

数组A的第一个下标的上、下界，c2?d2分别为第二各下标的上、下界，每个数据元素占K

个存储单元，二维数组中任一元素a[i,j]的存储位置可由( )式确定. ①Loc[i,j]=[( d2-c2+1)(i- c1)+(j- c2)]*k

②Loc[i,j]=loc[c1, c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k ③Loc{i,j}=A[c1, c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k ④Loc[i,j]=loc[0,0]+[( d2- c2+1)(i- c1)=(j- c2)]*k

12对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定. ①Loc[i,j]=A[m,n]+[(n+1)*i+j]*k ②Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k ③Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k ④Loc[i,j]=[(n+1)*i+j]*k

13.线性表的顺序存储结构是一种( )的存储结构,线性表的链式存储结构是一种（ ）的存储结构。

① 随机存取 ② 顺序存储

14．如果以链表作为栈的存储结构，则退栈操作是 ( ) ①必须判别栈是否满 ②必须判别栈是否空 ③判别栈元素的类型 ④对栈不做任何操作

15对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是 ( )

①按照矩阵A的列序来进行转置，算法的时间复杂度为0(nu+tu)

②按照A的三元组a.data的次序进行转置，算法的时间复杂度为O(nu*tu) ③按照矩阵A的列序来进行转置的方法称快速转置

④按照矩阵A的列序进行转置,对于tu<

16．稀疏矩阵的压缩存储方法是只存储 ( ) ①非零元素 ② 三元祖（i,j, aij） ③ aij ④ i,j 17．基于三元组的稀疏矩阵，对每个非零元素aij,可以用一个（ ）唯一确定。 ①非零元素 ②三元组(i,j,aij) ③ aij ④ i,j

18如果以链表作为栈的存储结构,则退栈操作时 ( )

①必须判别栈是否满 ②判别栈元素的类型 ③必须判别栈是否空 ④ 队栈不做任何判别

19．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear

为队为指针，则执行出队操作的语句为 （ ）

①front=front+1 ② front=（front+1）%m ③rear=(rear+1)%m ④ front=(front+1)%(m+1) 20.三角矩阵可压缩存储到数组（ ）中。

①M[1:n(n+1)/2+1] ② M[1:n(n+1)/2] ③M[n(n+1)/2+1] ④M[n(n+1)/2]

14

21.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是 （ ）

①2 ② 3 ③ 5 ④6

22．设有一顺序栈已含3个元素，如下图所示，元素a4正等待进栈。那么下列4个序列

中不可能出现的出栈序列是 （ ） 0 1 2 3 maxsize-1 sq a1 a2 a3 ↑top

①a3,a1,a4,a2 ②a3,a2,a4,a1 ③ a3,a4,a2,a1 ④a4,a3,a2,a1

23.向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为 （ ） ①Top->next=s ② s->next=Top->next;Top->next=s ③s->next=Top;Top=s ④ s->next=Top;Top=Top->next

24.从栈顶指针为Top的链栈中删除一个结点，并将被删节点的值保存到x中，其操作步骤为（ ）

①x=Top->data;Top=Top->next ②Top=Top->next;x=Top->data ③x=Top;Top=Top->next ④ x=Top->data

25.在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（ ） ①f->next=c;f=s ②r->next=s;r=s ③s->next=r;r=s ④ s->next=f;f=s

26常对数组进行的两种基本操作是 （ ） ①建立与删除 ② 索引与修改 ③ 查找与修改 ④ 查找与索引

27．链栈与顺序栈相比，有一个比较明显的优点即 （ ） ①插入操作更方便 ② 通常不会出现栈满的情况 ③不会出现栈空的情况 ④ 删除操作更方便

28．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就

完成了对该矩阵的转置运算，这种观点 （ ）

①正确 ②错误

29。二为数组M[i,j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从O到4，列下标j的范围从O到5。M按行存储时元素M[3,5] 的起始地址与M按列存储时元素( )的起始地址相同。

①M [2,4] ② M[3,4] ③M[3,5] ④M[4,4]

30.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 （ ）

① e d c b a ②d e c b a ③d c e a b ④a b c d e 31.一个队列的人列序是1，2，3，4，则队列的输出系列是 （ ） ① 4，3，2，1 ② 1，2，3，4， ③1，4，3，2 ④ 3，2，4，1 32．设计一个判别表达式中左、右括号是否配对出线的算法，采用（ ）数据结构最佳。

①线性标的顺序存储结构 ②栈

③ 队列 ④ 线性表的链式存储结构

33．若已知一个栈的输入序列为1，2，3，...,n,其输出序列为P1、P2、...Pn。若p1=n,则P1为

15

①i ②n=i ③ n-i+1 ④ 不确定 34．以下说法正确的是

①顺序队和循环队的队满和队空判断条件是一样的 ②栈可以作为实现过程调用的一种数据结构

③插人和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用

④在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件front=rear 35. 以下说法正确的是 ①数组是同类型值的集合 ②数组是一组相继的内存单元

③数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树形的 ④使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间 10.阅读下列程序，写出程序的运行结果。 # define sqstack_maxsize 40 For(ch=’A’;ch<=’A’+12;ch++) typedef struct sqstack { Push(&sq,ch); { char data[sqstack_maxsize]; printf(“%c”,ch); int top; } } SqStackTp; printf(“\\n”); main() while(!EmptyStack(sq)) { SqStackTp sq; { Pop(&sq,&ch); int i; printf(“&c”,ch); char ch; } printf(“\\n”); InitStack(&sq); } 11.阅读下列算法，写出其完整的功能。 Void reverse_list( LinkedListTP { Push(&lsdata); *head) p=p->next;} { LstackTP ls,p; p=head->next; DataType x; While(! EmptyStack(&ls)) InitStack(&ls); { Pop(&l,&x); p->data=x; p=head->next; p=p-next;} While(p!=NULL) } 五、算法设计

1.某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和货车类， 上渡船的有如下规定：同类车先到先上船；且每上4辆客车，才允许上一辆货车；若等待客车不足4辆，则以火车代替，若无货车等待允许客车都上船。试写一算法模拟渡口管理。

可以在一个数组中保存两个栈：一个栈以数组的第一个单元作为栈底，另一个

栈以数组的最后一个单元作为栈底（如下图所示）。设S是其中一个占，是分别编写过程push(S,X)(元素X入栈)， 出栈pop(S)和取栈顶元素Top(S).题示：设其中一个栈为0，另一栈为1。

0 1 2 M-1 M M+1

······

16

栈0底 栈0顶 栈1顶 栈1底

3．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的初始化队列、入队列和出队列算法。 4．假设以数组cycque[m](假设数组范围在0..m)存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法。

5．编写算法:按行优先存储顺序，将稀疏矩阵转换为三元组的表示形式。

6．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。

7．假设一个算术表达式中可以包含三中括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号与“{”和“}”，且这三种括号可按任意的次序嵌套试用，如（.. .[.. .{.. .}.. .[.. .].. .].. .( .. .[.. .].. .)。试利用栈的运算编写判断给定表达式中所含括号是否正确 配对出现的算法（可设表达式已存入字符型数组中）。

8．已知Ackerman函数定义如下：

?n?1当m?0时?akm(m,n)=?akm(m?1,1)当m?0,n?0时

?akm(m?1,akm(m,n?1))当m?0,n?0时?试写出递归算法。

9．设函数f(m,n)按下式定义（ m,n为）0的整数）

?m?n?1当m*n?0时f(m,n)=?

?f(m?1,f(m,n?1))当m*n?0时试写出计算函数的递归过程。

10．设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为w1,w2,.. .，wn.问能否从这n件物品中选择若干件放入此背包，使得放入的重量之和正好为S.如果存在一种符合上述要求的选择，则称此背包问题有解（或承接为真），否则此问题无解（或结为假），试用递归和非递归两种方法设计此背包问题的算法。 11．借助栈(可用栈的基本运算)来实现单链表的逆置运算。

第六章 树

17．以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。

Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶子数count的初值为0*/

{if(t!=NULL)

{if((t->lchild==NULL)&&(t->rchild==NULL))________; countleaf(t->lchild,&count); ________ } }

23．根据文字说明，请在以下横线处填充适当的语句。

17

采用静态链表作存储结构，设置一个大小为2n-1的数组,令数组每个元素由四个域组成：wt是结点的权值；lchild、rchild分别为结点的左、右孩子指针；parent是结点的双亲在数组中的下标。其数组元素类型定义如下：

typedef struct

{float wt /*权值*/ int parent,lchild rchild; /*指针域*/ }node;

typedef node hftree[2*n-1];

在这种存储结构上的哈夫曼算法可描述如下：

void Huffman(int k,float W[k],hftree T) /*求给定权值W的哈夫曼树T*/

{int i,j,x,y; float m,n;

for(i=0;i<2*k-1;i++)

{ T[i].parent=-1;T[i].lchild=-1;T[i].rchild=-1; if(________)T[i].wt=W[i]; else T[i].wt=0 }

for(i=0;i

{ x=0;y=0;m=maxint;n=maxint; for(j=0;j

if((T[j].wt

else if((T[j].wt

T[k+i].lchild=________;T[k+i].rchild=________; }

32．有m个叶子结点的哈夫曼树，其结点总数为________。

三、单向选择题

1．以下说法错误的是 ( ) ①树形结构的特点是一个结点可以有多个直接前趋 ②线性结构中的一个结点至多只有一个直接后继

18

③树形结构可以表达(组织)更复杂的数据 ④树(及一切树形结构)是一种\分支层次\结构 ⑤任何只含一个结点的集合是一棵树

2，以下说法错误的是( ) ①二叉树可以是空集 ②二叉树的任一结点都有两棵子树 ③二叉树与树具有相同的树形结构

④二叉树中任一结点的两棵子树有次序之分

3以下说法错误的是( ) ①完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 ②在三叉链表上，二叉树的求双亲运算很容易实现 ③在二叉链表上，求根，求左、右孩子等很容易实现 ④在二叉链表上，求双亲运算的时间性能很好

4、以下说法错误的是( ) ①一般在哈夫曼树中，权值越大的叶子离根结点越近 ②哈夫曼树中没有度数为1的分支结点

③若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点

④若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树 5．深度为6的二叉树最多有( )个结点( ) ①64 ②63 ③32 ④31

6．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从

左到右的顺序对结点编号，那么编号为41的双结点编号为 ( ) ①42 ②40 ③21 ④20 7．任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置 ( ) ①肯定发生变化 ②有时发生变化 ③肯定不发生变化 ④无法确定

8．设二叉树有n个结点，则其深度为( ) ①n-1 ②n ③5floor(log2n) ④无法确定

9．设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（ ）个

①k+1 ②2k ③2k-1 ④2k+1

10.下列说法正确的是( ) ①树的先根遍历序列与其对应的二叉树的先根遍历序列相同 ②树的先根遍历序列与其对应的二叉树的后根遍历序列相同 ③树的后根遍历序列与其对应的二叉树的先根遍历序列相同 ④树的后根遍历序列与其对应的二叉树的后根遍历序列相同

11．下列说法中正确的是( ) ①任何一棵二叉树中至少有一个结点的度为2 ②任何一棵二叉树中每个结点的度都为2

③任何一棵二叉树中的度肯定等于2 ④任何一棵二叉树中的度可以小于2

12．一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（ ）遍历方式就可以得到这棵二叉树所有结点的递增序列。 ①先根 ②中根 ③后根 ④层次

13．设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有（ ）个结点。 ①n1-1 ②n1 ③n1+n2+n3 ④n2+n3+n4

19

14．森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的左孩子上有（ ）个结点。 ①n1-1 ②n1 ③n1+n2+n3 ④n2+n3+n4

15.对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。

①0 ②1 ③2 ④不存在这样的二叉树 16．讨论树、森林和二叉树的关系，目的是为了（ ） ①借助二叉树上的运算方法去实现对树的一些运算 ②将树、森林按二叉树的存储方式进行存储 ③将树、森林转换成二叉树

④体现一种技巧，没有什么实际意义

17．如图选择题17所示二叉树的中序遍历序列是（ ）

①abcdgef ② dfebagc ③dbaefcg ④defbagc

18.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（ ）

①acbed ②deabc ③decab ④cedba 19.如果T2是由有序树T转化而来的二叉树，那么T中结点的前序就是T2中结点的（ ） ①前序 ②中序 ③后序 ④层次序 20．如果T2是由有序树T转化而来的二叉树，那么T中结点的后序就是T2中结点的（ ） ①前序 ②中序 ③后序 ④层次序

21．某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是

dgbaechf,则其后序遍历的结点访问顺序是 （ ）

①bdgcefha ②gdbecfha ③④ bdgechfa ④ gdbehfca 22.在图选择题22中的二叉树中，（ ）不是完全二叉树。

20

23、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 ( )①正确 ②错误

24、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 ( )①五确 ②错误

25，二叉树是每个结点的度不超过2的有序树的特殊情况，这种说法 ( ) ①正确 ②错误

26·树最适合用来表示 ( ) ①有序数据元素 ②无序数据元素

③元素之间具有分支层次关系的数据 ④元素之间无联系的数据 27，深度为5的二叉树至多有( )个结点。

①16 ②32 ③31 ④10

28、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于（ ）数据结构

①栈 ②树 ③双向队列 ④顺序表

29.堆(Heap)是 ( ) ①完全二叉树 ②线性表 ③满二叉树

30、下列说法中正确的是 ( ) ①二叉树中任何一个结点的度都为2 ②二叉树的度为2

③任何一棵二叉树中至少有一个结点的度为2 ④一棵二叉树的度可以小于2

31、设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是（ ） ①2h ②2h-1 ③2h-1 ④2h+1-1 32、设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( )

①都不相同 ②完全相同 ③先序和中序相同，而与后序不同 ④中序和后序相同，而与先序不同 33·以下说法错误的是 ( ) ①存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同 ②二叉树是树的特殊情形

③由树转换成二叉树，其根结点的右子树总是空的

④在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树 34、以下说法正确的是 ( ) ①先根遍历树和前序遍历与该树对应的二叉树，其结果不同 ②后根遍历树和前序遍历与该树对应的二叉树，其结果不同 ③前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同 ④后序遍历森林和中序遍历与该森林对应的二叉树，其结果不同

21

35·以下说法正确的是 ( ) ①一般来说，若深度为k的n个结点的二叉树具有最小路径长度，那么从根结点到第k-1层具有最多的结点数为2k-1-1余下的n-2k-1+1个结点在第k层的任一位置上 ②若有一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。

③若一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序遍历序列中的最后一个结点。

④在二叉树中插人结点，该二叉树便不再是二叉树

36、以下说法正确的是( ) ①若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。

②若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序离历序列中的最后一个结点

③二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。

④在二叉树中，具有一个子女结点，在中序遍历序列中，它没有后继子女结点。 37、以下说法错误的是 ( ) ①哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

②若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。

③已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。

④在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。

四、简答及应用题。

5．为什么图简答题所示的结构都不是树形结构？详细说明理由。

6．分别画出含3个结点的树与二叉树的所有不同形态。

7．分别画出图简答题7-1所示二叉树的二叉链表、三叉链表和顺序存储结构。

22

8．分别写出图简答题4.1（a）所示二叉树的先根、中根和后根序列。 9.试找出分别满足下列条件的所有二叉树：

（1） 先根序列和中根序列相同； （2）中根序列和后根序列相同； （ 3 ）先根序列和后根序列相同。

10．已知一棵二叉树的中根序列和后根序列分别为BDCEAFHG和EDCBHGEA，试画出这棵二叉树。

11． 试分别画出图简答题11-1所示树的孩子链表、孩子兄弟链表和静态双亲链表。

12．分别给出简答题11.1图中树的先根、后根和层次遍历的结点访问序列。 13．将图简答题13-1所示的林转换成二叉树。

14．分别画出图简答题14-1所示各二叉树对应的林。

23

15．给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树。17．已知一棵二叉树的前根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树。

18．设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码。

19．有一二叉树如图19-1所示，试画出它的顺序存储结构示意图。

20．将图简答20-1所示森林转换为二叉树。

第七章 图

填空：

21.以下是图的深度优先算法，请在________处填充适当的语句。 Dfs(GraphTp g,int v) { ArcNodeTp *p; printf(“%d”,v); visited[v]=1;

p=________________; while(p!=NULL)

{if(!________________) Dfs(g,p->adjvex);

24

p=________________; }

}

22.以下是图的广度优先搜索算法，请在________处填充适当的语句。 Bfs(GraphTp g,int v) {QueptrTp Q;

ArcNodeTp *p; InitQueue(&Q); printf(“%d”,v); visited[v]=1; ________________

while(!EmptyQueue(Q)) {________________;

p=g.adjlist[v].firstarc; while(p!=NULL)

{if(!visited[p->adjvex])

{printf(“%d”,p->>adjvex); visited[[->adjvex]=1; EnQueue(&Q,p->adjvex);

}

________________; } } }

一、 单项选择题

1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（ ）

①G’为G的子图 ②G’为G的连通分量 ③G’为G的极小连通子图且V’=V ④G’是G的无环子图

2.任何一个带权的无向连通图的最小生成树（ ）

①只有一棵 ②有一棵或多棵 ③一定有多棵 ④可能不存在 3.设图G采用邻接表存储，则拓扑排序算法的时间复杂度为（ ）

①O(n) ②O(n+e) ③O(n*n) ④O(n*e) 4.含n个顶点的连通图中的任意一条简单路径，其长度不可能超过 （ ）

①1 ② n/2 ③ n-1 ④n

5．一有向图G的邻接表存储结构如图单项选择5所示。现按深度优先遍历算法，从顶点V1出发，所得到的顶点序列是 ( ）

25

①V1,V3, V2 ,V4, V5 ②V1, V3, V4, V2, V5 ③V1,V2, V3, V4, V5 ④V1, V3, V4, V5 , V2

6.在无向图中，所有顶点的度数之和是所有边数的（ ）倍。

①0.5 ②1 ③2 ④4

7.在有向图中，所有顶点的入度之和是所有顶点出度之和的（ ）倍。 （ ）

①0.5 ② 1 ③ 2 ④4

8．在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 （ ）

①先根遍历 ② 中根遍历 ③ 后根遍历 ④按层次遍历 9．在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 （ ）

①先根遍历 ②中根遍历 ③后根遍历 ④按层次遍历 10．判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用 （ ） ①求关键路径方法②求最短路径的Dijkstra方法③广度优先遍历方法④深度优先遍历方法

11．在图单项选择中，从顶点V1出发，按广度优先遍历图的顶点序列是 （ ） ①V1 V3 V5 V4 V2 V6 V7 ②V1 V2 V4 V7 V6 V5 V3 ③V1 V5 V3 V4 V2 V7 V6 ④V1 V4 V7 V2 V6 V5 V3 12.在图单项选择中，从顶点V1出发,广度遍历图的顶点序列是 （ ） ①V1 V5 V3 V4 V2 V6 V7 ②V1 V5 V3 V4 V2 V7 V6 ③V1 V7 V2 V6 V4 V5 V3 ④V1 V2 V4 V7 V6 V5 V3

13.设有6个结点的无向图，该图至少应有（ ）条边能确保是一个连通图。 （ ） ① 5 ② 6 ③ 7 ④ 8

14.以下说法正确的是 （ ） ①连通图的生成树，是该连通图的一个极小连通子图。

②无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 ③任何一个有向图，其全部顶点可以排成一个拓扑序列。 ④有回路的图不能进行拓扑排序。

15以下说法错误的是（ ） ①用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

②邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。 ③存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了

③用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第 i行第j列的元素是否为0即可。

16．以下说法正确的是（ ） ①连通分量是无向图中的极小连通子图。 ②强连通分量是有向图中的极大强连通子图。

③在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。 ④对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。 四、简答及应用

3． 给出无向图简答题3中g1的邻接矩阵和邻接表。

26

4．分别给出图简答题3中g2的邻接矩阵、邻接表和逆邻接表。

5．分别给出图简答题3中g3从v5出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。

6．求出图简答题6-1的连通分量。

7．求出带权图简答题7-1的最小生成树 8．写出有向图简答题8-1的拓扑排序序列。 9．给出网图简答题9-1的邻接矩阵表示。

10．已知连通网的邻接矩阵如下，试画出它所表示的连通网及该连通网的最小生成树。

11．对于图简答题11-1从其邻接表中回答下列问题： （1） 图中有多少条弧？

（2） 图中是否存在从i到j的弧？ （3） 如何求顶点i的出度？

27

12．图简答题11-1所示为一有向图，请给出该图的下述要求： （1） 每个顶点的入/出度。 （2） 邻接矩阵。 （3） 邻接表。 （4） 逆邻接表。

13．拓扑排序的结果不是唯一的，对图简答题13-1进行拓扑排序，试写出其中任意5个不同的拓扑排序列。

14．对m个顶点的无向图G，采用邻接矩阵，如何判别下列有关问题： （1） 图中有多少条边？

（2） 任意两个顶点i和j是否有边相连？ （3） 任意一个顶点的度是多少？

15.已知图G的邻接表如图简答题15-1所试，顶点V1为出发点，完成要求： （1） 深度优先搜索的顶点序列； （2） 广度优先搜索的顶点序列；

（3） 由深度优先搜索得到的一棵生成树； （4） 由广度优先搜索得到的一棵生成树。 Vertex fi

16.设有一无向图G=(V,E),其中

V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)}。

（1） 按上述顺序输入后，画出其相应的邻接表；

（2） 在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。

17．图简答题17-1所示为一无向连通网络，先要求根据prim算法构造出它的最小生成树。

28

五、算法设计

1．写出将一个无向图的邻接矩阵转换成邻接表的算法。 2．写出将一个无向图的邻接表转换成邻接矩阵的算法。

3．试以邻接矩阵为存储结构，分别写出连通图的深度优先和广度优先搜索算法。 4．写出建立一个有向图的逆邻接表的算法。

5．G为一n个顶点的有向图，其存储结构分别为： （1） 邻接矩阵； （2） 邻接表。

请写出相应存储结构上的计算有向图G出度为0的顶点个数的算法。 6．以邻接表作存储结构，给出拓扑排序算法的实现。

第九章 查找表

二、填空题

12.以下算法在有序表R中用二分查找法查找键值等于K的元素，请分析程序，并在________上填充合适的语句。

int binsearch(sqtable R,keytype K)

{low=1;hig=R.n;/*置查找区间初值。low,hig分别标记查找区间的下、上界*/ while(low<=hig)

{mid=（low+hig)/2; switch

{case K==R.item[mid].key:return(mid);/*找到，返回位置mid*/ case KR.item[mid].kiy:________;break;/*缩小区间*/ } }

return(0);/*若区间长度已为0但仍不成功，则返回0，表示查找不成功*/ }

23.以下算法在指针T所指的二叉排序树上查找键值等于K的结点。成功时回送指向该结点的指针；否则回送空指针。请分析程序，并在________填充合适的语句。 bitreptr search_bst(bitreptr T,keytype K) {if(T==NULL)return(NULL); else swith

{case T->key==K:________;

case________: rerutn(search_bst(T->lchild,K)); case________: rerutn(search_bst(T->rchild,K));

29

} }

31.以下算法在开散列表HP中查找键值等于K的结点，成功时返回指向该结点的指针，不成功时返回空指针。请分析程序，并在________上填充合适的语句。 pointer research_openhash(keytype K,openhash HP) {i=H(K); /*计算K的散列地址*/

p=HP[i]; /*i的同义词子表表头指针传给p*/

while(________)p=p->next;/*未达表尾且未找到时，继续扫描*/ ________; }

32以下算法实现若开散列表HP中无键值为K结点，则插入一个这样的结点。请分析程序并在________上填充合适的语句。

void insert_openhash(keytype K,openhash HP) {if(research_openhash(K,HP)==NULL) {i=H(K);

q=malloc(size);q->key=________; /*生成新结点*/

________=HP[i];HP[i]=________; /*前插法链入新结点*/ } }

33.以下算法实现若开散列表HP中存在键值为K结点，则将其删除。请分析程序并在________上填充合适的语句。

void delete_openhash(keytype K,openhash HP) {i=H(K);

if(HP[i]==NULL)return;/*空表则退出*/ p=HP[i];

if(p->key==K){_______=p->next;free(p);return;} /*表首结为待点时的删除*/

while(p->next!=NULL) /*其他情况下的删除*/ {q=p;p=p=->next;

if(p->key==K){________=p->next;delete(p);return;} } }

36.以下算法假定以线性探测法解决冲突，在闭散列表HL中查找键值为K的结点，成功时回送该位置；不成功时回送标志-1。请分析程序，并在________上填充合适的语句。 int search_cloxehash(keytype K,closehash HL) {d=H(K); /*计算散列地址*/ i=d;

while(HL[i].key!=K&&(i!=d-1)i=______;/*未成功且未查遍整个HL时继续扫描*/

if(________)reurn(i); /*查找成功*/ else return(-1); /*查找失败*/ }

45.设线性表(a1,a2,?,a500)元素的值由小到大排列。对一个给定的k值，用二分法检索查找表中与k相等的元素，在检索不成功的情况下至多较________次。 46.设线性表L=（a1,a2,?,an)(n>2),表中元素按值的递增顺序排列。对一个给定的值k，

30

分别用顺序检索和二分法检索查找与k相等的元素，比较次数分别为s和b ，若检索不成功，则s和b的数量关系是________。

47.设有两个散列函数H1(k)=k mod 13 和H2(k)=k mod 11+1，散列表为T[0?12]，用双重散解决冲突。函数H1用来计算散列地址，当发生冲突时，H2作为计算下一个探测地址的地址增量，假定在某一时刻T的状态为：

T: 0 1 2 3 4 5 6 7 8 9 10 11 12 80 85 34 下一个被插入的关键码是42，其插入的位置是:______________。 48.设有一个已按各元素的值排好序的线性表，长度为125，对给定的k值，用二分法查找与k相等的元素，若查找成功，则至少需要比较________次，至多需比较________次。 三、单项选择题

1．以下说法错误的是 （ ） ①数字分析法对健值的各位进行分析，选择分布较均匀的若干位组成散列地址。 ②除余法选择一个适当的正整数p,以p除健值以所得的余数作为散列地址。 ③平方取中法以健值平方的中间几位作为散列地址。

④基数转换法将健值看成另一种进制的数再转换成原来进制的数，然后选择其中几位作为散列地址。

⑤随机数法选择一个随机函数random,以健值在该函数下的值作为散列地址。

2．以下所法正确的是 （ ） ①数字分析法需事先知道所有可能出现的健值及所有健值的每一位上各数字的分布情况，并且健值的位数比散列地址的位数多。 ②除余法要求事先知道全部健值。

③平方取中法需要事先掌握健值的分布情况。 ④随机数法适用于健值不相等的场合。 3．除余法选择一正整数p，以健值除以p所得的余数作为散列地址。通常选p为（ ） ①小于或等于散列表长的素数。

②接近表长的且不与组成关键字的字符基数直接相关的质数。 ③大于或等于散列表长的素数。 ④接近表长的质数。

4．顺序查找法适合于（ ）存储结构的查找表。

①压缩 ② 散列 ③索引 ④顺序或链式

5．对采用二分查找法进行查找运算的查找表，要求按（ ）方式进行存储。 ①顺序存储 ② 链式存储

③顺序存储且结点按关键字有序 ④ 链式存储且结点按关键字有序

6．设顺序表的长为n,则其每个元素的平均查找长度是 （ ） ①n ② (n-1)/2 ③ n/2 ④ (n+1)/2

7.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（ ）次比较后查找成功。 ①2 ② 3 ③ 4 ④ 12 8．静态查找表与动态查找表两者的根本差别在于 （ ） ①逻辑结构不同 ② 存储实现不同

③施加的操作不同 ④ 数据元素的类型不同

9．长度为12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的ASL值是 （ ） ①37/12 ② 62/13 ③ 39/12 ④49/13

31

10.在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数（ ） ①n ②1 ③ n+1 ④n-1 11.二分查找法适用于存储结构为（ ）的，且按关键字排序的线性表。 （ ） ①顺序存储 ② 链接存储 ③ 顺序存储或链接存储 ④索引存储

12．用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为 ①O（n2） ② O(nlog2n) ③ O（n） ④ O(log2n)

13．用二分查找法对具有n个结点的线性表查找的时间复杂性量级为 （ ） ①O(n2) ② O(nlog2n) ③ O(n) ④O(log2n)

14．二叉排序树的查找和折半查找的时间性能相同。这种说法 （ ） ①正确 ② 错误

15．与其他查找方法相比，散列查找法的特点是 （） ①通过关键字比较进行查找

②通过关键字计算记录存储地址进行查找

③通过关键字计算记录存储地址，并进行一定的比较进行查找

16．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，

在查找成功的情况下，所探测的这些位置上的健值 （） ①一定都是同义词 ② 一定都不是同义词

③都相同 ④ 健值不一定有序的顺序表 18．设散列函数为H(k)= k mod 7,一组关键码为23，14，9，6，30，12和18，散列表T的地址空间为0..6,用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为 （ ）

①0 1 2 3 4 5 6 14 6 23 9 18 30 12 ② 0 1 2 3 4 5 6 14 18 23 9 30 12 6 ③0 1 2 3 4 5 6 14 12 9 23 30 18 6 ④0 1 2 3 4 5 6 6 23 30 14 18 12 9 19．设有一个用线性探测法解决冲突得到的散列表：

T:0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 散列函数为H(k)=k mod 11,若要查找元素14，探测的次数是（ ） ① 18 ② 9 ③3 ④6

20．在散列函数H(k)=k MOD m 中，一般来讲，m应取 （ ） ①奇数 ②偶数 ③ 素数 ④ 充分大的数

21，分块查找的时间性能（ ） ①低于二分查找 ② 高于顺序查找而低于二分查找 ③高于顺序查找 ④ 低于顺序查找而高二分查找

22．以下说法正确的是（ ） ①顺序查找效率最低但限制最强。 ②二分查找效率最高但限制最少。

③分块查找效率介于顺序查找和二分查找之间。

23．以下说法正确的是（ ）

32

①查找表中数据元素的任何数据项都可以作为关键字。

②采用二分查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。 ③二叉排序树的查找和二分查找时间的性能相同。 ④最佳二叉排序树一定是平衡二叉树

⑤“顺序查找法”是指在顺序表上进行查找的方法。 24．．以下说法错误的是（ ） ①散列法存储的基本思想是由关键码的值决定数据的存储地址。 ②散列表的结点中只包含数据元素自身的信息，不包含任何指针。 ③装填因子是散列法的一个重要参数，它反映散列表的装填程度。

④散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。

25．以下说法错误的是（ ） ①当所有的结点的权之都相等时，用这些结点构造的二叉排序树的特点是只有右子树 ②中序遍历二叉排序树的结点就可以得到排好序的结点序列。

③任一二叉排序树的平均检查时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。

④对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。

⑤采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要。

26．以下说法正确的是（ ） ①平衡树一定是丰满树。

②虽然信息项的序列的顺序不一样，但依次生成的二叉排序树确是一样的。

③在二叉排序树上插入新的结点时，不必移动其他结点，只需改动某个结点的指针，由空变为非空即可。

④在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应的指针域置空即可。

27．长度为12的有序表：Apr,Aug,Dec,Feb,Jan,Jul,Jun,Mar,May,Nov,Oct,Sep,按折半查找法对该表进行查找。在表内各元素等概率情况下查找成功所需的平均比较次数为（ ）。

① 35/12 ②37/12 ③39/12 ④43/12

28．已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除一个记录，正确的

做法是（ ） ①将该元素所在的存储单元清空。 ②将该元素用一个特殊的元素代替 ③将与该元素有相同Hash地址的后继元素顺次前移一个位置。 ④用与该元素有相同Hash地址的最后插入表中的元素替代。 四、简答及应用

1．对长度为20的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均查找长度。 2．给定有序表

D={006,087,155,188,220,465,505,508,511,586,656,670,700,766,897,908}，用二分查找法在D中查找586，试用图示法表示出查找过程。 11．给定表（19，14，22，01，66，21，83，27，56，13，10）。

（1）试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成之后的二叉排序树。

（2）按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。

33

12． 给定表（Jan,Feb,Mar,Apr,May,Jun,Jun,Aug,Sep,Oct,Nov,Dec）.设取散列函

数H(x)=|_i/2_|,其中i为健值中第一个字母在英语字母表中的序号，要求： （1）画出相应的开散列表；

（2）画出闭散列表（以线性探测法处理）；

（3）分别求这两个散列表在等概率情况下查找成功与不成功时的平均查找长度。 13． 已知散列函数为H(K)=K mod 12,健值序列为25，37，52，43，84，99，120，

15，26，11，70，82，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。

14． 顺序查找时间为O(n),二分查找时间为O(log2n),散列查找时间为O(1),为什么

有高效率的查找方法而不放弃低效率的方法？

第十章 排序

二、填空

6.以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。 void straightsort(list r);

{for(i=___________;i<=n;i++)

{r[0]=r[i];j=i-1;

while(r[0].key

r[j+1]=_______; } }

7.直接插入排序是稳定的，它的时间复杂性为________，空间复杂度为________。 8.以下为冒泡排序的算法。请分析算法，并在________上填充适当的语句。 void bulbblesort(int n,list r) /*flag为特征位，定义为布尔型*/ {for(i=1;i<=________;i++) {_______________;

for(j=1;j<=_________;j++)

if(r[j+1].key

9.对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是________。 10.以下对r[h],r[h+1],??r[p]子序列进行一趟忆速排序。请分析算法，并在________上填充适当的语句。

int quickpass(list r,int h,int p)

{i=h;j=p;x=r[i];/*置初值，以第一个记录的键值为标准*/ while(i

{while((r[j].key>=x.key)&&(i

{________;i++;/* 将r[j].kiy

while((r[i].key<=x.key)&&(i

} }

r[i]=________;return(i);/*一趟快速 排序结束，将x移至正确的位置*/

34

}

11.对快速排序来讲，其最好情况下的时间复杂度是________，其最坏情况下的时间复杂度是________。

12.以下是直接选择排序的算法。请分析算法，并在横线上填充适当的语句。 void select(list r,int n)

{for(i=1;i<=________;i++)/*每次循环，选择出一个最小键值*/ {k=i;

for(j=i+1;j<=n;j++)if(r[j].key

}}

19.以下将ah,?,am和am+1,?,an两个有序序列（它们相应的关键字值满足Kh<=?<=Km,Km+1<=?<=Kn）合并成一个有序序列Rh，?,Rn（使其关键字值满足Kh<=?<=Kn）。请分析算法，并在________上填充适当的语句。

void merge(list a,list R,int h,int m,int n) {i=h;k=h;j=m+1;

while((i<=m)&&(j<=n))

{if(a[i].key<=a[j].key){R[k]=________;________;} else{R[k]=________;________;} k++; }

while(i<=________){R[k]=a[i];i++;k++;} while(j<=________){R[k]=a[j];j++;k++;}} 此算法的执行时间为________. 三、单项选择

1．以下说法错误的是 （ ） ①直接插入排序的空间复杂度为O(1)。 ②快速排序附加存储开销为O(log2n)。 ③堆排序的空间复杂度为O(n)。

④二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。

2．以下不稳定的排序方法是（ ）

①直接插入排序 ②冒泡排序 ③直接选择排序 ④二路归并排序 3．以下稳定的排序方法是（ ） ①?? 快速排序 ②冒泡排序 ③直接选择排序 ④ 堆排序 4．以下时间复杂性不是O(n2)的排序方法是（ ） ①?? 直接插入排序 ②二路归并排序 ③冒泡排序 ④直接选择排序 5．以下时间复杂性不是O(nlog2n)的排序方法是（ ） ①?? 堆排序 ② 直接插入排序 ③二路归并排序 ④快速排序 6．在文件局部有序或文件长度较小的情况下，最佳的排序方法是（ ） ①?? 直接插入排序 ② 冒泡排序 ③ 直接选择排序 ④归并排序

7．对于大文件的排序要研究在外设上的排序技术，即（ ） ①快速排序法 ② 内排序法 ③外排序法 ④ 交叉排序法 8．排序的目的是为了以后对已排序的数据元数进行（ ）操作。

①打印输出 ②分类 ③ 合并 ④查找

9．当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（ ）

2

①n-1 ②log2n ③ 2log2n ④n

35

10.快速排序在最坏的情况下的时间复杂度是（ ） ①O(log2n) ②O(nlog2n) ③ O(n2) ④O(n3)

11.具有24个记录的序列，采用冒泡排序至少的比较次数是（ ） ①1 ②23 ③ 24 ④ 529

12．用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下：

25 84 21 47 15 27 68 35 20 15 20 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84

则采取的排序方法是（ ） ①直接选择排序 ②冒泡排序 ③快速排序 ④二路归并排序 13．在排序过程中，健值比较的次数与初始序列的排列顺序无关的是 （ ） ①直接插入排序和快速排序 ②直接插入排序和归并排序 ③直接选择排序和归并排序 ④快速排序和归并排序 14．（ ）方法是从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。

①归并排序 ② 插入排序 ③快速排序 ④选择排序 15（ ）方法是从未排序序列中挑选元素，并将其依次放入已排序序列的一端。 ①归并排序 ②插入排序 ③ 快速排序 ④选择排序 16．（ ）方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。

①归并排序 ②插入排序 ③快速排序 ④选择排序 17．将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用（ ）方法能够最快地找出其中最大的正整数。

①快速排序 ②插入排序 ③ 选择排序 ④ 归并排序

18一般情况下，以下四种排序方法中，平均查找长度最小的是（ ） ①归并排序 ②快速排序 ③选择排序 ④插入排序

19．以下四种排序方法中，要求附加的内存容量最大的是（ ） ①插入排序 ②选择排序 ③快速排序 ④归并排序 20已知一个链表中有3000个结点，每个结点存放一个整数，（ ）可用于解决这3000个整数的排序问题且不需要对算法作大的变动。

①直接插入排序法 ②简单选择排序方法 ③快速排序方法 ④堆排序方法

21．若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（ ）次比较。

①33 ②45 ③70 ④91 22．在任何情况下，快速排序方法的时间性能总是最优的。这种说法 ①正确 ②错误

23．对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（ ）方法。 ①归并排序 ②直接插入排序 ③直接选择排序 ④快速排序。 四、简答及应用

1．对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行

36

排序中各趟的结果。

5．判断下列两序列是否为堆？如不是，按照建堆的思想把它调整为堆，并用图表示建堆的过程。 （1）（3，10，12，22，36，18，28，40）； （2）（5，8，11，15，23，20，32，7）。

6．对于下列一组关键字46，58，15，45，90，18，10，62，试写出快速排序每一趟的排序结果，并标出每一趟中各元素的移动方向。 7．已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。 五、算法设计

1.设计一个用链表表示的直接选择排序算法。 2.写出非递归调用的快速排序算法。

3.插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后的插入排序方法。

4.一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少交换次数。

5.已知（k1,k2??，kn）是堆，试写一个算法将（k1,k2,??，kn,kn+1）调整为堆。按此思想写一个从空堆开始一个一个填入元素的建堆算法（题示：增加一个k n+1后应从叶子向根的方向调整）。

设计一个用链表表示的直接插入排序算法。

37

本文来源：https://www.bwwdw.com/article/eftw.html