2010-2011第1学期数据结构基础期末考卷.doc

诚信应考 考出水平 考出风格 浙江大学城市学院 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 为( )。 A、 11 B、 10 C、 11 至1025 之间 D、 10 至1024 之间 14.具有10 个叶结点的二叉树中有( )个度为2 的结点。 A、 8 B、 9 C、 10 D、 11 15.一棵完全二叉树上有1001 个结点，其中叶子结点的个数是( )。 A、 250 B、 500 C、 254 D、 501 16.下列说法不正确的是( )。 A、 图的遍历是从给定的源点出发每一个顶点仅被访问一次 B、 遍历的基本算法有两种：深度遍历和广度遍历 C、 图的深度遍历不适用于有向图 D、 图的深度遍历是一个递归过程 17.设无向图的顶点个数为n，则该图最多有（ ）条边。 A、 n-1 B、 n(n-1)/2 C、 n(n+1)/2 D、 n/2 18．当一个有n 个顶点的无向图用邻接矩阵A 表示时，顶点Vi 的度是（ ）。 A、 B、 C、 D、 + 19．一个n 个顶点的连通无向图，其边的个数至少为（ ）。 A、 n-1 B、 n C、 n+1 D、 nlogn 20．一个有n 个结点的图，最少有1个连通分量，最多有（ ）个连通分量。 A、 0 B、 1 C、 n-1 D、 n 得分 二．填空题(本大题共_20_空，每空_1_分，共_20_分。) 1.一个算法的效率可分为 ⑴ 效率和 ⑵ 效率。 2. 在顺序表中访问任意一结点的时间复杂度均为 ⑶