计130121第二次作业.doc

第二次作业一、选择题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-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表示一个循环队列，如果当前的尾指针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(mn)10、已知串S=“abab”，其Next数组值为 0012 。A. 0123B. 0121C. 0112D. 012211、若字符串“ABCDEFG”采用不带表头的链式存储，每个结点保存一个字符。假设每个字符占用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-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元素依次进队，则不可能得到的顺序是 C 。A. bacdeB. dbaceC. dbcaeD. ecbad15、在双向链表中间插入一个结点时，需要修改修改 D 个指针域。A. 1B. 2C. 3D. 416、在按行优先顺序存储的三元组表中，下述陈述错误的是 D 。A. 同一行的非零元素，是按列号递增次序存储的B. 同一列的非零元素，是按行号递增次序存储的C. 三元组表中三元组行号是非递减的D. 三元组表中三元组列号是非递减的17、在稀疏矩阵的三元组表示法中，每个三元组表示 D 。A. 矩阵中非零元素的值B. 矩阵中数据元素的行号和列号C. 矩阵中数据元素的行号、列号和值D. 矩阵中非零数据元素的行号、列号和值18、对特殊矩阵采用压缩存储的目的主要是为了 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 。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”，则Length(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, (i, j), k)的长度是 5 ，深度是 3 。11、设广义表A( ( ( ), (a, (b), c) )2 )1，则Cal(Cdr(Cal(Cdr(Cal(A)= (b ) 三、设有一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的计数器count，试写出相应的判断队列空、判断队列满、出队算法和入队算法。要求：1、定义相应的循环队列的型（只有头指针，没有尾指针，但有一个元素个数的计数器）；2、定义该队列的四个算法：判断队列空、判断队列满、出队算法和入队算法；3、在main函数验证算法的正确性。/#include using namespace std;typedef 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(int argc, char *argv) Queue q;int i;for ( i = 0; i 10; i+) q.push_back(i);for ( i = 0; i 10; i+) coutq.font()endl;q.pop_font();cout=欢乐的分割线=endl;for ( i = 0; i 10; i+) q.push_back(i);for ( i = 0; i 10; i+) coutq.font()endl;q.pop_font();return 0;/四、设主串T=“abcaabbabcabaacbacba“，模式为p=“abcabaa”。 1、计算模式p的nextval函数值2、不写算法，只画出利用KMP算法进行模式匹配时，每一趟的匹配过程。要求：1、写出模式p的nextval值；2、画出KMP算法的每一趟匹配过程（可参照教材P61从第8行开始的内容）；3、不需要编写程序。0001211五、假设表达式中允许包含三种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈（用数组表示的栈）判断表达式中的括号是否正确配对。要求： 1、定义栈以及栈的型，栈中所存放元素的类型为字符型，定义枚举类型Boolean，其中两个元素分别为TRUE和FALSE。2、定义栈的各种操作。3、定义函数Boolean check(char *s); 判断s中的括号是否正确配对，如果正确配对，返回TRUE，否则返回FALSE。4、在主函数中验证所编写函数的正确性。/#include #include using namespace std;typedef stack STACK;enum BooleanFALSE = 0,TRUE = 1;Boolean check(char *s)STACK _;while (*s) switch (*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 (_.empty() return TRUE;elsereturn FALSE;/return _.empty();int main(int argc, char *argv) char *data1 = 123()owsanfak1(234sff)1faer;char *data2 = 12(3owsanfak1)234sff1faer;coutcheck(data1)endlcheck(data2)val);p = p-next;DLIST()Node* p;while (head) p = head;head = head-next;delete p;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 (str.substr(0,str.length()-4);friend ostream& operator(ostream& out,DLIST& list);friend int swap(elementtype x, DLIST &h);ostream& operatorval, buff, 10) + - );p = p-next;out val = x) /p is not the first elementif (p-pre) /p is not the second elementif (p-pre-pre) if (p-next) p-next-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-pre = NULL;return 1;p = p-next;return 0;#endif/main.cpp#include#include#includeusing namespace std;#include D-list.hint main(int argc, char* argv)DLIST list;for (int i = 0; i 10; i+)list.push_back(i);cout list endl;cout =我是萌萌哒的分割线= endl;swap(4,list);cout list endl;cout =我是萌萌哒的分割线= endl;list.print_back();cout endl;cout =我是萌萌哒的分割线= endl;return 0;/七、试编写一个求三元组顺序表示的稀疏矩阵对角线元素之和的算法/以下为 七 八 九 三题代码#include#include#includeusing 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);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 s;public:friend int SiagonalSum(TLIST& l);TLIST()TLIST(TLIST& l)s = l.s;void push_back(TNODE data)s.push_back(data);void insert(TNODE data)vector:iterator it;for (it = s.begin(); it s.end(); it+)if (*it) col & data.row = it-row)it-val += data.val;return;s.insert(it, data);TLIST operator+(TLIST& l)TLIST ret;vector: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;ret.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 str;vector:iterator it = l.s.begin(),end = l.s.end();while (it!=end)while (row row)str += n;row+;col = 1;while (col col)str += ;col+;str += (it-val+0);it+;while (row R_ROW)str += n;row+;out str;return 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(data, 0, sizeof(int) * R_COL * R_ROW);vector: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 col)return *(p + col);int SiagonalSum(TLIST& l)int ret = 0;vector: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_back(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 rowlist = 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=( ), (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)获得除第一个元素外的其他元素所形成的表L1，利用递归的方法求L1中原子的个数。要求：1、上述作业要求在单独完成；2、完成后，于规定期限内提交到ftp服务器的相应目录中中，注意，在提交时将所编写的程序统一拷贝到一个Word文件中，文件名格式为“学号+姓名”。/ listpointer.h#ifndef Wlist#define Wlist#include #include using namespace std;#ifdef DEBUG#define COUT_MA