内容发布更新时间 : 2024/11/16 17:48:24星期一 下面是文章的全部内容请认真阅读。

_…__…__…__…__…__…__…__…__…_：…名…姓…… __…__…__…__…__…__…__…_：…号线..学… _…__…__…__…__…__…__ 订.__…__…：…级…班… …__…__装_..__…__…__…__…__…__…__…__…：…业…专… _…__…__…__…__…__…__…：…级…年……

诚信应考 考出水平 考出风格

浙江大学城市学院

2010 — 2011 学年第一学期期末考试试卷

《 数据结构基础 》

开课单位：计算学院 ；考试形式：闭卷；考试时间：_2011_年__1__月__16__日； 所需时间： 120 分钟 题序 一 二 三 四 五 六 七 八 总 分 得分 评卷人 注：答案请写在答卷上，写在试卷上无效。

得分 一．单项选择题 (本大题共_20_题，每题_1_分，共_20_分。)

1.数据结构主要研究数据的( )。

A、 逻辑结构 B、 存储结构 C、 逻辑结构和存储结构 D、 逻辑结构和存储结构及其运算的实现 2.算法在发生非法操作时可以做出处理的特性称为( )。

A、 正确性 B、 易读性 C、 健壮性 D、 可靠性 3.下面的程序段违反了算法的( )原则。 void sam() { int n=2;

while (n%2==0) n+=2; printf(n); }

A、 有穷性 B、 确定性 C、 可行性 D、 健壮性 4.线性表是具有n个( )的有限序列。

A、 表元素 B、 字符 C、 数据元素 D、 数据项 5.用单链表表示的链式队列的对头在链表的( )位置。

A、 链头 B、 链尾 C、 链中 D、 任意 6.递归过程或函数调用时，处理参数及返回地址，要用一种称为( )的数据结构。

A、 队列 B、 多维数组 C、 栈 D、 线性表

7.以下叙述中哪个选项是不正确的。( )

A、 顺序存储方式只能用于存储线性结构。

B、 顺序查找法适用于存储结构为顺序或链接存储的线性表。 C、 栈和队列都是限制取点的线性结构 D、 消除递归不一定需要使用栈 8.循环链表的主要优点是( )。

A、 不再需要头指针了

B、 已知某个结点的位置后，能很容易找到它的直接前驱结点 C、 在进行删除操作后，能保证链表不断开 D、 从表中任一结点出发都能遍历整个链表

9.在一个单链表中，若要删除P结点的后继结点，则执行的语句是( )。

A、 p->next=p->next->next

B、 p=p->next；p->next=p->next->next; C、 p->next=p->next; D、 p=p->next->next;

10.设计一个判别表达式中左，右括号是否配对出现的算法，采用( )数据结构最佳。

A、 线性表的顺序存储结构 B、 队列 C、 线性表的链式存储结构 D、 栈

11.输入序列为ABC，可以变为CBA 时，经过的栈操作为( )。

A、 push,pop,push,pop,push,pop B、 push,push,push,pop,pop,pop C、 push,push,pop,pop,push,pop D、 push,pop,push,push,pop,pop 12.用链接方式存储的队列，在进行删除运算时( )。

A、 仅修改头指针 B、 仅修改尾指针 C、 头尾指针都要修改 D、 头、尾指针可能都要修改 13.一个具有1025 个结点的二叉树的高h 为( )。

11 10 A、 B、 C、 11 至1025 之间 D、10 至1024 之间

14.具有10 个叶结点的二叉树中有( )个度为2 的结点。

8 9 10 11 A、 B、 C、 D、

15.一棵完全二叉树上有1001 个结点，其中叶子结点的个数是( )。

250 500 254 501 A、 B、 C、 D、

16.下列说法不正确的是( )。

A、 图的遍历是从给定的源点出发每一个顶点仅被访问一次 B、 遍历的基本算法有两种：深度遍历和广度遍历 C、 图的深度遍历不适用于有向图 D、 图的深度遍历是一个递归过程

17.设无向图的顶点个数为n，则该图最多有（ ）条边。

n-1 n(n-1)/2 n(n+1)/2 n/2 A、 B、 C、 D、

18．当一个有n 个顶点的无向图用邻接矩阵A 表示时，顶点Vi 的度是（ ）。

A、

?A[i][j]

i?0n?1B、

?A[i][j]

j?0n?1

C、

?A[j][i]

i?0n?1D、

?A[i][j]+?A[j][i]

i?0n?1n?1j?019．一个n 个顶点的连通无向图，其边的个数至少为（ ）。

n-1 n n+1 nlogn A、 B、 C、 D、

20．一个有n 个结点的图，最少有1个连通分量，最多有（ ）个连通分量。

0 1 n-1 n A、 B、 C、 D、

得分 二．填空题(本大题共_20_空，每空_1_分，共_20_分。)

1.一个算法的效率可分为 ⑴ 效率和 ⑵ 效率。

2. 在顺序表中访问任意一结点的时间复杂度均为 ⑶ ，因此，顺序表也称为随机存取的数据结构。

3． 在n个结点的单链表中要删除已知结点*p，需找到它的 ⑷ 的地址，其时间复杂度为 ⑸ 。

4.线性表中结点的集合是有限的，结点间的关系是 ⑹ 的。

5. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 ⑺ 个元素。

6.在非空双向循环表中q所指的结点后面插入p所指的结点的过程已经依次进行了3步：p->prior=q；p->next=q->next；q->next=p；第4步应该是 ⑻ 。

7.栈是一种特殊的线性表，允许插入和删除运算的一端称为 ⑼ 。不允许插入和删除运算的一端称为 ⑽ 。

8.设Q[0..N-1]为循环队列，其头、尾指针分别为front 和rear，则队列Q 中当前所含元素个数为 ⑾ 。

9. 从循环队列中删除一个元素时，其操作是先 ⑿ ，后取出元素。 10. 一棵具有257个结点的完全二叉树，它的深度为 ⒀ 。 11. 由３个结点所构成的二叉树有 ⒁ 种形态。

12.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树总共有 ⒂ 个叶子结点。

13.树的后根遍历结果等价于所对应二叉树的 ⒃ 遍历。 14.设有一稠密图G，则G采用 ⒄ 存储较省空间。

15. n个顶点e条边的图，若采用邻接表存储，若对该图进行深度优先搜索遍历，则其时间复杂度为 ⒅ 。

16.在一个无向图中，所有顶点的度数之和等于所有边数 ⒆ 倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的 ⒇ 倍。

得分 三．解答题(本大题共_3_题，每题_6_分，共_18_分。)

1、假设以数组Queue[0..7]存放循环队列元素,变量f 指向队头元素的前一位置,变量r 指向队尾元素，如用A 和D 分别表示入队和出队操作，请：