数据结构(C++)第一次作业答案

2014年上半年数据结构（C++）第一次作业

一． 单项选择题(20分)

( )1. 已知一棵二叉树的前序遍历序列为ABCDEFG，则其中序遍历可能是___b_____。

a、CABDEFG b、ABCDEFG c、DACEFBG d、ADCFEGB

( )2. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用___b_____存储方式最节

省时间（假设链表仅设有一个first指针一个）。 a. 单链表 b. 带头结点的双循环链表 c. 单循环链表 d. 双链表

( )3. 有6个元素6,5,4,3,2,1顺序入栈，则所得到的输出序列不可能是___c____。

a. 5 4 3 6 1 2 b. 4 5 3 1 2 6 c. 3 4 6 5 2 1 d. 2 3 4 1 5 6

( )4. 链表不具有的特点是___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. 1 b. 4 c. () 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++)

1

}

}

y = y+i*j;

则语句“y = y+i*j”的执行次数多少？要求列出计算公式。 答：1+3+5+...+n-1=n2/4

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

13 5 225 1 运算数栈

- ( / + # 运算符栈

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

?0?0??0A??0??0??0900300000001200000008000?0??0?0??060??000?0000答： 三元组：

（（1,2,9），（3,4,12），（4,2,3），（5,3,8），（5,6,6））

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

略

5. 在下面数组a中链接存储着一个线性表，其表头“指针”为head==0，可利用空间表第一个元

素的“指针”av==5：

a data link 0 4 1 60 3 2 56 7 3 42 -1 4 38 2 5 12 8 6 74 -1 7 25 1 8 20 6 2

现在依次进行如下操作：1) 在元素56前插入元素78；2）删除元素60；3）删除25；4）在元素56后插入66；5）在元素66前插入88。请问，在进行上面操作后，av== 8 ,并将此时数组a的内容填入下表：

a data link 0 4 1 88 7 2 56 1 3 42 -1 4 38 5 5 78 2 6 74 -1 7 66 3 8 20 6 三． 程序填空（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); //在表的当前位置处插入元素item int 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<<\ curr=head=0; av=1; for(int i=1;i

int List::newElement(){

if(isFull()){cout<<\

3

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<<\}

void List::insert(const int & item) {

if(curr == -1){cout<<\ int newnode;

______④ _newnode=newElement(); ____ datalist[newnode].elem=item;

____⑤ datalist[newnode].next= datalist[curr].next; ____

datalist[curr].next = newnode; }

int List::remove(){

if(!isInList()){cout<<\ 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<<\ 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; }

4

下面是仅给出了部分操作某线性表类的定义和实现。试在程序的每一划线部分填入一条语句或表达式，完成相应的操作。 typedef node { int elem;

struct node *next; }node,*LinkListPtr;

typedef struct {

LinkListPtr head,tail; LinkListPtr curr; } LinkList;

void InitLinkList(LinkList &L) //初始化线性表 {

L.head = (node *)malloc(sizeof(node));

if(L.head == NULL){cout<<\ L.tail = L.head; L.curr = L.head; }

void insert(LinkList &L,int & item) //在表L的当前位置处插入元素item {

if(L.curr == NULL){cout<<\ node * newnode = (node *)malloc(sizeof(node));

if(newnode == NULL){cout<<\ newnode->elem=item;

④newnode->next=L.curr->next ; ⑤ L.curr->next = newnode ; if (L.tail == L.curr) L.tail = L.curr->next; }

void setFirst(LinkList &L) //将表的当前位置定位于第1个元素 {

⑥ L.curr = L.head ; }

int currValue(LinkList &L) //将表的当前位置的元素值返回 {

if(!isInList(L)) {

cout<<\}

return ⑦ L.curr->next->elem ; }

bool isEmpty(LinkList &L) //判断线性表是否为空 {

⑧ return L.head->next == NULL ; }

bool isInList(LinkList &L) //判断curr是否在表中 {

return (L.curr != NULL) && (L.curr->next != NULL) && (!isEmpty(L)); }

bool find(LinkList &L ,const int & eval) //从表的当前位置开始查找元素eval

5

{

while (isInList(L))

if ( ⑨ (L.curr->next->elem) == eval ) return TRUE; else ⑩ L.curr = L.curr->next; return FALSE; }

6

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构(C++)第一次作业答案在线全文阅读。