2002级数据结构及算法分析半期试题.doc

四川大学计算机学院2002级数据结构及算法分析半期试题学院_学号_姓名_一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题1分，共10分）1假设执行语句S的时间为O（1），则执行下列程序段for(i=1;i=n;i+) for(j=i;jnext=p-next; p-next=s;B）q-next=s; s-next=p;C）p-next=s-next; s-next=p;D）p-next=s; s-next=q;4串S=”ABC DEF”的串长为（ ）。A）3B）4C）7D）85若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是( )。A)O(1) B)O(n) C)O(n2)D)O(nlog2n)6在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则平均比较( )。个结点。A)n B)n2C)(n-1)2 D)(n+1)27研究数据结构就是研究( )。A 数据的逻辑结构B 数据的存储结构C 数据的逻辑结构和存储结构D 数据的逻辑结构、存储结构及其数据在运算上的实现8二维数组A1020，510采用行序为主序方式存储，每个数据元素占4个存储单元，且A105的存储地址是1000，则A189的地址是（ ）。A）1208B）1212C）1368D）13649利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来： L1(apple, pear, banana, orange)A）Head (Tail (Tail (L1) ) )B）Head(Head(Tail (Tail (L1) ) )C）Head(Tail (Tail (Tail (L1) ) )D）Head (Head (Tail (L1) ) )10如下陈述中正确的是（ ）。A）串是一种特殊的线性表B）串的长度必须大于零C）串中的元素只能是字母D）空串就是空白串二、填空题（每空1分，共15分）1当一个传值型形式参数所占空间较大时，最好说明为( )，以节省参数值传输时间和存储参数的空间。2一个算法的时间复杂度为(5n6-3n2log2n+7n-9)/(3n2+1)，其数量级表示为( )。3有一矩阵为a-3:1,2:6，每个元素占一个存储单元，存储的首地址为100，以行序为主，则元素a(-1,4)的地址为（ ）。4一维数组的逻辑结构是（ ）。5在有n个结点的单链表la中，删除指定结点p的操作delete(la,p)的时间复杂度为（ ）。6栈的插入与删除操作在( )进行，出栈操作时，需要修改 ( )。7表达式3*(x+2) - 5的后缀表达式为（ ）。8假设有一个9阶上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B0存储矩阵中第一个元素A，则B31中存放的元素是( )。9 数据的逻辑结构是从逻辑关系上描述数椐，它与数据的( )无关，是独立于计算机的。10设head为单链表的头结点，则判断单链表为空的条件是( )。11在具有n个单元的循环队列中，队满时共有( )个元素。12设有一个顺序栈S，元素s,s,s,s,s,s依次进栈，如果6个元素的出栈序列为s,s,s,s,s, s,则顺序栈的容量至少为（ ）。13广义表A=(a，b，A)的长度为( )，其深度为( )。三、判断改错题（判断正误，将正确的划上“”，错误的划上“”，每小题1分，共10分）1数据的逻辑结构是指数据元素之间的逻辑关系。（）2数组不是一种随机存取结构。（）3顺序表在物理存储空间中一定是连续的。（）4设一个栈的入栈序列是ABCD，则借助于一个栈能得出栈序列ACDB。（）5串的长度是指串中不同字符的个数。（）6矩阵压缩存储的方法都是用三元组表存储矩阵元素。（）7具有线性序关系的集合中，若a，b是集合中的任意两个原子，则必定有a F) /*注：按C+的优先级*/4画出下列广义表的图形表示和它们的存储表示：(1) D(A(c), B(e), C(a, L(b, c, d)(2) J1(J2(J1, a, J3(J1), J3(J1) 5稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。稀疏矩阵有多少行，在行指针数组中就有多少个元素：第i个元素的数组下标i代表矩阵的第i行，元素的内容即为稀疏矩阵第i行的第一个非零元素在二元组表中的存放位置。二元组表中每个二元组只记录非零元素的列号和元素值，且各二元组按行号递增的顺序排列。试对右图所示的稀疏矩阵，分别建立它的三元组表和带行指针数组的二元组表。五、算法题（共25分）1 程序填空题(每空2分，共8分)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同，如果last不合理则显示出错信息并退出运行，实现从表中删除所有其值重复的元素的函数如下：template void SeqList : DelDouble ( ) if ( last = -1 ) cerr “List is empty!” endl; _; int i = 0, j, k; Type temp; while ( i = last ) /循环检测 j = i + 1; temp = datai; while (_) /对于每一个i, 重复检测一遍后续元素if ( temp = dataj ) /如果相等, 后续元素前移 for ( k = j+1; k = last; k+ ) _; last-; /表最后元素位置减1else_ i+;/检测完datai, 检测下一个 2程序填空题(每空2分，共8分)编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。include include string.hvoid frequency( String& s, char& A , int& C , int &k ) / s是输入字符串，数组A 中记录字符串中有多少种不同的字符，C 中记录每/一种字符的出现次数。这两个数组都应在调用程序中定义。k返回不同字符数。int i, j, len = s.length( );if ( !len ) cout The string is empty. endl; k = 0; return; else A0 = s0; C0 = 1; k = 1; /*语句si是串的重载操作*/ for ( i = 1; i len; i+ )_; /*初始化*/ for ( i = 1; i len; i+ ) /*检测串中所有字符*/ j = 0; while ( j k & Aj != si ) j+;/*检查si是否已在A 中*/ if ( j = k ) _; Ck+;_ /*si从未检测过*/ else_; /*si已经检测过*/ 测试数据 s = cast cast sat at a tasa0测试结果 A c a s t b C 2 7 4 5 53(9分)阅读下面的算法，试回答：（1）此算法的功能是什么？（2），若串s为“aabbabcbaabaaacbab”，串t为“bab”，串v为“abdc”，则执行replace操作后，串s中的结果为：String & String : Replace ( String & t, String &v) if ( ( int id = Find ( t ) ) = -1 ) /没有找到，当前字符串不改，返回 cout The (replace) operation failed. endl; return *this; String temp( ch );/用当前串建立一个空的临时字符串 ch0 = 0; curLen = 0;/当前串作为结果串，初始为空 int j, k = 0, l;/存放结果串的指针 while ( id != -1 ) for ( j = 0; j id; j+) chk+ = temp.chj;/摘取temp.ch中匹配位置 if ( curLen+ id + v.curLen = maxLen ) l = v.curLen;/确定替换串v传送字符数l else l = maxLen- curLen- id; for ( j = 0; j l; j+ ) chk+ = v.chj;/连接替换串v到结果串ch后面 curLen += id + l;/修改结果串连接后的长度 if ( curLen = maxLen ) break;/字符串超出范围 for ( j = id + t.curLen; j temp.curLen; j+ ) temp.chj- id - t.curLen = temp.chj;/删改原来的字符串 temp.curLen -= id + t.curLen; id = temp.Find ( t ); return *this;六、写算法（共20分）1(12分) 设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。2(8分) 若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的插入(enqueue)和删除(dequeue)算法，并给出p为何值时队列空。【解答】链式队列的类定义template class Queue;/链式队列类的前视定义template class QueueNode /链式队列结点类定义friend class Queue;private: Type data;/数据域 QueueNode *link;/链域public: QueueNode ( Type d = 0, QueueNode *l = NULL ) : data (d), link (l) /构造函数;template class Queue /链式队列类定义public: Queue ( ) : p ( NULL ) /构造函数 Queue ( );/析构函数 void EnQueue ( const Type & item );/将item加入到队列中 Type DeQueue ( );/删除并返回队头元素 Type GetFront ( );/查看队头元素的值 void MakeEmpty ( );/置空队列，实现与Queue ( ) 相同 int IsEmpty ( ) const return p = NULL; /判队列空否private: QueueNod