2006年华北计算技术研究所专业课试题及答案

华北计算技术研究所2006年专业课试题参考答案一、填空题（15分）1.数据结构是相互之间存在一种或多种特定关系的数据元素的集合。通常有下列四种基本结构：集合、线性结构、树状结构和图状结构（或网状结构）。2.在顺序表中插入或删除一个元素，需要平均移动表中一半（或n/2个）元素，具体移动的元素个数与表长和该元素在表中的位置有关。3.0个字符的串称为空串，它的长度为0。4.矩阵压缩存储的基本思想是：值相同的多个元素只分配一个存储空间，零元素不分配空间。5.深度为k的二叉树至多有2k-1个结点，至少有k个结点。6.图的深度优先搜索遍历类似于树的先根遍历；图的广度优先搜索遍历类似于树的按层次遍历。二、选择题（20分）1.时间复杂性最好，即执行时间最短的是：B（A）O(n)（B）O(log2n)（C）O(nlog2n)（D）O(n2)2.具有6个顶点的无向图至少有D条边才能确保是一个连通图。（A）15（B）7（C）6（D）53.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是：D（A）希尔排序（B）起泡排序（C）插入排序（D）选择排序4.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为：C。（A）1和5（B）2和4（C）4和2（D）5和15.设栈的长度为3，入栈序列为A、B、C、D、E、F，不可能产生的出栈序列是：D。（A）A，B，C，D，E，F（B）B，A，D，C，F，E（C）C，B，A，F，E，D（D）D，C，B，A，F，E三、判断题。（10分）请判断下列说法的对错。1.数据元素是数据的最小单位。错2.串的三种存储表示方法为定长顺序存储表示、堆分配存储表示和块链存储表示。对3.一个稀疏矩阵的转置矩阵仍然是稀疏矩阵。对4.树状结构中，度为0的结点称为树根。错5.完全二叉树不一定是满二叉树，但满二叉树一定是完全二叉树。对四、根据下列要求分别编写算法。（20分）1.设计算法，判断一个算术表达式的圆括号是否正确配对。参考答案：#includestring.h#include“stack.h”IntPairBracket(char*S){//检查表达式中括号是否配对inti;SeqStackT;//定义一个栈InitStack(&T);for(i=0;istrlen(S);i++){if(S[i]==’(‘)Push(&T,S[i]);//遇‘(’时进栈if(S[i]==’)’)Pop(&T);//遇‘)’时出栈}Return!EmptyStack(&T);//由栈空否返回正确配对与否}2.已知一棵完全二叉树存于顺序表sa中，sa.elem[sa.last]中存放各结点的数据元素。编写算法由此顺序存储结构建立该二叉树的二叉链表。参考答案：StatusCreateBitree_SqList(Bitree&T,SpListsa)//根据顺序存储结构建立二叉链表{Bitreeptr[sa.last+1];//该数组存储与sa中各结点对应的树指针if(!sa.last){T=NULL;return;}ptr[1]=(BTNode*)malloc(sizeof(BTNode));ptr[1]-data=sa.elem[1];T=ptr[1];for(i=2;i=sa.last;i++){if(!sa.elem[i]returnERROR;ptr[i]=(BTNode*)malloc(sizeof(BTNode));ptr[i]-data=sa.elem[i];j=i/2;if(i-j*2)ptr[j]-rchild=ptr[i];//I是j的右孩子elseptr[j]-lchild=ptr[i];//I是j的左孩子}returnOK;}五、回答问题。（20分）1.设有上三角矩阵(aij)nxn，将其上三角元素逐行存于数组B[m]中（m充分大），使得B[k]=aij且k=f1(i)+f2(j)+c。试推导出函数f1，f2和常数c（要求f1和f2中不含常数项）。参考答案：)(,12)1()(jiiijnnik则得：2121)21()(iinifjjf)(2)1(nc2.写出下图中所示的二叉树的先序序列、中序序列和后序序列。参考答案：前序：124735689中序：472153869后序：742589631124573689六、下图是一个有向图，其中每条弧段上的数字表示该弧段的权值。利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。（15分）参考答案：终点DistbcdefgSK=115(a,b)2(a,c)12(a,d){a,c}K=215(a,b)12(a,d)10(a,c,e)6(a,c,f){a,c,f}K=315(a,b)11(a,c,f,d)10(a,c,e)16(a,c,f,g){a,c,f,e}K=415(a,b)11(a,c,f,d)16(a,c,f,g){a,c,f,e,d}K=515(a,b)14(a,c,f,d,g){a,c,f,e,d,g}K=615(a,b){a,c,f,e,d,g,b}故：a到各点最短路径分别为：bcdefg1521110614七、假设按下述递归方法进行顺序表的查找：若表长=10，则进行顺序查找，否则进行折半查找。试画出对表长n=50的顺序表进行上述查找时，描述该查找的判定树，并求出在等概率情况下查找成功的平均查找长度。（20分）bgeed469310f5815a212c4参考答案：25126…125…781118…131417…19202331…262730…32333644…394043…454649382437其等概率查找时查找成功的平均查找长度为：68.5)398)87654(432211(501succASL八、将下列C++程序的类定义和主函数分离，改成多文件结构。主函数使用类的方式采取包含类定义头文件的方法。并写出运行结果。（15分）#includeiostream.hclassCat{public:intGetAge();voidSetAge(intage);voidMeow();//喵喵叫protected:intitsAge;};intCat::GetAge(){returenitsAge;}voidCat::SetAge(intage){itsAge=age;}voidCat::Meow(){cout”Meow.\n”;}voidmain(){Catfrisky;Frisky.SetAge(5);Frisky.Meow();Cout”friskyisacatwhois“frisky.GetAge()”yearsold.\n”;frisky.Meow();}参考答案：//头文件cat.h#includeiostream.hclassCat{public:intGetAge();voidSetAge(intage);voidMeow();//喵喵叫protected:intitsAge;};intCat::GetAge(){returenitsAge;}voidCat::SetAge(intage){itsAge=age;}voidCat::Meow(){cout”Meow.\n”;}//主程序#includeiostream.h#include“cat.h”voidmain(){Catfrisky;Frisky.SetAge(5);Frisky.Meow();Cout”friskyisacatwhois“frisky.GetAge()”yearsold.\n”;frisky.Meow();}运行结果：Meow.Friskyisacatwhois5yearsold.Meow.九、用C++语言编写应用程序。定义一个Document类，包含成员变量name。从Document类派生出Book类，增加PageCount变量。程序运行输出为：NameofBook:Book1。（15分）参考答案：#includeiostream.h#includestring.hclassDocument{public:Document(){};Document(char*name);char*Name;//Documentname.voidPrintNameOf();//Printname.};Document::Document(char*name){Name=newchar[strlen(name)+1];Strcpy(Name,name);};voidDocument::PrintNameOf(){coutNameendl;}classBook:publicDocument{public:Book(char*name,longpagecount);voidPrintNameOf();private:longPageCount;};Book::Book(char*name,longpagecount):Document(name){PageCount=pagecount;}voidBook:PrintNameOf(){cout”Nameofbook:”;Document::PrintNameOf();}voidmain(){Documenta(“Document”);Bookb(“Book1”,100);b.printNameof();}