数据结构与算法设计

1、北京理工大学现代远程教育学院2004-2005学年第一学期数据结构和算法设计试卷班级：姓名：学号：成绩：一、选择(15 分 )1如果类 A 中定义了一个成员函数形式为void put(int)；以 A 类为基类的派生类中重载此函数，以下（）不对。A 、void put(float)；B、void put(int)；C、int put(int)；D 、 void put(char*);2如果以某个类的成员函数方式重载了运算符 ” /号”， a/b表达式对应的函数调用形式为（）A 、a. operator/(b);B、operator/(a，b);C、b. operator/(a);D 、 ope

2、rator/(b，a);3公有派生类的外部对象允许访问其基类（private 、 protected 、public各域）中的 ()域成员。A 、privateB 、publicC、 protectedD 、 protected 和 public4Base为基类， First 为其派生类， Last为 First 的派生类，如果定义Baseobj1 ，*P1； First obj2，*p2；Lastobj3 ，*p3；以下语句非法的为（）；A 、p1=&obj2;B 、p2=&obj3;C、 p3=&obj2;D、p2=&obj2;5如果类 A 中定义了一个成员

3、函数为虚函数，其函数原型为void put(int)；以 A类为基类的派生类 B 中， ( ) 函数具有虚特性。A 、void put(float)； B、int put( )；C、 void put(int)； D 、void put(char*);6高度为 K 的二叉树至多有（）个结点（ K>= -1 ）A 、 2 k+1 -1B 、 2 k+1+1C、 2 k -1D 、2 k +17 线性链表是通过何种方式表示元素之间的关系()A 、后继元素地址B 、元素的存储顺序C、左、右孩子地址1D 、元素的相对存储位置8 数据结构在计算机中的表示是指()A 、数据的存储结构B 、数据结构C

4、、数据的逻辑结构D 、数据元素9 用线性链表存储线性表时，要求存储空间()A 、必须是连续的B 、连续不连续都可以C、部分元素的存储空间必须是连续的D 、必须是不连续的.10 若某线性表最常用的操作是在表头或表尾结点之后插入一个结点或删除一个结点，则采用哪一种存储结构算法的时间效率最高。 ( )A、 单链表B 、 给出表头指针的单循环链表C、双向链表D 、给出表尾指针的循环链表11一个栈的输入序列为 m ， n ，p ，q ，则下列序列中不可能的输出序列是 ( ) 。A 、 npqmB 、 mpnqC、 qnpmD 、 mqpn12查找效率最高的二叉排序树是 ()A 、 所有结点右子树或左子树

5、都为空的二叉排序树；B 、 平衡二叉树C、 没有左子树的二叉排序树13在线性表顺序存储结构下，在第i 个元素之前插入新元素需要 ( )A 、 移动元素B 、 修改头指针C、 队头指针D 、 申请新的结点空间14对于经常要存取元素的应用，线性表应采用 ( ) 存储结构。A 、 顺序存储结构2B 、链式存储结构C、线性链表D 、栈15 二叉排序树的（）遍历结果是一个有序序列。A、中序B、后序C、前序D 、层次二、 指出每个程序中的出错行号，简要说明原因并修改（25 分）。1 #include <iostream.h>class myint x,y;public:my(int x0=10

6、,int y0) x=x0, y=y0;void set(int x,int y)my:x=x,my:y=y;main( )my *ptr ,data(10,20);ptr=new my5;ptr->set(3,4);cout<<ptr->x<<endl;2 class Fruitprotected:int num;public:Fruit( )num=0;Fruit(int n=10)num=n;virtual int show( )=0;class Apple:public Fruitpublic:Apple(int m=10):Fruit(m) voi

7、d show()cout<<num<<"n"void main( )3Fruitfru , *ptr;Applex;ptr=&x;ptr->show();3 class xint a;public:int set(int a0)a=a0;int get()return a;void outputa()cout<<a<<endl; class y:xint b;public:void setb()b=a*a;void outputb()outputa();cout<<b<<endl;void

8、 main()x*ptr;yy1;y1.setb();ptr=&y1;ptr->outputb();三、简答题 (20分)1 已知一棵度为k 的树中有 n 1 个度为 1 的结点， n 2 个度为 2 的结点， . ，n k个度为 k 的结点，问该树中有多少个叶子结点？2 请画出图示森林对应的二叉树。43 假设一棵树的后序序列为DHIEBFKLJGCA和中序序列为DBHEIAFCKJLG(1) 请画出该树(2) 至少给定哪几种遍历结果可以唯一地确定一棵二叉树？(3) 请写出其前序遍历的结果。4 假设输入序列为 9 ，17 ，5 ，4 ，23 ，8 ，6 ，54 ， 22 ，请构造

9、出二叉排序树，并给出此树删除 23 后的形状。5 试分别找出满足以下条件的所有二叉树(1 ）二叉树的前序序列与中序序列相同(2 ）二叉树的后序序列与中序序列相同(3) 二叉树的后序序列与前序序列相同四、程序填空题（ 16 分）1 假设称正读和反读都相同的字符序列为回文，例如， abba和 abcba是回文，而abcde和ababab则不是回文， 下列程序首先实现了一个简单的链栈， 然后利用此栈，判别输入的字符串是否为回文，请将程序补充完整。#include <string.h>#include <iostream.h>#include <assert.h>c

10、lass LinkStack;class StackNodechar data;StackNode *next;friend class LinkStack;class LinkStackprotected :5StackNode * top;/ 栈顶指针public:（ 1 ）/ 必要的构造函数声明LinkStack()Clear();void Clear();void Push(char& x);bool Pop(char&x);bool IsEmpty()（ 2 ）;/清空当前栈中元素void LinkStack:Clear()char x;while(Pop(x);/进

11、栈函数，将 x 压入链栈中void LinkStack:Push(char& x)StackNode *p;if(top)p=new StackNode;assert(p);(3)(4)(5)elsetop=new StackNode;assert(top);top->data=x;top->next=NULL;/ 出栈函数，将栈顶元素弹出，并将栈顶结点的数据元素值赋给 x bool LinkStack:Pop(char&x)StackNode *p;6if(!IsEmpty()/ 若栈中有元素x=top->data;(6)(7)(8)return true;

12、return false;void main()LinkStack stack;char s20,s120,c;cout<<"Please input string:"cin>>s;for(int i=0;(c=si)!=0;i+)(9)i=0;while( (10)(11)s1i=0;if(strcmp(s1,s)=0)cout<<"Yesn"elsecout<<"non"2 以下程序定义了一个简单顺序队列类，请将其补充完整。#include "iostream.h"

13、;#include "assert.h"class SeqQueneprotected:int head;/ 队头指针int tail;/ 队尾指针int *elements;/存放队列元素的数组int maxsize;/ 队列最大可容纳元素个数 public:SeqQuene(int i=10)head=tail=0;7maxsize=i<10?10:i;elements=new intmaxsize;assert(elements!=0);SeqQuene()delete elements;bool PushTail(int&);/ 将新元素插入在队尾bo

14、ol PopFront(int&);/ 从队头取一个元素;/ 将新元素插入在队尾bool SeqQuene:PushTail(int& x)if(12)(13)(14)return true;elsecout<<"Error1"return false;/ 从队头取一个元素bool SeqQuene:PopFront(int &x)if( head!=tail)(15)(16)return true;elsecout<<"Error2"return false;五、请给出程序的运行结果（24 分）1 #in

15、clude <iostream.h>class basepublic:base() cout<<"base!n"base()cout<<"base!n"8class base2public:base2()cout<<"base2!n"base2()cout<<"base2!n"class level1:public base2,virtual public base public:level1()cout<<"level1!n&quo

16、t;level1()cout<<"level1!n"class level2:public base2,virtual public base public:level2()cout<<"level2!n"level2()cout<<"level2!n"class toplevel:public level1,virtual public level2 public:toplevel() cout<<"toplevel!n"toplevel()cout<<

17、"toplevel!n"main()toplevel topobj;return 1;2 #include <iostream.h>class xprotected:int a;public:x()a=10;class x1:virtual public xpublic :x1()a=6;cout<<a<<"n"class x2:virtual public xpublic :9x2()a=20;cout<<a<<"n"class y:x2,x1public :y()cout

18、<<y:a<<" "<<x1:a<<" "<<x2:a<< "n"main()y obj; return 1;3 #include <iostream.h>#include <stdlib.h>class counterstatic int count;int objnum;public:counter()count+;objnum=count;counter()count-;objnum=count;void show()cout<

19、<"obj"<<objnum<<" "cout<<"count="<<count<<"n"int counter:count=0;void main()counter obj1,*p;p=new counter;p->show();obj1.show();delete p;obj1.show();4 #include <iostream.h>#include <assert.h>class X10public:X(int

20、 i=10) point=-1; maxsize=i>10?i:10; elements=new intmaxsize;assert(elements!=0);X()delete elements;void Fun1(int x);void Fun2(int&x);bool Fun3()return point=maxsize-1;bool Fun4()return point=-1;protected:int point;int *elements;int maxsize;void X:Fun1(int x ) assert(!Fun3();elements+point=x;v

21、oid X:Fun2(int& x)assert(!(point=-1);x=elementspoint-;void main() X s(2);int a=12345,b; int temp; while(a) temp=a%3; a=a/3;s.Fun1(temp);while(!s.Fun4() s.Fun2(temp); cout<<temp<<" "115 #include <iostream.h>int& f(int m) returnm*=2;int& g(int &n,int m) returnn+=m; intr( int &q)return q+;void main( )int a=1,b=2,c=3,d=4;a+=f(g(a,b);b+=g(c,f(b);c+=r(g(d,c);cout<<"a="<<a<<"n"<<&quo