《动态分配内存与数据结构》习题
学号姓名
一、选择题
1、是一种限制存取位置的线性表,元素的存取必须服从先进先出的规则。
A.顺序表B.链表C.栈D.队列
2、是一种限制存取位置的线性表,元素的存取必须服从先进后出的规则。
A.顺序表B.链表C.栈D.队列
3、与顺序表相比,链表不具有的特点是。
A.能够分散存储数据,无需连续内存空间
B.插入和删除无需移动数据
C.能够根据下标随机访问
D.只要内存足够,没有最大长度的限制
4、如果通过new运算符动态分配失败,返回结果是。
A.-1 B.0
C.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. ABCDE
B. EDCBA
C. EDBCA
D. BCADE
13、假设对4个元素A、B、C、D、E进行压栈或出栈的操作,压栈的先后顺序是ABCD,则出栈的先后顺序不可能是。
A. ABCD
B. DCBA
C. BCAD
D. DCAB
14、通过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.*28
22、对于循环队列,下列叙述中正确的是
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
using namespace std;
class stack{
int *rep;
int size,top;
public:
stack(int n=10):size(n){
cout<<"Initial Constructor"< rep=new int [size];top=0; } stack(stack &s):size(s.size) { cout<<"Copy Constructor"< rep=new int[size]; for (int i=0;i top=s.top; } ~stack(){ cout<<"Destructor"< 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.push(6); s1.push(7); while (!s2.isEmpty()) cout< cout< } 2、指出程序的运行结果: #include usingnamespacestd; class stack{ int *rep; int size,top; public: stack(int n=10):size(n)//构造函数 { cout<<"Initial Constructor"< rep=newint[size]; top=-1; } stack(stack &s):size(s.size)//复制构造函数,需深复制。 { cout<<"Copy Constructor"< rep=newint[size]; for (int i=0;i rep[i]= s.rep[i]; top=s.top; } ~stack() { cout<<"Destructor"< 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.push(ptr[1].pop()); ptr[0].push(ptr[1].pop()); s2.push(ptr[1].pop()); while(!s2.isEmpty()) cout< cout< delete[] ptr; return 0; } 3、写出程序的运行结果 #include #include using namespace std; template class Node { public: T data; Node Node(const T&info) {data=info;link=NULL;} }; template class OrderedLink { Node public: OrderedLink() {head=NULL;} OrderedLink(const T*list,int num) { head = NULL; for(;num>0;num--,list++) Insert(*list); } ~OrderedLink() { while(head!=NULL) { Node head=p->link; delete p; } } void Insert(const T&data) { Node 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 while(p) { cout< p = p->link; } } }; void main() { char *s = "bad"; OrderedLink a.show(); a.Insert('e'); a.show(); } 4、写出程序的运行结果 #include 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"< else { for(int i=0;i<=last;i++) cout< cout< } } void set(int i,int key) { if(i<0||i>last) cout<<"illegal subscript!"< else list[i] = key; } void insert(int key) { if(last==-1) { last++; list[last]=key; } else if(last==maxsize-1) cout<<"list full"< 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; //A a.insert(m); } a.print(); a.set(3,0); a.print(); cin>>m; //B a.insert(m); a.print(); } 如果A行输入4 6 1 0 9 2 6 7 5 3,B行输入8则输出的结果是 四、程序填空题 1、建立线性表模板,能够按照用户要求的元素个数(缺省为10个元素)创建数组、实现元素的有序插入(即将元素插入在有序数组适当位置,保持数组有序)、降序排列数组的二分查找以及数组打印。主函数中将模板实例化,创建一个整型数组,通过调用有序插入函数建立一个降序排列的数组,并测试二分查找功能。程序如下: #include using namespace std; template class seqlist{ T *slist; int last; int maxsize; public: seqlist(int n=10){ maxsize=n; slist=new T[n]; last=-1; } ~seqlist(){ if(slist) } void print(){ for(int i=0;i<=last;i++) cout< cout< } void insertOrder(T); int bisearch(T key); }; template { for(int i=last;i>=0&&slist[i] =key; last++; } template int seqlist int low=0,high=last,mid; while(low<=high){ mid=(low+high)/2; if(key else if(key>slist[mid]) high=mid-1; else break; } if(low>high) ; return mid; } int main(){ seqlist int k,p; cout<<"input 8 integers:"< for(int i=0;i<8;i++){ //建立降序排列数组 cin>>k; ; } a.print(); cout<<"input an integer to be searched:"< cin>>k; p=a.bisearch(k); if(p==-1) cout< else cout<<"a["< return 0; } 2、建立单链表模板类,并实例化为字符串链表,测试建立链表、查找结点并删除结点等功能。#include #include using namespace std; template template T data; Node* next; public: Node(){next=NULL;} Node(T d){data=d; next=NULL;} friend class List }; template class List{ Node public: List(){head=tail=new Node ~List(){makeEmpty(); delete head;} //析构函数 void makeEmpty(); //清空链表,只留下一个表头的空结点 Node void printList(); //打印链表 Node //建立数据结点 void insertRear(Node //将p结点插在当前链表尾 void deleteNode(Node }; template void List Node while(t){ cout< t=t->next; }