当前位置：文档之家 › 数据结构作业

数据结构作业

  • 格式：doc
  • 大小：211.53 KB
  • 文档页数：12

下载文档原格式

  / 12

合集下载

数据结构作业题及参考答案

数据结构作业题及参考答案

东北农业大学网络教育学院数据结构作业题（一）一、选择题（每题2分，共20分）1．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。

A、O(n)B、O (n/2)C、O (1)D、O (n2)2．带头结点的单链表first为空的判定条件是（）。

A、first == NULL;B、first->link == NULL;C、first->link == first;D、first != NULL;3．在一棵树中，（）没有前驱结点。

A、分支结点B、叶结点C、树根结点D、空结点4．在有向图中每个顶点的度等于该顶点的（）。

A、入度B、出度C、入度与出度之和D、入度与出度之差5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。

A、20B、18C、25D、226．下列程序段的时间复杂度为（）。

s=0；for(i=1；i<n；i++)for(j=1；j<n；j++)s+=i*j；A、O (1)B、O (n)C、O (2n)D、O (n2)7．栈是一种操作受限的线性结构，其操作的主要特征是（）。

A、先进先出B、后进先出C、进优于出D、出优于进8．假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。

若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（）。

A、(rear-front-1)％nB、(rear-front)％nC、(front-rear+1)％nD、(rear-front+n)％n9．高度为5的完全二叉树中含有的结点数至少为（）。

A、16B、17C、31D、3210．如图所示有向图的一个拓扑序列是( )A、ABCDEFB、FCBEADC、FEDCBAD、DAEBCF二、填空题（每空1分，共20分）1．n (n﹥0) 个顶点的无向图最多有条边，最少有条边。

数据结构作业及答案

数据结构作业及答案

第一章绪论一、选择题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.数据复杂性和程序复杂性k6.计算机算法指的是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.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。

数据结构-作业的状态与处理流程

数据结构-作业的状态与处理流程
பைடு நூலகம்
例题
• 一个计算机系统中拥有6台打印机，现有N 个进程竞争使用，每个进程要求两台，试 问，N的值如何选取时系统中绝对不会出现 死锁？
N<=6-1
假定某计算机系统有R1和R2两类可在使用资源 （其中R1有两个单位，R2有一个单位），它们被 进程P1和P2所共享，且已知两个进程均以 申请R1 申请R2 R2 释放R1 申请R1 释放R1 释放
其他算法
1. 最 短 剩 余 时 间 优 先 算 法 SRTF （ Shortest
Remaining Time First）:
• 把SJF算法改为抢占式的SJF算法 一个新作业进入就绪状态，如果新作业需要的 CPU时 间 比 当 前 正 在 执 行 的 作 业 剩 余 下 来 还 需 的 CPU时间短，SRTF强占当前正在执行作业的CPU。 此算法不但适用于作业JOB调度，同样也适用于 进程调度。
图2-19
作业的状态与状态的变迁
1. 提交状态：一个作业被提交给机房后或用户通过终端键 盘向计算机中键入其作业时所处的状态 为提交状态。 2. 后备状态 1）作业的全部信息都已通过输入机输入，并由操作系 统将其存放在磁盘的某些盘区中等待运行。 2）之后，系统为每个进入系统的作业建立作业控制 块，填写必要的信息，并把作业控制块放入作业后 备队列，为作业调度作准备。
请给出这四个作业的执行时间序列并计算出平均周转时间及带权平均周转时间作业调度算法应用例子两道批处理系统中最短作业优先作业算法计算结果四个作业的执行时间序列为
§补充： 作业的状态与处理流程
一、 作业状态
执行 提 交 状 态 输入 后 备 状 态 就绪 作业调度 运行状态 阻塞 作业调度 完 成 状 态
•

200721数据结构 作业(高起专、高起本)

200721数据结构 作业(高起专、高起本)

比较（
）个元素结点。
A、
B、n
C、
D、
20、设单链表中指针 p 指向结点 m，若要删除 m 之后的结点（若存在），则需修改指针的操作
为（
）。
A、
B、
C、
D、
21、在（
）运算中，使用顺序表比链表好。
A、插入
B、删除
C、根据序号查找
D、根据元素值查找
22、在一个具有 n 个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度
第 2 页 共 20 页 在您完成作业过程中，如有疑难，请登录学院网站“辅导答疑”栏目，与老师进行交流讨论！
C、一个无限序列，可以为空
D、一个无限序列，不可以为空
18、在一个长度为 n 的顺序表中删除第 i 个元素
时，需向前移动（
）个元素。
A、
B、
C、
D、i
19、从一个具有 n 个结点的单链表中查找其值等于 x 的结点时，在查找成功的情况下，需平均
（ ）个。
第 6 页 共 20 页 在您完成作业过程中，如有疑难，请登录学院网站“辅导答疑”栏目，与老师进行交流讨论！
A、15
B、16
C、17
D、47
48、设 n , m 为一棵二叉树上的两个结点，在中序遍历序列中 n 在 m 前的条件是（ ）。
A、n 在 m 右方
B、n 在 m 左方
C、n 是 m 的祖先
D、求串长
6、二维数组 M 的成员是 6 个字符（每个字符占一个存储单元）组成的串，行下标 i 的
范围从 0 到 8，列下标 j 的范围从 1 到 10，则存放 M 至少需要（
）个字节。
A、90
B、180

数据结构的作业

数据结构的作业

第五章作业： 第五章作业： 1.假设有二维数组 假设有二维数组a:array[1..6,0..7] of elemtp; 每个数据元 假设有二维数组 素占6个字节 存储器按字节编址 的基地址为1000,则： 素占 个字节,存储器按字节编址。a的基地址为 个字节 存储器按字节编址。 的基地址为 则 (1) 数组 的体积； 数组a的体积 的体积； (2)数组 的最后一个元素的第一个字节的地址； 数组a的最后一个元素的第一个字节的地址 数组 的最后一个元素的第一个字节的地址； (3)按行存储时，a[2,4]的第一个字节的地址； 按行存储时， 的第一个字节的地址； 按行存储时 的第一个字节的地址 (4)按列存储时，a[5,7]的第一个字节的地址； 按列存储时， 的第一个字节的地址； 按列存储时 的第一个字节的地址
7.写出下列各树的先根序列 后根序列 并且画出对应的二 写出下列各树的先根序列,后根序列 写出下列各树的先根序列 后根序列,并且画出对应的二 叉树. 叉树 A A A A B C D B C B C I 8.画出第 题的森林相应的二叉树 画出第7题的森林相应的二叉树 画出第 题的森林相应的二叉树. 9.画出和下列已知序列对应的树 画出和下列已知序列对应的树T: 画出和下列已知序列对应的树 树的先根次序访问序列为:GFKDAIEBCHJ,而且 而且 树的先根次序访问序列为 树的后根次序访问序列为:DIAEKFCJHBG。 。 树的后根次序访问序列为 E F J G H K
3.用单链表实现 用单链表实现Locate(L,x)函数。（可参考 函数。（可参考P26算法 算法2.5) 用单链表实现 函数。（可参考 算法 4.上机题：设单链表Va中的数据元素递增有序。试编 上机题：设单链表 中的数据元素递增有序 中的数据元素递增有序。 上机题 写程序，将数据X插入单链表 插入单链表Va， 写程序，将数据 插入单链表 ，要求插 入后保持该表的有序性。 入后保持该表的有序性。 5.写出双向链表删除第i个结点的算法 5.写出双向链表删除第i个结点的算法。 写出双向链表删除第 个结点的算法。 6.写出求双向循环链表长度的算法。（注：头结点 写出求双向循环链表长度的算法。（注 写出求双向循环链表长度的算法。（ 不算） 不算）

数据结构作业

数据结构作业

第二次作业一、选择题1、设有编号为1, 2, 3, 4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序为D。

A. 1234B. 1243C. 1324D. 14232、4个元素按A, B, C, D顺序进入S栈，执行两次Pop(S, x)运算后，栈顶元素的值是B 。

A. AB. BC. CD. D3、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列A 命令。

A. x=top; top=top->next;B. top=top->next; x=top->data;C. x=top->data;D. x=top->data; top=top->next;4、向顺序栈中输入元素时 A 。

A. 先存入元素，后移动栈顶指针B. 先移动栈顶指针，后存入元素C. 谁先谁后无关紧要D. 同时进行5、设有一个顺序栈，元素A, B, C, D, E, F依次进栈，如果6个元素出栈的顺序是B, D, C, F, E, A，则栈的容量至少为A。

A. 3B. 4C. 5 6. 66、设已将元素A, B, C依次入栈，元素D正等待进栈。

那么下列4个序列中不可能出现的出栈顺序为A。

A. CADBB. CBDAC. CDBAD. DCBA7、栈和队列的相同之处是C。

A.元素的进出满足先进后出B.元素的进出满足后进先出C.只允许在端点进行插入和删除操作D.无共同点8、设栈S 和队列Q 的初始状态为空,元素e1，e2，e3，e4，e5 和e6 依次通过栈，一个元素出栈后即进入队列Q,若6 个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S 的容量至少应该是B。

A. 6B. 4C. 3D. 29、队列通常采用的两种存储结构是( A)。

A. 顺序存储结构和链式存储结构B.散列方式和索引方式C. 链表存储结构和线性存储结构D.线性存储结构和非线性存储结构10、循环队列SQ队满的条件是B。

数据结构作业题目

一、第一次作业
①写一个函数find，实现从数组a[n]查找元素x，返回x在数组中的序号，如果找不到则返回-1。

②当a[n]递增有序时，有没有高效的算法？
③以Niklus Wirth的观点，程序是什么?
④算法有什么特性？
⑤好算法应该满足哪些标准？
⑥数据结构主要在哪些层面上讨论问题？
⑦按增长率由小至大的顺序排列下列各函数（严蔚敏题集1.10）
⑧试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z 的值（严蔚敏题集1.16）
二、第二次作业
1)题集2.2（严蔚敏）
2)题集2.10（严蔚敏）
3)题集2.12（严蔚敏）
4)题集2.7（严蔚敏）
5)题集2.15（严蔚敏）
三、第三次作业
第二章题集1、9、10（于津、陈银冬）
四、第四次作业
第三章题集1、2、3、4、5（于津、陈银冬）
五、第五次作业
①第四章题集2、5（于津、陈银冬）
②实现以下C库函数：
(1)strlen(cs)
(2)strcpy(s, ct)
(3)strcmp(cs, ct)
③完成对称矩阵、三角矩阵、对角矩阵在压缩存储下的输入输出算法
④第五章题集1、2、3（于津、陈银冬）
六、第六次作业
第六章题集1、2、10（于津、陈银冬）
七、第七次作业
第六章题集3、8、12、13（于津、陈银冬）
八、第八次作业
第六章题集6、7、9、15（于津、陈银冬）
九、第九次作业
第七章题集1、7（另加上“十字链表”存储）（于津、陈银冬）。

南开24秋学期《数据结构》作业参考一

24秋学期《数据结构》作业参考1.堆的形状是一棵()选项A：二叉排序树选项B：满二叉树选项C：完全二叉树选项D：平衡二叉树参考答案：C2.用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的选项A：栈选项B：队列选项C：树选项D：图参考答案：A3.栈中元素的进出原则是（）选项A：先进先出选项B：后进先出选项C：栈空则进选项D：栈满则出参考答案：B4.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()选项A：79,46,56,38,40,84选项B：84,79,56,38,40,46选项C：84,79,56,46,40,38选项D：84,56,79,40,46,38参考答案：B5.有8个结点的无向图最多有（）条边选项A：14选项B：28选项C：56选项D：112参考答案：B6.链表是一种采用存储结构存储的线性表选项A：顺序选项B：链式选项C：星式选项D：网状参考答案：B7.下列关键字序列中，()是堆选项A：16,72,31,23,94,53选项B：94,23,31,72,16,53选项C：16,53,23,94，31,72选项D：16,23,53,31,94,72参考答案：D8.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。

选项A：20，70，30，50选项B：30，88，70，50选项C：20，50选项D：30，88，50参考答案：A9.已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（）选项A：0 2 4 3 1 5 6选项B：0 1 3 5 6 4 2。

数据结构作业题

数据结构作业题(总15页) -本页仅作为预览文档封面，使用时请删除本页-第一章1、设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。

(1) i=1; k=0;while(i<n){ k=k+10*i;i++;}(2) i=0; k=0;do{k=k+10*i; i++;}while(i<n);(3) i=1; j=0;while(i+j<=n){if (i>j) j++;else i++;}(4)x=n; 编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。

当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。

两个栈均从两端向中间增长。

当向第0号栈插入一个新元素时，使top[0]增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top[1]减1得到新的栈顶位置。

当top[0]+1 == top[1]时或top[0] == top[1]-1时，栈空间满，此时不能再向任一栈加入新的元素。

试定义这种双栈(Double Stack)结构的类型定义，并实现初始化、判栈空、判栈满、插入、删除算法。

0 m-1【提示】类型定义：#define m 100；Typedef int dsType；试利用算符优先法，画出对如下中缀算术表达式求值时运算符栈和操作数栈的变化。

a +b * (c - d) – e# （#表示结束符）第四章设有模式串T1,T2，T1=‘aaab’，T2=‘abcabaa’，目标串s为‘abc aaabbabcabaacbacba’，（1）计算模式串T1的next(j) 和nextval(j)函数的值,并（按照nextval(j) ）画出KMP算法匹配过程。

（2）计算模式串T2的next(j) 和nextval(j)函数的值,并（按照nextval(j) ）画出KMP算法匹配过程。

数据结构形考作业

一、单项选择题（每小题2分，共42分）题目1对线性表进行二分查找时，要求线性表必须（）。

选择一项：A. 以链接存储方式，且数据元素有序B. 以顺序存储方式，且数据元素有序C. 以链接存储方式D. 以顺序存储方式题目2采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

选择一项：A. (n-1)/2B. nC. (n+1)/2D. n/2题目3有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。

选择一项：A. 29/9B. 26/10C. 31/10D. 29/10题目4已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（）次。

选择一项：A. 5B. 4C. 3D. 6题目5有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）。

选择一项：A. 12,24,30,37,45,53,96B. 37,24,12,30,53,45,96C. 30,24,12,37,45,96,53D. 45,24,53,12,37,96,30题目6对于顺序存储的有序表{5,12,20,26,37,42,46,50,64}，若采用折半查找，则查找元素26的比较次数是（）。

选择一项：A. 4B. 5C. 6D. 3题目7在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（）。

选择一项：A. 希尔排序B. 直接选择排序C. 直接插入排序D. 冒泡排序题目8从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。

将其放入已排序序列的正确的位置上，此方法称为（）。

选择一项：A. 交换排序B. 归并排序C. 插入排序D. 选择排序题目9依次将每两个相邻的有序表合并成一个有序表的排序方法称为（）。

选择一项：A. 归并排序B. 选择排序C. 交换排序D. 插入排序题目10当两个元素出现逆序的时候就交换位置，这种排序方法称为（）。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第六章树和二叉树
6.45 编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
6.46 编写复制一棵二叉树的非递归算法。
6.59 编写算法完成下列操作：无重复地输出以孩子兄弟链表存储的树T中所有的边（这里的边是指树T本身的分支，而不是孩子兄弟链表所形成的二叉树的分支）。输出的形式为（k1, k2）, ..., (ki, kj), ..., 其中，ki和kj为树结点中的结点标识。
1.20试编写算法求一元多项式 的值Pn(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为ai（i=0, 1,…, n）、x0和n，输出为Pn(x0)。
第二章线性表
2.11设顺序表va中的数据元素非递减有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
注：根据同学们的要求，将作业量从六道题减少到三道题，希望同学们能及时完成。
第五章数组和广义表
5.21 假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另设三元组C存放结果矩阵。
5.26 试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。
5.33 试编写递归算法，输出广义表中所有原子项及其所在的层次。
第十二章 文件
12.10假设某个有3000张床位的旅店需建立一个便于管理的文件,每个记录是一个旅客的身份和投宿情况。其中旅客身份证号(15位十进制数字)可作为主关键字，此外还需建立按姓名、投宿日期、从哪来等次关键字项索引。请为此文件确定一种组织方式(如:主文件如何组织,各次关键字项索引如何建立等
第十章 排序
10.23 试以L.r[k+1]作为监视哨改写直接插入排序算法。其中，L.r[1...k]为待排记录且k<MAXSIZE。
10.32 荷兰国旗问题：设有一个仅由红、白、蓝三种颜色的条块组成的条块序列。请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图 案。
2.12设A＝（a1，…，am）和B＝（b1，…，bn）均为顺序表，A’和B’分别为A和B中除去最大共同前缀后的子表（例如，A＝（x，y，y，z，x，z），B＝（x，y，y，z，y，x，x，z），则两者中最大的共同前缀为（x，y，y，z），在两表中除去最大共同前缀后的子表分别为A’＝（x，z）和B’＝（y，x，x，z））。若A’＝B’＝空表，则A＝B；若A’＝空表，而B’≠空表，或者两者均不为空，且A’的首元小于B’的首元，则A < B，意：在算法中，不要破坏原表A和B，并且也不一定先求得A’和B’才进行比较）。
3.31 假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一算法判别读入的一个以‘@’为结束符的字符序列是否是回文。
3.32 试利用循环队列编写求k阶斐波那契序列中前n+1项（f0,f1,…，fn）的算法，要求满足：fn≤max而fn+1＞max，其中max为某个约定的常数。（注意：本题所用循环队列的容量仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项fn-k+1,…，fn）。
2.19 已知线性表中的元素以值非递减有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删节点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。
2.22 试写一算法，对单链表实现就地（原地）逆置。
2.41 试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数（多项式），同时释放所有无用（被删）的结点。
第三章栈和队列
3.17试写一算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不包含字符‘&’，且序列2是序列1的逆序列。例如‘a+b&b+a’是属于该模式的字符序列，而‘1+3&3-1’则不是。
@y++;
}
答案： 向下取整
8)x = 91;
y = 100;
while (y > 0) {
@if (x > 100) { x -= 10; y--;}
else {
x++;
}
}
答案：if执行次数为1100，if判断内部执行为100次
1.19试编写算法，计算i!·2i（i = 0, 1,…, n-1）的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT，则当n > arrsize或对某个k（0 ≤k≤n-1）使k!·2k> MAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。
9.11试推导含12个结点的平衡二叉树的最大深度，并画出一棵这样的树。
9.25假设顺序表关键字自大而小有序，修改教科书9.1.1节中的顺序查找算法，将哨兵设在高下标端。然后画出此查找过程的判定树，分别求出等概率情况下查找成功和不成功时的平均查找长度。
9.45假设哈希表长为m，哈希函数为H(x)，用链地址法处理冲突。试编写输入一组关键字并建造哈希表的算法。
数据结构习题
第一章绪论
1.6在程序设计中，常用下列三种不同的出错处理方式：
1)用exit语句终止执行并报告错误；
2)以函数的返回值区别正确返回或错误返回；
3)设置一个整形变量的函数参数以区别正确返回或某种错误返回。
试讨论这三种方法各自的优缺点。
1.7在程序设计中，可采用下列三种方法实现输出和输入：
1)通过scanf和printf语句；
7.31 试完成求有向图的强连通分量的算法，并分析算法的时间复杂度。
7.42以邻接表作为存储结构实现求从源点到其余各顶点的最短路径的Dijkstra算法。
第八章动态存储管理
8.6 二进制地址为011011110000，大小为(4)10的块的伙伴的二进制地址是什么？若块大小为(16)10时又如何？
第九章查找
3.21 假设表达式由单字母变量和双目四则运算符构成。试写一算法，将一个通常书写形式且书写正确的表达式转换成逆波兰式。
3.22 如题3.21的假设条件，试写一算法，对以逆波兰式表示的表达式求值。
3.30 假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回对头元素）。
@x += delta;
}
}
}
答案：n*(n+1)*(n+2)
=1+（1+2）+（1+2+3）+...+(1+2+3+...+n)
=
=1/2*
=n*(n+1)*(2n+1)/12 +n*(n+1)/4
=n*(n+1)*(n+2)/6
7)x = n;//n是不小于1的常数
y = 0;
while (x >= (y + 1) * (y + 1)) {
2)通过函数的参数显示传递；
3)通过全局变量隐式传递。
试讨论这三种方法的优缺点。
1.8设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：
5)for (i = 1; i <= n; i++ ) {
for (j = 1; j <=i; j++) {
for (k = 1; k <=j; k++) {
第七章图
7.22试基于图的深度优先搜索策略编写一算法，判别以邻接表方式存储的有向图中是否存在从顶点vi到顶点vj的路径(i≠j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。
7.24利用栈的基本操作编写，按深度优先搜索策略遍历一个强连通图的非递归算法。算法中不规定具体的存储结构，而将图Graph看成是一个抽象的数据类型。
2.38 设有一双向循环链表，每个结点中除有prior，data和next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的置均初始化为零，而每当对链表进行一次LOCATE（L，x）的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1,同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCATE操作的算法。
第四章串
4.17 编写算法，实现串的基本操作Replace(&S, T, V)。
4.23 假设以块链结构作串的存储结构。试编写判别给定串是否具有对称性的算法，并要求算法的时间复杂度为O(StrLength(S))。
4.28假设以结点大小为1（带头结点）的链表结构表示串，则在利用next函数值进行串匹配时，在每个结点中需设三个域：数据域chdata、指针域succ和指针域next。其中chdata域存放一个字符；succ域存放指向同一链表中后继结点的指针；next域在主串中存放指向同一链表中前驱结点的指针，但在模式串中存放指向当该结点的字符与主串中的字符不等时，模式串中下一个应进行比较的字符结点（即与该结点字符的next函数值相对应的字符结点）的指针，若该结点字符的next函数值为零，则其next域的值应指向头结点。试按上述定义的结构改写求模式串的next函数值的算法。