文档库 最新最全的文档下载
当前位置:文档库 › 数据结构作业3

数据结构作业3

数据结构作业3
数据结构作业3

第3章栈和队列

【书面作业】

1.简述以下算法的功能(栈的元素类型SElemType为int)。

(1) status algo1(Stack S) {

int i ,n ,A[255];

n=0;

while (! StackEmpty(S) ) { n++; Pop(S,A[n]);};

for (i=1;i<=n;i++) Push(S,A[i]);

}

(2) status algo2(Stack S, int e) {

Stack T;int d;

InitStack(T);

while (!StackEmpty(S)) {

Pop(S,d);

if (d!=e) Push(T,d);

}

while (!StackEmpty(T)) {

Pop(T,d);

Push(S,d);

}

}

2.写出以下程序段的输出结果(队列中元素类型QElemType为char)。

void main( ) {

Queue Q; InitQueue(Q);

Char x=’e’,y=’c’;

EnQueue(Q,’h’); EnQueue(Q,’r’);EnQueue(Q,y);

DeQueue(Q,x);EnQueue(Q,x);

DeQueue(Q,x);EnQueue(Q,’a’);

while (!QueueEmpty (Q)) {

DeQueue(Q,y);

printf(y);

}

printf(x);

}

3.有6个元素a,b,c,d,e,f依次进栈,允许任何时候出栈,能否得到下列出栈序列?

(1)cdbefa (2)abedfc (3) dceabf (4)baefcd (5)abcdef

4.用一维数组a[7]顺序存储一个循环队列,队首和队尾指针分别用front和rear表示,当前队列中已有5个元素:23,45,67,80,34,其中,23为队首元素,front的值为3,请画出对应的存储状态,当连续做4次出队运算后,再

让15,36,48元素依次进队,请再次画出对应的存储状态。

【上机作业】

1.试写一个将某十进制数转化为其他任意进制数的算法。

2.试写一个判别表达式中开、闭括号是否配对出现的算法。

3.教材P64上循环队列算法实现。

数据结构第3次作业

1. 填空题 (1) 顺序栈s的数据存储在数组element中,则栈满的条件是____________,栈空的条件是。 (2) 顺序栈s进行出栈操作后,要执行的语句是top____。s进行进栈操作前,要执行的语句是top______运算。 (3) 元素进入队列的一端是____________;队列出队的一端是____________。 (4)顺序队列q满的条件是,顺序队列q空的条件 是。 (5) 空串的长度等于,非空串的长度等于。 2. 选择题 (1) 串是一种特殊的线性表,其特征体现在_____。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 (2) 栈是限定在__________处进行插入或删除操作的线性表。 A. 端点 B. 栈底 C. 栈顶 D. 中间 (3) 在栈顶一端可进行的全部操作是___________。 A. 插入 B.删除 C. 插入和删除 D. 进栈 (4) 4个元素按A、B、C、D顺序连续进S栈,进行x=pop()运算后,x的值是___________, 栈顶元素的值是. A. A B. B C. C D. D (5) 栈的特点是__________。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不进不出 (6) 顺序栈存储空间的实现使用___________。 A. 链表 B. 数组 C.循环链表 D. 变量 (7) 一个顺序栈一旦说明,其占用空间的大小___________。 A. 已固定 B. 可以改变 C. 不能固定 D. 动态变化 (8) 栈与一般线性表的区别主要在___________方面。 A. 元素个数 B. 元素类型 C. 逻辑结构 D. 插入、删除元素的位置 (9) 栈s经过下列运算后s.get()的值是___________, s.isEmpty( )的值是___________。 s.push(a);s.push(b);s.pop(); A. a B. b C. 1 D. 2

数据结构第三章习题答案

第三章习题 1.按图3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度,回答: ⑴如进站的车厢序列为123,则可能得到的出站车厢序列是什么? ⑵如进站的车厢序列为123456,能否得到435612和135426的出站序列,并说明原因。(即写出 以“S”表示进栈、以“X”表示出栈的栈操作序列)。 2.设队列中有A、B、C、D、E这5个元素,其中队首元素为A。如果对这个队列重复执行下列4步 操作: (1)输出队首元素; (2)把队首元素值插入到队尾; (3)删除队首元素; (4)再次删除队首元素。 直到队列成为空队列为止,得到输出序列: (1)A、C、E、C、C (2) A、C、E (3) A、C、E、C、C、C (4) A、C、E、C 3.给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满? 4.按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,画出对下列算术表达式求值时操 作数栈和运算符栈的变化过程: A-B*C/D+E↑F 5.试写一个算法,判断依次读入的一个以@为结束符的字母序列,是否为形如‘序列1& 序列2’ 模式的字符序列。其中序列1和序列2中都不含字符’&’,且序列2是序列1的逆序列。例如,‘a+b&b+a’是属该模式的字符序列,而‘1+3&3-1’则不是。 6.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法,将一个通常书写形式且书写 正确的表达式转换为逆波兰式。 7.假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针), 试编写相应的队列初始化、入队列和出队列的算法。 8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分 头尾指针相同时的队列状态的空与满,请编写与此结构相应的入队与出队算法。

南京工业大学 数据结构 作业答案 作业6

第六次作业 1. 假定对有序表:(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题: (1)画出描述折半查找过程的判定树; (2)若查找元素54,需依次与哪些元素比较? (3)若查找元素90,需依次与哪些元素比较? (4)假定每个元素的查找概率相等,求查找成功时的平均查找长度。 2. 设哈希(Hash)表的地址范围为0~17,哈希函数为:H(K)=K MOD 16。 K为关键字,用线性探测法再散列法处理冲突,输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49) 造出Hash表,试回答下列问题: (1)画出哈希表的示意图; (2)若查找关键字63,需要依次与哪些关键字进行比较? (3)若查找关键字60,需要依次与哪些关键字比较? (4)假定每个关键字的查找概率相等,求查找成功时的平均查找长度。 3. 在一棵空的二叉查找树中依次插入关键字序列为12,7,17,11,16,2,13,9,21,4,请画出所得到的二叉查找树。 4. 试写一个判别给定二叉树是否为二叉排序树的算法,设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。 1.假定对有序表:(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题: (5)画出描述折半查找过程的判定树; (6)若查找元素54,需依次与哪些元素比较? (7)若查找元素90,需依次与哪些元素比较? (8)假定每个元素的查找概率相等,求查找成功时的平均查找长度。 解: (1)先画出判定树如下(注:mid=?(1+12)/2?=6): 30 5 63 3 7 42 87 4 24 54 72 95 (2) 查找元素54,需依次与30, 63, 42, 54 等元素比较; (3) 查找元素90,需依次与30, 63,87, 95, 72等元素比较; (4)求ASL之前,需要统计每个元素的查找次数。判定树的前3层共查找1+2×2+4×3=17次; 但最后一层未满,不能用8×4,只能用5×4=20次, 所以ASL=1/12(17+20)=37/12≈3.08

完整版数据结构习题集第3章栈和队列

第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是(A )。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示,则栈ST 为空的条件是( B ) A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时,则执行( C ) A、HS->next=s; B、s->next=HS->next;HS->next=s; C、s->next=HS;HS=s; D、s->next=HS;HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点,用x 保存被删除结点的值,则执行( C) A 、x=HS;HS=HS->next; B 、HS=HS->next;x=HS->data; C 、x=HS->data;HS=HS->next; D 、s->next=Hs;Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为( B ) A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-(B+C/D)*E 的后缀形式是( D ) A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1,2,3,4,则队列的输出序列是( B ) A、4,3,2,1 B、1,2,3,4 C、1,4,3,2 D、3,2,4,1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值,已知其头尾指针分别是front 和rear,则判定此循环队列为空的条件是() A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值,已知其头尾指针分别是front 和rear,则判定此循环队列为满的条件是() A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列,且当前rear 和front 的值分别为0 和3,当从 队列中删除一个元素,再加入两个元素后,rear 和front 的值分别为() A、1,5 B、2, 4 C、4,2 D、5,1 11.用单链表表示的链式队列的队头在链表的()位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q(最多元素为n 个)为空的条件是() A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中,插入s 所指结点需顺序执行的指令是() A 、Q.front->next=s;f=s; B 、Q.rear->next=s;Q.rear=s;

计算机文化基础-第三次在线作业

计算机文化基础 第三次在线作业 单选题 (共40道题) 展开 收起 1.( 2.5分)Internet实现了分布在世界各地的各类网络的互联,其最基础和核心的协议是()。 ? A、HTTP ? B、FTP ? C、HTML ? D、TCP/IP 我的答案:D 此题得分:2.5分 2.(2.5分)在下述计算机网络的拓扑结构中,可靠性好,适用于广域网中的是()。 ? A、网状结构 ? B、星型结构 ? C、总线结构 ? D、树形结构

我的答案:A 此题得分:2.5分 3.(2.5分)对于个人用户而言,在一般情况下,使用()连入Internet是一个较为恰当的选择。 ? A、专线连接 ? B、微机局域网连接 ? C、微波连接 ? D、电话拨号连接 我的答案:D 此题得分:2.5分 4.(2.5分)以下不是常用的传输媒体的是()。 ? A、双绞线 ? B、同轴电缆 ? C、光纤 ? D、电线 我的答案:D 此题得分:2.5分 5.(2.5分)支持局域网与广域网互连的设备称为()。 ? A、交换机 ? B、路由器 ? C、转发器 ? D、网桥 我的答案:B 此题得分:2.5分

6.(2.5分)下列关于IP地址的叙述中正确的是()。 ? A、IP地址是4个由点号分开的十进制数组成,因此必须转换为二进制数,才能被计算机识别。 ? B、IP地址的分为A、B、C、D、E类,一般从IP地址中第一个数字的取值范围,就能辨别出IP地址的种类。 ? C、IP地址是唯一的,可以任意使用。 ? D、通过拨号上网使用固定的IP地址,通过局域网上网则使用动态分配的IP地址 我的答案:B 此题得分:2.5分 7.(2.5分)以下是A类IP地址的是()。 ? A、126.256.2.6 ? B、202.205.2.1 ? C、102.24.5.21 ? D、224.200.11.31 我的答案:C 此题得分:2.5分 8.(2.5分)DNS的作用是()。 ? A、将数字信号转变成模拟信号 ? B、将十进制转换成二进制 ? C、将文本文件转换成二进制文件 ? D、将域名转换成IP地址 我的答案:D 此题得分:2.5分

数据结构第六章一二次作业

上机题 (1)编写完整程序,用先序遍历法建立二叉树的二叉链 表存储结构。输出该二叉树的先、中、后序遍历结 点访问次序以及层次遍历结点访问次序。(建议结 点数据域类型为char) // erchashu.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include #include typedef struct node { char data; struct node *lchild, *rchild; }*BiT, BiTNode; BiT crtBT() { char ch; BiT bt; ch=getchar(); if(ch=='#') return NULL; bt=new BiTNode(); bt->data=ch; bt->lchild=crtBT(); bt->rchild=crtBT(); return bt;

} void preorder(BiT bt) { if(bt) { printf("%c",bt->data); preorder(bt->lchild); preorder(bt->rchild); } //printf("\n"); } void midorder(BiT bt) { if(bt) { midorder(bt->lchild); printf("%c",bt->data); midorder(bt->rchild); } //printf("\n"); } void lasorder(BiT bt) { if(bt) { lasorder(bt->lchild); lasorder(bt->rchild); printf("%c",bt->data); } //printf("\n"); } int main(int argc, char* argv[]) { BiT bt; bt=crtBT(); preorder(bt); printf("\n"); midorder(bt); printf("\n"); lasorder(bt); printf("\n"); return 0; } (2)从键盘输入n个数据建立n元完全二叉树顺序存储结

数据结构作业及答案

第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R),其中K是1的有限集,R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中,从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构,线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1,算法分析的两个主要方面其一是指2,其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1,它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的,这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时,要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中,正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算:插入、删除和查找,这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和,树形结构和图形结构合称为。2.在线性结构中,第一个结点前驱结点,其余每个结点有且只有个前驱结点;最后一个结点后续结点,其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3;

第三次作业参考答案

?2.1 比较程序的顺序执行和并发执行。 答: 答: 1)进程是一个动态的概念,而程序则是一个静态的概念。程序是指令的有序集合,没有任何执行含义,而进程则强调执行过程,它动态地被创建,并被调度执行后消亡。 2)进程具有并行特征,而程序没有。进程具有并行特征的两个方面,即独立性和异步性。也就是说,在不考虑资源共享的情况下,各进程的执行是独立的,它们之间不存在逻辑上的制约关系,各进程的是异步的。由于程序不反映执行过程,所以不具有并行特征。 3)进程是系统中独立存在的实体,是竞争资源的基本单位。进程对应特殊的描述结构 并有申请、使用、释放资源的资格。由于系统中存在多个进程,系统资源的有限性必然导致多个进程对资源的共享和竞争,从而使进程的并行性受到系统的制约。 4)进程的存在必然需要程序的存在,但进程和程序不是一一对应的。由于进程是程序 的执行过程,所以程序是进程的一个组成部分。处于静止状态的程序并不对应于任何进程。当程序被处理机执行时,它一定属于某一个或者多个进程。属于进程的程序可以是一个,也可以是多个。不同的进程可以包含同一个程序,只要该程序所对应的数据集不同。 ?2.3 试对进程的状态及状态转换进行总结,注意状态转换的物理含义及转化条件。

答:处于就绪状态的进程,在调度程序为之分配了处理机之后,该进程便可执行,相应地,它就由就绪状态转变为运行状态。正在执行的进程也称为当前进程,如果分配给它的时间 片已完而被暂停执行时,该进程便由执行状态又回复到就绪状态;如果因发生某事件而使 进程的执行受阻,使之无法继续执行,该进程将由执行状态转变为阻塞状态。引入挂起状 态后,又增加了从挂起状态到非挂起状态之间的转换,当进程处于未被挂起的就绪状态时,用挂起原语Suspend将该进程挂起后,该进程便转变成为静止就绪状态,此时进程不再被 调度执行。当进程处于未被挂起的阻塞状态时,用Suspend原语将它挂起后,进程便转变 为静止阻塞状态,处于该状态的进程在其所期待的事件出现后,将从静止阻塞状态变成静 止就绪。处于活动就绪状态的进程,若用激活原语Active激活后,该进程将转变为挂起就 绪状态。处于活动阻塞状态的进程,若用激活原语Active激活后,将转变为阻塞挂起状态。 ?2.4 试举例说明引起进程创建、撤消、阻塞或被唤醒的主要事件分别有哪些? 答:引起进程创建,如用户登录;作业调度;提供服务;应用请求。 进程撤销,当一个进程到达了自然结束点,或时出现了无法克服的错误,或是被操作 系统所中介,或是被其他有终止权的进程所终结,都会引起进程撤销。 进程阻塞,请求系统服务,不能立即满足;启动某种操作,且必须在该操作完成之后才能 继续执行;新数据尚未到达,相互合作进程的一方需首先获得另一进程数据才能继续;无新工 作可做,特定功能系统进程当完成任务且暂无任务。 进程被唤醒,系统服务满足;操作完成;数据到达;新任务出现。 ?2.5 试根据你自己的理解,采用类C语言设计和描述操作系统关于进程控制块的数据结构、组织方式及管理机制。在此基础上,给出进程的创建、终止、阻塞、唤醒、挂起与激活等函数原型及函数代码。注意,对于过于复杂的功能或你无法解决的细节可采用指定功能的函数模块如处理机调度scheduler()来替代。 答:进程控制块的数据结构: Struct task_struct { long state; /*任务的运行状态(-1 不可运行,0 可运行(就绪),>0 已停止)*/ long counter;/*运行时间片计数器(递减)*/ long priority;/*优先级*/ long signal;/*信号*/ struct sigaction sigaction[32];/*信号执行属性结构,对应信号将要执行的操作和标志信息*/ long blocked; /* bitmap of masked signals */ /* various fields */ int exit_code;/*任务执行停止的退出码*/ unsigned long start_code,end_code,end_data,brk,start_stack; /*代码段地址代码长度(字节数) 代码长度 + 数据长度(字节数)总长度堆栈段地址*/ long pid,father,pgrp,session,leader;/*进程标识号(进程号) 父进程号父进程组号会话号会话首领*/ unsigned short uid,euid,suid;/*用户标识号(用户id)有效用户id 保存的用户id*/ unsigned short gid,egid,sgid; /*组标识号(组id)有效组id 保存的组id*/

数据结构第1章作业

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的()。 A.效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于() A.问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是(1),它必须具备(2)这三个特性。 (1) A.计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A.可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4.一个算法应该是()。 A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A和C. 5. 下面关于算法说法错误的是() A.算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是() (1)算法原地工作的含义是指不需要任何额外的辅助空间 (2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界 (4)同一个算法,实现语言的级别越高,执行效率就越低 A.(1) B.(1),(2) C.(1),(4) D.(3) 7.从逻辑上可以把数据结构分为()两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 8.以下与数据的存储结构无关的术语是()。 A.循环队列 B. 链表 C. 哈希表 D. 栈 9.以下数据结构中,哪一个是线性结构()? A.广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10.以下那一个术语与数据的存储结构无关?() A.栈 B. 哈希表 C. 线索树 D. 双向链表 11.在下面的程序段中,对x的赋值语句的频度为() FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A. O(2n) B.O(n) C.O(n2) D.O(log2n) 12.程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换;

数据结构第一次作业答案.

假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递增次序排列的单链表。 【解答】算法的基本设计思想:因为两链表已按元素值递增次序排列,将其合并是,均从第一个结点起进行比较,将小的结点链入链表中,同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列,故新链表的建立,应该采用头插法(也就是书本上讲的那种从链表中插入元素值的方法。比较结束后,可能会有一个链非空,此时用头插法将剩下的结点依次插入新链表中即可。算法实现如下: void MergeList(ListList &La,LinkList &Lb { LinkList r,pa=La->next,pb=Lb->next; //pa和pb分别是链表La 和 //Lb的工作指针 La->next=NULL; while(pa&&pb //当两链表均不为空时 if(pa->data<=pb->data { r=pa->next; //将pa的后继结点暂存于r pa->next=La->next; La->next=pa; //将pa结点链于结果表中,同时逆//置(头插法 pa=r; //恢复pa为当前待比较结点 } else { r=pb->next; //将pb的后继结点暂存于r pb->next=La->next;

La->next=pb; //将pb结点链于结果表中,同时逆置 pb=r; } If(pa pb=pa; //通常情况下会剩下一个链表非空,处理剩//下的部分 while(pb{ r=pb->next; pb->next=La->next; La->next=pb; pb=r; } free(Lb; } 选择题:1、D 2、B 1、栈的特点是先进后出,由于进栈和出栈操作是可以穿插着进行的。当第i个元素第一个出栈时,则i之前的元素可以依次排在i之后出栈,但剩余的元素可以在此时进栈并且也会排在i之前的元素出栈,所以第就j个出栈的元素是不确定的。 2、后缀表达式中,每一个计算符号均位于它两个操作数的直接后面,按照这样的方式逐步根据计算的优先级将每个计算式进行变换即可 得到后缀表达式。 那道进制转换的题,上传的课件中有,自己参考去

数据结构作业标准答案

第一章 单选题 1、下列关于算法的基本特征,说法不正确的是()。能行性是算法中的每一个步骤必须能够实现且能达到预期的目的。算法的确定性是指算法中的每一个步骤必须是有明确的定义,不允许模棱两可。 算法的有穷性是指算法必须能在有限的时间内做完。算法与提供情报无关。 [D] 教师批改:D 2、算法的时间复杂度取决于()。问题的规模待处理的数据的初态 问题的难度 A 和B [D] 教师批改:D 3、下列选项中,不是算法基本特征的是()。可行性有穷性 确定性高效率 [D] 教师批改:D 4、通常一个好的算法应达到的目标中,不包括()。正确性可读性 技巧性健壮性 [C] 教师批改:C 5、在一般的计算机系统中,基本的运算和操作不包括()。语法处理算术运算 关系运算数据传输 [A] 教师批改:A 6、工程上常用的分治法是()。列举法归纳法 减半递推技术回溯法 [C] 教师批改:C 多选题 7、算法设计的要求包括()。 正确性可读性 健壮性唯一性 [ABC] 教师批改:A,B,C 8、算法的时间复杂度应该与()无关。 所使用的计算机程序设计语言 基本运算的执行次数程序编制者 [ABD] 教师批改:A,B,D 9、下列关于算法的描述中,不正确的有()。 算法即是计算机程序算法是解决问题的计算方法 算法是排序方法算法是解决问题的有限运算序列 [ABC] 教师批改:A,B,C 填空题 16、所谓算法是指()。 教师批改:解题方案的准确而完整的描述 17、算法的基本特征有()、()、()和() 教师批改:能行性、确定性、有穷性和拥有足够的情报。

18、一个算法通常由两种基本要素组成,它们是()和()。 教师批改:算法中对数据的运算和操作。 算法的控制结构。 19、工程上常用的几种算法设计方法有列举法、()、()、()、()和回溯法。 教师批改:归纳法、递推、递归、减半递推技术。 20、算法的复杂度主要包括()复杂度和()复杂度。 教师批改:时间、空间 综合题 21、设给定3个整数a,b,c,试写出寻找这3个整数的中数的算法;并分析在平均情况与最坏情况下,该算法分别要做多少次比较? 寻找这3个整数的中数的算法用C语言描述如下(中数m由函数值返回): int mid ( int a, int b, int c) { int m 。m=a 。 if ( m>=b ) { if (m>=c) { if ( b>=c ) m=b 。else m=c 。} } else { if ( m<=c) { if (b>=c) m=c。else m=b 。} } return ( m ) 。 } 假设a,b,c中的每一个数为中数的概率相等(均为1/3)。由于当a为中数时需要比较2次,b或c为中数时均需要比较3次,因此,在平均情况下上述算法所需要的比较次数为 2*(1/3)+3*(1/3)+3*(1/3)= 8/3 即在平均情况下,上述算法需要比较8/3次。 在最坏情况下,上述算法需要比较3次(当b或c为中数时)。 第二章 选择题 1、下列排序方法中,哪一个是稳定的排序方法()。归并排序稀尔排序 堆排序快速排序 [A] 教师批改:A 2、设输入序列为1,2,3,4,借助一个栈得到的输出序列可以是()。3,4,1,2 4,2,1,3 4,1,2,3 1,3,4,2 [D] 教师批改:D 3、用数组A[m]存放循环队列的元素值,若其头尾指针分别为front和rear,则循环队列中当前元素的个数为()。(rear+front)%m (rear-front+m)%m (rear-front)%m (rear-front+1)%m [D] 教师批改:B 4、对于下三角矩阵A,若采用一个一维数组B以行为主顺序存放压缩矩阵A,则A43存放在()中. B7 B8 B9 B10 [C] 教师批改:C 5、深度为5的二叉树至多有()个结点。16 32

《电大社区治理》第二次作业答案(第3―4章)

《社区治理》第二次作业答案(第3—4章) 一、不定项选择题(每小题2分,共18分) 1.1954年全国人民代表大会常务委员会通过的《城市街道办事处组织条例》规定: 街道办事处是(C)。 A.城市最基层的政府机关 B.城市基层群众性自治组织 C.市辖区或者不设区的市的人民委员会的派出机关 D.城市社区的社会团体 2.1954年全国人民代表大会党务委员会通过的《城市居民委员会组织条例》规定,居民委员会是(B)。 A.街道办事处的派出机构 B.城市基层群众居民组织 C.城市群众性社会团体 D.城市最基层政权形式 3.1958年之前,我国农村基层实行的管理体制是(B)。 A.人民公社政社合一管理体制 B.乡(行政)管理体制 C.三级所有、队为基础管理体制 D.乡政村管理体制 4.

1998年11月,全国人大通过的《中华人民共和国村民委 员会组织法》明确界定了村民委员会的性质为(B)。 A.农村基层的政权组织 B.农村基层群众性自治组织 C.农村基层的经济组织 D.农村基层的社会团体 4.政府机构具有扩张的本性已被(B)所证明。 A.亚当-斯密关于市场“看不见的手”的论述 B.帕金森定律 C.“马太效应”理论 D.凯恩斯的“消费驱动”理论 5.党的领导在社区工作中主要体现为(B)。 A.组织领导 B.政治领导 C.行政领导 D.工作领导 6.社区工作学者杰克-罗斯曼把资本主义国家的社区治理策略划分成(ABC)几种模式。 A.地区发展策略 B.社会行为策略 C.社会计划策略

D.自我帮助策略 7.1954年全国人民代表大会常务委员会通过的《城市街道办事处组织条例》规定: 街道办事处的工作主要包括(ABD)。 A.办理基层政府有关居民工作的交办事项 B.指导居民委员会建设 C.领导辖区经济 D.反映居民意见和要求 8.根据约翰-霍普金斯大学萨拉蒙教授的观点,非营利组织的基本特征,除了正规性和民间性之外,还包括(ABCD)。 A.非营利性 B.自治性 C.志愿性 D.公益性 9.社区党建工作的必要性体现在(ABCD)。 A.加强社区党建工作是抓好党的基层组织建设、巩固执政党地位的需要 B.加强社区党建工作是在社区工作中发挥正确政治思想导向作用的需要 C.搞好社区党建是新时期落实党密切联系群众工作方法的必然选择 D.搞好社区党建是化解社会矛盾、维护社会稳定的需要 二、名词解释(每小题5分,共15分) 1.市场失灵:

华工平时作业数据结构第一次作业

1判断题 (对)1. 数据的逻辑结构与数据元素本身的内容和形式无关。 (错)2. 线性表的逻辑顺序与物理顺序总是一致的。 (对)3. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点,则它一定是该子树的中序遍历结果序列的最后一个结点。 (错)4. 对于同一组待输入的关键码集合,虽然各关键码的输入次序不同,但得到的二叉搜索树都是相同的。 (对)5. 最优二叉搜索树的任何子树都是最优二叉搜索树。 (对)6. 在二叉搜索树上插入新结点时,不必移动其它结点,仅需改动某个结点的指针,使它由空变为非空即可。 (对)7. 有n(n≥1)个顶点的有向强连通图最少有n条边。 (错)8. 连通分量是无向图中的极小连通子图。 (错)9. 二叉树中任何一个结点的度都是2。 (错)10. 单链表从任何一个结点出发,都能访问到所有结点。 二、单选题 1 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动( B )个元素。 A.8 B. 63.5 C. 63 D. 7 2 设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间,则A[3][3]在( A )位置,(10)表明用10进数表示。 A.692(10) B. 626(10) C. 709(10) D. 724(10) 3 N个顶点的连通图至少有( A )条边。 A.N-1 B. N C. N+1 D. 0 4 下面程序的时间复杂度为( C )。 for(int i=0; ilink=p->link; p->link =s; B. q->link=s; s->link =p; C. p->link=s->link; s->link =q; D. p->link=s; s->link =q; 6栈的插入和删除操作在( A )进行。 A.栈顶 B. 栈底 C. 任意位置 D. 指定位置 7 若让元素1,2,3依次进栈,则出栈次序不可能出现哪种情况( C )。 A.3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,2 8 广义表A(a),则表尾为( C )。 A.a B. (()) C. 空表 D. (a)

数据结构第一次作业

#include #include using namespace std; typedef struct node { int data; struct node *next; }Lnode, *LinkList; void CreatList(LinkList h, int a[], int n) { LinkList s, r; int i; r=h; for(i=0; idata = a[i]; r->next = s; r=s; } r->next = NULL; } void DispList(LinkList h)

LinkList r = h->next; while(r != NULL) { printf("%d ",r->data); r = r->next; } putchar('\n'); } void InsertList(LinkList h, int x, int y) { LinkList s, p, q; s = new Lnode; s->data = y; q = h; p = q->next; while((p!=NULL) && (p->data != x)) { q = p; p = p->next; } s->next = p; q->next = s; } void DeleteList(LinkList h, int x) { LinkList p, q; q = h; p = q->next; while((p != NULL) && (p->data != x)) { q = p; p = p->next; } if(p == NULL) printf("no"); else { q->next = p->next; delete(p); printf("yes"); } }

数据结构练习题第三章栈、队列和数组习题及答案

第三章栈、队列和数组 一、名词解释: 1.栈、栈顶、栈底、栈顶元素、空栈 2.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上(下)三角矩阵 二、填空题: 1.栈修改的原则是_________或称________,因此,栈又称为________线性表。在栈顶 进行插入运算,被称为________或________,在栈顶进行删除运算,被称为________ 或________。 2.栈的基本运算至少应包括________、________、________、________、________五 种。 3.对于顺序栈,若栈顶下标值top=0,此时,如果作退栈运算,则产生“________”。 4.对于顺序栈而言,在栈满状态下,如果此时在作进栈运算,则会发生“________”。 5.一般地,栈和线性表类似有两种实现方法,即________实现和________实现。 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);

软件技术基础第三次作业

软件技术基础第三次作业 一、单选题(23题,每题3分) 1、若有说明int *ptr1, *ptr2, m=5,n;,下面正确的语句组是 A. ptr1=&m; ptr2=&ptr1; B. ptr1=&m; ptr2=n; *ptr2=*ptr1; C. ptr1=&m; ptr2=ptr1; D. ptr1=&m; *ptr2=*ptr1; 2、对于10的-5次方,合法的C常量表示是 A. le-5 B. 10e-5 C. 10*e-5 D.1*e-5 3、以下叙述正确的是 A.输入项可以是一个实型常量,如scanf(“%f,3.5”); B.只有格式控制,没有输入项,也能正确输入数据到内存,例如scanf(“a=%d,b=%d”); C.当输入一个实数数据时,格式符可以控制小数的位数,例如scanf(“%4.2f”,&f); D.当输入数据时,必须指明变量地址,例如scanf(“%f”,&f); 4、若已定义: int a[ ]={0,1,2,3,4,5,6,7,8,9}, *p=a,i; 其中0≤i≤9, 则对a数组元素不正确的引用是___ ___。 A. a[p-a] B. *(&a[i]) C. p[i] D. a[10] 5、设x和y均为int型变量,则以下语句:x+=y;y=x-y;x-=y;的功能是____ A.把x和y按从大到小排列 B. 把x和y按从小到大排列 C. 无确定结果 D. 交换x和y中的值 6、在一个单链表中,若指针p1所指结点不是最后结点,则在p1之后插入指针p2所指 结点应执行。 A. p1->next=p2; p2->next=p1; B. p2->next=p1->next; p1=p2; B. p2->next=p1; p1->next=p2; D. p2->next=p1->next; p1->next=p2; 7、已知:char s[4] = "cba"; char *p; 执行语句序列p = s;printf("%c\n",*(p+1));后,输出为_____。 A. 字符?c? B. 字符?b? C. 字符?a? D. 字符?d? 8、设p1和p2是指向同一个int型一维数组的指针变量, k为int型变量,则不能正确执行的语句是__ ___。 A. k=*p1+*p2; B. p2=k; C. p1=p2; D. k=*p1 *(*p2); 9、有一链式堆栈ls(无头结点),其栈顶指针为ls.top,结点结构为:data域和 link(指针)域。现在对该栈进行出栈操作,出栈后ls.top的值为:。 A. ls.top->link B. ls.top-- C. ls.top->data D. ls.top++ 10、线性表的顺序存储结构是一种存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. Hash存取

相关文档
相关文档 最新文档