数据结构试题及答案

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

一、选择题

1。评价一个算法时间性能的主要标准是（）。

A、算法易于调试

B、算法易于理解

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

D、算法的时间复杂度

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

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

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

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

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

3。带头结点的单链表head为空的判定条件是()。

A、head==NULL

B、head—〉next==NULL

C、head—〉next==head

D、head!=NULL

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

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

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

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

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

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

A、基地址

B、结点大小

C、向量大小

D、基地址和结点大小

6.（）运算中，使用顺序表比链表好。

A、插入

B、删除

C、根据序号查找

D、根据元素值查找

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

A、n—i

B、n—i+1

C、n-i-1

D、i

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

A、顺序表

B、单链表

C、循环链表

D、双向链表

9。栈和队列的共同点是(）

A、都是先进后出

B、都是先进先出

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

D、没有共同点

10.一个队列的入列序列是1234,则队列的输出序列是(）。

A、4321

B、1234

C、1432

D、3241

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

A、数据元素的类型不同

B、运算是否受限制

C、数据元素的个数不同

D、逻辑结构不同

12.“假上溢”现象会出现在（）中.

A、循环队列

B、队列

C、链队列

D、顺序队列

二、填空题

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

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

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

i=s=0;

while(s〈n）

{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进行一系列栈操作SSXSX

得到的输出序列为bceda。

14．设栈S和队列Q的初始状态为空,元素a、b、c、d、e、f依次通过栈S,一个元素出栈后即进入

这6个元素出队列的顺序是b、d、c、f、e、a,则栈S的容量至少应该是3.

三、算法填空

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

关键字不同的元素在表中只保留一个。

voidpurge_sq(SqList＆la）

｛

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

不相同的元素

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

for（i=0；i〈；++i）//顺序考察表中每个元素

｛j=0；

while（j〈=k＆＆[j]！=la。elem［i］）

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

if（k==—1｜｜j〉k)//k=-1表明当前考察的是第一个元素

[++k］=la。elem［i］;

}//for

la。length=k+1；//修改表长

}//purge_sq

2．一个头指针为head的单链表,其中每个结点存放一个整数,以下算法将其拆分为两个单链表head

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

voidparate(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;

｝

el｛p->next=head2—>next；

head2->next=p；

｝

p=q;

｝//while

free（head）;

｝//perate

3．设一个长度大于1的循环单链表中,既无头结点也无头指针,p为指向该链表中某个结点的指针，

删除该结点直接前驱结点的算法。

voiddelete(LinkListp)

{

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

//删除指针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．voidelemdelete_x（LinkList＆l，ElemTypex)

{

//删除头指针为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（“Notfoundxn”）；

}//elemdelete_x

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

的所有结点全部删除之.

2．voiddelete(LinkList&head，ElemTypex，ElemTypey）

｛

//在头指针为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．voidrearrange（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；}

el2分

{p0->next=p-〉next;

s=p；p=p—>next；

pt—〉next=s；s-〉next=NULL；

pt=s；

}

｝//huafen3分

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

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

5．voidrevert（ElemType＆R[］，ints，intt）

｛

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

//即将（R

S,

R

s+1，…，

R

t—1,

R

t

)改变为(R

t，

R

t-1，…，

R

s+1，

R

s

）

for(k=s；k<=（s+t)/2；k++)

｛w=R[k］；

R［k］=R[t—k+s］；

R[t-k+s］=w；

｝//for

}//revert

voidexchange（SqList＆a，ElemTypex,ElemTypey）

{

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

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

if(!（LocateElem（la，x,equal）&＆LocateElem（la,y，equal)）)

returnerror；//找不到相应的x和y

k=LocateElem(la,x,equal）；l=LocateElem(la,y，equal)；

if((k>=la。length)|｜（l>)｜|（l—k=1)｜|（k〉l)）

returnerror;

elrevert（,k+1，l—1）；

}//exchange