文档库 最新最全的文档下载
当前位置:文档库 › 中国铁道出版社数据结构(第二版)单元3练习参考答案

中国铁道出版社数据结构(第二版)单元3练习参考答案

中国铁道出版社数据结构(第二版)单元3练习参考答案
中国铁道出版社数据结构(第二版)单元3练习参考答案

单元练习3

一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳)

(√)(1)栈是运算受限制的线性表。

(√)(2)在栈空的情况下,不能作出栈操作,否则产生下溢出。

(ㄨ)(3)栈一定是顺序存储的线性结构。

(√)(4)栈的特点是“后进先出”。

(ㄨ)(5)空栈就是所有元素都为0的栈。

(ㄨ)(6)在C或C++语言中设顺序栈的长度为MAXLEN,则top=MAXLEN时表示队满。

(√)(7)链栈与顺序栈相比,其特点之一是通常不会出现栈满的情况。

(ㄨ)(8)一个栈的输入序列为:A,B,C,D,可以得到输出序列:C,A,B,D。

(ㄨ)(9)递归定义就是循环定义。

(√)(10)将十进制数转换为二进制数是栈的典型应用之一。

二.填空题

(1)在栈结构中,允许插入、删除的一端称为栈顶。

(2)在顺序栈中,当栈顶指针top=-1时,表示栈空。

(3)在有n个元素的栈中,进栈操作的时间复杂度为 O(1)。

(4)在栈中,出栈操作的时间复杂度为:O(1) 。

(5)已知表达式,求它的后缀表达式是栈的典型应用。

(6)在一个链栈中,若栈顶指针等于NULL,则表示栈空。

(7)向一个栈顶指针为top的链栈插入一个新结点*p时,应执行p->next=top;和top=p;操作。

(8)顺序栈S存储在数组 S->data[0..MAXLEN-1]中,进栈操作时要执行的语句有:S->top ++ 。(或= S->top+1)

(9)链栈LS,指向栈顶元素的指针是 LS->next 。

(10)从一个栈删除元素时,首先取出栈顶元素,然后再移动栈顶指针。

(11)由于链栈的操作只在链表的头部进行,所以没有必要设置头结点。

(12)已知顺序栈S,在对S进行进栈操作之前首先要判断栈是否满。

(13)已知顺序栈S,在对S进行出栈操作之前首先要判断栈是否空。

(14)若内存空间充足,链栈可以不定义栈满运算。

(15)链栈LS是空的条件是 LS->next=NULL 。

(16)链栈LS的栈顶元素是链表的首元素。

(17)同一栈的各元素的类型相同。

(18)若进栈的次序是A、B、C、D、E,执行三次出栈操作以后,栈顶元素为 B 。

(19)A+B/C-D*E的后缀表达式是:ABC/+DE*- 。

(20)四个元素按A、B、C、D顺序进S栈,执行两次Pop(S,x)运算后,x的值是 C 。

三.选择题

(1)插入和删除只能在一端进行的线性表,称为( C )。

A.队列 B.循环队列 C.栈 D.循环栈

(2)设有编号为1,2,3,4的四辆列车,顺序进入一个栈结构的站台,下列不可能的出站顺序为 ( D )

A.1234 B.1243 C.1324 D.1423

(3)如果以链表作为栈的存储结构,则出栈操作时( B )

A.必须判别栈是否满 B.必须判别栈是否空

C.必须判别栈元素类型 D.队栈可不做任何判别

(4)元素A,B,C,D依次进栈以后,栈顶元素是( D )

A.A B.B C.C D.D

(5)顺序栈存储空间的实现使用( B )存储栈元素。

A.链表B.数组 C.循环链表D.变量

(6)在C或C++语言中,一个顺序栈一旦被声明,其占用空间的大小( A )。

A.已固定 B.不固定C.可以改变D.动态变化

(7)带头结点的链栈LS的示意图如下,栈顶元素是( A )

LS

A.A B.B C.C D.D

(8)链栈与顺序栈相比,有一个比较明显的优点是( B )。

A.插入操作更加方便 B.通常不会出现栈满的情况。

C.不会出现栈空的情况 D.删除操作根加方便

(9)从一个栈顶指针为top的链栈中删除一个结点时,用x保存被删除的结点,应执行下列 ( D )命令。

A.x=top;top=top->next; B.top=top->next;x=top->data;

C.x=top->data; D.x=top->data;top=top->next;

(10)在一个栈顶指针为HS的链栈中,将一个S指针所指的结点入栈,应执行下列 ( B )命令。

A.HS->next=S; B.S->next=HS->next;HS->next=S;

C.S->next=HS->next;HS=S; D.S->next=HS;HS=HS->next;

(11)四个元素按A、B、C、D顺序进S栈,执行两次Pop(S,x)运算后,栈顶元素的值是( B )。

A.A B.B C.C D.D

(12)元素A,B,C,D依次进栈以后,栈底元素是( A )。

A.A B.B C.C D.D

(13)经过下列栈的运算后,再执行ReadTop(s)的值是( A )。

InitStack(s) (初始化栈);Push(s,a);Push(s,b); Pop(s)

A.a B.b C.1 D.0

(14)经过下列栈的运算后,x的值是( B )。

InitStack(s) (初始化栈);Push(s,a);Push(s,b); ReadTop(s);Pop(s,x);

A.a B.b C.1 D.0

(15)经过下列栈的运算后,x的值是( B )。

InitStack(s) (初始化栈);Push(s,a);Pop(s,x);Push(s,b);Pop(s,x);

A.a B.b C.1 D.0

(16)经过下列栈的运算后,SEmpty(s)的值是( C )。

InitStack(s) (初始化栈); Push(s,a); Push(s,b);Pop(s,x); Pop(s,x);

A.a B.b C.1 D.0

(17)向顺序栈中压入元素时,( B )。

A.先存入元素,后移动栈顶指针 B.先移动栈顶指针,后存入元素

C.谁先谁后无关紧要 D.同时进行

(18)初始化一个空间大小为5的顺序栈S后,S->top的值是( B )。

A.0 B.-1 C.不再改变D.动态变化

(19)一个栈的入栈次序ABCDE,则栈的不可能的输出序列是 ( C )。

A.EDCBA B.DECBA C.DCEAB D.ABCDE

(20)设有一个顺序栈S,元素A,B,C,D,E,F,依次进栈,如果六个元素出栈的顺序是B,D,C,F,E,A,则栈的容量至少应是 ( A )。

A.3 B.4 C.5 D. 6

四.设有一个栈,元素进栈的次序为:A,B,C,D,E,用I表示进栈操作,O表示出栈操作,写出下列出栈的操作序列。

(1)C,B,A,D,E

(2)A,C,B,E,D

解:(1)IIIOOOIOIO

(2)IOIIOOIIOO

五.求后缀表达式

(1)A^B^C/D

(2)-A+B*C+D/E

(3)A*(B+C)*D-E

(4)(A+B)*C-E/(F+G/H)-D

(5) 8/(5+2)-6

解:

(1)A B ^ C ^ D /

(2)0 A – B C * + D E / +

(3)A B C + * D * E -

(4)A B + C * E F G H / + / - D -

(5)8 5 2 + / 6 -

六.算法设计题

1.设用一维数组stack[n]表示一个堆栈,若堆栈中每个元素需占用M个数组单元(M>1),(1)试写出其入栈操作的算法。

(2)试写出其出栈操作的算法。

2.设计一个算法,要求判别一个算术表达式中的圆括号配对是否正确。

1.解:用一整型变量top表示栈顶指针,top为0时表示栈为空。栈中元素从S [1]开始存放元素。(1)入栈算法:

void push (char x)

{

if ((top+M)>MAXLEN-1)

printf (“堆栈溢出!”);

else

{

if (top= =0)

{

top++;

S [top]=x;

}

else

{

top=top+M;

S [top]=x;

}

}

}

(2)出栈算法:

void pop (char x)

{

if (top= =0)

printf (“堆栈为空栈!”);

else

{

if (top= =1)

{

x= S [top];

top––;

}

else

{

x= S [top];

top=top–M;

}

}

}

2.解:设表达式在字符数组a[ ]中,使用一堆栈S来帮助判断。

int correct (char a[ ])

{

stack s ;

InitStack (s); // 调用初始化栈函数

for (i=0; i

if (a[i]= =’(’)

Push (s,’(’);

else if (a[i]= =’)’)

{

if StackEmpty (s) // 调用判栈空函数

return 0; // 若栈为空返回0;否则出栈else

Pop(s);

}

if (StackEmpty (s) ) // 调用判栈空函数

printf (“配对正确!”); //若栈空,说明配对正确,并返回1

else

printf (“配对错误!”); // 配对错误返回0

}

模拟考题

求后缀表达式

1.求下列表达式:A/B∧C+D*E-A*C 的后缀表达式。

解: A B C ∧/ D E * + A C * -

2.求下列表达式:A/B-C+D*E-F 的后缀表达式。

解: A B/ C - D E * +F -

写出运行下列程序段的输出结果

void main()

{ Stack S;

char x,y;

InitStack(S); // 初始化栈

x= "c ";

y= "k ";

Push(S,x); Push(S, "a ");

Push(S,y); Pop(S,x);

Push(S, "t "); Push(S,x);

Pop(S,x); Push(S, "s ");

While (!SEmpty(S))

{ Pop(S,y);cout<

cout<

}

答:"stack "

程序填空

1. 下列程序是判别一个算术表达式(存在字符数组a[ ]中)的圆括号配对是否正确?试填空完成下列程序。

int correct(char a[ ])

{ stack s ;

InitStack(s); // 初始化栈

for (i=0; i

if (a[i]= =’(’)

Push ( s,’(’ );

else if (a[i]= = ’)’ )

{

if SEmpty (s)

return 0; // 若栈为空返回0;否则出栈

else

Pop(s);

}

if (SEmpty(s))

cout<< " 配对正确!"; // printf (" 配对正确!");

else

cout<< " 配对错误!"; // printf (" 配对错误!");

}

2.链栈的存储结构和栈顶指针定义如下,试写出把十进数转换为二进制数的程序。

#define MAXLEN 100

typedef struct stacknode // 定义栈的存储结构

{ int data;

struct stacknode *next;

}stacknode;

typedef struct

{ stacknode *top; // 定义栈顶的指针

}linkstack;

解:

void Conversion(int n) // 栈的应用:二—十进制转换

{ linkstack s;

int x;

s.top=NULL; // 置栈空

do

{ x=n%2; // 取余数

n= n/2 ; // 取新的商

stacknode *p=new stacknode ; // 申请新结点

p->next=s.top ; // 修改栈顶指针

s.top=p;

s.top->data= x ; // 余数入栈

}

while (n);

cout<< " 转换后的二进制数值为:"; // printf(" 转换后的二进制数值为:");

while (s.top) // 出栈处理

{ cout<< s.top->data ;

stacknode *p=s.top;

s.top= s.top->next ;

delete p ; // 出栈一个余数,收回一个结}

}

数据结构实验三(顺序栈的基本操作)

#include<> #include<> #include<> #define MAXSIZE 100 typedef int DataType; typedef struct stack { DataType data[MAXSIZE]; int top; }sqstack; sqstack *InitStack(sqstack *S)出* 1.顺序栈的初始化*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* * *┃\n"); printf("\t┃* 2.元素的入栈* 3.元素的出栈*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* * *┃\n"); printf("\t┃* 4.取栈顶元素* 5.判空*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* *┃\n"); printf("\t┃* 6.将十进制数转换为其他进制数*┃\n"); printf("\t┃* *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); while ((m='0')&&(m='1')&&(m='2')&&(m='3')&&(m='4')&&(m='5')&&(m='6')&&(m='7')) { printf("\n请选择你需要操作的步骤(0至7):"); fflush(stdin); scanf("%c",&m); switch(m) { case '0': { exit(0); break; }

数据结构实验报告3--链串

宁波工程学院电信学院计算机教研室 实验报告 课程名称:___ 数据结构 ___ __ 实验项目:链串的基本算法 指导教师: 实验位置:电子楼二楼机房姓名: 学号: 班级:计科102 日期: 2011/10/13 一、实验目的 1)熟悉串的定义和串的基本操作。 2)掌握链串的基本运算。 3)加深对串数据结构的理解,逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C++6.0的计算机。 三、实验内容 编写一个程序,实现链串的各种基本运算,并在此基础上设计一个主程序。具体如下: 编写栈的基本操作函数 链串类型定义如下所示: typedef struct snode{ char data; struct snode *next; }listring; (1)串赋值Assign(s,t) 将一个字符串常量赋给串s,即生成一个其值等于t的串s (2)串复制StrCopy(s,t)

?将串t赋给串s (3)计算串长度StrLength(s) ?返回串s中字符个数 (4)判断串相等StrEqual(s,t) ?若两个串s与t相等则返回1;否则返回0。 (5)串连接Concat(s,t) ?返回由两个串s和t连接在一起形成的新串。 (6)求子串SubStr(s,i,j) ?返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j 个字符组成的子串。 (7)插入InsStr (s,i,t) ?将串t插入到串s的第i(1≤i≤StrLength(s)+1)个字符中,即将t 的第一个字符作为s的第i个字符,并返回产生的新串(8)串删除DelStr (s,i,j) ?从串s中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j 的子串,并返回产生的新串。 (9)串替换RepStr (s,s1,s2) ?在串s中,将所有出现的子串s1均替换成s2。 (10)输出串DispStr(s) ?输出串s的所有元素值 (11)判断串是否为空IsEmpty(s) 编写主函数 调用上述函数实现下列操作: (1)建立串s=“abcdefghijklmn”,串s1=“xyz”,串t=“hijk” (2)复制串t到t1,并输出t1的长度 (3)在串s的第9个字符位置插入串s1而产生串s2,并输出s2 (4)删除s第2个字符开始的5个字符而产生串s3,并输出s3 (5)将串s第2个字符开始的3个字符替换成串s1而产生串s4,并输出s4 (6)提取串s的第8个字符开始的4个字符而产生串s5,并输出s5 (7)将串s1和串t连接起来而产生串s6,并输出s6 (8)比较串s1和s5是否相等,输出结果 程序清单: #include

操作系统习题答案(中国铁道出版社_刘振鹏_李亚平_王煜_张明) (2)

⒉什么是操作系统?操作系统追求的主要目标是什么? 答:操作系统是计算机系统中的一个系统软件,是能有效地组织和管理计算机系统中的硬件和软件资源,合理地组织计算机工作流程,控制程序的执行,并向用户提供各种服务功能,使得用户能够灵活、方便、有效地使用计算机,并使整个计算机系统能高效地运行的一组程序模块的集合。 操作系统追求的主要目标包括四个方面,分别是:方便性、有效性、可扩充性、开放性。⒌操作系统分成哪几类? 答:单道批处理系统、多道批处理系统、分时系统、实时系统、微机操作系统、多处理机操作系统、网络操作系统和分布式操作系统。 ⒍从资源管理观点看,操作系统具有哪些功能? 答:处理机管理、存储器管理、I/O设备管理、文件管理。 ⒕简述操作系统的特性。 答:并发、共享、虚拟、异步性。 第二章 ⒊什么叫作业调度?作业调度选择作业的必要条件是什么? 答:操作系统根据允许并行工作的道数和一定的算法从等待的作业(后备作业)中选取若干作业装入主存储器,使它们可以去获得处理器运行,这项工作称为作业调度。作业调度的必要条件是,即只有在系统当前尚未分配的资源可以满足在系统中等待执行的作业的资源要求。 ⒍系统采用不能移动已在主存储器中作业的可变分区方式管理主存储器,现有供用户使用的主存空间100K,系统配有4台磁带机,有一批作业见表2.6。 表2.6 作业序号进输入井时间要求计算时间需要主存量申请磁带机数 1 l0:00 25分钟15K 2台 2 10:20 30分钟60K 1台 3 10:30 10分钟50K 3台 4 10:3 5 20分钟10K 2台 5 10:40 15分钟30K 2台 该系统采用多道程序设计技术,对磁带机采用静态分配,忽略设备工作时间和系统进行调度所花的时间,请分别写出采用“先来先服务调度算法”、“计算时间短的作业优先算法”和选中作业执行的次序以及各个作业的装入主存时间、开始执行时间、完成时间、周转时间以及它们的平均周转时间。 答:先来先服务调度算法”、“计算时间短的作业优先算法”和选中作业执行的次序以及它们的平均周转时间的结果是一样的: 选中作业的次序:选中作业执行的次序均为1,2,4,5,3。 作业1的周转时间:25分钟; 作业2的周转时间:35分钟; 作业3的周转时间:70分钟; 作业4的周转时间:40分钟;

数据结构练习3答案..

数据结构练习(三)参考 一、选择题 1.顺序查找法适合于存储结构为的线性表 A)哈希存储 C)压缩存储D)索引存储 2.一个长度为100的已排好序的表,用二分查找法进行查找,若查找不成功,至少比较________次。 A)9 B)8 C)7 3.采用顺序查找方法查找长度为n的线性表时,平均比较次数为。 A)n B)n/2 n+1)/2 D)(n-1)/2 4.对线性表进行折半查找时,要求线性表必须。 A)以顺序方式存储 C)以链表方式存储D)以链表方式存储,且结点按关键字有序排列 5.采用二分查找法查找长度为n的线性表时,每个元素的平均查找长度为。 A)O(n2)B)O(nlog2n)C)O(n)(log2n)6.有一个长度为12的有序表R[0…11],按折半查找法对该表进行查找,在表内各元素等概率查找情况下查找成功所需的平均比较次数为。 A)35/12 C)39/12 D)43/12 7.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,99},当采用折半查找法查找关键字为82的元素时,次比较后查找成功。 A)1 B.2 D)8 8.当采用分块查找时,数据的组织方式为。 A)数据分成若干块,每块内存数据有序 每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块 C)数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块 D)数据分成若干块,每块(出最后一块外)中的数据个数需相同 9.采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,

假设采用顺序查找来确定结点所在的块时,每块应有个结点最佳。 A)10 C)6 D)625 10.不能生成右图所示二叉排序树的关键字序列是_____。 B)42531 C)45213 D)42315 11.按____遍历二叉排序树,可以得到按值递增或递减次序的关键码序列。 A)先序C)后序D)层序 12.在一棵平衡二叉树中,每个结点的平衡因子的取值范围是。 —1 B)-2—2 C)1—2 D)0—1 13.具有5层结点的A VL树至少有个结点 A)10 C)15 D)17 14.在含有15个结点的平衡二叉树上,查找关键字为28的结点,则依次比较的关键字可能是。 A)30,36 B)38,48,28 ,18,38,28D)60,30,50,40,38,36 15.一棵深度为k的平衡二叉树,其每个非叶子结点的平衡因子均为0,则该树共有个结点。 A)2k-1-1 B)2k-1 C)2k-1 +1k-1 16.查找效率最高的二叉排序树是。 A.所有结点的左子树都为空的二叉排序树 B.所有节点的右子树都为空的二叉排序树 D.没有左子树的二叉排序树 17.下面关于B-树和B+树的叙述中,不正确的结论是。 树和B+树都能有效地支持顺序查找 B)B-树和B+树都能有效地支持随机查找 C)B-树和B+树都是平衡的多分支树 D)B-树和B+树都可用于文件索引结构 18.设有n个关键字,哈希查找法的平均查找长度是。 (1)B)O(n)C)O(log2n)D)O(n2) 19.将10个元素散列到100000个单元的哈希表,则产生冲突。 A)一定会B)一定不会D)以上都不对

中国铁道出版社数据结构(第二版)单元3练习参考答案

单元练习3 一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳) (√)(1)栈是运算受限制的线性表。 (√)(2)在栈空的情况下,不能作出栈操作,否则产生下溢出。 (ㄨ)(3)栈一定是顺序存储的线性结构。 (√)(4)栈的特点是“后进先出”。 (ㄨ)(5)空栈就是所有元素都为0的栈。 (ㄨ)(6)在C或C++语言中设顺序栈的长度为MAXLEN,则top=MAXLEN时表示队满。 (√)(7)链栈与顺序栈相比,其特点之一是通常不会出现栈满的情况。 (ㄨ)(8)一个栈的输入序列为:A,B,C,D,可以得到输出序列:C,A,B,D。 (ㄨ)(9)递归定义就是循环定义。 (√)(10)将十进制数转换为二进制数是栈的典型应用之一。 二.填空题 (1)在栈结构中,允许插入、删除的一端称为栈顶。 (2)在顺序栈中,当栈顶指针top=-1时,表示栈空。 (3)在有n个元素的栈中,进栈操作的时间复杂度为 O(1)。 (4)在栈中,出栈操作的时间复杂度为:O(1) 。 (5)已知表达式,求它的后缀表达式是栈的典型应用。 (6)在一个链栈中,若栈顶指针等于NULL,则表示栈空。 (7)向一个栈顶指针为top的链栈插入一个新结点*p时,应执行p->next=top;和top=p;操作。 (8)顺序栈S存储在数组 S->data[0..MAXLEN-1]中,进栈操作时要执行的语句有:S->top ++ 。(或= S->top+1) (9)链栈LS,指向栈顶元素的指针是 LS->next 。 (10)从一个栈删除元素时,首先取出栈顶元素,然后再移动栈顶指针。 (11)由于链栈的操作只在链表的头部进行,所以没有必要设置头结点。 (12)已知顺序栈S,在对S进行进栈操作之前首先要判断栈是否满。 (13)已知顺序栈S,在对S进行出栈操作之前首先要判断栈是否空。 (14)若内存空间充足,链栈可以不定义栈满运算。 (15)链栈LS是空的条件是 LS->next=NULL 。 (16)链栈LS的栈顶元素是链表的首元素。 (17)同一栈的各元素的类型相同。 (18)若进栈的次序是A、B、C、D、E,执行三次出栈操作以后,栈顶元素为 B 。 (19)A+B/C-D*E的后缀表达式是:ABC/+DE*- 。 (20)四个元素按A、B、C、D顺序进S栈,执行两次Pop(S,x)运算后,x的值是 C 。

数据结构练习试题和答案解析

第1章绪论 一、判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。(√) 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。(√) 3.数据元素是数据的最小单位。(×) 4.数据的逻辑结构和数据的存储结构是相同的。(×) 5.程序和算法原则上没有区别,所以在讨论数据结构时可以通用。(×) 6.从逻辑关系上讲,数据结构主要分为线性结构和非线性结构两类。(√) 7.数据的存储结构是数据的逻辑结构的存储映象。(√) 8.数据的物理结构是指数据在计算机实际的存储形式。(√) 9.数据的逻辑结构是依赖于计算机的。(×) 10.算法是对解题方法和步骤的描述。(√) 二、填空题 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外,还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类,它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中,除了树根结点以外,其余每个结点只有1个前驱结点。 6.在图形结构中,每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法(或运算)3个方面的容。 13.数据结构被定义为(D,R),其中D是数据的有限集合,R是D上的关系有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算法和事后统计法。 16.一个算法的时间复杂度是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间,它是该算法求解问题规模的n的函数。 18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O(nlog2n)。 19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O(n2)。 20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象,以及它们之间的关系和运算的学 科。 三、选择题 1.数据结构通常是研究数据的(A)及它们之间的相互关系。 A.存储结构和逻辑结构B.存储和抽象C.联系和抽象D.联系与逻辑 2.在逻辑上可以把数据结构分成(C)。 A.动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构D.部结构和外部结构。 3.数据在计算机存储表示时,物理地址和逻辑地址相同并且是连续的,称之为(C)。 A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构 4.非线性结构中的每个结点(D)。 A.无直接前驱结点.B.无直接后继结点.

数据结构 实验报告三

实验三的实验报告 学期: 2010 至_2011 第 2 学期 2011年 3月 27日课程名称: 数据结构专业:信息与计算科学 09 级5班实验编号: 03 实验项目:栈和队列实验指导教师 _冯山_姓名:朱群学号: 2009060548 实验成绩: 一实验目的: (1)熟练掌握栈和队列的抽象数据类型及其结构特点; (2)实现基本的栈和队列的基本操作算法程序。 二实验内容:(类C算法的程序实现,任选其一) (1) 设计与实现基本的堆栈和队列结构下的各种操作(如堆栈的PUSH、POP 等操作)(必做); (2)以表达式计算为例,完成一个可以进行算术表达式计算功能的算法设计 与实现(选做); (3)以迷宫问题为例,以堆栈结构完成迷宫问题的求解算法和程序(选做)。三实验准备: 1) 计算机设备;2)程序调试环境的准备,如TC环境;3)实验内容的算法分 析与代码设计与分析准备。 四实验步骤: 1.录入程序代码并进行调试和算法分析; 2.编写实验报告。 五实验过程 一设计与实现基本的堆栈结构下的各种操作(如堆栈的PUSH、POP等操作)(1)问题描述 实现堆栈各种基本操作,如Pop,Push,GetTop等操作,即输入数据,通过Push入栈,再通过Pop操作输出出栈的元素,即入栈a,b,c,d,出栈d,c,b,a (2)算法实现及基本思想 堆栈是后进先出的线性表,由Push输入元素,Pop输出元素,堆栈的Push 操作思想,即插入元素e为新的的栈顶元素,先判断栈满与否,追加存储空间,然后将e值赋给栈顶指针Top。输入数据时用for循环 堆栈的Pop操作思想,先判断栈是否为空,若栈不空,则删除栈的栈顶元素,用e返回其值, (3)数据结构 栈的顺序存储结构 Typedef struct {

中国铁道出版社数据结构(第二版)单元8练习参考答案

单元练习8 一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳) (√)(1)图可以没有边,但不能没有顶点。 (ㄨ)(2)在无向图中,(V1,V2)与(V2,V1)是两条不同的边。 (ㄨ)(3)邻接表只能用于有向图的存储。 (√)(4)一个图的邻接矩阵表示是唯一的。 (ㄨ)(5)用邻接矩阵法存储一个图时,所占用的存储空间大小与图中顶点个数无关,而只与图的边数有关。 (ㄨ)(6)有向图不能进行广度优先遍历。 (√)(7)若一个无向图的以顶点V1为起点进行深度优先遍历,所得的遍历序列唯一,则可以唯一确定该图。 (√)(8)存储无向图的邻接矩阵是对称的,因此只要存储邻接矩阵的上三角(或下三角)部分就可以了。 (ㄨ)(9)用邻接表法存储图时,占用的存储空间大小只与图中的边数有关,而与结点的个数无关。(√)(10)若一个无向图中任一顶点出发,进行一次深度优先遍历,就可以访问图中所有的顶点,则该图一定是连通的。 二.填空题 (1)图常用的存储方式有邻接矩阵和邻接表等。 (2)图的遍历有:深度优先搜和广度优先搜等方法。 (3)有n条边的无向图邻接矩阵中,1的个数是 _2n____。 (4)有向图的边也称为 _ 弧___ 。 (5)图的邻接矩阵表示法是表示 __顶点____之间相邻关系的矩阵。 (6)有向图G用邻接矩阵存储,其第i行的所有元素之和等于顶点i的 __出度____。 (7)n个顶点e条边的图若采用邻接矩阵存储,则空间复杂度为:O(n2)。 (8)n个顶点e条边的图若采用邻接表存储,则空间复杂度为:O(n+e)。 (9)设有一稀疏图G,则G采用 _邻接表____存储比较节省空间。 (10)设有一稠密图G,则G采用 _邻接矩阵____存储比较节省空间。 (11)图的逆邻接表存储结构只适用于 __有向____图。 (12) n个顶点的完全无向图有 n(n-1)/2_ 条边。 (13)有向图的邻接表表示适于求顶点的出度。 (14)有向图的邻接矩阵表示中,第i列上非0元素的个数为顶点V i的入度。 (15)对于具有n个顶点的图,其生成树有且仅有n-1 条边。 (16)对n个顶点,e条弧的有向图,其邻接表表示中,需要n+e 个结点。 (17)从图中某一顶点出发,访遍图中其余顶点,且使每一顶点仅被访问一次,称这一过程为图的遍历。 (18)无向图的邻接矩阵一定是对称矩阵。

数据结构_实验三_栈和队列及其应用

实验编号:3四川师大《数据结构》实验报告2016年10月29日 实验三栈与队列及其应用_ 一.实验目得及要求 (1)掌握栈与队列这两种特殊得线性表,熟悉它们得特性,在实际问题背景下灵活运用它们; (2)本实验训练得要点就是“栈”得观点及其典型用法; (3)掌握问题求解得状态表示及其递归算法,以及由递归程序到非递归程序得转化方法。 二.实验内容 (1)编程实现栈在两种存储结构中得基本操作(栈得初始化、判栈空、入栈、出栈等); (2)应用栈得基本操作,实现数制转换(任意进制); (3)编程实现队列在两种存储结构中得基本操作(队列得初始化、判队列空、入队列、出队列); (4)利用栈实现任一个表达式中得语法检查(括号得匹配)。 (5)利用栈实现表达式得求值。 注:(1)~(3)必做,(4)~(5)选做。 三.主要仪器设备及软件 (1)PC机 (2)Dev C++ ,Visual C++, VS2010等 四.实验主要流程、基本操作或核心代码、算法片段(该部分如不够填写,请另加附页)(1)编程实现栈在两种存储结构中得基本操作(栈得初始化、判栈空、入栈、出栈等); A、顺序储存: ?代码部分: //Main、cpp: #include"SStack、h" int main() { SqStack S; SElemType e;

int elect=1; InitStack(S); cout << "已经创建一个存放字符型得栈" << endl; while (elect) { Muse(); cin >> elect; cout << endl; switch (elect) { case 1: cout << "input data:"; cin >> e; Push(S, e); break; case 2: if(Pop(S, e)) {cout << e <<" is pop"<< endl; } else{cout<<"blank"<

操作系统 第三版 中国铁路出版社

第一章引论 1、计算机硬件是指计算机系统中由电子、机械和光电元件等组成的各种部件和设备。由这些部件和设备依据计算机系统结构的要求构成的有机整体,称为计算机硬件系统 2、计算机软件是指安装在计算机系统中的程序和有关的文件 3、按应用将软件分类为:系统软件、支撑软件和应用软件 4、操作系统的定义:操作系统是计算机系统中的系统软件,能有效的组织和管理计算机系统中的硬件和软件资源,合理的组织计算机工作流程,控制程序的执行,并向用户提供各种服务功能,使的用户能够合理、方便、有效的使用计算机,使整个计算机系统能更高效运行的一组程序模块的集合。 5、操作系统的目标:①方便性。②有效性。③可扩充性。④开放性。 6、单道批处理系统的特征:①自动性。②顺序性。③单道性。 7、多处理机操作系统的类型:①非对称多处理机模式②对称多处理机模式 8、网络操作系统的功能:①网络通信。②资源管理。③网络服务。 ④网络管理。⑤互操作能力。 9、资源的分类(4类):处理机、存储器、I/O设备以及文件(程序和数据)。 10、处理及管理的功能:1进程控制 2进程同步 3进程通信 4调度。

11、处理机 :一般的处理机由运算器、一系列的寄存器以及高速缓存构成。 12、计算机存储系统的设计主要考虑3个问题:容量、速度和成本。 13、缓冲区:硬件设备之间进行数据传输时,专门用来暂存这些数据的一个存储区域。 第二章用户接口和作业管理 1、作业;通常是指用户在一次计算过程中或者一次事物处理过程中要求计算机系统所做的工作的集合。 2、每个作业有一个作业控制块,所有作业的作业控制块构成一个表,该表称为作业表 3、操作系统与用户之间的接口可以分为命令接口、程序接口和图形接口。 4、一个作业的建立过程包括两个子过程:一个是作业控制块JCB的建立,一个是作业的输入。 5、一般可以将作业的状态分为4个状态,即提交状态、后备状态、运行状态、完成状态。 第三章进程与进程管理 1、进程:进程是具有独立功能的可并发执行的程序在一个数据集合上的运行过程 2、进程的特征:(1)动态性(2)并发性(3)独立性(4)异步

数据结构练习附答案

一、单项选择题 1.逻辑关系是指数据元素间的() A.类型 B.存储方式 C.结构 D.数据项 2.对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构 为( ) A.顺序表 B.用头指针表示的单循环链表 C. 用尾指针表示的单循环链表 D. 单链表 3.设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear 为队尾指针,则执行出队操作后其头指针front值为() A.front=front+1 B.front= (front+1)%(m-1) C.front=(front-1)%m D.front=(fro nt+1)%m 4.在具有n个单元的顺序存储的循环队列中,假定front和rear分别 为队头指针和队尾指针,则判断队满的条件为( )。 A.rear%n==front B.(front+l)%n==rear C.rear%n-1==front D.(rear+l)%n==front 5.在具有n个单元的顺序存储的循环队列中,假定front和rear分别 为队头指针和队尾指针,则判断队空的条件为( )。 A.rear%n==front B.front+l=rear C.rear==front D.(rear+l)%n=front 6.已知一颗二叉树上有92个叶子结点,则它有____个度为2的结点。 ( ) A. 90 B. 91 C. 92 D. 93 7.在一棵非空二叉树的中序遍历序列中,根结点的右边_____。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的所有结点 D. 只有左子树上的部分结点 8.有n条边的无向图的邻接表存储法中,链表中结点的个数是( )个。 A. n B. 2n C. n/2 D. n*n 9.判断有向图是否存在回路,除了可利用拓扑排序方法外,还可以利 用()。 A. 求关键路径的方法 B.求最短路径的方法 C. 深度优先遍历算法 D.广度优先遍历算法 10.对线性表进行二分查找时,要求线性表必须( )。

数据结构实验三

实验报告 学院(系)名称:计算机科学与工程学院 姓名赵振宇学号20175302 专业 计算机科学与技术 班级 2017级4班实验项目 实验三:图的遍历与应用 课程名称 数据结构与算法 课程代码 0661913 实验时间 2019年5月27日 第3、4节 实验地点 7-219 考核标准实验过程25分 程序运行20分 回答问题15分 实验报告30分 特色功能5分 考勤违纪情况5分 成绩 成绩栏 其它批改意见: 教师签字: 考核内容 评价在实验课堂中的表现,包括实验态度、编写程序过程等内容等。 □功能完善,□功能不全□有小错□无法运行 ○正确○基本正确○有提示○无法回答 ○完整○较完整 ○一般 ○内容极少○无报告 ○有 ○无 ○有 ○无一、实验目的 1、实验目的:通过实验使学生理解图的主要存储结构,掌握图的构造算法、图的深度优先和广度优先遍历算法,能运用图解决具体应用问题。 二、实验题目与要求 要求:第1题为必做题,2,3,4至少选一 1.输入指定的边数和顶点数建立图,并输出深度优先遍历和广度优先遍历的结果。 1)问题描述:在主程序中设计一个简单的菜单,分别调用相应的函数功能:1…图的建立2…深度优先遍历图3…广度优先遍历图0…结束

2)实验要求:在程序中定义下述函数,并实现要求的函数功能:CreateGraph():按从键盘的数据建立图 DFSGrahp():深度优先遍历图 BFSGrahp():广度优先遍历图 3)实验提示: 图的存储可采用邻接表或邻接矩阵; 图存储数据类型定义(邻接表存储) #define MAX_VERTEX_NUM8//顶点最大个数 typedef struct ArcNode {int adjvex; struct ArcNode*nextarc; int weight;//边的权 }ArcNode;//表结点 #define VertexType int//顶点元素类型 typedef struct VNode {int degree,indegree;//顶点的度,入度 VertexType data; ArcNode*firstarc; }Vnode/*头结点*/,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum;//顶点的实际数,边的实际数}ALGraph; 4)注意问题: 注意理解各算法实现时所采用的存储结构。 注意区别正、逆邻接。 2.教学计划编制问题

数据结构实验3二叉树

一、实验目的 1.进一步掌握指针变量的含义。 2.掌握二叉树的结构特征,以及各种存储结构的特点及使用范围。 3.掌握用指针类型描述、访问和处理二叉树的运算。 二、实验要求 1.认真阅读和掌握本实验的参考程序。 2.按照对二叉树的操作需要,在创建好二叉树后再通过遍历算法验证创建结果。3.保存程序的运行结果,并结合程序进行分析。 三、实验内容 以下参考程序是按完全二叉树思想将输入的字符串生成二叉树,并通过遍历来验证二叉树创建正确与否,但不能创建非完全二叉树,请认真研究该程序,然后模仿教材例6.4初始化方式创建二叉树:所有的空指针均用#表示,如教材图 6-13对应的二叉树,建立时的初始序列为:AB#D##CE##F##。然后通过遍历算法验证二叉树是否正确(先递归验证后非递归验证)。 参考程序略 程序代码如下: #include "stdio.h" #include "stdlib.h" typedef char Datatype; #define MAXSIZE 100 typedef struct bnode { Datatype data; struct bnode *lchild,*rchild; }BNode,*BTree; typedef struct{ BTree data[MAXSIZE]; int front,rear; }seqqueue,*Pseqqueue; typedef struct{ BNode *node; int flag; }Data; typedef struct node { Data Data[MAXSIZE]; int top; }SeqStack,*PSeqStack; PSeqStack Init(void)

中国铁道出版社数据结构(第二版)单元4练习参考答案

单元测验4 一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳) (√)(1)队列是限制在两端进行操作的线性表。 (√)(2)判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。 (×)(3)在链队列上做出队操作时,会改变front指针的值。 (√)(4)在循环队列中,若尾指针rear大于头指针front,其元素个数为rear- front。(×)(5)在单向循环链表中,若头指针为h,那么p所指结点为尾结点的条件是p=h。(√)(6)链队列在一定范围内不会出现队满的情况。 (×)(7)在循环链队列中无溢出现象。 (×)(8)栈和队列都是顺序存储的线性结构。 (×)(9)在队列中允许删除的一端称为队尾。 (×)(10)顺序队和循环队关于队满和队空的判断条件是一样的。 二.填空题 (1)在队列中存取数据应遵循的原则是先进先出。 (2)队列是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。 (3)在队列中,允许插入的一端称为队尾。 (4)在队列中,允许删除的一端称为队首(或队头)。 (5)队列在进行出队操作时,首先要判断队列是否为空。 (6)顺序队列在进行入队操作时,首先要判断队列是否为满。 (7)顺序队列初始化后,front=rear= -1 。 (8)解决顺序队列“假溢出”的方法是采用循环队列。 (9)循环队列的队首指针为front,队尾指针为rear,则队空的条件为 front == rear 。 (10)链队列LQ为空时,LQ->front->next= NULL 。 (11)设长度为n的链队列用单循环链表表示,若只设头指针,则入队操作的时间复杂度为 O(n)。 (12)设长度为n的链队列用单循环链表表示,若只设尾指针,则出队操作的时间复杂度为 0(1)。 (13)在一个链队列中,若队首指针与队尾指针的值相同,则表示该队列为空。

数据结构练习3答案

数据结构练习(三)参考 一、选择题 1?顺序查找法适合于存储结构为________ 的线性表 A) 哈希存储| B )顺序存储或链式存储 C)压缩存储 D )索引存储 2. —个长度为100的已排好序的表,用二分查找法进行查找,若查找不成功,至 少比较__________ 。 A) 9 B)8 C)7 |D) 6 3. 采用顺序查找方法查找长度为n的线性表时,平均比较次数为_________ 。 A) n B) n/2 G 5+1)/2 D) (n-1 ) /2 4. 对线性表进行折半查找时,要求线性表必须________ 。 A )以顺序方式存储以顺序方式存储,且结点按关键字有序排列 C )以链表方式存储 D )以链表方式存储,且结点按关键字有序排列 5. 采用二分查找法查找长度为n的线性表时,每个元素的平均查找长度 为 ______ 。 A) O (n2) B) O (nlog2n) C) O (n) D) O (log2n) 6. 有一个长度为12的有序表R[0…11],按折半查找法对该表进行查找,在 表内各元素等概率查找情况下查找成功所需的平均比较次数为 _________ 。 A) 35/12 B) 37/12 C) 39/12 D) 43/12 7. 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,99},当采用折半查找法查找关键字为82的元素时,________ 次比较后查找成功。 A) 1 B.2 C)4 D ) 8 8. 当采用分块查找时,数据的组织方式为________ o A )数据分成若干块,每块内存数据有序 B )数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最 小)的数据组成索引块 C)数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块

中国铁道出版社数据结构(第二版)单元9练习参考答案

单元练习9 一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳) (√)(1)二分查找法要求待查表的关键字值必须有序。 (ㄨ)(2)对有序表而言采用二分查找总比采用顺序查找法速度快。 (ㄨ)(3)在二叉排序树中,根结点的值都小于孩子结点的值。 (√)(4)散列存储法的基本思想是由关键字的值决定数据的存储地址。 (√)(5)哈希表是一种将关键字转换为存储地址的存储方法。 (ㄨ)(6)选择好的哈希函数就可以避免冲突的发生。 (ㄨ)(7)在有序的顺序表和有序的链表上,均可以采用二分查找来提高查找速度。 (√)(8)采用分块查找,既能实现线性表所希望的查找速度,又能适应动态变化的需要。 (√)(9)哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。 (ㄨ)(10)在二叉排序树上删除一个结点时,不必移动其它结点,只要将该结点的父结点的相应的指针域置空即可。 二.填空题 (1)顺序查找法,表中元素可以任意存放。 (2)在分块查找方法中,首先查找索引,然后再查找相应的块。 (3)顺序查找、二分查找、分块查找都属于静态查找。 (4)静态查找表所含元素个数在查找阶段是固定不变的。 (5)对于长度为n的线性表,若进行顺序查找,则时间复杂度为 O(n)。 (6)对于长度为n的线性表,若采用二分查找,则时间复杂度为: O(log2n)。 (7)理想情况下,在散列表中查找一个元素的时间复杂度为: O(1)。 (8)在关键字序列(7,10,12,18,28,36,45,92)中,用二分查找法查找关键字92,要比较 4 次才找到。 (9)设有100个元素,用二分查找时,最大的比较次数是 7 次。 (10)对二叉排序树进行查找的方法是用待查的值与根结点的键值进行比较,若比根结点小,则继续在左子树中查找。 (11)二叉排序树是一种动态查找表。 (12)哈希表是按散列存储方式构造的存储结构 (13)哈希法既是一种存储方法,又是一种查找方法。 (14)散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。(15)设散列函数H和键值k1,k2,若k1≠k2,且H(k1)=H(k2),则称这种现象为冲突。(16)处理冲突的两类主要方法是开放定址法和拉链法(或链地址法)。 (17)散列表(或散列)查找法的平均查找长度与元素个数n无关。 (18)在哈希函数H(key)=key % P中,P一般应取质数。 (19)在查找过程中有插入元素或删除元素操作的,称为动态查找。 (20)各结点左右子树深度之差的绝对值至多为 1 的二叉树称谓平衡二叉树。

数据结构课程课后习题答案.

《数据结构简明教程》练习题及参考 答案 练习题1 1. 单项选择题 (1)线性结构中数据元素之间是()关系。 A.一对多 B.多对多 C.多对一 D.一对一 答:D (2)数据结构中与所使用的计算机无关的是数据的()结构。 A.存储 B.物理 C.逻辑 D.物理和存储 答:C (3)算法分析的目的是()。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 答:C (4)算法分析的两个主要方面是()。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 答:A (5)计算机算法指的是()。 A.计算方法 B. 排序方法 C.求解问题的有限运算序列 D.调度方法 答:C (6)计算机算法必须具备输入、输出和()等5个特性。 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答:B 2. 填空题 (1)数据结构包括数据的①、数据的②和数据的③这三个方面的内容。

数据结构简明教程 答:①逻辑结构 ②存储结构 ③运算 (2)数据结构按逻辑结构可分为两大类,它们分别是 ① 和 ② 。 答:①线性结构 ②非线性结构 (3)数据结构被形式地定义为(D,R ),其中D 是 ① 的有限集合,R 是D 上的 ② 有限集合。 答:①数据元素 ②关系 (4)在线性结构中,第一个结点 ① 前驱结点,其余每个结点有且只有1个前驱结点;最后一个结点 ② 后继结点,其余每个结点有且只有1个后继结点。 答:①没有 ②没有 (5)在树形结构中,树根结点没有 ① 结点,其余每个结点有且只有 ② 个前驱结点;叶子结点没有 ③ 结点,其余每个结点的后继结点数可以是 ④ 。 答:①前驱 ②1 ③后继 ④任意多个 (6)在图形结构中,每个结点的前驱结点数和后继结点数可以是( )。 答:任意多个 (7)数据的存储结构主要有四种,它们分别是 ① 、 ② 、 ③ 和 ④ 存储结构。 答:①顺序 ②链式 ③索引 ④哈希 (8)一个算法的效率可分为 ① 效率和 ② 效率。 答:①时间 ②空间 3. 简答题 (1)数据结构和数据类型两个概念之间有区别吗? 答:简单地说,数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素,而且还在其上定义了一组操作。 (2)简述线性结构、树形结构和图形结构的不同点。 答:线性结构反映结点间的逻辑关系是一对一的,树形线性结构反映结点间的逻辑关系是一对多的,图在结构反映结点间的逻辑关系是多对多的。 (3)设有采用二元组表示的数据逻辑结构S=(D,R),其中D={a ,b ,…,i },R={(a ,b ),(a ,c ),(c ,d ),(c ,f ),(f ,h ),(d ,e ),(f ,g ),(h ,i )},问相对于关系R ,哪些结点是开始结点,哪些结点是终端结点? 答:该逻辑结构为树形结构,其中a 结点没有前驱结点,称为根结点,b 、e 、g 、i 结点没有后继结点,是终端结点,也称为叶子结点。 (4)以下各函数是算法中语句的执行频度,n 为问题规模,给出对应的时间复杂度: T 1(n )=n log 2n -1000log 2n T 2(n )=3log 2n -1000log 2n T 3(n )=n 2-1000log 2n T 4(n )=2n log 2n -1000log 2n 答:T 1(n )=O(n log 2n ),T 2(n )=O( ),T 3(n )=O(n 2),T 4(n )=O(n log 2n )。 (5)分析下面程序段中循环语句的执行次数。 int j=0,s=0,n=100; 3 log 2n

数据结构实验3

数据结构实验3

《数据结构与算法》实验报告 实验序号:3 实验项目名称:链式表的操作学号1507112104 姓名陈忠表专业、班15商智实验地点指导教师林开标实验时间16.11.09 一、实验目的及要求 1. 通过实验理解单链表的逻辑结构; 2. 通过实验掌握单链表的基本操作和具体的函数实现。 二、实验设备(环境)及要求 微型计算机; windows 操作系统; Microsoft Visual Studio 6.0集成开发环境。 三、实验内容与步骤 链式表表示和实现线性表的如下: #include"stdio.h" #include"stdlib.h" typedef struct node //定义结点 { int data; //结点的数据域为整型 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自

定义LinkList单链表类型 LinkList CreatListR1(); //函数,用尾插入法建立带头结点的单链表 ListNode *LocateNode(LinkList head, int key); //函数,按值查找结点 void DeleteList(LinkList head,int key); //函数,删除指定值的结点 void printlist(LinkList head); //函数,打印链表中的所有值 void DeleteAll(LinkList head); //函数,删除所有结点,释放内存 //==========主函数============== void main() { int num; char ch; LinkList head; head=CreatListR1(); //用尾插入 法建立单链表,返回头指针 printlist(head); //遍历链表 输出其值 printf(" Delete node (y/n):"); //输入

相关文档