4) 分析计算作图题：序号1-55（选自《数据结构题集》—严蔚敏等编）
【1， 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
【2， 1，4】（选自《数据结构题集》1.9，选做题）
假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n函数形式表示）
int Time (int n) {
count =0; x=2; while( x x*=2; count++; } return (count); } // Time 答：从while的循环控制可以看出，n每增加一倍,count的值增加1。所以该算法的时间复杂度为O(log2 n)，根据初值，变量count 的值为「log2 (n-2) 」- 1 【3， 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； 【4， 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 【5， 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相同的元素删除。 【6， 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) { // 初始化，构造一个空栈tws tws．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； } // initstack Status 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 if（i） * tws.top[1] -- = x； else * tws.top[0] ++ = x； return OK; } // push Status pop（SqStack &tws，int i） { // 若栈不空，则删除tws的栈顶元素，并返回OK；否则返回ERROR if（tws.top[0] ＝＝ base[0] || tws.top[1] ＝＝ base[1]） return ERROR； if（i） ++ tws.top[1]； else ――tws.top[0]； return OK； } // pop 【7， 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中的元素变成倒置排列。 【8， 3，2】（选自《数据结构题集》3.19，选做题） 假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”和花括号“{”和“}”，且这三种括号可以按任意的次序嵌套使用（如：?[?{?}?[?]?]?[?]?(?)?）。编写判别给定表达式所含括号是否正确配对出现的算法（已知表达式已存入数据元素为字符的顺序表中）。 解：算法如下： Status MatchBrackets ( ) { SqStack &S; InitStack (S); while ((c=getchar())!=‘\\n’){ if(!StackEmpty (S) && (c==‘)’&& GetTop (S)==‘(’|| c==‘ ]’ && GetTop (S)== ‘[’|| c==‘}’ && GetTop (S)==‘{’) ) Pop (S); //判断括号是否匹配 else if(IsLeftBracket(c)) Push (S, c)； //判断是否是括号 } if(!StackEmpty(S)) return ERROR; else return TRUE; } 【9， 4，1】（选自《数据结构题集》4.3，必做题） 设s =‘I AM A STUDENT’,t =‘GOOD’,q =‘WORKER’。求： StrLength(s), StrLength(t), SubString(s,8,7), SubString(t,2,1), Index(s, ‘A’), Index(s, t), Replace(s, ‘STUDENT’,q ), Concat(SubString(s,6,2),Concat(t,SubString(s,7,8))) 答：StrLength(s) = 14, StrLength(t) = 4, SubString(s,8,7) =‘STUDENT’, SubString(t,2,1) =‘O’, Index(s,‘A’) = 3, Index(s, t) = 0, Replace(s, ‘STUDENT’,q ) = ‘I AM A WORKER’, Concat(SubString(s,6,2),Concat(t,SubString(s,7,8))) =‘A GOOD STUDENT’ 【10， 5，1】（选自《数据结构题集》5.1，必做题） 假设有两维数组A6x8，每个元素用相邻的6个字节存储，存储按字节编址。已知A的起始地址为1000，计算： (1) 数组A的存储量； = 6x8x6 = 288 (字节) (2) 数组A的最后一个元素a57的第一个字节的地址；=1000+288-6=1282