《动态分配内存与数据结构》习题学号姓名一、选择题1、是一种限制存取位置的线性表，元素的存取必须服从先进先出的规则。

A．顺序表B．链表C．栈D．队列2、是一种限制存取位置的线性表，元素的存取必须服从先进后出的规则。

A．顺序表B．链表C．栈D．队列3、与顺序表相比，链表不具有的特点是。

A．能够分散存储数据，无需连续内存空间B．插入和删除无需移动数据C．能够根据下标随机访问D．只要内存足够，没有最大长度的限制4、如果通过new运算符动态分配失败，返回结果是。

A．-1 B．0C．1D．不确定5、实现深复制中，不是必须自定义的。

A．构造函数B．复制构造函数C．析构函数D．复制赋值操作符函数6、分析下列代码是否存在问题，选择合适的选项：。

int main(void){int *p = new int [10];p = new int [10];delete [] p;p = NULL;return 0;}A．没有问题 B．有内存泄漏C．存在空悬指针 D．存在重复释放同一空间7、通过new运算符动态分配的对象，存储于内存中的。

A．全局变量与静态变量区 B．代码区 C．栈区 D．堆区8、下列函数中，可以是虚函数。

A．构造函数 B．析构函数 C．静态成员函数 D．友元函数9、关于通过new运算符动态创建的对象数组，下列判断中是错误的。

A. 动态创建的对象数组只能调用默认构造函数B. 动态创建的对象数组必须调用delete []动态撤销C. 动态创建的对象数组的大小必须是常数或常变量D. 动态创建的对象数组没有数组名10、顺序表不具有的特点是A. 元素的存储地址连续B. 存储空间根据需要动态开辟，不会溢出C. 可以直接随机访问元素D. 插入和删除元素的时间开销与位置有关11、假设一个对象Ob1的数据成员是指向动态对象的指针，如果采用浅复制的方式复制该对象得到对象Ob2，那么在析构对象Ob1和对象Ob2时会的问题。

A. 有重复释放B. 没有C. 内存泄漏D. 动态分配失败12、假设对5个元素A、B、C、D、E进行压栈或出栈的操作，压栈的先后顺序是ABCDE，则出栈的先后顺序不可能是。

A. ABCDEB. EDCBAC. EDBCAD. BCADE13、假设对4个元素A、B、C、D、E进行压栈或出栈的操作，压栈的先后顺序是ABCD，则出栈的先后顺序不可能是。

A. ABCDB. DCBAC. BCADD. DCAB14、通过new运算符动态创建的对象的存放在中。

A. 代码区B. 栈区C. 自由存储区D. 全局数据区15、链表不具有的特点是。

A. 元素的存储地址可以不连续B. 存储空间根据需要动态开辟，不会溢出C. 可以直接随机访问元素D. 插入和删除元素的时间开销与位置无关16、有关内存分配和释放的说法，下面当中错误的是A．new运算符的结果只能赋值给指针变量B．动态创建的对象数组必须调用delete []动态撤销C．用new分配的空间位置是在内存的栈区D．动态创建的对象数组没有数组名17、关于栈，下列哪项不是基本操作A．删除栈顶元素B．删除栈底元素C．判断栈是否为空D．把栈置空18、关于链表，说法错误的是A. 元素的存储地址可以不连续B. 存储空间根据需要动态开辟，不会溢出C. 必须是单向的，不能是双向的或者是环形的。

D. 插入和删除元素的时间开销与位置无关19、关于线性链表，其不具备的特点是A．链表不需要事先分配空间，可以根据需要动态分配B．链表和数组一样可随机访问表内任一元素C．插入删除不需要移动表内的元素D．链表所需空间大小与其节点数成正比20、下列关于队列的描述中正确的是A．在队列中只能插入元素而不能删除元素B．在队列中只能删除元素而不能插入元素C．队列是特殊的线性表，只能在一端插入或删除元素D．队列是特殊的线性表，只能在一端插入元素，而在另一端删除元素21、设内存分配语句int *p=new int，选择合适的填充使P所指的存储单元赋初值28。

A．(28) B．[28] C．{28} D．*2822、对于循环队列，下列叙述中正确的是A．队头指针是固定不变的B．队头指针一定大于队尾指针C．队头指针一定小于队尾指针D．队头指针可以大于队尾指针，也可以小于队尾指针23、下列关于线性链表的叙述中，正确的是A．各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B．各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C．进行插入与删除时，不需要移动表中的元素D．以上三种说法都不对24、设有如图的线性链表，其中p,q,r都为指向链表中节点的指针。

先需要将上述链表当中q和r所指的节点交换位置，同时保持链表的连续，则下列语句当中无法胜任的是__________A. q->next=r->next; p->next=r; r->next=q;B. p->next=r; q->next=r->next; r->next=q;C. q->next=r->next; r->next=q; p->next=r;D. r->next=q; p->next=r; q->next=r->next;二、填空题1、在长度为10 的顺序存储的线性表中插入一个元素，最坏情况下需要移动表中个元素。

2、设某循环队列的容量为40，头指针front=3（指向队头元素的前一位置），尾指针rear=25（指向队尾元素），则该循环队列中共有个元素。

3、假设有一长度为20的线性表用来存储栈，如果栈底元素bottom=19,栈顶元素top=10，则该栈当中具有个元素。

4、假设有int *p = new int [20],则当释放该数组时，应用语句来完成。

5、单向链表的节点分为域和域两部分。

如果需要实现环形链表，则需要把最后一个节点的指向。

6、一般情况下，使用系统提供的默认析构函数就可以了，但当对象的成员中使用了运算符动态分配内存空间时，就必须以正确释放对象空间。

为了对象间能正确赋值，还必须要。

7、通过new运算符动态创建的对象的存放在中。

8、默认复制构造函数是按成员复制，称为9、void a(node *p,Datatype x){node *q=new node;q->info=x;q->link=p->link;p->link=q;}以上a函数实现的功能是10、对含有动态分配的数据成员的类对象应该采用复制，动态分配的资源通常要求在中释放。

三、程序阅读题1、指出程序的运行结果：#include <iostream>using namespace std;class stack{int *rep;int size,top;public:stack(int n=10):size(n){cout<<"Initial Constructor"<<endl;rep=new int [size];top=0;}stack(stack &s):size(s.size) {cout<<"Copy Constructor"<<endl;rep=new int[size];for (int i=0;i<size;i++) rep[i]= s.rep[i];top=s.top;}~stack(){cout<<"Destructor"<<endl;delete [] rep;}void push(int a) {rep[top]=a;top++;}int pop(){--top; return rep[top];}bool isEmpty() const{return top == 0;}};void main(void){stack s1;for(int i=1;i<5;i++) s1.push(i);stack s2(s1);for(i=1;i<3;i++) cout<<s2.pop()<<',';s2.push(6);s1.push(7);while (!s2.isEmpty()) cout<<s2.pop()<<',';cout<<endl;}2、指出程序的运行结果：#include <iostream>usingnamespacestd;class stack{int *rep;int size,top;public:stack(int n=10):size(n)//构造函数{cout<<"Initial Constructor"<<endl;rep=newint[size];top=-1;}stack(stack &s):size(s.size)//复制构造函数，需深复制。

{cout<<"Copy Constructor"<<endl;rep=newint[size];for (int i=0;i<size;i++)rep[i]= s.rep[i];top=s.top;}~stack(){cout<<"Destructor"<<endl;delete [] rep;}void push(int a) {rep[++top]=a; }int pop() {return rep[top--];}bool isEmpty() {return top == -1;}};int main(){stack *ptr=new stack[2];for(int i=1;i<5;i++){ ptr[0].push(i);ptr[1].push(i+6);}stack s2(ptr[0]);for(i=0;i<2;i++)cout<<s2.pop()<<',';s2.push(ptr[1].pop());ptr[0].push(ptr[1].pop());s2.push(ptr[1].pop());while(!s2.isEmpty())cout<<s2.pop()<<',';cout<<endl;delete[] ptr;return 0;}3、写出程序的运行结果#include <iostream>#include <string>using namespace std;template <typename T>class Node{public:T data;Node<T> *link;Node(const T&info) {data=info;link=NULL;}};template <typename T>class OrderedLink{Node<T> *head;public:OrderedLink() {head=NULL;}OrderedLink(const T*list,int num){head = NULL;for(;num>0;num--,list++)Insert(*list);}~OrderedLink(){while(head!=NULL){Node<T> *p=head;head=p->link;delete p;}}void Insert(const T&data){Node<T> *p = new Node<T>(data),*q = head;if(!q)head = p;else if(p->data>q->data){p->link = head;head = p;}else{while(q->link&&p->data>q->link->data)q = q->link;if(q->link) p->link=q->link;q->link=p;}}void show(){Node<T> *p = head;while(p){cout<<p->data<<endl;p = p->link;}}};void main(){char *s = "bad";OrderedLink<char> a(s,strlen(s));a.show();a.Insert('e');a.show();}4、写出程序的运行结果#include <iostream>using namespace std;class Array{int *list;int last;int maxsize;public:Array(int n=20){maxsize = n;last = -1;list = new int[n];}~Array() {delete []list;}void print(){if(last==-1)cout<<"empty list"<<endl;else{for(int i=0;i<=last;i++) cout<<list[i]<<"";cout<<endl;}}void set(int i,int key){if(i<0||i>last) cout<<"illegal subscript!"<<endl;else list[i] = key;}void insert(int key){if(last==-1){last++;list[last]=key;}else if(last==maxsize-1) cout<<"list full"<<endl;else{for(int i=last;i>=0&&list[i]>key;i--)list[i+1] = list[i];list[i+1] = key;last++;}}};void main(){Array a(10);int m;for(int i=0;i<10;i++){cin>>m; //Aa.insert(m);}a.print();a.set(3,0);a.print();cin>>m; //Ba.insert(m);a.print();}如果A行输入4 6 1 0 9 2 6 7 5 3，B行输入8则输出的结果是四、程序填空题1、建立线性表模板，能够按照用户要求的元素个数（缺省为10个元素）创建数组、实现元素的有序插入（即将元素插入在有序数组适当位置，保持数组有序）、降序排列数组的二分查找以及数组打印。