《2022年数据结构第一次作业答案文件 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构第一次作业答案文件 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 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
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_。(1i 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!=N
3、ULL; ( )7.用数组 A0.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.设关于串的叙述中，哪一个是不正确的
4、？_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+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -
5、- 第 1 页，共 6 页 - - - - - - - - - 2 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的三元组表和十字链表。00000000600800000003
6、00001200000000000000090A答：三元组：（ 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 0 1 2 3 4 5 6 7 8 data 60 56 42 38 12 74 25 20 link 4 3 7 -1 2 8 -1 1 6 名师资料总结 - - -精品资料欢迎下载 - - -
7、 - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 3 现在依次进行如下操作：1) 在元素 56 前插入元素78；2）删除元素60；3）删除 25； 4）在元素56 后插入 66；5）在元素 66 前插入 88。请问，在进行上面操作后，av= 8 ,并将此时数组 a 的内容填入下表：三程序填空（ 24分）下面是仅给出了部分操作某线性表类的定义和实现。试在程序的每一划线部分填入一条语句或表达式，完成相应的操作。class node public: int elem; int next;
8、 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为释放
9、单元的下标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; /将表的
10、当前位置的元素值返回bool find(const int & eval); /从将表的当前位置开始查找元素eval ; List:List (int Size):maxSize(Size) datalist=new nodemaxSize+1; if(datalist = NULL)coutInsufficient memory availablen ;exit(0); curr=head=0; av=1; for(int i=1;imaxSize;i+) _ datalisti.next=i+1; _ int List:newElement() if(isFull()coutInsuffi
11、cient memory availablen ;exit(0); a 0 1 2 3 4 5 6 7 8 data 88 56 42 38 78 74 66 20 link 4 7 1 -1 5 2 -1 3 6 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 4 int newnode = av; _ av=datalistav.next; _ return newnode; void List:freeElement(in
12、t n) _ datalistn.next=av; _ av=n; void List:next () if(curr!=-1)curr=datalistcurr.next; else coutCurrent position is not a legal positionn;exit(0); void List:insert(const int & item) if(curr = -1)coutCurrent position is not a legal positionn;exit(0); ; int newnode; _ _newnode=newElement(); _ datalis
13、tnewnode.elem=item; _ datalistnewnode.next= datalistcurr.next; _ datalistcurr.next = newnode; int List:remove() if(!isInList()coutCurrent position is not a legal positionn;exit(0); int retVal=currValue(); int n; _ _n=curr-; _ _ datalistcurr.next=datalistn.next; _ freeElement(n); return retVal; void
14、List:setFirst() _ curr=head; _ int List:currValue () const if(!isInList()coutCurrent position is not a legal positionn;exit(0); return _ datalistcurr.item; _ bool List:isEmpty () const return _ curr=0 & head=0; _; bool List:isFull() retrun _ av=-1; ;_ bool List:isInList() const return (curr != -1) &
15、 (datalistcurr.next!=-1) & (!isEmpty(); bool List:find (const int & eval) while (isInList() if (_ _datalistcurr.item=eval _) return TRUE; else next(); return FALSE; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 5 下面是仅给出了部分操作某线性表类的定义和实现。试在
16、程序的每一划线部分填入一条语句或表达式，完成相应的操作。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)coutInsufficient memory availablen ;exit(0); L.tail
17、 = L.head; L.curr = L.head; void insert(LinkList &L,int & item) /在表 L的当前位置处插入元素item if(L.curr = NULL)coutCurrent position is not a legal positionn;exit(0); ; node * newnode = (node *)malloc(sizeof(node); if(newnode = NULL)coutelem=item; newnode-next=L.curr-next ; L.curr-next = newnode ; if (L.tail =
18、 L.curr) L.tail = L.curr-next; void setFirst(LinkList &L) / 将表的当前位置定位于第1个元素 L.curr = L.head ; int currValue(LinkList &L) / 将表的当前位置的元素值返回 if(!isInList(L) coutnext-elem ; bool isEmpty(LinkList &L) /判断线性表是否为空 return L.head-next = NULL ; bool isInList(LinkList &L) / 判断 curr 是否在表中 return (L.curr != NULL)
19、 & (L.curr-next != NULL) & (!isEmpty(L); bool find(LinkList &L ,const int & eval) /从表的当前位置开始查找元素eval 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 6 while (isInList(L) if ( (L.curr-next-elem) = eval ) return TRUE; else L.curr = L.curr-next; return FALSE; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -