1、华北计算技术研究所2006年专业课试题参考答案一、 填空题（15分）1. 数据结构是相互之间存在一种或多种特定关系的 数据元素 的集合。通常有下列四种基本结构： 集合 、 线性结构 、 树状结构 和 图状结构（或网状结构） 。 2. 在顺序表中插入或删除一个元素，需要平均移动 表中一半（或n/2个） 元素，具体移动的元素个数与表长和该元素在表中的位置有关。3. 0 个字符的串称为空串，它的长度为 0 。4. 矩阵压缩存储的基本思想是： 值相同 的多个元素只分配一个存储空间， 零元素 不分配空间。5. 深度为k的二叉树至多有 2k-1 个结点，至少有 k 个结点。6. 图的深度优先搜索遍历类似于
2、树的 先根 遍历；图的广度优先搜索遍历类似于树的 按层次 遍历。二、 选择题（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
3、和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. 完全二叉树不一定是满二叉树，但满二叉树一定是完全
4、二叉树。对四、 根据下列要求分别编写算法。（20分）1. 设计算法，判断一个算术表达式的圆括号是否正确配对。参考答案：#include #include “stack.h”Int PairBracket(char *S)/检查表达式中括号是否配对int i;SeqStack T;/定义一个栈InitStack (&T);for(i=0;idata=sa.elem1;T=ptr1;for(i=2;idata=sa.elemi;j=i/2;if(i-j*2) ptrj-rchild=ptri; /I是j的右孩子else ptrj-lchild=ptri;/I是j的左孩子return OK;五、 回
5、答问题。（20分）1. 设有上三角矩阵(aij)nxn，将其上三角元素逐行存于数组Bm中（m充分大），使得Bk=aij且k=f1(i)+f2(j)+c。试推导出函数f1，f2和常数c（要求f1和f2中不含常数项）。参考答案：则得：2. 写出下图中所示的二叉树的先序序列、中序序列和后序序列。124573689 参考答案：前序：124735689中序：472153869后序：742589631六、 下图是一个有向图，其中每条弧段上的数字表示该弧段的权值。利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。（15分） bgeed469310f5815a212
6、c4参考答案：终点DistbcdefgSK=115(a,b)2(a,c)12(a,d)a,cK=215(a,b)12(a,d)10(a,c,e)6(a,c,f)a,c,fK=315(a,b)11(a,c,f,d)10(a,c,e)16(a,c,f,g)a,c,f,eK=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,gK=615(a,b)a,c,f,e,d,g,b故：a到各点最短路径分别为：bcdefg1521110614七、 假设按下述递归方法进行顺序表的查找：若表长=10，则进行顺序查找，否则
7、进行折半查找。试画出对表长n=50的顺序表进行上述查找时，描述该查找的判定树，并求出在等概率情况下查找成功的平均查找长度。（20分）参考答案：其等概率查找时查找成功的平均查找长度为：八、 将下列C+程序的类定义和主函数分离，改成多文件结构。主函数使用类的方式采取包含类定义头文件的方法。并写出运行结果。（15分）#include class Catpublic:int GetAge( );void SetAge(int age);void Meow( ); /喵喵叫protected:int itsAge;int Cat:GetAge( )returen itsAge;void Cat:SetA
8、ge(int age)itsAge=age;void Cat:Meow( )cout”Meow.n”;void main( )Cat frisky;Frisky.SetAge(5);Frisky.Meow( );Cout”frisky is a cat who is “frisky.GetAge( )”years old.n”;frisky.Meow( );参考答案：/头文件cat.h#include class Catpublic:int GetAge( );void SetAge(int age);void Meow( ); /喵喵叫protected:int itsAge;int Cat
9、:GetAge( )returen itsAge;void Cat:SetAge(int age)itsAge=age;void Cat:Meow( )cout”Meow.n”;/主程序#include #include “cat.h”void main( )Cat frisky;Frisky.SetAge(5);Frisky.Meow( );Cout”frisky is a cat who is “frisky.GetAge( )”years old.n”;frisky.Meow( );运行结果：Meow.Frisky is a cat who is 5 years old.Meow.九、
10、用C+语言编写应用程序。定义一个Document类，包含成员变量name。从Document类派生出Book类，增加PageCount变量。程序运行输出为：Name of Book: Book1。（15分） 参考答案：#include #include class Documentpublic:Document() ;Document(char *name);char *Name; /Document name.void PrintNameOf(); /Print name.;Document:Document(char *name)Name=new charstrlen(name)+1;St
11、rcpy(Name,name);void Document:PrintNameOf()coutNameendl;class Book:public Documentpublic:Book(char *name,long pagecount);void PrintNameOf();private:long PageCount;Book:Book(char *name,long pagecount):Document(name)PageCount=pagecount;void Book:PrintNameOf()cout”Name of book:”;Document:PrintNameOf();void main()Document a(“Document”);Book b(“Book1”,100);b.printNameof();
