数据结构与算法作业答案
- 格式：doc
- 大小：876.00 KB
- 文档页数：24
《数据结构与算法》作业参考答案说明：1、题号形式: 每题都以【sn，cha，sec】开头，sn表明本题的题目序号，每道题都有唯一的序号；cha表示内容所在的章；sec表示内容所在的节。
如:【17，2，1】表示序号17的题来自第2章第1节。
2、题型：1) 选择题：序号1-180题2) 是非题：序号181-220题3) 分析计算作图题：序号221-250题（选自《数据结构题集》—严蔚敏等编）3、内容取舍：根据本学期上课课件中的内容，未上课章节的练习可舍弃。
4、必做题或选做题：是非题和选择题（序号1-220）只要在上过课的章节中都是必做题，分析计算作图题（序号221-250）在每题后标出是必做题还是选做题，其中16个必做题14个选做题。
1) 选择题：序号1-180题序号参考答案1 BD2 D3 C4 A5 C6 D7 C8 D9 B10 D11 B12 D13 C14 C15 D16 A17 A18 A19 A20 A21 A22 D24 A25 B26 C27 C28 C29 B30 B31 B32 B33 B34 A35 A36 C37 D38 D39 B40 C41 B42 A43 D44 B45 D46 B47 C48 C49 B50 B51 A52 D53 D54 C55 A56 A57 C58 C59 C60 B61 A62 D64 B65 C66 B67 D68 D69 B70 A71 C72 B73 A74 D75 D76 B77 C78 C79 D80 B81 D82 C83 B84 A85 B86 C87 D88 B89 B90 B91 D92 C93 D94 A95 C96 C97 B98 A99 C 100 C 101 A 102 D 103 C105 C 106 D 107 C 108 B 109 B 110 D111 A 112 B 113 A 114 B 115 C 116 D 117 B 118 C 119 A 120 B121 A 122 A 123 C 124 C 125 B 126 B 127 B 128 C 129 C 130 B131 A 132 D 133 AB 134 D 135 C 136 C 137 B 138 A 139 B 140 B141 D 142 A 143 B145 A146 A147 C148 B149 C150 A151 B152 B153 C154 B155 A156 C157 C158 C159 A160 B161 C162 A163 A164 D165 B166 C167 D168 C169 C170 B171 B172 C173 B174 D175 C176 D177 B178 A179 A180 B2) 是非题：序号181-220题181 T182 T183 F184 T185 T186 F187 T188 T189 T190 T191 F192 T193 T194 F195 F196 T197 F198 T199 F200 T201 T202 T203 F204 T205 T206 F207 T208 T209 F210 T211 F212 T213 T214 F215 T216 T217 F218 T219 T220 F3) 分析计算作图题：序号221-250（选自《数据结构题集》—严蔚敏等编）【221，1，4】（选自《数据结构题集》1.8，选做题）设n为正整数，试确定下列各段程序中前置以记号@的语句的频度(语句的频度指的是该语句重复执行的次数)。
(1) i=1；k=0;while (i<=n-1){i++;@ k+=10*i;}答：该语句的频度为n-1(2) x=91; y=100;while(y>0){@ if(x>100) {x-=10; y--;}else x++;}答：在循环中，if语句为真1次，else语句执行10次，所以if 语句执行11次y 的值减1。
该语句的频度为100x(1+10) = 1100【222，1，4】（选自《数据结构题集》1.9，选做题）假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n函数形式表示）int Time (int n) {count =0; x=2;while( x<n/2 ) {x*=2; count++;}return (count);} // Time答：从while的循环控制可以看出，n每增加一倍,count的值增加1。
所以该算法的时间复杂度为O(log2 n)，根据初值，变量count 的值为「log2 (n-2)」- 1【223，2，3】（选自《数据结构题集》2.6，必做题）已知L是无表头结点的单链表，且P既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a．在P结点后插入S结点的语句序列是___（4）（1）____b．在P结点前插入S结点的语句序列是___（7）（11）（8）（4）（1）____ c．在表首插入S结点的语句序列是____（5）（12）________d．在表尾插入S结点的语句序列是______（9）（1）（6）_______（1）P —> next ＝S ；（2）P —> next ＝P —> next —> next；（3）P —> next ＝S —> next；（4）S —> next ＝P —> next；（5）S —> next ＝L；（6）S —> next ＝NULL；（7）Q ＝P；（8）while （P —> next ！＝Q）P ＝P —> next；（9）while （P —> next ！＝NULL）P ＝P —> next；（10）P ＝Q；（11）P ＝L；（12）L ＝S；（13）L ＝P；【224，2，2】（选自《数据结构题集》2.10，选做题）指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。
Status DeleteK（SqList &a，int i，int k）{//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if（i < 1 || k < 0 || i + k > a.length）return INFEASIBLE；// 参数不合法else {for（count ＝1；count < k；count ++）{//删除一个元素for（j ＝ a.length；j >＝i +1；j ――）a.elem[j－1] ＝ a.elem[j]；a.length ――；}return OK；} // DeleteK答：错误之处：题中有下划线处应改为：for （j ＝i+1；j <= a.length；j++） a.elem[j－1] ＝ a.elem[j]；低效费时之处：该算法每删除一个元素，其后所有的元素都向前移一位，包括将要删除的元素，比较耗时间。
（其中n＝a.length）下划线的语句的频度为：改进方法是将k个元素在一个循环内删除，算法如下：Status DeleteK（SqList &a，int i，int k）{//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if（i < 1 || k < 0 || i + k > a.length）return INFEASIBLE；// 参数不合法else {for（count ＝0；count < a.length－k－i；count ++）a.elem[i-1+ count] ＝ a.elem[k + i-1 + count ]；//删除k个元素a.length ＝ a.length－k；}return OK；} // DeleteK【225，3，1】（选自《数据结构题集》3.4，必做题）简述以下算法的功能（栈的元素类型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]）；}功能：利用数组A，将栈中所有的元素倒置。
（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）；}}功能：将栈S中与e相同的元素删除。
【226，3，1】（选自《数据结构题集》3.15，选做题）假设以顺序存储结构实现一个双向栈，即在一堆数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。
试编写实现这个双向栈tws的三个操作：初始化inistack（tws）、入栈push（tws，i，x）和出栈pop（tws，i）的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为变参）或函数设计这些操作算法各有什么优缺点。
typedef struct {SElemType *base[2];SElemType *top[2];int stacksize;} SqStack;Status initstack ( SqStack &tws) { // 初始化，构造一个空栈twstws．base[0] ＝（SElemType *）malloc（STACK_INIT_SIZE * sizeof（））；if（！tws.base[0]）exit（OVERFLOW）；// 存储分配失败tws．stacksize ＝STACK_INIT_SIZE；tws．base[1] ＝tws．base[0] + tws.stacksize－1;tws．top[0] ＝tws．base[0];tws．top[1] ＝tws．base[1];return OK；} // initstackStatus push（SqStack &tws，int i，ElemType x）{ // 插入元素x为新的栈顶元素if（tws.top[0] －base[0] + tws.top[1] －base[1] >= tws.stacksize）{// 栈满，追加存储空间increment0 = tws.top[0] －base[0];//０端的元素个数increment1 = tws.top[1] －base[1]; //１端的元素个数tws．base[0] ＝（SElemType *）realloc（tws.base[0] ,(tws.base[0]+STACKINCREMENT) * sizeof（ElemType））；if（！tws.base[0]）exit（OVERFLOW）；// 存储分配失败tws.stzcksize += STACKINCREMENT;temp=tws.base[1];tws．base[1] ＝tws．base[0] + tws.stacksize－1;for(i=0; i<increment1; i++)*(tws.base[1] - i) =*(temp - i); //把１端栈中元素移到新的双向栈的１端tws．top[0] ＝tws．base[0] + increment0;tws．top[1] ＝tws．base[1] - increment1;}if（i）* tws.top[1] -- = x；else* tws.top[0] ++ = x；return OK;} // pushStatus pop（SqStack &tws，int i）{// 若栈不空，则删除tws的栈顶元素，并返回OK；否则返回ERRORif（tws.top[0] ＝＝base[0] || tws.top[1] ＝＝base[1]）return ERROR；if（i）++ tws.top[1]；else――tws.top[0]；return OK；} // pop【227，3，4】（选自《数据结构题集》3.13，必做题）简述以下算法的功能（栈和队列的元素类型均为int）void algo3(Queue &Q){Stack S; int d;InitStack (S);while (!QueueEmpty (Q)) {DeQueue (Q, d); Push (S,d);}while (!StackEmpty (S)) {Pop (S, d); EnQueue(Q, d);}}答：将队列Q中的元素变成倒置排列。
