2024年1月4日发(作者：)

;.

数据结构期末考试试题及答案

一、选择题

1. 评价一个算法时间性能的主要标准是( )。

;.'

A、算法易于调试

B、算法易于理解

C、算法的稳定性和正确性

D、算法的时间复杂度

A、可行性、可移植性和可扩充性

B、可行性、确定性和有穷性

C、确定性、有穷性和稳定性

D、易读性、稳定性和安全性

A、head==NULL

B、head->next==NULL

C、head->next==head

D、head！=NULL

A、线性表中的数据元素可以是数字、字符、记录等不同类型。

B、线性表中包含的数据元素个数不是任意的。

C、线性表中的每个结点都有且只有一个直接前趋和直接后继。

D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。

A、基地址

B、结点大小

C、向量大小

D、基地址和结点大小

A、插入

B、删除

C、根据序号查找

D、根据元素值查找

A、n-i

B、n-i+1

C、n-i-1

2. 计算机算法具备有输入、输出、（ ）等五个特性。

3. 带头结点的单链表head为空的判定条件是（ ）。

4. 以下关于线性表的说法不正确的是( )。

5. 在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。

6. ( )运算中，使用顺序表比链表好。

7. 一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动（ ）个元素

;.

D、i

A、顺序表

B、单链表

C、循环链表

D、双向链表

A、都是先进后出

B、都是先进先出

C、只允许在端点处插入和删除元素

D、没有共同点

A、4 3 2 1

B、1 2 3 4

C、1 4 3 2

D、3 2 4 1

A、数据元素的类型不同

B、运算是否受限制

C、数据元素的个数不同

D、逻辑结构不同

A、循环队列

B、队列

C、链队列

D、顺序队列

8. ( )适合作为经常在首尾两端操作线性表的存储结构。

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

10. 一个队列的入列序列是1 2 3 4，则队列的输出序列是( )。

11. 队列与一般的线性表的区别在于( )。

12. “假上溢”现象会出现在( )中。

;.'

;.

二、填空题

1．数据的逻辑结构被分为 集合、线性结构、树形结构和图结构。

2．数据的逻辑结构被分为集合、线性结构、树形结构和图状结构。

3．下面程序段的时间复杂度是O（n）。

i=s=0;

while (s

{ i++;

s++;;

}

4．树型结构和图形结构合称是非线性结构。

5．在长度为n的顺序存储线性表的第i个元素（1≤i≤n）之前插入一个元素时，

需要向后移动n-i+1个元素。

6．在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，

需要向前移动n-i个元素。

7．指针p指向非空循环单链表head的尾结点，则p满足p->next=head。

8．已知L是带头结点的非空单链表，且P结点既不是第一个数据结点，也不是最后一个结点，试的答案中选择合适的语句序列，实现删除P结点的直接后继结点的语句序列是 ⑥

①

⑨ 。

①

P->next = P->next ->next;

②

P=P->next->next;

③

while (P->next!=Q) P=P->next;

④

while (P->next->next=Q) P=P->next;

⑤

Q=P;

⑥

Q=P->next;

;.'

;.

⑦

P=L;

⑧

L=L->next;

⑨

free(Q);

9．在线性结构中，第一个结点无前驱结点，其余每个结点有且只有1个前驱结点。

10．单链表是线性表的链式存储表示。

11．栈是限定仅在表尾进行插入或删除操作的线性表。

12．在栈顶指针为HS的链栈中，判定栈空的条件是HS=NULL。

13．假设以S和X分别表示进栈和退栈操作，则对输入序列a、b、c、d、e进行一系列栈操作SS后，得到的输出序列为bceda。

14．设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈S，一个元素出栈后即若这6个元素出队列的顺序是b、d、c、f、e、a，则栈S的容量至少应该是3。

三、算法填空

1．已知一个顺序表中的元素按关键字值非递减有序，下列算法删除顺序表中关键字相同的多余元关键字不同的元素在表中只保留一个。

void purge_sq(SqList &la)

{

//删除顺序表la中关键字相同的多余元素，即使操作之后的顺序表中只保留操作之前表中所有按不相同的元素

k= -1; //k指示新表的表尾

for (i=0;i<;++i) //顺序考察表中每个元素

{j=0;

while (j<=k &&[j]!=[i])

++j; //在新表中查询是否存在和[i]相同的元素

if (k= = -1||j>k) //k= -1表明当前考察的是第一个元素

[++k]= [i];

;.'

;.

}//for

=k+1; //修改表长

}//purge_sq

2．一个头指针为head的单链表，其中每个结点存放一个整数，以下算法将其拆分为两个单链表head使head 1中仅含有正整数，head 2中仅含有负整数。

void separate(LinkList &head, LinkList &head1,LinkList &head2)

{

//将头指针为head的单链表（带头结点）拆分为两个单链表head1和head2，

//使head1中仅含有正整数，head2中仅含有负整数

head1=(LinkList)malloc(sizeof(Lnode)); head1->next=NULL;

head2=(LinkList)malloc(sizeof(Lnode)) ; head2->next=NULL;

p=head->next;

while(p)

{ q=p->next;

if （p->data>=0）

{p->next=head1->next;

head1->next=p;

}

else {p->next=head2->next;

head2->next=p;

}

p=q;

} //while

;.'

;.

free(head);

}//seperate

3．设一个长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某个结点的指一个删除该结点直接前驱结点的算法。

void delete(LinkList p)

{

//在一个既无头结点也无头指针的长度大于一的循环链表中，

//删除指针p所指的某个结点的直接前驱结点

q=p; //查找p结点的前驱结点q

while(q->next!=p)

q=q->next;

r=q; //查找q结点的前驱结点r

while(r->next!=q)

r=r->next;

r->next=p;

free(q);

}

四、计算题

1．设有头指针为head的单链表。写算法要求在链表中查找元素值等于x的结点，若找到则删除复，直至所有值为x的元素全部删除为止；若一个也找不到则给出相应提示信息。

1．void elemdelete_x(LinkList &l,ElemType x)

{

//删除头指针为head的单链表中（带头结点）所有的值为x的 元素

n=0; pre=l; //记下结点*p的前驱

;.'

;.

p=l->next;

while(p) //顺序考察表中每个元素

{

while(p&&p->data!=x)

{pre=p; p=p->next; } //在表中查询是否存在和x相同的元素

if(p) //将结点＊p插入到新的表中

｛pre->next=p->next;

q=p; p=p->next; free(q);

n++;

} //if

}//while

if(n==0)printf(“Notfound xn”);

}//elemdelete_x

2．有头指针为head的单链表，写算法在链表中查找出所有按先后顺序出现的元素x和y，并将的所有结点全部删除之。

2．void delete (LinkList &head , ElemType x, ElemType y)

{

//在头指针为head的单链表中查找出所有按先后顺序出现的元素x和y，

//并将x和y之间的所有结点全部删除

p=head->next;

while(p){

while (p&&p->data!=x)

;.'

;.

p=p->next;

if (!p) exit(1); //没找到x

r=p->next;

while(r&&r->data!=y)

r=r->next;

if(!r) exit(1); //没找到相应的y

while(p->next!=r)

{q=p-next;

p->next=q->next;

free(q);

}//while

}//while

}

3．设某个单链表以la为头指针，链表中每个元素均为整数且无序，写算法按递增顺序打印链表方法是：反复找出链表中最小的元素，打印并删除之，直至表空为止。

3．void rearrange(LinkList &la){

//将头指针是la的单链表按递增顺序打印出来

p=la->next; p1=la;

while(p->next!=NULL)

{a=p->data; q1=p; q=p->next;

while(q!=NULL)

{if(a>q->data)

;.'

;.

{a=q->data; p1=q1;}//if

q1=q; q=q->next;

}//while

s=p1->next;

printf(s->data);

p1->next=p1->next->next;

free(s);

p1=la; p=la->next;

}//while

printf(p->data);

free(p); free(la);

}//rearrange

4．设有一个头指针为head的单链表，每个结点存放一个整数。写一算法将其按负整数在前部

正整数在后部的次序存放（正整数与正整数之间、负整数与负整数之间不要求有序），存储空

间仍占用原来的链表。

4．huafen(LinkList &L)

{//L为带头结点的单链表的头指针

p=L->next;

while(p->next) p=p->next;

pt=p; pr=p; p0=L;

p=p0->next; 3分

while(p!=pr)

;.'

;.

if (p->data>=’0’&& p->data<=’9’)

{p0=p; p=p->next;}

else 2分

{p0->next=p->next;

s=p; p=p->next;

pt->next=s; s->next=NULL;

pt=s;

}

}//huafen 3分

5．设有一顺序表a，写算法在表中查找先后出现的元素x和y，将x和y之间的元素逆置，

逆置部分不包含x和y。若找不到相应的x和y则给出提示信息。

5．void revert(ElemType &R[], int s,int t)

{

//本算法将数组R中下标自 s到t的元素逆置

//即将（RS,Rs+1,…,Rt-1,Rt）改变为（Rt,Rt-1,…,Rs+1,Rs）

for (k=s;k<=(s+t)/2;k++)

{w=R[k];

R[k]=R[t-k+s];

R[t-k+s]=w;

}//for

}//revert

;.'

;.

void exchange (SqList &a,ElemType x,ElemType y)

{

//本算法实现在顺序表a中查找先后出现的元素x和y之间的元素逆置，

//逆置部分不包含x和y。

if (!(LocateElem (la,x,equal)&&LocateElem(la,y,equal)))

return error; //找不到相应的x和y

k=LocateElem(la,x,equal); l=LocateElem(la,y,equal);

if ((k>=)||(l>)||(l-k=1)||(k>l))

return error;

else revert (,k+1,l-1)；

}//exchange

;.'

;.

;.'