搜索
第1章绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1=n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题babadbcabdcddac2．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。ElemTypeMax(LinkListL){if(L-next==NULL)returnNULL;pmax=L-next;//假定第一个结点中数据具有最大值p=L-next-next;while(p!=NULL){//如果下一个结点存在if(p-datapmax-data)pmax=p;p=p-next;}returnpmax-data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。voidinverse(LinkList&L){//逆置带头结点的单链表Lp=L-next;L-next=NULL;while(p){q=p-next;//q指向*p的后继p-next=L-next;L-next=p;//*p插入在头结点之后p=q;}}（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。[题目分析]在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。voidDelete（ElemTypeA[]，intn）∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。{i=1；j=n；∥设置数组低、高端指针（下标）。while（ij）{while（ij&&A[i]!=item）i++；∥若值不为item，左移指针。if（ij）while（ij&&A[j]==item）j--；∥若右端元素值为item，指针左移if（ij）A[i++]=A[j--]；}[算法讨论]因元素只扫描一趟，算法时间复杂度为O（n）。删除元素未使用其它辅助空间，最后线性表中的元素个数是j。第3章栈和队列1．选择题CCDAADABCDDDBCB2.算法设计题（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)根据提示，算法可设计为：//以下为顺序栈的存储结构定义#defineStackSize100//假定预分配的栈空间最多为100个元素typedefcharDataType;//假定栈元素的数据类型为字符typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;intIsHuiwen(char*t){//判断t字符向量是否为回文，若是，返回1，否则返回0SeqStacks;inti,len;chartemp;InitStack(&s);len=strlen(t);//求向量长度for(i=0;ilen/2;i++)//将一半字符入栈Push(&s,t[i]);while(!EmptyStack(&s)){//每弹出一个字符与相应字符比较temp=Pop(&s);if(temp!=S[i])return0;//不等则返回0elsei++;}return1;//比较完毕均相等则返回1}（7）假设以数组Q[m]存放循环队列中的元素,同时设置一个标志tag，以tag==0和tag==1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。【解答】循环队列类定义#includeassert.htemplateclassTypeclassQueue{//循环队列的类定义public:Queue(int=10);~Queue(){delete[]Q;}voidEnQueue(Type&item);TypeDeQueue();TypeGetFront();voidMakeEmpty(){front=rear=tag=0;}//置空队列intIsEmpty()const{returnfront==rear&&tag==0;}//判队列空否intIsFull()const{returnfront==rear&&tag==1;}//判队列满否private:intrear,front,tag;//队尾指针、队头指针和队满标志Type*Q;//存放队列元素的数组intm;//队列最大可容纳元素个数}构造函数templateclassTypeQueueType::Queue(intsz):rear(0),front(0),tag(0),m(sz){//建立一个最大具有m个元素的空队列。Q=newType[m];//创建队列空间assert(Q!=0);//断言:动态存储分配成功与否}插入函数templateclassTypevoidQueueType::EnQueue(Type&item){assert(!IsFull());//判队列是否不满，满则出错处理rear=(rear+1)%m;//队尾位置进1,队尾指针指示实际队尾位置Q[rear]=item;//进队列tag=1;//标志改1，表示队列不空}删除函数templateclassTypeTypeQueueType::DeQueue(){assert(!IsEmpty());//判断队列是否不空，空则出错处理front=(front+1)%m;//队头位置进1,队头指针指示实际队头的前一位置tag=0;//标志改0,表示栈不满returnQ[front];//返回原队头元素的值}读取队头元素函数templateclassTypeTypeQueueType::GetFront(){assert(!IsEmpty());//判断队列是否不空，空则出错处理returnQ[(front+1)%m];//返回队头元素的值}第4章串、数组和广义表1．选择题BBCABBBCBBABDCBC2.综合应用题（1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。模式串t的next和nextval值如下：j123456789101112t串abcaabbabcabnext[j]011122312345nextval[j]011021301105（3）数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求：①存放该数组所需多少单元？②存放数组第4列所有元素至少需多少单元？③数组按行存放时，元素A[7,4]的起始地址是多少？④数组按列存放时，元素A[4,7]的起始地址是多少？每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。（1）242（2）22（3）s+182（4）s+142(4)请将香蕉banana用工具H()—Head()，T()—Tail()从L中取出。L=(apple,(orange,(strawberry,(banana)),peach),pear)H（H（T（H（T（H（T（L）））））））（5）写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。voidCount（）//统计输入字符串中数字字符和字母字符的个数。｛inti，num[36]；charch；for（i＝0；i36；i++）num[i]＝０；//初始化while（（ch＝getchar（））!=‘#’）//‘#’表示输入字符串结束。if（‘0’=ch=‘9’）｛i=ch－48;num[i]++；｝//数字字符elseif（‘A’=ch=‘Z’）｛i=ch-65+10;num[i]++；｝//字母字符for（i=0；i10；i++）//输出数字字符的个数printf（“数字％d的个数＝％d\n”，i，num[i]）；for（i＝10；i36；i++）//求出字母字符的个数printf（“字母字符％c的个数＝％d\n”，i＋55，num[i]）；｝//算法结束。第5章树和二叉树1．选择题ADDCACCBDCCCACC2．应用题（2）设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC①画出这棵二叉树。②画出这棵二叉树的后序线索树。③将这棵二叉树转换成对应的树（或森林）。(1)(2)（3）假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。①试为这8个字母设计赫夫曼编码。②试设计另一种由二进制表示的等长编码方案。③对于上述实例，比较两种方案的优缺点。解：方案1；哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6],(7,10)】,……19,21,32（100）（40）（60）192132（28）（17）（11）7106（5）23方案比较：方案1的WPL＝ABMFD(3)CEMHGAEDCBHGFAEDCBHGFnull字母编号对应编码出现频率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10010101192132010101710601232(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码3．算法设计题以二叉链表作为二叉树的存储结构，编写以下算法：（1）统计二叉树的叶结点个数。intLeafNodeCount(BiTreeT){if(T==NULL)return0;//如果是空树，则叶子结点个数为0elseif(T-lchild==NULL&&T-rchild==NULL)return1;//判断该结点是否是叶子结点（左孩子右孩子都为空），若是则返回1elsereturnLeafNodeCount(T-lchild)+LeafNodeCount(T-rchild);}（3）交换二叉树每个结点的左孩子和右孩子。voidChangeLR(BiTree&T){BiTreetemp;if(T-lchild==NULL&&T-rchild==NULL)return;else{temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;}ChangeLR(T-lchild);ChangeLR(T-rchild);}第6章图1．选择题CBBBCBABAADCCDDB2．应用题（1）已知如图6.27所示的有向图，请给出：①每个顶点的入度和出度；②邻接矩阵；③邻接表；④逆邻接表。（2）已知如图6.28所示的无向网，请给出：①邻接矩阵；②邻接表；③最小生成树a→b4→c3b→a4→c5