2014年上半年数据结构（C++）第一次作业一.单项选择题(20分)1.已知一棵二叉树的前序遍历序列为ABCDEFG，则其中序遍历可能是____b____。

a、CABDEFGb、ABCDEFGc、DACEFBGd、ADCFEGB2.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用__b______存储方式最节省时间（假设链表仅设有一个first指针一个）。

a. 单链表b. 带头结点的双循环链表c. 单循环链表d. 双链表3.有6个元素6,5,4,3,2,1顺序入栈，则所得到的输出序列不可能是___c____。

a. 5 4 3 6 1 2b. 4 5 3 1 2 6c. 3 4 6 5 2 1d. 2 3 4 1 5 64.链表不具有的特点是__d___。

a．插入,删除不需要移动元素 b．所需空间与线性长度成正比c．不必事先估计存储空间 d．可随机访问任一元素5.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为_____c____。

(1≤i≤n+1)a、O(0)b、O(1)c、O(n)d、O(n2)6.对于一个头指针为head的带头结点的单链表，该表为空表的条件是__a____为真值；a. head->next==NULL;b. head==NULL;c. head->next==head;d. head!=NULL;7.用数组A[0..N-1]存放一个循环队列，一元素出队时，其队头指针front的修改方法是___a____：a. front = (front + 1) mod N;b. front = (front - 2)mod N;c. front = front + 1;d. front = front – 2;8.若用Head()和Tail()分别表示取广义表的表头和表尾，广义表A=（1,2,(3,4),(5,(6,7))），则Head(Tail(Head(Tail(Tail(A))))) b 。

a. 1b. 4c. ()d. （4）9.设关于串的叙述中，哪一个是不正确的？___b_____a. 串是字符的有限序列b. 空串是由空格构成的串c. 模式匹配是串的一种重要运算d. 串既可以采用顺序存储，也可以采用链式存储10.链下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是____c____。

a.堆排序b.起泡排序c.直接选择排序d.快速排序二.填空作图题（共56分）：1.设 n是偶数，且有程序段：for(i=1; i<=n; i++){if(2*i <= n){for(j = 2* i; j<=n;j++)y = y+i*j;}}则语句“y = y+i*j”的执行次数多少？要求列出计算公式。

解答：语句y=y+i*j;在i=1时，执行n-1次，在i=2时，执行n-3次，……，当i=n/2时执行1次，当i>n/2时不再执行。

故总的执行次数是： (n-1)+(n-3)+(n-5)+……+3+1=n2/4运算符栈2.如果采用一运算数栈和一运算符栈来计算由键盘输入的中缀表达式1+((2+3)*4+5)*9/(5-(6+7)*8)#的值,这里运算数栈用来存放计算过程中使用或产生的运算数，运算符栈用来存放尚未用于计算的运算符，那么按照算法，请将当运算数栈第一次在栈顶出现13时各栈中存放的数据情况填入下表。

运算数栈3.画出稀疏矩阵A的三元组表和十字链表。

4.已知广义表为（（()）, （2）, (‘q’,(‘p’,5,8)))；试画出该广义表的存储表示。

答：三元组：（（1,2,9），（3,4,12），（4,2,3），（5,3,8），（5,6,6））a 0 1 2 3 4 5 6 7 85.在下面数组a中链接存储着一个线性表，其表头“指针”为head==0，可利用空间表第一个元素的“指针”av==5：a 0 1 2 3 4 5 6 7 8；3）删除25；4）在元素56后插入66；5）在元素66前插入88。

请问，在进行上面操作后，av== ,并将此时数组a的内容填入下表：三.程序填空（24分）下面是仅给出了部分操作某线性表类的定义和实现。

试在程序的每一划线部分填入一条语句或表达式，完成相应的操作。

class node {public:int elem;int next;node(const int elemval, int nextval =-1){ elem = elemval; next = nextval; } node(int nextval =-1) { next = nextval; }};class List{private:node * datalist;int head;int curr;int av; //可利用空间表第一个空闲单元的位置int maxSize; //可存放元素的个数int newElement(); //分配一空闲单元，返回单元所在下标void freeElement(int n); //释放一空闲单元到可利用空间表，参数n为释放单元的下标public:List(int Size=10);bool isEmpty()const; //判断线性表是否为空bool isFull()const; //判断线性表是否已满bool isInList()const; //判断curr是否在表中void insert(const int & item); //在表的当前位置处插入元素itemint remove(); //将当前位置的元素从表中删除,并返回被删除元素的值void setFirst(); //将表的当前位置定位于第1个元素void next(); //定位到下一个元素int currValue() const; //将表的当前位置的元素值返回bool find(const int & eval); //从将表的当前位置开始查找元素eval};List::List(int Size):maxSize(Size) {datalist=new node[maxSize+1];if(datalist == NULL){cout<<"Insufficient memory available\n" ;exit(0);};curr=head=0;av=1;for(int i=1;i<maxSize;i++) ____① _datalist[i].next=i+1;__}int List::newElement(){if(isFull()){cout<<"Insufficient memory available\n" ;exit(0);};int newnode = av;____② av=datalist[av].next;____return newnode;}void List::freeElement(int n){_____③ datalist[n].next=av;av=n;}void List::next(){if(curr!=-1)curr=datalist[curr].next;else {cout<<"Current position is not a legal position\n";exit(0);}}void List::insert(const int & item) {if(curr == -1){cout<<"Current position is not a legal position\n";exit(0); }; int newnode;______④ _newnode=newElement(); ____datalist[newnode].elem=item;____⑤ datalist[newnode].next= datalist[curr].next;__datalist[curr].next = newnode;}int List::remove(){if(!isInList()){cout<<"Current position is not a legal position\n";exit(0);}int retVal=currValue();int n;_____⑥_n=curr--; _________⑦ datalist[curr].next=datalist[n].next; _freeElement(n);return retVal;}void List::setFirst(){___⑧ curr=head; ___}int List::currValue() const{ if(!isInList()){cout<<"Current position is not a legal position\n";exit(0);} return ____⑨ datalist[curr].item; ___ }bool List::isEmpty() const{return ____⑩ curr==0 && head==0;}bool List::isFull(){retrun ______⑾ av==-1; ___}bool List::isInList() const{ return (curr != -1) && (datalist[curr].next!=-1) && (!isEmpty()); }bool List::find(const int & eval) {while (isInList())if (____⑿ datalist[curr].item==eval ____) return TRUE;else next();return FALSE;}。