清华大学《数据结构与算法》

数据结构与算法

一选择题

1.算法的计算量的大小称为计算的（b）。

a.效率b.复杂性c.现实性d.难度

2.下面说法正确的是（c）

（1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度o（n）的算法在时间上总是优于复杂度o（2）的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低

a.（1）b.（1），（2）c.（1），（4）d.（3）

3.连续存储设计时，存储单元的地址（a）。

a.一定连续b.一定不连续c.不一定连续d.部分连续，部分不连续

4.下述哪一条是顺序存储结构的优点。（a）

a.存储密度大b.插入运算方便c.删除运算方便d.可方便地用于各种逻辑结构的存储表示

5.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（a）存储方式最节省时间。

a.顺序表b.双链表c.带头结点的双循环链表d.单循环链表

6.下面的叙述不正确的是（bc）

a.线性表在链式存储时，查找第i个元素的时间同i的值成正比b.线性表在链式存储时，查找第i个元素的时间同i的值无关

c.线性表在顺序存储时，查找第i个元素的时间同i的值成正比d.线性表在顺序存储时，查找第i个元素的时间同i的值无关

7.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（c）（1next==head;d）p->next==0

34.一个栈的输入序列是a，b，c，d，e，则可能的出栈序列是（d）。

a）ecdabb）cebdac）daecbd）abcde

35.设栈s的类型为sqstack，判定栈空的条件是（c）。

a）s==nullb）s->top==0c）s.top==0d）s.top==null

36.深度为5的二叉树至多有个（b）结点。

a）12b）31c）14d）15

37.已知二叉树的后、中根序列分别是bedfca和badecf，则该二叉树的前根遍历序列是（c）。a）defbca

b）fedbcac）abcdefd）fedcba

38.一个有n个顶点的有向图最多有（b）弧。

a）n（n+1）b）n（n-1）c）n（n+1）/2d）n（n-1）/2

39.具有n个顶点的无向图至少要有（b）条边才有可能是一个连通图。

a）n（n+1）b）n-1c）n+1d）n（n-1）

40.图中有关路径的定义是（a）。

a.由顶点和相邻顶点序偶构成的边所形成的序列b.由不同顶点所形成的序列c.由不同边所形成的序列d.上述定义都不是

41.一个向量的第一个元素的地址是100，每个元素的长度是2，则第五个元素的地址是（c）

a）102b）110c）108d）120

42.一个循环顺序队列，队头、尾指针的值分别为front，rear，则队列中元素个数为（a）。（maxlen为循环顺序表的长度）

a）（rear-front+maxlen）%maxlenb）（rear-front）%maxlenc）rear-front+1d）front-rear+1

43.一个有n个顶点的图最少有（d）条边。

a）n（n+1）b）n（n-1）c）n（n+1）/2d）0

44.具有5个顶点的无向图至少要有（a）条边才能确保是一个连通图。

a）4b）5c）6d）7

45.设栈s的类型为sqstack，最多可容纳maxlen个元素，则判定栈满的条件是（b）。

a）s==maxlen-1b）s.top==maxlen-1c）s->top==maxlen-1d）s.top==0