《2002级数据结构及算法分析半期试题》由会员分享，可在线阅读，更多相关《2002级数据结构及算法分析半期试题（7页珍藏版）》请在金锄头文库上搜索。
1、1四川大学计算机学院 2002 级数据结构及算法分析半期试题学院_学号_姓名_一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题 1分，共 10分）1假设执行语句 S 的时间为 O（1） ，则执行下列程序段for(i=1;inext=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）3 B）4C）7 D）85若给定有 n 个元素的向量，则建立一个有序单向链表的时间复杂性的量级
2、是( )。A)O(1) B)O(n) C)O(n2) D)O(nlog2n)6在一个具有 n 个结点的单链表中查找值为 m 的某结点，若查找成功，则平均比较( )。个结点。A)n B)n2 C)(n-1)2 D)(n+1)27研究数据结构就是研究( )。A 数据的逻辑结构B 数据的存储结构C 数据的逻辑结构和存储结构D 数据的逻辑结构、存储结构及其数据在运算上的实现8二维数组 A10 20，5 10 采用行序为主序方式存储，每个数据元素占 4 个存储单元，且 A105的存储地址是 1000，则 A189的地址是（ ） 。2A）1208 B）1212C）1368 D）13649利用广义表的 he
3、ad 和 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当一个传值型形式参数所占空间较大时，
4、最好说明为( )，以节省参数值传输时间和存储参数的空间。2一个算法的时间复杂度为(5n 6-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 按
5、列优先顺序压缩存储在一维数组 B 中，其中 B0存储矩阵中第一个元素 A ，则 B31中存放的元素是( )。1,9 数据的逻辑结构是从逻辑关系上描述数椐，它与数据的( )无关，是独立于计算机的。10设 head 为单链表的头结点，则判断单链表为空的条件是 ( )。11在具有 n 个单元的循环队列中，队满时共有( )个元素。12设有一个顺序栈 S，元素 s ,s ,s ,s ,s ,s 依次进栈，如果 6 个元素的出栈序列123456为 s ,s ,s ,s ,s , s ,则顺序栈的容量至少为（ ） 。23465113广义表 A=(a，b，A) 的长度为 ( )，其深度为( )。三、判断改错题
6、（判断正误，将正确的划上“” ，错误的划上“” ，每小题 1 分，共 10 分）1数据的逻辑结构是指数据元素之间的逻辑关系。 （ ）2数组不是一种随机存取结构。 （ ）33顺序表在物理存储空间中一定是连续的。 （ ）4设一个栈的入栈序列是 ABCD，则借助于一个栈能得出栈序列 ACDB。 （）5串的长度是指串中不同字符的个数。 （ ）6矩阵压缩存储的方法都是用三元组表存储矩阵元素。 （）7具有线性序关系的集合中，若 a，b 是集合中的任意两个原子，则必定有 a F) /*注：按 C+的优先级*/4画出下列广义表的图形表示和它们的存储表示：(1) D(A(c), B(e), C(a, L(b,
7、c, d)(2) J1(J2(J1, a, J3(J1), J3(J1) 5稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。稀疏矩阵有多少行，在行指针数组中就有多少个元素：第 i 个元素的数组下标 i 代表矩阵的第 i 行，元素的内容即为稀疏矩阵第 i 行的第一个非零元素在二元组表中的存放位置。二元组表中每个二元组只记录非零元素的列号和元素值，且各二元组按行号递增的顺序排列。试对右图所示的稀疏矩阵，分别建立它的三元组表和带行指针数组的二元组表。五、算法题（共 25 分）1 程序填空题(每空 2 分，共 8 分)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同，如果 last 不
8、合理则显示出错信息并退出运行，实现从表中删除所有其值重复的元素的函数如下：template void SeqList : DelDouble ( ) if ( last = -1 ) cerr 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 class Queue
9、; /链式队列类的前视定义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 &
10、item ); /将 item 加入到队列中Type DeQueue ( ); /删除并返回队头元素Type GetFront ( ); /查看队头元素的值void MakeEmpty ( ); /置空队列，实现与Queue ( ) 相同int IsEmpty ( ) const return p = NULL; /判队列空否private: QueueNode *p; /队尾指针（在循环链表中）;队列的析构函数template Queue:Queue ( ) /队列的析构函数QueueNode *s;while ( p != NULL ) s = p; p = p-link; delete s; /逐个删除队列中的结点队列的插入函数template void Queue:EnQueue ( const Type & item ) 7队列的删除函数template Type Queue:DeQueue ( )
