北京理工大学现代远程教育学院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、operator/(b,a);
3.公有派生类的外部对象允许访问其基类(private、protected、public各域)中的( ) 域成员。
A、private
B、public
C、protected
D、protected和public 4.Base为基类,First为其派生类,Last为First的派生类,如果定义
Base obj1,*P1;First obj2,*p2;Last obj3,*p3;以下语句非法的为();
A、p1=&obj2;
B、p2=&obj3;
C、p3=&obj2;
D、p2=&obj2;
5.如果类A中定义了一个成员函数为虚函数,其函数原型为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、2k+1-1
B、2k+1+1
C、2k-1
D、2k+1
7.线性链表是通过何种方式表示元素之间的关系( )
A、后继元素地址
B、元素的存储顺序
C、左、右孩子地址
D、元素的相对存储位置
8.数据结构在计算机中的表示是指( )
A、数据的存储结构
B、数据结构
C、数据的逻辑结构
D、数据元素
9.用线性链表存储线性表时,要求存储空间( )
A、必须是连续的
B、连续不连续都可以
C、部分元素的存储空间必须是连续的
D、必须是不连续的 .
10.若某线性表最常用的操作是在表头或表尾结点之后插入一个结点或删除一个结点,则采用哪一种存储结构算法的时间效率最高。( )
A、单链表
B、给出表头指针的单循环链表
C、双向链表
D、给出表尾指针的循环链表
11.一个栈的输入序列为m,n,p,q,则下列序列中不可能的输出序列是( )。
A、n p q m
B、m p n q
C、q n p m
D、m q p n
12.查找效率最高的二叉排序树是( )
A、所有结点右子树或左子树都为空的二叉排序树;
B、平衡二叉树
C、没有左子树的二叉排序树
13.在线性表顺序存储结构下,在第i个元素之前插入新元素需要( )
A、移动元素
B、修改头指针
C、队头指针
D、申请新的结点空间
14.对于经常要存取元素的应用,线性表应采用( )存储结构。
A、顺序存储结构
B、链式存储结构
C、线性链表
D、栈
15.二叉排序树的()遍历结果是一个有序序列。
A、中序
B、后序
C、前序
D、层次
二、指出每个程序中的出错行号,简要说明原因并修改(25分)。
1.#include
class my{
int x,y;
public:
①my(int x0=10,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 my[5];
⑤ptr->set(3,4);
⑥cout< } 2.class Fruit{ protected: int num; public: ①Fruit( ){num=0;} ②Fruit(int n=10){num=n;} ③virtual int show( )=0; }; ④class Apple:public Fruit{ public: ⑤Apple(int m=10):Fruit(m){ } ⑥void show(){cout< }; void main( ) { ⑦Fruit fru , *ptr; ⑧Apple x; ⑨ptr=&x; ⑩ptr->show(); } 3.class x{ int a; public: int set(int a0){a=a0;} int get() {return a;} void outputa() {cout< }; ①class y:x{ ②int b; public: ③void setb(){b=a*a;} ④void outputb() ⑤{outputa();cout< }; void main( ) { ⑥x *ptr; ⑦y y1; ⑧y1.setb(); ⑨ptr=&y1; ⑩ptr->outputb(); } 三、简答题(20分) 1.已知一棵度为k的树中有n1个度为1的结点,n2个度为2的结点,...,n k 个度为k的结点,问该树中有多少个叶子结点? 2.请画出图示森林对应的二叉树。 3.假设一棵树的后序序列为DHIEBFKLJGCA和中序序列为DBHEIAFCKJLG (1) 请画出该树 (2) 至少给定哪几种遍历结果可以唯一地确定一棵二叉树? (3) 请写出其前序遍历的结果。 4.假设输入序列为{9,17,5,4,23,8,6,54,22},请构造出二叉排序树,并给出此树删除23后的形状。 5.试分别找出满足以下条件的所有二叉树 (1)二叉树的前序序列与中序序列相同 (2)二叉树的后序序列与中序序列相同 (3) 二叉树的后序序列与前序序列相同 四、程序填空题(16分) 1.假设称正读和反读都相同的字符序列为回文,例如,’abba’和’abcba’是回文,而’abcde’和’ababab’则不是回文,下列程序首先实现了一个简单的链栈,然后利用此栈,判别输入的字符串是否为回文,请将程序补充完整。 #include #include #include class LinkStack; class StackNode{ char data; StackNode *next; friend class LinkStack; }; class LinkStack{ protected : StackNode * 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)); } //进栈函数,将x 压入链栈中 void LinkStack::Push(char& x) { StackNode *p; if(top) { p=new StackNode; assert(p); (3) (4) (5) } else { top=new StackNode; assert(top); top->data=x; top->next=NULL; } } //出栈函数,将栈顶元素弹出,并将栈顶结点的数据元素值赋给x bool LinkStack::Pop(char&x) { StackNode *p; if(!IsEmpty()) //若栈中有元素 { x=top->data; (6) (7) (8) return true; } return false; } void main() { LinkStack stack; char s[20],s1[20],c; cout<<"Please input string:"; cin>>s; for(int i=0;(c=s[i])!=0;i++) (9) i=0; while((10) ) (11) s1[i]=0; if(strcmp(s1,s)==0) cout<<"Yes\n"; else cout<<"no\n"; } 2.以下程序定义了一个简单顺序队列类,请将其补充完整。#include "iostream.h" #include "assert.h" class SeqQuene{ protected: int head; //队头指针 int tail; //队尾指针 int *elements;//存放队列元素的数组 int maxsize;//队列最大可容纳元素个数 public: SeqQuene(int i=10) { head=tail=0; maxsize=i<10?10:i; elements=new int[maxsize]; assert(elements!=0); } ~SeqQuene() {delete elements;} bool PushTail(int&); //将新元素插入在队尾bool PopFront(int&); //从队头取一个元素}; //将新元素插入在队尾 bool SeqQuene::PushTail(int& x) { if( (12) ) { (13) (14) return true; } else {cout<<"Error1";return false;} } //从队头取一个元素 bool SeqQuene::PopFront(int &x) { if( head!=tail) { (15) (16) return true; } else {cout<<"Error2";return false;} } 五、请给出程序的运行结果(24分) 1. #include class base{ public: base() {cout<<"base!\n";} ~base() {cout<<"~base!\n";} }; class base2{ public: base2() {cout<<"base2!\n";} ~base2() {cout<<"~base2!\n";} }; class level1:public base2,virtual public base{ public: level1() {cout<<"level1!\n";} ~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<<"~toplevel!\n";} }; main() { toplevel topobj; return 1; } 2. #include class x{ protected: int a; public: x(){a=10;} }; class x1:virtual public x{ public : x1() {a=6;cout< }; class x2:virtual public x{ public : {a=20;cout< }; class y:x2,x1{ public : y() {cout< main() { y obj; return 1; } 3. #include #include class counter{ static int count; int objnum; public: counter(){count++;objnum=count;} ~counter(){count--;objnum=count;} void show() {cout<<"obj"< cout<<"count="< }; int counter::count=0; void main() { counter obj1,*p; p=new counter; p->show(); obj1.show(); delete p; obj1.show(); } 4. #include #include class X{ X(int i=10) { point=-1; maxsize=i>10?i:10; elements=new int[maxsize]; 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; } void X::Fun2(int& x) { assert(!(point==-1)) ; x=elements[point--]; } 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< } } 5. #include int& f(int m) { return m*=2;} int& g(int &n,int m) { return n+=m; } int r( 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="< cout<<"c="< } 6. #include class x{ protected: int a; public: x(int z=100) {a=z;cout<<"class x\n";} void print( ) {cout<<"a="< }; class y:public x{ int b; public: y(){b=50;} y (int z1,int z2=20):x(z1){b=z2;cout<<"class y\n";} void print()