当前位置:首页 >> 其它课程 >>

数据结构基础期末试卷


诚信应考
…………………………………………………………..装………………….订…………………..线……………………………………………………… 班级:_________________ 学号:_______________ 姓名:__________________

考出水平
浙江大学城市学院

考出风格

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、 线性表

《数据结构基础》期末考卷,共 6 页,第 1 页

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 为( )。 10 A、11 B、 C、 11 至 1025 之间 D、 10 至 1024 之间 14.具有 10 个叶结点的二叉树中有( )个度为 2 的结点。 9 11 A、8 B、 C、10 D、 15.一棵完全二叉树上有 1001 个结点,其中叶子结点的个数是( )。 500 501 A、250 B、 C、254 D、 16.下列说法不正确的是( )。 A、 图的遍历是从给定的源点出发每一个顶点仅被访问一次 B、 遍历的基本算法有两种:深度遍历和广度遍历 C、 图的深度遍历不适用于有向图 D、 图的深度遍历是一个递归过程 17.设无向图的顶点个数为 n,则该图最多有( )条边。 n(n-1)/2 n/2 A、n-1 B、 C、n(n+1)/2 D、 18.当一个有 n 个顶点的无向图用邻接矩阵 A 表示时,顶点 Vi 的度是( ) 。 A、

? A[i][ j ]
i ?0

n ?1

B、

? A[i][ j]
j ?0

n ?1

C、

? A[ j ][i]
i ?0

n ?1

D、

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

n ?1

n ?1

j ?0

《数据结构基础》期末考卷,共 6 页,第 2 页

19.一个 n 个顶点的连通无向图,其边的个数至少为( ) 。 n nlogn A、n-1 B、 C、n+1 D、 20.一个有 n 个结点的图,最少有 1 个连通分量,最多有( )个连通分量。 1 n A、0 B、 C、n-1 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. 由3个结点所构成的二叉树有 ⒁ 种形态。 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 分别表示入队和出队操作,请: (1) 写出队空的初始条件; (2) 写出执行操作序列 A3D1A5D2A1D2A2 后 f 和 r 的值。 (注:A3 表示入队 3 次,D1 表示出队 1 次,依次类推)

《数据结构基础》期末考卷,共 6 页,第 3 页

2、一棵二叉树的先序、中序、后序序列如下,其中一部分未标出,请补充完整空缺部分并画出 该二叉树。 先序序列 :A B C D E F G H I J K 中序序列 :C B _ _ F A _ J K I G 后序序列 :_ E F D B _ J I H _ A

3、已知某图的邻接表为: ⑴写出由 v1 开始的广度优先遍历的序列; ⑵写出由 v1 开始的深度优先遍历的序列。

得分

四.程序阅读题(本大题共_3_题,每题_4_分,共_12_分。)

1、阅读下面算法,回答下列问题: ⑴ 写出下列算法的时间复杂度; ⑵ 写出 f(5)的大小。 算法:int f(int n) { int i,j,k,sum= 0; for(i=1; i<n+1;i++) {for(j=n;j>i-1; j--) for(k=1;k<j+1;k++ ) sum++; } return (sum); } 2、写出下面算法的功能 void Fun(Queue q1,Queue q2,int n) { int i,x; cout << "从键盘输入" << n << "个整数:"<<endl; for(i=0;i<n;i++){ cin >> x; if (x%2) EnQueue(q1,x); else EnQueue(q2,x); } }
《数据结构基础》期末考卷,共 6 页,第 4 页

3、指出下面函数的功能。 void preserve(BTreeNode *BT,ElemType a[]) { static int i = 0; if (BT){ preserve(BT->left,a); a[i++] = BT->data; preserve(BT->right,a); } } 五.程序填空题(本大题共_7_空,每空_2_分,共_14_分。) 得分

1. 以下函数是实现二叉树的中序遍历的非递归算法。请在空白处填入适当的语句, 使算法完整。
提示: 二叉树中序遍历的非递归算法就是运用栈这种数据结构将递归的中序遍历转换成非递归 的中序遍历,采用的是间接转换方式。中序遍历非递归算法的 N-S 流程图如下:
初始化栈 S 指针 p 指向根结点指针 T p 非空或栈非空 p 非空 Y p 进栈 p 指向 p 的左孩子 元素出栈存入 p 输出 p 指向的结点的值 p 指向 p 的右孩子 N

#define maxsize 100 typedef struct { BTNode *Elem[maxsize]; int top; }Stack; void InOrderUnrec(BTNode *t) { Stack s; BTNode *p; InitStack (s); ⑴ ; while (p!=null || !StackEmpty(s)) { while ( ⑵ )
《数据结构基础》期末考卷,共 6 页,第 5 页

{ push(s,p); ⑶ ;

} if (!StackEmpty(s)) { p=pop(s); cout << p->data <<' '; ⑷ ; } } } 2、下面程序的功能是返回二叉树 BT 中值为 X 的节点所在的层号,请在划线的地方填写合适的 内容。 int NodeLevel(BTreeNode *BT,ElemType x) { if (BT==NULL) return 0; //空树的层号为 0 else if(BT->data==x) return 1; //根结点的层号为 1 else { //向子树中查找 x 结点 int c1 = NodeLevel(BT->left,x); if (c1>=1) ⑸ ; int c2 = ⑹ ; if (c2>=1) ⑺ ; //若树中不存在 x 结点则返回 0 return 0; } } 六.算法设计题(本大题共 2 题,第 1 题 6 分,第 2 题 10 分,共 16 分。) 得分

1、根据下面函数声明编写从一棵二叉树 BT 中求出结点值大于 x 的结点个数的算法,并返回所 求结果。 int BTreeCount(BTreeNode *BT, ElemType x); 2、设有一个长度大于 1 的单向循环链表,该链表既无头结点,也无头指针,s 为指向表中某个 结点的指针,如图所示。试编写一个算法,删除链表中指针 s 所指结点的直接前驱。

《数据结构基础》期末考卷,共 6 页,第 6 页



相关文章:
2010-2011第1学期数据结构基础期末考卷
学年第一学期期末考试试卷数据结构基础 》 开课单位:计算学院 ;考试形式:闭卷;考试时间:_2011_年__1__月__16__日; 所需时间: 120 分钟 题序 得分...
2015河北省数据结构基础试题及答案
2015河北省数据结构基础试题及答案_韩语学习_外语学习_教育专区。2015河北省数据结构基础试题及答案 1、向一个栈顶指针为 hs 的链栈中插入一个 s 结点时,应执行...
2011-2012第1学期数据结构基础期末考卷 2
《 学期期末考试试卷数据结构基础 开课单位: 计算分院 ;考试形式:闭卷;考试时间: 2012 年 1 月 3 日; 所需时间: 120 分钟 题序 得分 评卷人 得分 ...
2007-2008第1学期数据结构基础期末考卷
学期期末 学期期末考试试卷数据结构基础 》开课单位: 计算分院 ;考试形式:闭卷;考试时间: 2008 年 1 月 11 日; 所需时间: 120 分钟 题序 得分 评卷...
数据结构模拟题答案
数据结构模拟题答案_电脑基础知识_IT/计算机_专业资料。第 1 页 数据结构模拟试题答案一.选择题(每题 2 分,共 20 分) (请将答案填写到表格中) 1.数据结构...
2007-2008第1学期数据结构基础期末考卷_06级 2
《 学期期末考试试卷数据结构基础 开课单位: 计算分院 ;考试形式:闭卷;考试时间: 2008 年 1 月 11 日; 所需时间: 120 分钟 题序 得分 评卷人 得分...
数据结构基础期中考卷
学期期中考试试卷数据结构基础 》开课单位: 计算分院 ;考试形式:闭卷;考试时间: 2007 年 11 月 10 日; 所需时间: 120 分钟 题序 一二三四五六总分 ...
(答案)数据结构复习试卷一
(答案)数据结构复习试卷一 - 《数据结构》答案(试一. 简述下列术语(14 分) 卷 1) 数据类型: 是一个值的集合和定义在这个值集上的一组操作的总称。 在用...
数据结构试卷及答案
树的基本遍历策略分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历...2012 年数据结构期末考试题及答案 一、选择题 1.在数据结构中,从逻辑上可以把...
数据结构试题_试卷一_已填答案
数据结构试题_试卷一_已填答案_电脑基础知识_IT/计算机_专业资料。模拟试题 一 模拟试题一一、选择题(30 分) 1.组成数据的基本单位是( C )。 A)数据项 B)...
更多相关标签: