《数据结构作业题》word版

《《数据结构作业题》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第一章1、设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。(1)i=1;k=0; 　　while(ij)j++;　　　　elsei++;　　　}(4)x=n;//n>1 　while(x>=(y+1)*(y+1))　　y++;(5)x=91;y=100;    while(y>0)　　　　if(

2、x>100)　　　　　{x=x-10;y--;}　　　　elsex++;2、按增长率由小至大的顺序排列下列各函数：2100,(3/2)n，(2/3)n，nn,n0.5,n!，2n，lgn,nlgn,n(3/2)第二章2-7针对带表头结点的单链表，试编写下列函数。(1)定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。(2)求最大值函数max：通过一趟遍历在单链表中确定值最大的结点。第三章3-1.将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶

3、指针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时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈(DoubleStack)结构的类型定义，并实现初始化、判栈空、判栈满、插入、删除算法。-1top[0]top[1]m0m-1【提示】类型定义：#definem100；Typede

4、fintdsType；//双栈的元素类型Typedefstruct{inttop[2];//双栈的栈顶指针和栈底指针dsTypeV[m];//栈数组}DoubleStack；初始化空双栈算法：InitdStack(DoubleStack&ds){//初始化空双栈dsds.top[0]=-1;ds.top[1]=m;}判栈空算法：intDStackEmpty(DoubleStackds,inti){//判断双栈ds的第i（0或1）个栈是否为空，空则返回1，否则返回0if(i==0&&ds.top[0]==-1)return1;if(i==1&&ds.

5、top[1]==m)return1;return0;}3-2.试利用算符优先法，画出对如下中缀算术表达式求值时运算符栈和操作数栈的变化。a+b*(c-d)–e#（#表示结束符）步序扫描项项类型动作OPND栈变化OPTR栈变化0FOPTR栈与OPND栈初始化,‘#’进OPTR栈,取第一个符号#1a操作数Fa进OPND栈,取下一符号a#2+操作符F‘+’>‘#’,进OPTR栈,取下一符号a#+………………………………3-3分别写出顺序循环队列队列Q状态为“空”还是“满”的条件和计算队列中元素个数的公式。第四章设有模式串T1,T2，T1=‘aaab’，T

6、2=‘abcabaa’，目标串s为‘abcaaabbabcabaacbacba’，（1）计算模式串T1的next(j)和nextval(j)函数的值,并（按照nextval(j)）画出KMP算法匹配过程。（2）计算模式串T2的next(j)和nextval(j)函数的值,并（按照nextval(j)）画出KMP算法匹配过程。学号尾数为奇数做第（1）题；偶数做第（2）题第五章5-1设有一个二维数组A[m][n]（按照列优先存储，m、n均大于5），假设A[0][0]存放位置在644(10)，A[2][3]存放位置在676(10)，每个元素占一个空间，问

7、A[4][4](10)存放在什么位置？脚注(10)表示用10进制表示。5-2假二维数组A9´3´5´8，第一个元素的字节地址是1000，每个元素占6个字节。问下列元素的存储地址是什么？（1）a0000（2）a8247（3）按行优先存储（最左下标优先）时a3125的地址（4）按照列优先存储（最右下标优先）时a1111的地址5-3矩阵(aij)n´n的压缩存储方式,我们把它们按行存放于一个一维数组B中:（1）设有一个n´n的下三角矩阵A，如图(a)所示。为了节约存储，只存对角线或对角线以下的元素。若在一维数组B中从0号位置开始存放，则下三角矩阵中的任一

8、元素aij在应存于一维数组的什么下标位置？给出计算公式。（2）设有一个n´n的上三角矩阵A，如图(b)所示。为了节约存储，