2015年福建华侨大学数据结构与C++考研真题.doc-资料库

第1页 / 共10页

第2页 / 共10页

第3页 / 共10页

第4页 / 共10页

第5页 / 共10页

第6页 / 共10页

第7页 / 共10页

第8页 / 共10页

2015 年福建华侨大学数据结构与 C++考研真题第一部分数据结构（总分 75 分）一. 单项选择题（每题 2 分，共 20 分） 1．删除顺序表 L 的第 i (1≤i≤L.length)个元素，需要移动（）个元素。 A）i B）L.length C）L.length +i D）L.length -i 2.判断带头结点的单向循环链表 L 是否为空表的条件是（）。 A）L==NULL B）L->next==NULL C）L->next==L D）L==L->next->next 3．在一个空的带头结点的单链表 L 中，插入元素 x 的操作为（）。 A）LNODE *s=new LNODE; s->data=x; s->next=L->next; L->next=s; B）LNODE *s=new LNODE; s->data=x; s->next=L; L->next=s; C）LNODE *s=new LNODE; s->data=x; s->next=L; L=s; D）LNODE *s=new LNODE; s->data=x; s->next=L->next; L=s->next; 4. 设 A, B, C, D 依次进栈，进栈和出栈操作可以交替进行，不可能的出栈序列是（）。 A）A,B,C,D B）A,B,D,C C）A,D,B,C D）C,B,A,D 5. 以下程序的输出结果为（）。 #include using namespace std; void P( int w ) { if(w==0) return; P(w-1); cout<next==NULL)&&(Q.rear->next==NULL)

B）(Q.front==NULL)&&(Q.rear==NULL) C）(Q.front->next==NULL)&&(Q.rear==NULL) D）(Q.front==NULL)&&(Q.rear->next==NULL) 7. 在层序遍历二叉树的算法中，通常要用到数据结构（）。 A）栈 B）散列表 C）队列 D）图 8. 具有 n 个顶点的完全有向图的边数为（）。 A）n(n-1) B）n(n-1)/2 C）n(n+1) D）n(n+1)/2 9. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（）算法。 A）堆排序 B）直接插入排序 C）快速排序 D）简单选择排序 10. 对有序表 L={11,33,55,66,100,120，150,180}，进行二分查找值为 100 的结点，需要比较（）次查找成功。 A） 1 B）2 C） 3 D） D） 4 二、简答题（共 30 分） 1.（5 分）下面算法对不带头结点的非空单向链表 L 中的各个结点按序进行遍历输出。请将该算法改为递归算法实现。 void print(LinkedList L){ LNode* p=L->next； while(p){ cout<data<<’,’; p=p->next; } } 2. （5 分）已知某棵二叉树的中序遍历序列为 BFDAEGC，后序遍历序列为 FDBGECA。（1）（1 分）画出该二叉树；（2）（2 分）若采用顺序存储结构表示，请画出该存储结构示意图；（3）（2 分）画出其对应的不带头结点的中序线索二叉树。 3. （5 分）有如下无向图 G：

（1）（2 分）画出 G 的邻接表存储结构（顶点的各个邻接点按字母升序排列）；（2）（2 分）给出从顶点 A 出发对 G 进行深度优先搜索的顶点序列和相应的深度优先生成树；（3）（1 分）画出 G 的连通分量。 4. （5 分）已知某系统在通信联络中只可能出现 8 种字符，其概率分别为 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试画出对应的赫夫曼树。 5. （5 分）设有序查找表 st 的顺序存储结构如下所示：（1）（2 分）画出对其进行二分（折半）查找的判定树；（2）（2 分）给出查找 K=13 的关键字比较次数；（3）（1 分）分别计算查找成功与查找失败时的 ASL（平均查找长度）。 6. （5 分）对关键字序列（12，2，16，30，8，28），写出用快速排序算法从小到大排序第一趟结束时的序列（选取第一个记录作为枢轴）。三、算法设计题（共 25 分） 1.（12 分）L 为带头结点的单链表头指针且链表长度大于 2，试设计算法删除链表 L 的尾结点，并将该结点插入到链表 L 的首结点之前（即头结点之后）。 2.（13 分）设无向图 g 各个顶点（顶点数不超过 100）只存储单个字符信息，采用邻接矩阵表示，编写函数 void fun2(MGraph& g, char vi, char vj)，将顶点 vi 与顶点 vj 之间的无向边（vi,vj），插入到图 G 中（假设原先 vi 与顶点 vj 之间无边相连）说明：无向图 G 的邻接矩阵类型定义如下： typedef struct{ char vexs[100]; //顶点向量 int arcs[100][100]; //邻接矩阵, 0 表示无边，1 表示有边 int vexnum, arcnum; //顶点数，边数 }MGraph; 第二部分 C++ (共 75 分) 一、选择题（单选，每题 2 分，总 30 分） 1. 当 i!=1 时，与表达式++i+=1 的计算结果相同的表达式是（）。

A) i=i*1 B) i+++1 C) i++,i+1 D) i=i+3 2. 若有以下定义语句：int array[10]={0,1,2,3,4,5,6,7,8,9}; 则下列哪个是对该数组元素的正确引用（）。 A) array [10] B) array [array [3]-4] C) array [array [9]] D) array [array [4]+4] 3. 已知字母 a 的 ASCⅡ码为十进制的 97,下面程序的输出是（）。 A) 99,d B) b,c C) c,d D) 不确定的值 #include using namespace std; int main() { char ch1,ch2; ch1='a'+'5'-'3';ch2='a'+'6'-'3';cout< using namespace std; int main() { int a[8]={0,2,4,6,8,10},*p=a; cout<<*(p+3); return 1; } 6. 程序 char str[]="abcde";cout<

B）bcde C）cde D）abcd 7. 若有以下定义，则赋值正确的是（）。 int n1,n2 , *p; float n3, *q; A．p=&n3 B．q=p C．p=NULL D．q=new int; 8. 设有说明“int y[ ]={1,2,3,4,5,6,7},*p=y;”, 输出值不是 7（数组 y 的元素个数）的是（）。 A）cout< using namespace std; int main() { int y=16; for(;y>0;y--) if(y%4==0) cout<<--y<<" "; return 1; } 10. 下列关于构造函数的描述中，错误的是（）。 A) 构造函数可以没有参数 B) 构造函数不可以设置默认参数 C) 构造函数可以是内联函数 D) 构造函数可以重载 11. 面向对象方法的多态性是指（）。 A) 一个类可以派生出多个特殊类 B) 一个对象在不同的运行环境中可以有不同的变体 C) 针对一消息，不同的对象可以以适合自身的方式加以响应 D) 一个对象可以是由多个其他对象组合而成的 12. 假定 Apple 为一个类，则该类的拷贝构造函数的声明语句为（）。 A) Apple&( Apple x)； B) Apple (Apple x)

C) Apple (const Apple & x)； D) Apple (const Apple *x) 13. 定义如下的基类和派生类: class Base { public:int i; protected: int j; private: int k; }; class Derived; public Base {public:fun(); }; 则下列基类成员可以被函数 fun()访问的是（）。 A) i , j, k B) i, j C) i D) j, k 14. 下面关于运算符重载的说法中正确的是（）。 A) 通过运算符重载可以定义新的运算符 B) 只能通过成员函数重载运算符“[ ]” C) 如果重载运算符“+”，则函数的名字是+ D) 当重载二元运算法时，必须声明两个参数 15. 下面程序的正确输出结果是（）。 #include< iostream> using namespace std; class myclass{ public: myclass(){cout<<"A";} myclass(char c){cout< using namespace std;

void func(int* x, int n, int ref){ for(int i = 0; i < n; ++i){ *(x+i) = (*(x+i) > ref)?1:0; } } int main(){ int x[] = {3, 5, 6, 7, 8, 8, 7, 6, 5}; func(x, sizeof(x)/sizeof(int),6); for(int i = 0; i < sizeof(x)/sizeof(int); ++i) cout << x[i] << " "; return 1; } 2) #include using namespace std; void func(int *s,int *y) { static int t=2; *y=s[t]; t--; } int main() { int a[]={1,2,3,4},i,x=0; for(i=0;i<4;i++) { func(a,&x); cout< #include using namespace std; class Student{ int n; string name; public: void set(string str){ static int number = 0; name = str; n = ++number; } void print(){ cout< students are "<

Student s1; s1.set("Kitty"); Student s2; s2.set("Jim"); s1.print(); }//------------------------------------ int main(){ Student s; s.set("Smith"); fn(); s.print(); return 1; } 三. 程序填空和简答（10 分）。 1. 计算的值。对如下程序填空。(5 分) #include int main() { double x,p1=1,p2=1,s=0; int i,j=1; cout<<"输入 x 的值:"; cin>>x; for(i=1;i<=10;i++) { p1*=___(1)_____; p2*=____(2)____; s+=j*p1/p2; //j 的值为(-1)i+1 j=____(3)____; } cout<=0 ; j--) if(strcmp(p,table[j])<0) ___(5)___; else break; table[j+1]=___(6)___; } } 四、编程题(共计 23 分) 1. 键盘任意输入 n 个整数并存储，使前面各个数顺序向后移动 m(m

资料库

2015年福建华侨大学数据结构与C++考研真题.doc

相关推荐

考研

热门标签

最新资料