西华大学2008-2009第二学期数据结构期末试题A

Anhui University OF ArchitectureSemester 2 ,2008-2009 Final Examination(A)Subject Title: Object-Oriented ProgrammingPart One Fill in the blanks (3 ⨯10=30 marks)1.If int b[][3]={{1},{3,2},{6,5,4},{0}};then b[2][2]= 42.If int b []={1,2,3,4,5};then * b= 13.The main characteristics of OOP are encapsulation, inheritance and polymorphism4.Constructor\destructor\ \copy constructor, which one is not method in classfriend function5.Virtual base class can prevent data redundance(冗余) in derived class.6.Not all function have return type, for example: constructor7.Not all Operator can be changed through overloading. for example:.*、. 、-> 、:: .8.How many identifiers(标识符) are legal: 2 (idea\7person\s-d\private\Only123)9.Part Two Error Correction. Maybe there are several mistakes, please modify them (6⨯3=18 marks)1.#include <iostream.h>class A{A ( ){cout<<”hello” ;} // {A ( ){ public:cout<<”hello” ;}} // };int main(){A a;return 0;}2.#include <iostream>#include <string.h>Using name space;class Animal{private:int age;public: // public: Animal(){}Animal(int n){ age = n;}~Animal(){}};class Dog : public Animal{public:Dog(int m,string newname){ age = m;name= newname;}// Dog(int m,string newname): Animal(m){ name= newname;} ~Dog(){}private:string name;};void main(){ Dog a;Dog b(2,”huahua”);}3.#include <iostream > //#include <iostream > using namespace std;class point{public:virtual void m()=0; // virtual void m(){};point(){}}void main(){point A;}Part Three What is the output ( 10*3=30 )int * p1,a=5,b=20;p1=&a;cout<<a<<“ ”<<*p1<<endl;a=10;cout<<a<<“ ”<<*p1<<endl;*p1=15;cout<<a<<“ ”<<*p1<<endl;p1=&b;cout<<a<<“ ”<<*p1<<endl;2.class A {int a,b;public :A() { a=b=0; cout<<”use”<<endl;}A(int aa,int bb) {a=aa; b=bb;cout <<a<<“ ” <<b<<endl;}~ A(){cout<<a+b<<”end”;}};void main(){A x,y(2,3),z(4,5);}3.class BaseClass{public:BaseClass() { cout << "构造基类对象~BaseClass() { cout << "析构基类对象};class DerivedClass : public BaseClass{public:DerivedClass() {cout << "构造派生类对象!" << endl;}~DerivedClass() {cout << "析构派生类对象!" << endl;}};void main(){DerivedClass d;}Part Four Answer the following question (9 marks) When is the copy constructor called automatically?Solution:⏹When a class object is defined and initialized by an object of the same class⏹When a function returns a value of the class type⏹When an argument of the class type is plugged in for a call-by-value parameter Part Five programming ( 14 marks)Circle is a base class and Cylinder is inherited from it.They all have function getArea().Besides Cylinder have function getV olume to figure out Cylinder’s volume(体积) and print it, try to compile the programSolution:#include <iostream >using namespace std;const double pi =3.14;class Circle{public:Circle(int r) { r0=r;}float getr(){return r0;}double getArea(){return pi*r0*r0;}~Circle() { }private:int r0;};class Cylinder : public Circle{public:Cylinder(int r,int h): Circle(r){h1=h;}double getArea(){return 2*pi*getr()*h1;}double getV olume(){return Circle::getArea()*h1;}void V olumedisplay(){cout<<getV olume()<<endl;}~Cylinder(){}private:int h1;};void main(){Cylinder d(5,2);d.V olumedisplay();}。

数据结构期末考试试题(含答案)C.{100,98,85,77,80,60,82,40,20,10,66} 答：C。

10.在哈夫曼编码中，若有n个字符，其权值分别为w1，w2，…，wn，编码长度分别为l1，l2，…，ln，则哈夫曼编码的平均长度为a。

A.∑(wi/2li)B.∑(wi/li)C.∑(wi/2li-1)D.∑(wi/li-1)答：A。

2005-2006学年第二学期“数据结构”考试试题（A）要求：所有的题目的解答均写在答题纸上。

每张答题纸上需写清楚姓名、班号和学号，并在上面写上题目的序号。

一、单项选择题（每小题2分，共20分）1.数据的运算效率与采用何种存储结构有关。

因此，选项A是正确答案。

2.链表不具备的特点是可随机访问任一结点。

参见本节要点3.因此，选项A是正确答案。

3.在顺序表中删除一个元素的时间复杂度为O(n)。

因此，选项C是正确答案。

4.具有随机存取功能的线性表存储结构是顺序表。

因此，选项D是正确答案。

5.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是dceab。

因此，选项C是正确答案。

6.循环队列qu的队空条件是qu.rear==qu.front。

因此，选项D是正确答案。

7.两个串相等必有串长度相等且串中各位置字符均对应相等。

因此，选项B是正确答案。

8.用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是21,32,46,40,80,69,90,94.因此，选项C是正确答案。

9.以下序列不是堆（大根或小根）的是{100,98,85,77,80,60,82,40,20,10,66}。

因此，选项C是正确答案。

10.在哈夫曼编码中，若有n个字符，其权值分别为w1，w2，…，wn，编码长度分别为l1，l2，…，ln，则哈夫曼编码的平均长度为∑(wi/2li)。

因此，选项A是正确答案。

C。

{10.20.40.60.66.77.80.82.85.98.100}D。

数据结构真题2009年下半年(总分：124.98，做题时间：90分钟)一、{{B}}单项选择题{{/B}}(总题数：15，分数：30.00)1.按值可否分解，数据类型通常可分为两类，它们是 ( )（分数：2.00）A.静态类型和动态类型B.原子类型和表类型C.原子类型和结构类型√D.数组类型和指针类型解析：[解析] 按“值”是否可分解，可将数据类型划分为两类：原子类型，其值不可分解；结构类型，其值可分解为若干个成分。

2.对于三个函数f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008和h(n)=8888nlogn+3n2，下列陈述中不成立的是 ( )（分数：2.00）A.f(是O(g()B.g(是O(f()C.h(是O(nlog √D.h(是O(n2)解析：[解析] 当n充分大时，由题意可得：f(n)与n3是同阶的，g(n)与n3是同阶的，h(n)与n2是同阶的。

所以f(n)=O(g(n))，g(n)=O(f(n))，h(n)=O(n2)。

3.指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是( ) （分数：2.00）A.p—＞next=r; q—＞next=r—＞next; r—＞next=q; √B.p—＞next=r; r—＞next=q; q—＞next=r—＞next;C.r—＞next=q; q—＞next=r—＞next; p—＞next=r;D.r—＞next=q; p—＞next=r; q—＞next=r—＞next;解析：4.若进栈次序为a,b,e，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是 ( ) （分数：2.00）A.3B.5 √C.6D.7解析：5.假设以数组A[n]存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为 ( )（分数：2.00）A.rear==frontB.(front+1)%n==rearC.rear+1==frontD.(rear+1)%n==front √解析：[解析] 在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。

注意事项：1、下面关于串的叙述中，哪一个是不正确的？（ ）A ．串是字符的有限序列B ．空串是由空格构成的串C ．模式匹配是串的一种重要运算D ．串既可以采用顺序存储，也可以采用链式存储 2、设无向图的顶点个数为n ，则该图最多有（ ）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0 3、以下数据结构中，（ ）是非线性数据结构。

A ．树B ．字符串C ．队列D ．栈 4、下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。

B ．线性表采用顺序存储，便于进行插入和删除操作。

C ．线性表采用链接存储，不必占用一片连续的存储单元。

D ．线性表采用链接存储，便于插入和删除操作。

5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。

A ．(rear-front+m)%mB ．rear-front+1C ．(front-rear+m)%mD ．(rear-front)%m6、在单链表指针为p 的结点之后插入指针为s 的结点,正确的操作是（ ）。

A ．p->next=s; s->next=p->next;B ．s->next=p->next; p->next=s;C ．p->next=s; p->next=s->next;D ．p->next=s->next; p->next=s; 7、设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。

A ．1，2，4，3B ．2，1，3，4C ．1，4，3，2D ．4，3，1，2， 8、广义表（a,(b,c),d,e ）的表头和表尾分别为（ ）。

A ．a 和(b,c),d,e B ．（a ）和(b,c),d,eC ．a 和 ((b,c)，d,e)D ．(a) 和((b,c)，d,e)9、栈和队都是（ ）A ．顺序存储的线性结构B ．链式存储的非线性结构C ．限制存取点的线性结构D ．限制存取点的非线性结构 10、从逻辑上可以把数据结构分为（ ）两大类。