计130121第二次作业

1、第二次作业一、选择题1、栈和队列的相同之处是C。A.元素的进出满足先进后出B.元素的进出满足后进先出C.只允许在端点进行插入和删除操作D.无共同点2、设栈S 和队列Q 的初始状态为空,元素e1，e2，e3，e4，e5 和e6 依次通过栈，一个元素出栈后即进入队列Q,若6 个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S 的容量至少应该是C。A. 6 B. 4 C. 3 D. 2 3、队列通常采用的两种存储结构是( A)。A. 顺序存储结构和链式存储结构B.散列方式和索引方式C. 链表存储结构和线性存储结构D.线性存储结构和非线性存储结构4、循环队列SQ队满的条件是A。A. SQ-&

2、gt;rear=SQ->frontB. (SQ->rear+1)%MAXLEN=SQ->frontB. SQ->rear=0D. SQ->front=05、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为B。A. 5和1B. 4和2C. 2和4D. 1和56、链栈与顺序栈相比，有一个较为明显的优点是A。A. 通常不会出现满栈的情况B. 通常不会出现栈空的情况C. 插入操作更加方便D. 删除操作更加方便7、设用一个大小为M=60的顺序表AM表示一个循环队列，如果

3、当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为B。A. 42B. 16C. 17D. 418、串是一种特殊的线性表，其特殊性体现在B。A. 可以顺序存储B. 数据元素是一个字符C. 可以链式存储D. 数据元素可以是多个字符9、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为C。A. O(m)B. O(n)C. O(m+n)D. O(m×n)10、已知串S=“abab”，其Next数组值为0012。A. 0123B. 0121C. 0112D. 012211、若字符串“ABCDEFG”采用不带表头的链式存储，每个结点保存一个字符。

4、假设每个字符占用1个字节，每个指针占用两个字节，则该字符串的存储密度为D。A. 20%B. 40%C. 50%D. 33.3%12、在双向链表中，在指针p所指的结点前插入一个指针q所指向的结点，操作是C。A. p->Prior=q; q->Next=p; p->Prior->next=q; q->Prior=q;B. p->Prior=q; p->Prior->next=q; q->next=p; q->Prior=p->Prior;C. q->Next=p; q->Prior=p->Prior; p->

5、Prior->Next=q; p->Prior=q;D. q->Prior=p->Prior; q->Next=q;p->Prior=q; p->Next=q;13、已知循环队列存储在一维数组A0n-1中，且队列非空时front和rear分别指向对头元素和队尾元素，且要求第一个进入队列的元素存储在A0处，则初始时front和rear的值分别是B。A. 0, 0B. 0, n-1C. n-1, 0D. n-1, n-114、某队列允许在两端进行入队操作，但仅允许在一端进行出队操作（称为输出受限的双端队列），若a, b, c, d, e元素依次进队，则不可

6、能得到的顺序是C。A. bacdeB. dbaceC. dbcaeD. ecbad15、在双向链表中间插入一个结点时，需要修改修改D个指针域。A. 1B. 2C. 3D. 416、在按行优先顺序存储的三元组表中，下述陈述错误的是D。A. 同一行的非零元素，是按列号递增次序存储的B. 同一列的非零元素，是按行号递增次序存储的C. 三元组表中三元组行号是非递减的D. 三元组表中三元组列号是非递减的17、在稀疏矩阵的三元组表示法中，每个三元组表示D。A. 矩阵中非零元素的值B. 矩阵中数据元素的行号和列号C. 矩阵中数据元素的行号、列号和值D. 矩阵中非零数据元素的行号、列号和值18、对特殊矩阵采用

7、压缩存储的目的主要是为了D。A. 表达变得简单B. 对矩阵元素的存取变得简单C. 去掉矩阵中的多余元素D. 减少不必要的存储空间19、广义表是线性表的推广，它们之间的区别在于A。A. 能否使用子表B. 能否使用原子项C. 表的长度D. 是否能为空20、已知广义表(a, b, c, d)的表头是A，表尾是D。A. aB. ()C. (a, b, c, d)D. (b, c, d)21、下面说法不正确的是A。A. 广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构表示D. 广义表可以是一个多层次的结构22、若广义表A满足Head(A)=Tail(A)，则A为B

8、。A. ( )B. ()C. ( ),( )D. ( ), ( ), ( )二、填空题1、对于循环向量的循环队列，求队列长度的公式为（rear-front+n+1）%n。2、栈的逻辑特点是后进先出。队列的逻辑特点是先进先出。两者的共同特点是只允许在它们的两端出插入和删除数据元素，区别是出栈在顶端，出队列在头部。3、链队列LQ为空时，LQ->front->next=NULL.4、在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为front->next = rear。5、设串S=“Ilikecomputer”，T=“com”，则Lengt

9、h(S)=13。Index(S, T)=5。6、在KMP算法中，nextj只与T串有关，而与S无关。7、字符串“ababaab“的Next数组值是0012312。8、稀疏矩阵一般压缩存储的方式有三种，分别是三元组表、带行表的三元组表和稀疏矩阵的链式结构。9、二维数组M中每个元素的长度是3字节，行下标i从07，列下标j从09，从首地址&M00开始连续存放在存储器中。若按行优先的方式存放，元素M75的起始地址为(void)&M00 + 3*70+5；若按列优先方式存放，元素M75的起始地址为(void)&M00+3*40+7。10、广义表(a, (a, b), d, e,

10、(i, j), k)的长度是5，深度是3。11、设广义表A( ), (a, (b), c)，则Cal(Cdr(Cal(Cdr(Cal(A)=(b)三、设有一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的计数器count，试写出相应的判断队列空、判断队列满、出队算法和入队算法。要求：1、定义相应的循环队列的型（只有头指针，没有尾指针，但有一个元素个数的计数器）；2、定义该队列的四个算法：判断队列空、判断队列满、出队算法和入队算法；3、在main函数验证算法的正确性。/#include <iostream>using namespace std;type

11、def int ele;class Queueele data10;ele* _font;int len;public:Queue()_font = data;len = 0;void push_back(ele val)data(_font-data+len)%10 = val;len+;bool full()return (len >= 10);bool empty()return (len = 0);void pop_font()_font = data + (_font - data + 1)%10;len-;int font()return *_font;int main(in

12、t argc, char *argv) Queue q;int i;for ( i = 0; i < 10; i+) q.push_back(i);for ( i = 0; i < 10; i+) cout<<q.font()<<endl;q.pop_font();cout<<"=欢乐的分割线="<<endl;for ( i = 0; i < 10; i+) q.push_back(i);for ( i = 0; i < 10; i+) cout<<q.font()<<endl;

13、q.pop_font();return 0;/四、设主串T=“abcaabbabcabaacbacba“，模式为p=“abcabaa”。 1、计算模式p的nextval函数值2、不写算法，只画出利用KMP算法进行模式匹配时，每一趟的匹配过程。要求：1、写出模式p的nextval值；2、画出KMP算法的每一趟匹配过程（可参照教材P61从第8行开始的内容）；3、不需要编写程序。0001211五、假设表达式中允许包含三种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈（用数组表示的栈）判断表达式中的括号是否正确配对。要求： 1、定义栈以及栈的型，栈中所存放元素的类型为字符型，定义枚举类型Bool

14、ean，其中两个元素分别为TRUE和FALSE。2、定义栈的各种操作。3、定义函数Boolean check(char *s); 判断s中的括号是否正确配对，如果正确配对，返回TRUE，否则返回FALSE。4、在主函数中验证所编写函数的正确性。/#include <iostream>#include <stack>using namespace std;typedef stack<char> STACK;enum BooleanFALSE = 0,TRUE = 1;Boolean check(char *s)STACK _;while (*s) switch

15、 (*s) case '': case '(':case '':_.push(*s);break;case '':if (_.top() != '')return FALSE;_.pop();break;case ')':if (_.top() != '(')return FALSE;_.pop();break;case '':if (_.top() != '')return FALSE;_.pop();break;default:;+s;if (_.

16、empty() return TRUE;elsereturn FALSE;/return _.empty();int main(int argc, char *argv) char *data1 = "123()owsanfak1(234sff)1faer"char *data2 = "12(3owsanfak1)234sff1faer"cout<<check(data1)<<endl<<check(data2)<<endl;return 0;/六、设有一个带头结点的双向链表h，设计一个算法用于查找第一个元

17、素之为x的结点，并将其与其前驱结点进行交换。要求： 1、定义带头结点的双向链表的型DLIST。 2、定义双向链表DLIST的基本操作。 3、定义函数int swap(elementtype x, DLIST &h)，查找第一个元素之为x的结点，如果在链表中存在元素值为x的结点，并其与其前驱结点进行交换，并返回1，否则返回0。 4、在主函数中测试所编写函数的正确性。/ D-list.h#ifndef D_LIST#define D_LISTtypedef int elementtype;struct Node Node* pre;Node* next;elementtype val;No

18、de(elementtype _val,Node* _pre,Node* _next):val(_val),pre_pre,next(_next);class DLISTNode* head;Node* last;public:DLIST()head = NULL;last = NULL;DLIST(DLIST& list)Node* p = list.head;while (p) push_back(p->val);p = p->next;DLIST()Node* p;while (head) p = head;head = head->next;delete p;

19、void push_back(elementtype val)if (last) last->next = new Node(val,last,NULL);last = last->next;elsehead = last = new Node(val,NULL,NULL);void print_back()string str;char buff13;Node* p = last;while (p) str += (string(itoa(p->val, buff,10) + " -> ");p = p->pre;cout <<

20、(str.substr(0,str.length()-4);friend ostream& operator<<(ostream& out,DLIST& list);friend int swap(elementtype x, DLIST &h);ostream& operator<<(ostream& out,DLIST& list)char buff13;string str;Node* p = list.head;while (p) str += (string(itoa(p->val, buff, 1

21、0) + " -> ");p = p->next;out << (str.substr(0,str.length()-4);return out;int swap(elementtype x, DLIST &h)Node*p = h.head;while (p) if (p->val = x) /p is not the first elementif (p->pre) /p is not the second elementif (p->pre->pre) if (p->next) p->next->

22、;pre = p->pre;Node* tmp = p->pre->pre;p->pre->pre->next = p;p->pre->pre = p;p->pre->next = p->next;p->next = p->pre;p->pre = tmp;elseif (p->next) p->next->pre = p->pre;p->pre->pre = p;p->pre->next = p->next;p->next = p->pre;p

23、->pre = NULL;return 1;p = p->next;return 0;#endif/main.cpp#include<iostream>#include<string>#include<cstdlib>using namespace std;#include "D-list.h"int main(int argc, char* argv)DLIST list;for (int i = 0; i < 10; i+)list.push_back(i);cout << list << e

24、ndl;cout << "=我是萌萌哒的分割线=" << endl;swap(4,list);cout << list << endl;cout << "=我是萌萌哒的分割线=" << endl;list.print_back();cout << endl;cout << "=我是萌萌哒的分割线=" << endl;return 0;/七、试编写一个求三元组顺序表示的稀疏矩阵对角线元素之和的算法/以下为 七 八 九 三题代码#i

25、nclude<iostream>#include<string>#include<vector>using namespace std;class TLIST;class RowList;const int COL = 10;const int ROW = 10;const int R_COL = COL + 1;const int R_ROW = ROW + 1;struct TNODEint row;int col;int val;TNODE(int _row,int _col,int _val):row(_row),col(_col),val(_val

26、);bool operator <(TNODE& a, TNODE& b)if (a.row < b.row)return 1;return (a.col < b.col);TNODE operator +(TNODE& a, TNODE& b)return TNODE(a.row,a.col,a.val+b.val);class TLISTvector<TNODE> s;public:friend int SiagonalSum(TLIST& l);TLIST()TLIST(TLIST& l)s = l.s;voi

27、d push_back(TNODE data)s.push_back(data);void insert(TNODE data)vector<TNODE>:iterator it;for (it = s.begin(); it < s.end(); it+)if (*it) < data)continue;break;if (it = s.end()s.push_back(data);return;if (data.col = it->col && data.row = it->row)it->val += data.val;retur

28、n;s.insert(it, data);TLIST operator+(TLIST& l)TLIST ret;vector<TNODE>:iterator it1 = s.begin(),it2 = l.s.begin(),end1 = s.end(),end2 = l.s.end();while (it1!= end1 && it2 != end2)if (*it1<*it2)ret.push_back(*it1);+it1;continue;if (*it2<*it1)ret.push_back(*it2);+it2;continue;re

29、t.push_back(*it1+*it2);it1+;it2+;while (it1!=end1)ret.push_back(*it1);+it1;while (it2!=end2)ret.push_back(*it2);+it2;return ret;friend ostream& operator<<(ostream& out, TLIST& l);friend RowList;ostream& operator<<(ostream& out, TLIST& l)int col = 1,row = 1;string

30、str;vector<TNODE>:iterator it = l.s.begin(),end = l.s.end();while (it!=end)while (row < it->row)str += "n"row+;col = 1;while (col < it->col)str += " "col+;str += (it->val+'0');it+;while (row < R_ROW)str += "n"row+;out << str;return

31、out;struct Nodeint row, col, val;Node(int _r, int _c, int _v) :row(_r),col(_c),val(_v);class RowListclass _RowList;int dataR_ROW * R_COL;public:RowList()memset(data, 0, sizeof(int) * R_COL * R_ROW);RowList(RowList& l)memcpy(data, l.data, sizeof(int) * R_COL * R_ROW);RowList(TLIST& l)memset(d

32、ata, 0, sizeof(int) * R_COL * R_ROW);vector<TNODE>:iterator it= l.s.begin(),end = l.s.end();while (it!=end)(*this)it->rowit->col += it->val;+it;_RowList operator(int row)return _RowList(data+R_COL*(row);class _RowListint* p;public: _RowList(int* _p) :p(_p)public: int& operator(int

33、 col)return *(p + col);int SiagonalSum(TLIST& l)int ret = 0;vector<TNODE>:iterator it = l.s.begin(),end = l.s.end();while (it!=end)if (it->col && it->row)ret += it->val;+it;return ret;int main(int argc,char* argv)TLIST list1,list2;for (int i = 1; i < 11; i+)list1.push_b

34、ack(TNODE(i, i, 3);list2.push_back(TNODE(i, i, 2);cout << list1 << endl << list2 << endl<<(list1+list2)<<endl;cout << "=欢乐的分割线=" << endl;cout << SiagonalSum(list1) << endl;cout << "=欢乐的分割线=" << endl;RowList r

35、owlist = list1 + list2;for (int i = 1; i < R_ROW; i+)for (int j = 1; j < R_COL; j+)cout << rowlistij << ' 'cout << endl;return 0;/以上为 七 八 九 三题代码八、当具有相同行值和列值的稀疏矩阵A和B均以三元组顺序表方式存储时，试写出矩阵相加的算法，其结果存放在以行逻辑链接顺序表方式存储的矩阵C中。九、设有一个稀疏矩阵：1、写出三元组顺序表存储表示2、写出十字链表存储的顺序表示十、画出广义表LS=( ),

36、 (e), (a, (b, c, d)的头尾链表存储结构(类似于教材P70图2-27.9)。要求：按照教材中的事例画出相应的图形，不需要编程。t 其中第一个节点如下：十一、试编写求广义表中原子元素个数的算法。要求：1、定义广义表的节点的型；2、定义广义表的基本操作；3、定义本题要求的函数int elements(listpointer L)；函数返回值为广义表中原子的个数。例如，广义表(a, b, c, d)原子的个数为4，而广义表(a, (a, b), d, e, (i, j), k)中院子的个数为3。提示：先利用基本操作Cal(L)获得表头，判断表头是不是原子，再利用基本操作Cdr(L)获

37、得除第一个元素外的其他元素所形成的表L1，利用递归的方法求L1中原子的个数。要求：1、上述作业要求在单独完成；2、完成后，于规定期限内提交到ftp服务器的相应目录中中，注意，在提交时将所编写的程序统一拷贝到一个Word文件中，文件名格式为“学号+姓名”。/ listpointer.h#ifndef Wlist#define Wlist#include <iostream>#include <string>using namespace std;#ifdef DEBUG#define COUT_MARK cout<<" DEBUG Line &quo

38、t; << _LINE_ <<endl;#else#define COUT_MARK #endifenum listtypeATOM = 0,LIST = 1;class basetermint val;bool TYPE;public:baseterm(int _val, bool _TYPE):val(_val),TYPE(_TYPE)bool getTYPE()return TYPE;int getval()return val;void setval(int _val)val = _val;void chengeTYPE(bool _TYPE)TYPE = _T

39、YPE;class _list:virtual public baseterm_list* data;int len;int MAX_LEN;void resize( int size )_list* tmp = new _listsize;copy(data,data+len,tmp);delete data;data = tmp;MAX_LEN = size;bool NO_INI;public:_list():baseterm(0, ATOM)NO_INI = true;data = NULL;len = -1;MAX_LEN = -1;_list(int _val, bool _TYP

40、E = ATOM) :baseterm(_val, ATOM)NO_INI = false;if ( ATOM = getTYPE() )data = NULL;len = -1;MAX_LEN = -1;elsedata = new _list10;len = 0;MAX_LEN = 10;_list(_list& source) :baseterm(source.getval(), source.getTYPE()if (ATOM = source.getTYPE()data = NULL;len = -1;MAX_LEN = -1;NO_INI = source.NO_INI;e

41、lsedata = new _listsource.MAX_LEN;len = source.len;MAX_LEN = source.MAX_LEN;copy(source.data, source.data + source.len, data);_list()if (data)delete data;int getMAX_LEN()return MAX_LEN;int getlen()return len;void push_back(int _val)if (NO_INI)setval(_val);NO_INI = false;return;if (ATOM = getTYPE()ch

42、engeTYPE(LIST);data = new _list10;data0 = _list(getval(),ATOM);data1 = _list(_val, ATOM);len = 2;MAX_LEN = 10;elseif (len = MAX_LEN)resize(2 * MAX_LEN);*(data + len) = _val;len+;_list& operator(int pos)return *(data + pos);string toString()if (ATOM = getTYPE()return string(1,getval()+'0');string ret = ""