下载文档原格式
1、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。
假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。
#include <stdio.h>typedef char datatype;typedef struct node{datatype data;struct node * next;} listnode;typedef listnode* linklist;/*--------------------------------------------*//* 删除单链表中重复的结点 *//*--------------------------------------------*/linklist deletelist(linklist head){ listnode *p,*s,*q;p=head->next;while(p){s=p;q=p->next;while(q)if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{ s=q; /*找与P结点值相同的结点*/q=q->next;}p=p->next;}return head;}2、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。
20分void Hospital(AdjMatrix w,int n)//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。
1、设置屏幕显示属性时，与屏幕分辨率及颜色质量有关的设备是____。
A、CPU和硬盘B、显卡和显示器C、网卡和服务器D、CPU和操作系统2、软盘和硬盘属于____A、输入设备B、输出设备C、外存储器D、内存储器3、标准键盘的回车键上一般都标着____。
A、ShiftB、EnterC、TabD、Backspace4、计算机的三类总线中，不包括____。
A、控制总线B、地址总线C、传输总线D、数据总线5、根据统计，当前计算机病毒扩散最快的途径是____。
A、软件复制B、网络传播C、磁盘拷贝D、运行游戏软件6、用高级程序设计语言编写的程序，要转换成等价的可执行程序，必须经过____。
A、汇编B、编辑C、解释D、编译和连接7、标准ASCII码是用7位____代码来表示的。
A、八进制代码B、十进制代码C、二进制代码D、十六进制代码8、在Windows中关于查找文件，下列说法中不正确的是____。
A、可以按作者查找文件B、可以按日期查找文件C、可以按大小查找文件D、可以按文件名中包含的字符查找文件9、主页的含义是指____。
A、WEB站点默认的首页B、在浏览器中设定的第一个显示的页面C、网页的另一种说法D、WEB站点中的主要页面10、关于信息，以下说法不正确的是____。
A、信息是特指计算机中保存的程序B、信息可以影响人们的行为和思维C、信息需要通过媒体才能传播D、信息有多种不同的表示形式11、全球信息网(WWW)的主要传输的通讯协议是____。
A、FTPB、HTTPC、HTMLD、XMTP12、在Word2000中，可用于计算表格中某一数值列平均值的函数是____。
A、Average()B、Count()C、Abs()D、Total()13、E-mail地址格式为：usename@hostname，其中usename称为____。
A、用户名B、某网站名C、某网络公司名D、主机域名14、计算机中的存储系统是指____A、RAMB、ROMC、主存储器D、主存储器和外存储器15、在Word下，将文档的一部分文本内容复制到别处，首先要进行的操作是____。
1、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。
void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度{BiTree p=bt,l[],s[]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点int i，top=0,tag[],longest=0;while(p || top>0){ while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下if(tag[top]==1) //当前结点的右分枝已遍历{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}//保留当前最长路径到l栈，记住最高栈顶指针，退栈}else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下}//while(p!=null||top>0)}//结束LongestPath2、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。
采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。
本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。
后序遍历必然先遍历到结点p，栈中元素均为p的祖先。
将栈拷入另一辅助栈中。
再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。
1、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。
设当n=m-1时结论成立，现证明当n=m时结论成立。
设中序序列为S1，S2，…，Sm,后序序列是P1,P2,…，Pm。
因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，…，Si-1是左子树的中序序列，而Si+1,Si+2,…,Sm是右子树的中序序列。
若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，…，Sm}和{P1，P2，…，Pm-1}可以唯一确定右子树，从而也确定了二叉树。
若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一确定左子树，从而也确定了二叉树。
最后，当1<i<m时，Si把中序序列分成{S1，S2，…，Si-1}和{Si+1,Si+2,…，Sm}。
由于后序遍历是“左子树—右子树—根结点”，所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉树的左子树和右子树的后序遍历序列。
因而由{S1，S2，…，Si-1}和{P1，P2，…，Pi-1}可唯一确定二叉树的左子树，由{Si+1,Si+2,…，Sm}和{Pi,Pi+1,…，Pm-1}可唯一确定二叉树的右子树。
2、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}写出G的拓扑排序的结果。
1、与Web站点和Web页面密切相关的一个概念称"统一资源定位器"，它的英文缩写是____。
A、UPSB、USBC、ULRD、URL2、在Word2000种，编辑英文文本时经常会出现红色下划波浪线，表示____。
A、语法错误B、单词拼写错误C、格式错误D、逻辑错误3、在Word2000的默认状态下，不用"打开"文件对话框就能直接打开最近使用过的文档的方法是____。
A、快捷键Ctrl+OB、工具栏上"打开"按钮C、选择"文件"菜单中的"打开"命令D、选择"文件"菜单底部文件列表中的文件4、下面关于Windows 中滚动条的叙述，是不正确的是____A、通过单击滚动条上的滚动箭头可以实现单步滚动B、通过拖动滚动条上的滚动块可以实现快速滚动C、滚动条有水平滚动条和垂直滚动条两种D、每个窗口上都具有滚动条5、微型计算机的核心部件是____。
A、控制器B、存储器C、微处理器D、运算器6、下列哪种不是预防计算机病毒的主要做法____A、不使用外来软件B、定期进行病毒检查C、复制数据文件副本D、当病毒侵害计算机系统时，应停止使用，须进行清除病毒7、下列属于应用软件的是____A、LinuxB、PASCALC、Excel 2000D、Windows 20008、下列哪一项是属于局域网中外部设备的共享____A、局域网中的多个用户共同使用某个应用程序B、局域网中的多个用户共同使用网上的一台打印机C、将多个用户的计算机同时开机D、借助网络系统传送数据9、下列带有通配符的文件名，能表示文件ABC、TXT的是____。
A、*BC、?B、A?.*C、?BC、*D、?.?10、以下各项在Word的窗口显示中不可隐藏的是____。
A、水平和垂直滚动条B、绘图工具栏C、菜单栏D、状态栏11、关于word2000中的分页符的描述，错误的是____。
1、因特网中的BBS是指____A、电子邮箱B、电子政务C、电子商务D、电子公告栏2、Internet起源于____。
A、美国B、英国C、德国D、澳大利亚3、C、A_jy@D、A_jy #4、一个汉字和一个英文字符在微型机中存储时所占字节数的比值为____。
A 、4:1 B、2:1 C、1:1 D、1:45、在Outlook Express中设置唯一的电子邮件账号kao@，现发送一封电子邮件给shi@，则发送完成后____A、发件箱中有kao@邮件B、发件箱中有shi@邮件C、已发送邮件中kao@邮件D、已发送邮件中shi@邮件6、以____将网络划分为广域网、城域网和局域网。
A、接入的计算机多少B、接入的计算机类型C、拓朴类型D、接入的计算机距离7、下列4项内容中，不属于Internet（因特网）提供的服务的是____。
A、电子邮件B、文件传输C、远程登录D、实时监测控制8、HTTP指的是____。
A、超文本标记语言B、超文本文件C、超媒体文件D、超文本传输协议9、完整的冯?诺依曼结构的计算机，其硬件系统包括____A、CPU、内存、键盘、显示器B、运算器、控制器、键盘、显示器C、CPU、存储器、输出设备、输入设备D、CPU、存储器、键盘、鼠标器、显示器10、域名最右边的部分表示区域， cn代表____A、加拿大B、中国C、联合国D、美国11、在Windows中，为了查找文件名以"A"字母打头，后跟一字母的所有文件，应当在查找名称框内输入____。
A、AB、A*C、A？D、A#12、在一个文件夹____A、只能包含文件B、只能包含文件夹C、可以包含文件或文件夹D、必须包含文件或文件夹13、14、在Word文档中插入图形的第一步操作是____。
A、执行"插入"菜单中的"图片"命令B、将插入点置于图形预期出现的位置C、在图片对话框中选择要输入的图片文件名D、单击"确定"按钮，插入图片15、Word2000常用工具栏上←、→按钮的作用是____。
1、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。
设当n=m-1时结论成立，现证明当n=m时结论成立。
设中序序列为S1，S2，…，Sm,后序序列是P1,P2,…，Pm。
因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，…，Si-1是左子树的中序序列，而Si+1,Si+2,…,Sm是右子树的中序序列。
若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，…，Sm}和{P1，P2，…，Pm-1}可以唯一确定右子树，从而也确定了二叉树。
若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一确定左子树，从而也确定了二叉树。
最后，当1<i<m时，Si把中序序列分成{S1，S2，…，Si-1}和{Si+1,Si+2,…，Sm}。
由于后序遍历是“左子树—右子树—根结点”，所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉树的左子树和右子树的后序遍历序列。
因而由{S1，S2，…，Si-1}和{P1，P2，…，Pi-1}
可唯一确定二叉树的左子树，由{Si+1,Si+2,…，Sm}和
{Pi,Pi+1,…，Pm-1}可唯一确定二叉树的右子树。
2、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}
写出G的拓扑排序的结果。
G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7
3、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。
所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。
请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。
注：圈就是回路。
4、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。
int Similar(BiTree p,q)//判断二叉树p和q是否相似
{if(p==null&&q==null)return(1);
else if(!p&&q||p&&!q)return(0);
else return(Similar(p->lchild,q->lchild)&&Similar(p->rchild,q->rchild)) }//结束Similar
5、二部图（bipartite graph）G=（V，E）是一个能将其结点集V分为两不相交子集V1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。
（1）．请各举一个结点个数为5的二部图和非二部图的例子。
（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。
设G用二维数组A来表示，大小为n*n（n为结点个数）。
请在程序中加必要的注释。
若有必要可直接利用堆栈或队列操作。
【
6、编程实现单链表的就地逆置。
23．在数组A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.
7、假设以I和O分别表示入栈和出栈操作。
栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
（15分）
（1）A和D是合法序列，B和C是非法序列。
（2）设被判定的操作序列已存入一维数组A中。
int Judge(char A[])
//判断字符数组A中的输入输出序列是否是合法序列。
如是，返回true，否则返回false。
{i=0;//i为下标。
j=k=0;//j和k分别为I和字母O的的个数。
while(A[i]!=‘\0’)//当未到字符数组尾就作。
{switch(A[i])
{case‘I’:j++;break;//入栈次数增1。
case‘O’:k++;if(k>j){printf(“序列非法\n”)；exit(0);}
}
i++;//不论A[i]是‘I’或‘O’，指针i均后移。
}
if(j!=k){printf(“序列非法\n”)；return(false);}
else{printf(“序列合法\n”)；return(true);}
}//算法结束。
8、设一棵二叉树的结点结构为(LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p 和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。
9、设从键盘输入一整数的序列：a1,a2,a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况（入栈满等）给出相应的信息。
设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。
问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。
设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。
请在下列算法的下划线处填空，使其正确求解背包问题。
Knap(S，n)
若S=0
则Knap←true
否则若（S<0）或(S>0且n<1)
则Knap←false
否则若Knap(1),_=true
则print(W[n])；Knap←true
否则Knap←Knap(2)_,_
设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,
s3,s4,s6,s5,s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。
例如：
设str1和str2是分别指向两个单词的头结点，请设计一个尽可能的高效算法，找出两个单词共同后缀的起始位置，分析算法时间复杂度。
将n(n>1)个整数存放到一维数组R中。
设计一个尽可能高效（时间、空间）的算
法，将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据（x0,x1,x2,…,xn-1），变换为(xp，xp＋1,…,xn-1,x0,x1,…,xp-1)。
10、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}
写出G的拓扑排序的结果。
G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7
11、设从键盘输入一整数的序列：a1,a2,a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况（入栈满等）给出相应的信息。
设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。
问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。
设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。
请在下列算法的下划线处填空，使其正确求解背包问题。
Knap(S，n)
若S=0
则Knap←true
否则若（S<0）或(S>0且n<1)
则Knap←false
否则若Knap(1),_=true
则print(W[n])；Knap←true
否则Knap←Knap(2)_,_
设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2, s3,s4,s6,s5,s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。
例如：
设str1和str2是分别指向两个单词的头结点，请设计一个尽可能的高效算法，找出两个单词共同后缀的起始位置，分析算法时间复杂度。
将n(n>1)个整数存放到一维数组R中。
设计一个尽可能高效（时间、空间）的算
法，将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据（x0,x1,x2,…,xn-1），变换为(xp，xp＋1,…,xn-1,x0,x1,…,xp-1)。
