2014香港特别行政区数据结构(C++)理论考试试题及答案

1、ascii码是一种（A）a、字符编码b、压缩编码c、传输码d、校验码2、windows2000（d）版，是microsoft提供的功能最为强大的服务器操作系统。

a、专业 b、服务器 c、高级服务器 d、数据中心3、（b）是用户操作windows2000的基本对象。

a、菜单b、窗口c、对话框d、a，b，c4、在“开始“按钮的右边，有（a）可快速完成一些日常操作。

ａ、三个小图标ｂ、一个窗口ｃ、一个对话框ｄ、按钮、5、在“开始“按钮的右边，有（a）可快速完成一些日常操作。

ａ、三个小图标ｂ、一个窗口ｃ、一个对话框ｄ、按钮、6、（b）是用户操作windows2000的基本对象。

a、菜单b、窗口c、对话框d、a，b，c7、以下不属于磁盘指标参数的是（c）`a、磁道b、扇区c、精度d、密度8、以下哪条不属于计算机的基本特点（d）a、运算速度快b、记忆能力c、精度高d、密度9、鼠标器上一般有两个或（a）个按扭。

a、3 b、1 c、5 d、410、一个窗口一般只占桌面的部分空间，使之充满整个桌面，这称为窗口（d）。

a、放大b、最小化 c、恢复 d、最大化11、用鼠标器点击在“桌面”上的许多“图像”，可以完成（a）a、相应操作b、保存文件c、上网d、关闭窗口12、位于互联网上的计算机都有其唯一的地址，称为（c）a、网络地址b、域名c、ip地址d、主机名13、在任务栏的左边是“开始“按钮，任务栏的右边显示时间，单击任务栏上的按钮可以（b）应用程序。

a、关闭b、快速切换c、保存d、打印14、用杀毒软件清除计算机病毒是较好的一种方法，但对于不断出现的新病毒，应该（c）a、及时上报b、购买新软件c、更新杀毒盘d、没办法15、鼠标器上控制着（b）上的一个光标。

a 、窗口 b、屏幕 c、图像 d、菜单16、windows2000（a）版，是为商务用户开发的，供台式机和便携电脑使用的操作系统。

a、专业b、服务器c、高能服务器d、数据中心17、使用（a）程序可以将用户的计算机通过网络与另一台计算机连接起来。

1、使用搜狐搜索引擎时，要搜索中国人获诺贝尔奖方面的情况，应输入____A、中国人诺贝尔奖B、中国人|诺贝尔奖C、中国人—诺贝尔奖2、每台计算机必须知道对方的____ 才能在Internet上与之通信。

A、电话号码B、主机号C、IP地址D、邮编与通信地址3、一般用高级语言编写的应用程序称为____。

A、编译程序B、编辑程序C、连接程序D、源程序4、记录在录音机磁带、录像带上的信息属于____。

A、模拟信息B、数字信息C、仿真信息D、广播信息5、目前，配有P4 CPU的微型计算机属于计算机的____。

A、第一代产品B、第二代产品C、第三代产品D、第四代产品6、计算机的存储程序和程序控制的工作原理是由数学家____提出的。

A、图灵B、帕斯卡C、冯?诺依曼D、莱布尼兹7、在WORD中，以下关于文字设置的说法正确的是____。

A、默认字体有宋体、黑体、楷体、隶B、文字格式工具栏中加粗按钮可以设置文字的颜色C、利用格式菜单打开字体对话框，可以设置字符间距D、利用格式菜单打开段落对话框，可以设置字符间距8、计算机网络的资源共享功能包括____。

A、硬件资源和软件资源共享B、软件资源和数据资源共享C、设备资源和非设备资源共享D、硬件资源、软件资源和数据资源共享9、为了保证任务栏任何时候在屏幕上可见，应在"任务栏属性"对话框的"任务栏选项"标签中选择____。

Ａ、不被覆盖 B、总在最前 C、自动隐藏 D、显示时钟10、计算机存储器的一个字节可以存放____。

A、一个汉字B、二个汉字C、一个西文字符D、二个西文字符11、Internet 主要采用的协议是_____。

A、FTPB、HTTPC、IPX/SPXD、TCP/IP12、Word 将一些常用命令用图标代替，集中在一起而形成工具栏。

如果想在屏幕上显示或隐藏其他工具栏，应____并在子菜单中进行选择便可。

A、选择"视图"菜单 / 单击"全屏显示"B、选择"视图"菜单 / 单击"工具栏"C、选择"工具"菜单 / 单击"选项"D、选择"工具"菜单 / 单击"自定义"13、电子邮件地址由两部分组成，用@号隔开，其中@号前为____。

1、和通信网络相比，计算机网络最本质的功能是____。

A、数据通信B、资源共享C、提高计算机的可靠性和可用性D、分布式处理2、在Word的编辑状态，进行"替换"操作时，应当使用____菜单中的命令。

A、"工具"菜单中的命令B、"视图"菜单中的命令C、"格式"莱单中的命令D、"编辑"菜单中的命令3、在 Word的编辑状态，执行编辑菜单中的“粘贴”命令后___。

A、将文档中被选择的内容复制到当前插入点处B、将文档中被选择的内容移到剪贴板C、将剪贴板中的内容移到当前插入点处D、将剪贴板中的内容拷贝到当前插入点处。

4、在Excel中，计算求和的函数是____。

A、CountB、SumC、MaxD、Average5、划分计算机发展四个时代的主要依据是____。

A 、价格 B、体积 C、存储容量 D、电子元器件6、下列专门用于浏览网页的应用软件是____。

A、WORDB、Outlook expressC、FrontPageD、Internet Explorer7、编辑Word 2000表格时，用鼠标指针拖动水平标尺上的列标记，可以调整表格的____。

A、行高B、单元格高度C、列宽D、单元格宽度8、在word编辑状态下，不用“打开”文件对话框就能直接打开最的使用过的文档的方档的方法是________A、快捷键CTRL＋OB、工具栏上“打开”按钮C、选择“文件”菜单底部文件列表中的文件D、选择“文件”菜单中的“打开”命令9、标准ASCII码是用7位____代码来表示的。

A、八进制代码B、十进制代码C、二进制代码D、十六进制代码10、下列选项中属于数据库管理系统的是____。

A、LinuxB、AccessC、Auto CADD、Word11、在Word的编辑状态，执行“文件”菜单中的“保存”命令后____。

A、将所有打开的文档存盘B、只能将当前文档存储在原文件夹内C、可以将当前文档存储在原文件夹内D、可以先建立一个新文件夹，再将文档存储在该文件夹内12、将高级语言程序设计语言源程序翻译成计算机可执行代码的软件称为 ____A、汇编程序B、编译程序C、管理程序D、服务程序13、网络中计算机之间的通信是通过____实现的，它们是通信双方必须遵守的约定。

1、FTP是一个____协议，它可以用来下载和传送计算机中的文件。

A、文件传输B、网站传输C、文件压缩D、文件解压2、“冯?诺依曼计算机”的体系结构主要分为____五大组成。

A、外部存储器、内部存储器、CPU、显示、打印B、输入、输出、运算器、控制器、存储器C、输入、输出、控制、存储、外设D、都不是3、数字化信息指的是____A、数学中的信息B、用数字0和1来表示的信息C、用数字表示的字符信息4、使用“开始”菜单中的查找命令，要查找的文件名中可以使用____。

A、通配符?B、通配符*C、两者都可以D、两者都不可以5、对PC机，人们常提到的"Pentium"、"Pentium IV"指的是_____。

A、存储器B、内存品牌C、主板型号D、CPU类型6、有关窗口的说法中，错误的是____。

A、窗口大小可以改变B、窗口的位置可以移动C、窗口能被最小化D、桌面上可以有多个活动窗口7、代表政府机构的网络名是____。

A、GovB、EduC、ComD、Net8、计算机系统由哪几部分组成____。

A、主机和外部设备B、软件系统和硬件系统C、主机和软件系统D、操作系统和硬件系统9、根据统计，当前计算机病毒扩散最快的途径是____。

A、软件复制B、网络传播C、磁盘拷贝D、运行游戏软件10、计算机的系统软件和应用软件均属于____。

A、办公系统B、操作系统C、软件系统D、硬件系统11、word2000文字处理软件是____。

A、操作系统B、通用应用软件C、系统软件D、语言处理程序12、计算机的系统软件和应用软件均属于____。

A、办公系统B、操作系统C、软件系统D、硬件系统13、设置了屏幕保护程序后，如用户在一段时间____Windows将执行屏幕保护程序。

A、没有按键盘B、没有移动鼠标器C、既没有按键盘，也没有移动鼠标器D、没有使用打印机14、Access是一种____数据库管理系统。

1、在word编辑状态下，若要将另一文档的内容全部添加在当前文档插入点处，应该选择的操作是____。

A、单击“文件”—“打开”B、单击“文件”—“新建”C、单击“插入”—“文件”D、单击“插入”—“超级链接”2、计算机中字节是常用单位，它的英文名字是____。

Ａ、Bit B、byte C、bout D、baut3、E-mail地址格式为：usename@hostname，其中usename称为____。

A、用户名B、某网站名C、某网络公司名D、主机域名4、图像数据压缩的目的是____。

A、为了符合ISO标准B、为了符合各国的电视制式C、为了减少数据存储量，利于传输D、为了图像编辑的方便5、多媒体信息不包括____。

A、文字、图形B、音频、视频C、影像、动画D、光盘、声卡6、hebei@sohu、com是一个电子邮件地址，其中hebei是____。

A、域名B、用户名C、Ip地址D、计算机名7、WWW网是____。

A、局域网的简称B、城域网的简称C、广域网的简称D、万维网的简称8、用户在 WORD97 中编辑某文档时，突然被要求创建一新的文档进行编辑。

这时，该用户正确操作方法是____。

A、选择"文件"菜单 / 单击"打开"B、选择"文件"菜单 / 单击"新建"C、选择"插入"菜单 / 单击"文件"D、选择"插入"菜单 / 单击"对象"9、在Excel工作表中，每个单元格都有唯一的编号叫地址，地址的使用方法是____。

A、字母+数字B、列标+行号C、数字+字母D、行号+列标10、计算机的系统软件和应用软件均属于____。

A、办公系统B、操作系统C、软件系统D、硬件系统11、计算机网络在应用上的两种主要类型分别是局域网和____。

A、广域网B、局部网C、全球网D、互联网12、文件的存取控制属性中，只读的含义是指该文件只能读而不能____。

1、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。

#define MAX 100typedef struct Node{char info; struct Node *llink, *rlink; }TNODE;char pred[MAX],inod[MAX];main(int argc,int **argv){ TNODE *root;if(argc<3) exit 0;strcpy(pred,argv[1]); strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE *restore(char *ppos,char *ipos,int n){ TNODE *ptr； char *rpos; int k;if(n<=0) return NULL;ptr->info=(1)_______;for((2)_______ ; rpos<ipos+n;rpos++) if(*rpos==*ppos) break;k=(3)_______;ptr->llink=restore(ppos+1, (4)_______,k );ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);return ptr;}postorder(TNODE*ptr){ if(ptr=NULL) return;postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); }2、给出折半查找的递归算法，并给出算法时间复杂度性分析。

1、一般用高级语言编写的应用程序称为____。

A、编译程序B、编辑程序C、连接程序D、源程序2、微型计算机硬件系统主要包括：微处理器、____、输入设备、输出设备。

A、运算器B、控制器C、存储器D、主机3、以下属于操作系统的是____A、WPSB、ADSLC、LinuxD、Excel4、TCP的主要功能是_____。

A、进行数据分组B、保证可靠传输C、确定数据传输路径D、提高传输速度5、在计算机网络中WAN表示____。

A、有线网B、无线网C、局域网D、广域网6、浏览Web网站必须使用浏览器，目前常用的浏览器是____。

A、HotmailB、Outlook ExpressC、Inter ExchangD、Internet Explorer7、计算机存储器是一种____。

A、运算部件B、输入部件C、输出部件D、记忆部件8、在Windows 中，有些菜单项的右端有…标记，表示该菜单项____。

A、开关命令B、单选命令C、有子菜单D、有对话框9、在微机中，bit 的中文含义是____。

A、二进制位B、双字C、字节D、字用一个字节最多能编出____不同的码。

A、8个B、16个C、128个D、256个10、操作系统的主要功能是针对计算机系统的四类资源进行有效的管理，该四类资源是____。

A、处理器、存储器、打印机B、处理器、硬盘、键盘和显示器C、处理器、网络设备D、处理器、存储器、I/O设备和文件系统11、在 Windows 中有两个管理系统资源的程序组，它们是____。

A、“我的电脑”和“控制面板”B、“资源管理器”和“控制面板”C、“我的电脑”和“资源管理器”D、“控制面板”和“开始”菜单12、信息技术包括计算机技术、网络技术和____。

A、编码技术B、电子技术C、通信技术D、显示技术13、体现我国政府对计算机软件知识产权进行保护的第一部政策法规是____A、《计算机软件保护条例》B、《中华人民共和国技术合同法》C、《计算机软件著作权登记》D、《中华人民共和国著作权法》14、IP地址是____。

1、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。

20分void Hospital(AdjMatrix w,int n)//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。

{for (k=1;k<=n;k++) //求任意两顶点间的最短路径for (i=1;i<=n;i++)for (j=1;j<=n;j++)if (w[i][k]+w[k][j]<w[i][j]) w[i][j]=w[i][k]+w[k][j];m=MAXINT; //设定m为机器内最大整数。

for (i=1;i<=n;i++) //求最长路径中最短的一条。

{s=0;for (j=1;j<=n;j++) //求从某村庄i（1<=i<=n）到其它村庄的最长路径。

if (w[i][j]>s) s=w[i][j];if (s<=m) {m=s; k=i;}//在最长路径中，取最短的一条。

m记最长路径，k记出发顶点的下标。

Printf(“医院应建在%d村庄，到医院距离为%d\n”,i,m);}//for}//算法结束对以上实例模拟的过程略。

各行中最大数依次是9，9，6，7，9，9。

这几个最大数中最小者为6，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。

1、对图1所示的连通网G，请用Prim算法构造其最小生成树（每选取一条边画一个图）。

2、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。

采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。

本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。

1、目前网络传输介质中传输安全性最高的是______。

（A）A．光纤 B．同轴电缆C．电话线 D．双绞线2、想要完全释放计算机的IP地址在Dos提示符下输入的命令为______。

（B）A．IPCONFIG／ALL B．IPCONFIG／RENEWC．IPCONFIG／RELEASE D．WINIPCFG3、若要系统中每次缺省添加用户时，都自动设置用户的宿主目录为/users，需修改哪一个配置文件？（A）A．/etc/default/useradd B．/etc/login.defs C．/etc/shadow D．/etc/passwd4、你的计算机装的Windows 2000 Professional。

当你运行“磁盘碎片整理”程序的时候办公室停电了。

重启计算机，你收到如下的错误信息：“不能找到操作系统或操作系统已坏”你该怎么做呢________。

（D）A．用安全模式进入计算机，重新格式化硬盘B．用调试模式进入计算机，重新格式化硬盘C．用应急磁盘启动计算机，准备恢复主引导记录D．用光驱启动计算机，用恢复控制台准备恢复主引导记录5、当在Windows2000下创建分区时，FAT32分区大小的限制是_________。

（C）A．8GB B．16GB C．32GB D．64GB6、以下哪个命令可以保存路由器RAM中的配置文件到NVRAM中________。

（C）A．copy running-config tftp B．copy startup-config tftpC．copy running-config startup-config D．copy startup-config running-config7、如果两台交换机直接用双绞线相连，其中一端采用了，白橙/橙/白绿/蓝/白蓝/绿/白棕/棕的线序，另一端选择哪一种线序排列是正确的_______。

（B）A．白绿/绿/白橙/橙/白蓝/蓝/白棕/棕 B．白绿/绿/白橙/蓝/白蓝/橙/白棕/棕C．白橙/橙/白绿/绿/白蓝/蓝/白棕/棕 D．白橙/橙/白绿/蓝/白蓝/绿/白棕/棕8、在Windows 2000 Advanced Server最多支持的处理器数量是______。

1、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入一个结点的操作为（ B ）。

A）front=front->next; B） rear=rear->next;C） rear=front->next; D） front=rear->next ;2、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入一个结点的操作为（ B ）。

A）front=front->next; B） rear=rear->next;C） rear=front->next; D） front=rear->next ;3、n个顶点的强连通图至少有（ A ）条边。

A）n B）n+1 C）n-1 D）n(n-1)4、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ D ）存储方式最节省时间。

A）顺序表B）双链表C）带头结点的双循环链表D）单循环链表5、设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ A ）。

A）p->next=p->next->next; B） p=p->next;C）p=p->next->next; D） p->next=p;6、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（ A ）。

A）一个数量级别 B）一个平均值C）一个最大值 D）一个均方值7、串的逻辑结构与（ D ）的逻辑结构不同。

A）线性表 B）栈C）队列 D）树8、下列序列中，执行第一趟快速排序后得到的序列是（ A ）。

A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]9、（ C ）在进行插入操作时，常产生假溢出现象。

1、在网页制作中，我们经常用下列____办法进行页面布局。

A、文字B、表格C、表单D、图片2、Internet上，访问Web信息时用的工具是浏览器。

下列____就是目前常用的Web浏览器之一。

A、Internet ExplorerB、Outlook ExpressC、YahooD、FrontPage3、在计算机网络中，表征数据传输可靠性的指标是____。

A、误码率B、频带利用率C、信道容量D、传输速率4、在Windows操作系统中所采用的目录结构为____。

A、树型B、星型C、环型D、网络型5、目前，同学们使用的计算机属于____。

A、微型机B、小型机C、中型机D、巨型机6、中央处理器中主要包括____A、内存和计算器B、控制器和运算器C、只读存储器和随机存储器D、内存储器、控制器和运算器7、在计算机网络上必须做到____A、在Internet上要随意发表各种言论，言无不尽B、要学会寻找和进入人家的资料档案库C、要学会如何利用有价值的信息源来学习和发展自己D、要帮助其他同学，让自己买来的软件安装到朋友的机器上用8、在Internet中，用户通过FTP可以____。

A、发送和接收电子邮件B、上载和下载文件C、浏览远程计算机上的资源D、进行远程登录9、利用计算机来模拟人类的某些思维活动，如医疗诊断、定理证明等，这一应用属于A、数值计算B、自动控制C、人工智能D、辅助教育10、利用计算机将文字、声音、图形、图像和视频等多种媒体有机结合起来进行处理的技术称为____。

A、数字技术B、多媒体技术C、网络技术D、通信技术11、在对Word文档进行编辑时，如果操作错误，则____。

A、无法纠正B、只能手工修改C、单击’自动更正’D、单击*撒消’12、新建文档时，Word默认的字体和字号分别是____。

A、黑体、3号B、楷体、4号C、宋体、5号D、仿宋、6号13、com、cn，其中用户名是____。

A、JndhsgB、Fm365C、Fm14、IP地址是一串难以记忆的数字，人们用域名来代替它，完成IP地址和域名之间转换工作的是____服务器。

1、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。

int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数{if(bt==null || k<1) return(0);BiTree p=bt,Q[]; //Q是队列，元素是二叉树结点指针,容量足够大int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针，level 是二叉树的层数while(front<=rear){p=Q[++front];if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点if(p->lchild) Q[++rear]=p->lchild; //左子女入队if(p->rchild) Q[++rear]=p->rchild; //右子女入队if(front==last) {level++; //二叉树同层最右结点已处理,层数增1last=rear; } //last移到指向下层最右一元素if(level>k) return (leaf); //层数大于k 后退出运行}//while }//结束LeafKLevel2、有一个带头结点的单链表，每个结点包括两个域，一个是整型域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;}3、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。

1、浏览Web网站必须使用浏览器，目前常用的浏览器是____。

A、HotmailB、Outlook ExpressC、Inter ExchangD、Internet Explorer2、计算机的硬件系统是由____组成A、CPU、控制器、存储器、输入设备和输出设备B、运算器、控制器、存储器、输入设备和输出设备C、运算器、存储器、输入设备和输出设备D、CPU、运算器、存储器、输入设备和输出设备3、网址字符的开头的“http”表示____。

A、高级程序设计语言B、域名C、超文本传输协议D、网址4、计算机的主存储器指的是____。

A、ROM和RAMB、硬盘和软盘C、硬盘和光盘D、光盘和软盘5、计算机正常关机后____中的信息不会消失。

A、ROMB、RAMC、CACHED、CPU6、计算机网络在应用上的两种主要类型分别是局域网和____。

A、广域网B、局部网C、全球网D、互联网7、记录在光盘、硬盘、软件中的数据属于____。

A、模拟信息B、数字信息C、仿真信息D、广播信息8、WEB上的信息是由什么语言来组织的____。

A、CB、BASICC、JAVAD、HTML9、画图中，选择编辑→复制菜单命令，选定的对象将被复制到____中。

A、我的文档B、桌面C、剪贴板D、其它的图画10、想访问最近曾经访问过的网页用哪个按钮____。

A、搜索B、收藏C、历史D、刷新11、存储器的最小存储单元是字节（即B），而容量常用KB表示，例如4KB表示存储单元有____。

A、4000个字B、4000个字节C、4096个字D、4096个字节12、下面列出的计算机病毒传播途径，不正确的说法是____。

A、使用来路不明的软件B、通过借用他人的软盘C、通过非法的软件拷贝D、通过把多张软盘叠放在一起13、发送一个新的电子邮件之前，除了写好信内容，填写信的主题以外，还必须____。

A、填写收信人的E-mail地址B、填写E-mail到达所经过的路径C、填写邮件的编号D、填写发信人的电话号码14、计算机的硬盘属于____。

1、串的逻辑结构与（ D ）的逻辑结构不同。

A）线性表 B）栈C）队列 D）树2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ D ）存储方式最节省时间。

A）顺序表B）双链表C）带头结点的双循环链表 D）单循环链表3、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a??11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。

A）13 B）33 C）18 D）404、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ D ）存储方式最节省时间。

A）顺序表B）双链表C）带头结点的双循环链表 D）单循环链表5、在数据结构中，从逻辑上可以把数据结构分为（ C ）。

A）动态结构和静态结构 B）紧凑结构和非紧凑结构C）线性结构和非线性结构 D）内部结构和外部结构6、线性表的链接实现有利于（ A ）运算。

A）插入 B）读元素C）查找 D）定位7、串的逻辑结构与（ D ）的逻辑结构不同。

A）线性表 B）栈C）队列 D）树8、串的逻辑结构与（ D ）的逻辑结构不同。

A）线性表 B）栈C）队列 D）树9、以下属于顺序存储结构优点的是（ A ）。

A) 存储密度大B) 插入运算方便C）删除运算方便D）可方便地用于各种逻辑结构的存储表示10、与无向图相关的术语有（ C ）。

A）强连通图 B）入度C）路径 D）弧11、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ C ）。

A）顺序表示法 B）单字符为结点的单链表表示法C）等量分块表示法 D）不等量分块表示法12、n个顶点的强连通图至少有（ A ）条边。

A）n B）n+1 C）n-1 D）n(n-1)。

1、数据库概念设计的过程中，视图设计一般有三种设计次序，以下各项中不对的是(D)A. 自顶向下B. 由底向上C. 由内向外D. 由整体到局部2、设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为(B) 注：利用公式n=n0+n1+n2、n0=n2+1和完全二叉数的特点可求出A. 349B. 350C. 255D. 3513、在结构化方法中，软件功能分解属于下列软件开发中的阶段是(C) 注：总体设计也就是概要设计A. 详细设计B. 需求分析C. 总体设计D. 编程调试4、数据的存储结构是指(B)A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据5、下面概念中，不属于面向对象方法的是 (D)A. 对象B. 继承C. 类D. 过程调用6、检查软件产品是否符合需求定义的过程称为(A)A. 确认测试B. 集成测试C. 验证测试D. 验收测试7、对建立良好的程序设计风格，下面描述正确的是(A)A. 程序应简单、清晰、可读性好B. 符号名的命名要符合语法C. 充分考虑程序的执行效率D. 程序的注释可有可无8、设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为(B) 注：利用公式n=n0+n1+n2、n0=n2+1和完全二叉数的特点可求出A. 349B. 350C. 255D. 3519、下列关于队列的叙述中正确的是(C)A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表10、算法的空间复杂度是指(D)A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 算法执行过程中所需要的存储空间11、关系数据库管理系统能实现的专门关系运算包括(B)A. 排序、索引、统计B. 选择、投影、连接C. 关联、更新、排序D. 显示、打印、制表12、信息隐蔽的概念与下述哪一种概念直接相关(B)A.软件结构定义B. 模块独立性C. 模块类型划分D. 模拟耦合度13、将E-R图转换到关系模式时，实体与联系都可以表示成(B)A. 属性B. 关系C. 键D. 域14、下面不属于软件工程的3个要素的是(D)A. 工具B. 过程C. 方法D. 环境15、在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送(D)A. 调用语句B. 命令C. 口令D. 消息。

1、设有一个数组中存放了一个无序的关键序列K1、K2、…、Kn。

现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。

51. 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。

设此组记录存放于数组r[l..h]中。

若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。

请编写出算法并简要说明算法思想。

2、假设以I和O分别表示入栈和出栈操作。

栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

（15分）（1）下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。

若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

3、二部图（bipartite graph） G=（V，E）是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。

（1）．请各举一个结点个数为5的二部图和非二部图的例子。

（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。

设G用二维数组A来表示，大小为n*n（n为结点个数）。

请在程序中加必要的注释。

若有必要可直接利用堆栈或队列操作。

【4、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。

所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。

void Translation（float *matrix，int n）//本算法对n×n的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。