数据结构答案1-5章

习题练习 第一章 绪论

1、void maxtrixmult (int n,int a[][100],int b[][100],intc[][100]) {

int j,k,r;

int x;

for(r=0;r<=n;r++) 1) n+2

{

for (j=0;j<=n;j++) 2) (n+1)*(n+2) {

x=0; 3) (n+1)2 for(k=1；k<=n;k++) 4) (n+1)3 x+=a[r][k]*[k][j]; 5) n* (n+1)2 c[r][j]=x; 6) (n+1)2 } } }

计算时间每条语句的频度和该算法的时间复杂度 2．一个算法应该是（ B ）。【中山大学 1998 二、1（2分）】

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 3. 下面说法错误的是（ C ）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间

n

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3)

4．从逻辑上可以把数据结构分为（ C ）两大类。 【武汉交通科技大学 1996 一 、4（2分）】

A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 5．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1（2分）】

A．循环队列 B. 链表 C. 哈希表 D. 栈 6．连续存储设计时，存储单元的地址（ A ）。【中山大学 1999 一、1（1分）】

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 7. 数据元素是数据的最小单位。( F )

【北京邮电大学 1998 一、1（2分）】【青岛大学 2000 一、1 （1分）】 【上海交通大学 1998 一、1】 【山东师范大学 2001 一、1 （2分）】 8. 记录是数据处理的最小单位。 ( F ) 【上海海运学院 1998 一、5（1分）】 9. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。( F )

【华南理工大学 2002 一、2 （1分）】

10. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( F )

【上海海运学院 1999 一、1（1分）】

11. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( F )

【上海海运学院 1998 一、1（1分）】

12．一个数据结构在计算机中 映像 称为存储结构。【华中理工大学 2000 一、1（1分）】

13.下面程序段中带下划线的语句的执行次数的数量级是： log2n 【合肥工业大学1999三、1（2分）】

i：=1； WHILE i

1

14. 下面程序段中带下划线的语句的执行次数的数量级是(.n )。【合肥工业大学 2000 三、1（2分）】

i:=1;

WHILE i

第二章 线性表

1．线性表是具有n个（ C ）的有限序列（n>0）。 【清华大学 1998 一、4（2分）】 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项

2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。【哈尔滨工业大学 2001 二、1（2分）】

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 3．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。【南开大学 2000 一、3】

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 4．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表

5. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。【北京航空航天大学 1999 一、1（2分）】

2

A. O(0) B. O(1) C. O(n) D. O(n)

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

A．O（i） B．O（1） C．O（n） D．O（i-1）【中山大学 1999 一、2】 7．非空的循环单链表head的尾结点p↑满足（ A ）。【武汉大学 2000 二、10】

A．p->next=head B．p->next=NIL C．p=NIL D．p= head 8．循环链表H的尾结点P的特点是（ A ）。【中山大学 1998 二、2（2分）】 A．P->NEXT=H B．P->NEXT= H->NEXT C．P=H D．P=H->NEXT 9．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（A）【南京理工大学1998 一、15（2分）】

A. p->next=h B. p->next=NIL C. p->next->next=h D. p->data=-1 10．完成在双循环链表结点p之后插入s的操作是（D ）；【北方交通大学 1999 一、4（3分）】

A． p->next=s ; s->priou=p; p->next->priou=s ; s->next=p->next; B． p->next->priou=s; p->next=s; s->priou=p; s->next=p->next; C． s->priou=p; s->next=p->next; p->next=s; p->next->priou=s ; D． s->priou=p; s->next=p->next; p->next->priou=s ; p->next=s;

11．在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( C )。【北京邮电大学 1998 二、2（2分）】

注:双向链表的结点结构为(llink,data,rlink)。 供选择的答案： 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=p；

p->llink=q； p->llink=q；

2

12. 线性表的特点是每个元素都有一个前驱和一个后继。( F )【合肥工业大学2001 二、1（1分）】 13．线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是__（n-1）/2____。插入是n/2【北方交通大学 2001 二、9】

14．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动______N-I+1__个元素。

15、从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较 （N+1）/2 个结点【北京工商大学 2001 二、4（4分）】

16. 带头结点的双循环链表L中只有一个元素结点的条件是：_L->next->next==L ___

【合肥工业大学 1999 三、3 2000 三、2（2分）】

17. 在单链表L中，指针p所指结点有后继结点的条件是：．p->next!=null__ 【合肥工业大学 2001 三、3 （2分）】

18设有一带头结点的单链表,编程将链表颠倒过来.要求不用另外的数组或结点完成.【南京航空航天大学 1999 八 （10分）】

（1）要求编程实现带头结点的单链表的逆置。首先建立一单链表，然后逆置。

typedef struct node

{int data；∥假定结点数据域为整型。 struct node *next； }node,*LinkedList； LinkedList creat（ ） {LinkedList head，p int x；

head=（LinkedList）malloc（sizeof（node））； head->next=null； /*设置头结点*/ scanf（“%d”，&x）；

while（x!=9999） /*约定输入9999时退出本函数*/ {p=（LinkedList）malloc（sizeof（node））； p->data=x；

p->next=head->next；/* 将新结点链入链表*/ head->next=p； scanf（“%d”，&x）； }

return（head）； }∥结束creat函数。

LinkedList invert1（LinkedList head） /*逆置单链表*/

{LinkedList p=head->next; /*p为工作指针*/ head->next=null； while（p!=null）

{r=p->next； /*暂存p的后继*/ p->next=head->next； head->next=p； p=r； }

return（head）；

}/*结束invert1函数*/ main（）

3

{LinkedList la； la=creat( ）； /*生成单链表*/ la=invert1（la）；/*逆置单链表*/ }

19、设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。【清华大学 1997 二 （10分）】

[题目分析]首先在双向链表中查找数据值为x的结点，查到后，将结点从链表上摘下，然后再顺结点的前驱链查找该结点的位置。

DLinkList locate(DLinkList L，ElemType x)

∥ L是带头结点的按访问频度递减的双向链表，本算法先查找数据x,查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。

{ DLinkList p=L->next,q; ∥p为L表的工作指针，q为p的前驱，用于查找插入位置。 while (p && p->data !=x) p=p->next; ∥ 查找值为x的结点。 if (!p) {printf(“不存在值为x的结点\\n”); exit(0);}

else { p->freq++; ∥ 令元素值为x的结点的freq域加1 。 p->next->pred=p->pred; ∥ 将p结点从链表上摘下。 p->pred->next=p->next;

q=p->pred; ∥ 以下查找p结点的插入位置

while (q !=L && q->freqfreq) q=q->pred;

p->next=q->next; q->next->pred=p;∥ 将p结点插入 p->pred=q; q->next=p； }

return(p); ∥返回值为x的结点的指针 } ∥ 算法结束

第三章 栈和队列

1、判定一个循环队列QU（最多元素为m0）为空的条件 QU.rear= =QU.front

2、判定一个循环队列QU（最多元素为m0）为满的条件 QU.front= =(QU.rear+1)%m0 3、一个循环队列QU（最多元素为m0）队列满时，队列中有 m0-1 个元素

4. 一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。 A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】

5. 若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】

6. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2（2分）】 7. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ D ）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b

4

8. 执行完下列语句段后，i值为：（ B ）【浙江大学 2000 一 、6 (3分)】

int f(int x)

{ return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));

A．2 B. 4 C. 8 D. 无限递归 9. 表达式a*(b+c)-d的后缀表达式是( B )。【南京理工大学 2001 一、2（1.5分）】

A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd

10. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ D ），其中^为乘幂 。

A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 11. 循环队列存储在数组A[0..m]中，则入队时的操作为（ D ）。【中山大学 1999 一、6（1分）】

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

12. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( B )【浙江大学1999 四、1(4分)】

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

13、从一个带头结点的栈顶指针为HS的链式栈中插入一个S所指的结点时，执行 S->next=HS->next; HS->next=S 。

14、从一个带头结点的栈顶指针为HS的链式栈中删除一个结点时，并用x保存被删除结点的值，则执行 x= HS->next->data; HS->next= HS->next->next 。

15．完善下面算法。【中山大学 1998 四、2（6分）】

后缀表达式求值，表达式13/25+61的后缀表达式格式为： 13, 25/61, +

FUNC compute(a):real; 后缀表达式存储在数组a[1..m]中。 BEGIN

setnull(s)；i:=1；ch:= (1)__ a[i]或a[1] ___； WHILE ch<>’@’ DO BEGIN

CASE ch OF

‘0’..‘9’: x:=0;

WHILE ch<>’,’DO BEGIN

x:=x*10+ord(ch)-ord(‘0’); i:=i+1；ch:= (2)___ a[i] __; END

‘+’: x:=pop(s)+pop(s);

‘-‘: x:=pop(s);x:=pop(s)-x; ‘*’: x:=pop(s)*pop(s);

‘/’: x:=pop(s);x:=pop(s)/x;

ENDCASE

push(s,x)；i:=i+1；ch:=a[i]； END;

comput:= (3)_ pop（s）或s[1]___； END;

16. 有字符串次序为3*-y-a/y^2,利用栈，给出将次序改为3y-*ay2^/-的操作步骤。（可用X代表扫描该

5

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