数据结构作业题及答案

数据结构作业题及答案 第一章 绪论 1、简述下列概念：数据、数据元素、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 数据：指能够被计算机识别、存储和加工处理的信息载体。 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素 有时可以由若干数据项组成。 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、 存储结构和数据的运算。 逻辑结构：指各数据元素之间的逻辑关系。 存储结构：就是数据的逻辑结构用计算机语言的实现。 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一 个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。 2、常用的存储表示方法有哪几种? 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储 单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字 段表示的。由此得到的存储表示称为链式存储结构。 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。 3、求解下列算法的时间复杂度 (1) i=1; k=0 while(i1 while (x=(y+1)*(y+1) y+; T(n)=n1/2 T(n)=O(n 1/2) 最坏的情况是 y=0，那么循环的次数是 n1/2次，这是一 个按平方根阶递增的函数。 (5) x=91; y=100; while(y0) if(x100) x=x-10;y-; else x+; T(n)=O(1) 这个程序看起来有点吓人，总共循环运行了 1000 次， 但是我们看到 n 没有? 没。这段程序的运行是和 n 无关 的，就算它再循环一万年，我们也不管他，只是一个常 数阶的函数。 第二章 线性表 1、试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时) ，单链表由头指针唯一确定，因此单链表可以 用头指针的名字来命名。 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不 论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置 上的操作一致(都是在某一结点之后 )。 2、何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有 以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜 采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构 为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链 表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 3、在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答：在等概率情况下，顺序表中插入一个结点需平均移动 n/2 个结点。删除一个结点需平均移动(n-1)/2 个 结点。具体的移动次数取决于顺序表的长度 n 以及需插入或删除的位置 i。i 越接近 n 则所需移动的结点 数越少。 4、设顺序表 L 是一个递增有序表，试写一算法，将 x 插入 L 中，并使 L 仍是一个有序表。 因已知顺序表 L 是递增有序表，所以只要从头找起找到第一个比它大(或相等) 的结点数据，把 x 插入到这 个数所在的位置就是了。算法如下： void InsertIncreaseList( Seqlist *L , Datatype x ) int i; for ( i=0 ; i length s=(ListNode *)malloc(sizeof(ListNode); s-data=x; s-next=p-next; p-next=s; return L; 6、写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。 先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的 值，重复上述过程直到最后一个结点。 void DeleteList(Nodetype *L) Nodetype *p,*q,*s; if(L-Next=NULL|L-Next=NULL) printf(“删除错误n“);exit(0); p=L-Next; q=p-Next; while(p-Next!=NULL) while(q) s=q; if(q-Data=p-Data) s-Next=q-Next; free(q); q=s-Next; else q=q-Next; p=p-Next; 第三章 栈与队列 1、简述栈的逻辑结构、存储结构及其相关算法 答：栈的逻辑结构和线性表相同，如果它是非空的，则有且只有一个开始结点，有且只能有一个终端结 点，其它的结点前后所相邻的也只能是一个结点(直接前趋和直接后继), 但是栈的运算规则与线性表相比 有更多的限制，栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为 栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为 LIFO 表(Last In First Out)。由于栈也是线性表，因此栈有顺序栈和链栈两种存储结构 栈的基本运算有六种： 构造空栈：InitStack(S)、 判栈空: StackEmpty(S)、 判栈满： StackFull(S)、 进栈： Push(S,x)、可形象地理解为压入，这时栈中会多一个元素 退栈： Pop(S) 、 可形象地理解为弹出，弹出后栈中就无此元素了。 取栈顶元素：StackTop(S), 不同与弹出，只是使用栈顶元素的值，该元素仍在栈顶不会改变。 2、简述队列的逻辑结构、存储结构及其相关算法。 答：队列是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进 行(只进不出) ，而删除只能在表的另一端进行(只出不进) ，允许删除的一端称为队尾(rear)，允许插入的一 端称为队头 (Front) ,队列的操作原则是先进先出的，所以队列又称作 FIFO 表(First In First Out)。队列也 有顺序存储和链式存储两种存储结构，前者称顺序队列，后者为链队。 队列的基本运算也有六种： 置空队 ：InitQueue(Q) 判队空： QueueEmpty(Q) 判队满： QueueFull(Q) 入队 ： EnQueue(Q,x) 出队 ： DeQueue(Q) 取队头元素： QueueFront(Q),不同与出队，队头元素仍然保留 3、简述顺序队列“假上溢“ 的现象出现的原因。 答：因为我们的队列是存储在一个向量空间里，在这一段连续的存储空间中，由一个队列头指针和一个 尾指针表示这个队列，当头指针和尾指针指向同一个位置时，队列为空，也就是说，队列是由两个指针 中间的元素构成的。在队列中，入队和出队并不是象现实中，元素一个个地向前移动，走完了就没有了, 而是指针在移动，当出队操作时，头指针向前(即向量空间的尾部) 增加一个位置，入队时，尾指针向前增 加一个位置，在某种情况下，比如说进一个出一个，两个指针就不停地向前移动，直到队列所在向量空 间的尾部，这时再入队的话，尾指针就要跑到向量空间外面去了，仅管这时整个向量空间是空的，队列 也是空的，却产生了“上溢“ 现象，这就是假上溢。 4、设计算法判断一个算术表达式的圆括号是否正确配对。 对表达式进行扫描，凡遇到“(”就进栈，遇“) ”就退掉栈顶的 “(”，表达式被扫描完毕，栈为空。表示 圆括号匹配。否则圆括号不匹配。 int PairBracket( char *S) /检查表达式中括号是否配对 int i; SeqStack T; /定义一个栈 InitStack ( for (i=0; istrlen(S) ; i+) if ( Si=( ) Push( /遇(时进栈 if ( Si=) ) Pop( /遇)时出栈 return !EmptyStack( / 由栈空否返回正确配对与否 第四章 串 1、简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态 分配的顺序串；目标串和模式串；有效位移和无效位移。 答：空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主 串。 静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用 malloc 和 free 等函数根据需要动态地分 配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间) 。 目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相 对的。 有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模 式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功) ，反之，若有 不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败) 。 2、假设有如下的串说明：char s130=“Stocktom,CA“, s230=“March 5 1999“, s330, *p; (1)在执行如下的每个语句后 p 的值是什么? p=stchr(s1,t); p=strchr(s2,9); p=strchr(s2,6); 答：stchr(*s,c)函数的功能是查找字符 c 在串 s 中的位置，若找到，则返回该位置，否则返回 NULL。 因此：执行 p=stchr(s1,t);后 p 的值是指向字符 t 的位置, 也就是 p=后 p 的值是指向 s2 串中第一个 9 所在的位置,也就是 p=之后，p 的返回值是 NULL。 (2)在执行下列语句后，s3 的值是什么 ? strcpy(s3,s1); strcat(s3,“,“); strcat(s3,s2); 答：strcpy 函数功能是串拷贝，strcat 函数的功能是串联接。 所以：在执行 strcpy(s3,s1); 后，s3 的值是“Stocktom,CA“ 在执行 strcat(s3,“,“); 后，s3 的值变成“Stocktom,Ca,“ 在执行完 strcat(s3,s2);后，s3 的值就成了“Stocktom,Ca,March 5,1999“ (3)调用函数 strcmp(s1,s2)的返回值是什么 ? 答：函数 strcmp(串 1，串 2)的功能是串比较，按串的大小进行比较，返回大于 0，等于 0 或小于 0 的值以 表示串 1 比串 2 大，串 1 等于串 2 ，串 1 小于串 2。因此在调用函数 strcmp(s1,s2)后，返回值是大于 0 的数 (4)调用函数 strcmp( Temp=(char *)malloc(sizeof(charMaxsize);/ 设置一个临时串 if(i=strlen(S) strcpy(Temp,/将第 i 位起以后的字符拷贝到临时串中 strcpy(/将串 T 拷贝到串 S 的第 i 个位置处，覆盖后面的字符 strcat(S,Temp);/把临时串中的字符联接到串 S 后面 free( Temp ); 4、一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为： a b c d e f g h i j k l m n o p q r s t u v w x y z n g z q t c o b m u h e l k p d a w x f y i v r s j 则字符串“encrypt“被加密为 “tkzwsdf“.试写一算法将输入的文本串进行加密后输出。 答：加密算法可以用两个串中字符的一一对应关系来实现，当输入一个字符时，由算法在串 1 中查找其 位置，然后用串 2 中相应位置的字符去替换原来的字符就