当前位置：文档之家 › 2009年春城市科技学院《数据结构》重修试题(B卷)(标准版)

2009年春城市科技学院《数据结构》重修试题(B卷)(标准版)

  • 格式：doc
  • 大小：104.00 KB
  • 文档页数：3

重 庆 大 学 城 市 科 技 学 院
《 数据结构 》课程重修试卷
2008 ~2009 学年 第 一 学期
开课学院： 电气工程 课程号： 考试日期：
考试方式：
考试时间： 分钟
一、单项选择题：（每题1分，共16分）
1、下列各项中不属于算法设计要求的是 （ ） A 、至少有一个输出 B 、正确性 C 、可读性 D 、健壮性
2、下列算法的时间复杂度中最差的是 （ ） A 、O(n) B 、O(n log 2n) C 、O(log 2n) D 、O(2n )
3、线性表中，元素间的逻辑关系的特点是 （ ） A 、一对一 B 、多对多 C 、多对一、一对多 D 、都不是
4、链接存储的线性表，称为链表。

它不能作的操作是 （ ） A 、插入和删除 B 、修改元素值 C 、查找 D 、直接访问
5、P 指针指向了带表头结点head 的单链表中的某个结点，S 指向了同类型的一个结点，以下代码系列的操作是 （ ）
S->next=P->next; P ->next= S ;
A 、删除在P 结点之后的S 结点。

B 、删除在P 结点之前的S 结点。

C 、在P 结点之前插入S 结点。

D 、在P 结点之后插入S 结点。

6、L 为双向链表，P 指向了其中某个中间结点，S 为与P 同类型的指针，以下代码系列的操作是 （ ）
S =P->next; P->next=S->next ; P->next ->prior =P ; free(S) ;
A 、删除P 结点的直接前趋S 。

B 、删除P 结点的直接后继S 。

C 、在P 结点之前插入S 结点。

D 、在P 结点之后插入S 结点。

7、5×5的三对角矩阵的非0元素的个数为 （ ） A 、12个 B 、13个 C 、14个 D 、15个
8、对二叉排序树遍历能得到一个升序系列的遍历方法是 （ ） A 、层次遍历 B 、先根遍历 C 、中根遍历 D 、后根遍历
9、下面对完全二叉树的描述正确的是 （ ）。

A 、一定是满二叉树 B 、可能是满二叉树 C 、不是二叉树 D 、一定不是满二叉树
10、下面有关二叉树的描述不正确的是 （ ） A 、是度为2的树 B 、是有序树 C 、可以是空树 D 、它的度不超过2 11、4个顶点的无向完全图中，每个顶点的度都是 （ ） A 、2 B 、3 C 、4 D 、5
12、从下列4个先序遍历二叉排序树系列中可见，是平衡二叉排序树的是（ ） A 、4 18 25 32 54 72 B 、72 54 25 32 18 4 C 、32 18 4 25 54 72 D 、18 4 25 32 72 54
13、将关键字系列：32 18 25 54 72 4排成升序。

在快速排序进行了第一趟结束
之后的数据系列是 （ ） A 、4 18 25 32 54 72 B 、72 54 25 32 18 4 C 、18 32 25 54 4 72 D 、4 18 25 32 72 54
14、将关键字系列：32 18 25 54 72 4，建成大根堆后的数据系列是（ ） A 、4 18 25 32 54 72 B 、72 54 25 32 18 4 C 、72 32 25 54 4 18 D 、4 18 25 32 72 54
15、在下列排序方法中，哪一种是稳定的 （ ） A 、直接插入法 B 、希尔法 C 、堆排序 D 、快速排序
16、下列排序方法中不属于就地排序的是 （ ） A 、直接选择 B 、希尔法 C 、归并 D 、快速 二、填空题（每小题2分，每空1分，共26分） 1、，若顺序栈的栈顶下标top 初始值为0则栈空的条件是 ；若顺序队
列的队头下标front 和队尾下标rear 初始值均为0，则队列空的条件是 。

2、a 为5×5的对称矩阵，将其包含主对角线的下三角压缩存储在一维数组s[15]中，
s[0]中存储的是a[0][0]元素，则元素a[2][3]存储在 中，元素a[3][1]存储在 中。

3、一棵非空二叉树，第3层上最多有 个结点。

高度为5的二叉树的最大
结点个数为 个。

4、对于完全二叉树，既可以采用 存储也可以采用 存储。

5、在有30个结点顺序存储的完全二叉树中，若根结点的序号为1，则序号为11的结
点的双亲结点的序号为 。

序号为14的结点的右孩子结点的序号为 。

6、图（a ）所示的树中，在中序遍历时E 结点的直接前趋结点是 ，直接后
命题人：王炳华
组题人：
审
题人：
命题时间：2008。

12
教务处制
学院 专业、班 年级 学号 姓名
公平竞争、诚实守信、严肃考纪、拒绝作弊
封
线
密
继结点是 。

7、图（a ）中，先根遍历时D 结点的直接前趋结点是 ，直接后继结点是 。

8、对二叉树采用链接存储时，结点的结构体类型中，至少应有两个指针。

一个用于指
向它的 ，另一个用于指向它的 。

9、5个顶点的无向完全图中有 条边。

4个顶点的有向完全图中有 条边。

10、在图（b ）所示的无向图中，若从顶点v1出发对其进行深度优先遍历（当同一顶
点有多个未遍历的邻接顶点时，先遍历序号小的顶点）时，则遍历得到的系列是 。

若是进行广度优先遍历，则得到的遍历系列是 。

11、若图（c ）所示的AOV 网中，各个顶点的字符代表的某个专业的课程编号，则该专业第一学期可以安排的课程的编号是 ，第二学期可以安排的课程的编号是 。

12、数据元素的数据项若能标识这个数据元素，则称该数据项是一个 。

其中能唯一地标识一个数据元素者，称为 。

13、分块查找是先在 中查找待查关键字所在的块，然后在查找表中它所
在块的子表中进行 查找。

三、多项选择题（错选和漏选均不得分，每小题2分，共6分）
1、数据的逻辑结构分成的两大类是 （ ）
A 、线性结构
B 、树结构
C 、图结构
D 、非线性结构
2、下面可作为满二叉树的定义的叙述是 （ ） A 、叶子结点都在最下层的二叉树 B 、没有度为1的结点的二叉树 C 、当深度为K 时，结点个数为2K -1的二叉树 D 、没有度为1的结点且叶子结点都在同一层的二叉树
3、下列关键字系列中符合堆（大根或小根）性质的是 （ ） A 、45 35 43 26 12 40 B 、42 34 25 32 35 21
C 、16 18 25 20 54 27
D 、18 20 30 32 47 29 四、判断题（正确的打√，错误的打×。

每小题1分，共12分）
1、循环队列中，可以从任何一个元素开始对整个队列进行遍历。

（ ）
2、p 指针指向了链表中的一个元素，p++操作可以使它指向其后继元素。

（ ）
3、要删除链表中的一个元素，应先判断表是否已空，空则不能删除。

（ ）
4、顺序队和顺序栈在插入和删除元素时都不需要移动元素。

（ ）
5、哈夫曼树的每一层上只能有一个叶子结点。

（ ）
6、在结点总数 n 为偶数的完全二叉树中，一定有一个度为1的结点 。

（ ）
7、任意一棵树转换成的二叉树，根结点一定没有右子树。

（ ）
8、中序遍历系列是一个升序系列的二叉树一定是二叉排序树。

（ ）
9、如果一个连通图中没有关节点，它就是重连通图。

（ ） 10、有向带权图的关键路径是带权路径之和为最大的路径。

（ ） 11、对任何顺序表，都可以采用折半查找的方法进行查找。

（ ） 12、在基数排序的过程中，没有进行关键字之间的比较。

（ ） 五、简答题（每小题4分，共40分）（以下答在后面，只写题号不抄题） 1、将顺序对列构成循环队列有何好处？
2
a
图（a ）二叉树 图（b ）无向图
图（c ）AOV 网 图（d ） 二叉树
3、画出图（d ）的二叉树转换成的树。

4、两个栈共享有何好处？
5、写出无向图（b ）（在第二页上）和有向图（e ）的邻接矩阵。

6、画出有向图（e ）的邻接表。

7、画出无向带权图（f ）的最小生成树。

8、已知A 、B 、C 、D 、E 、F ，6个结点的权分别为48、22、14、19、6、12请画出其
最优二叉树（哈夫曼树）。

9、画出按以下顺序输入的关键字系列40、43、21、35、62、48、54、74所生成的二
叉排序树。

10、若待排序的关键字为：48 32 19 28 5 65 78 22 12 91 3 35，画出
建成的大根堆。

（以下答题，写不下答在下一页白纸上，注意写明班级和姓名。

）
图（e ）有向图
图（f ）无向带权图。

合集下载

2009年9月答案解析

2009年9月答案解析

2009年9月二级VF笔试真卷参考答案一、选择题（1）C）【解析】根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。

循环队列、带链队列和带链栈都是线性结构，而二叉树是非线性结构。

（2）B）【解析】栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据；队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。

（3）D）【解析】所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。

在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。

循环队列的主要操作是：入队运算和退队运算。

每进行一次入队运算，队尾指针就进一。

每进行一次退队运算，排头指针就进一。

当rear或front等于队列的长度加1时，就把rear 或front值置为1。

所以在循环队列中，队头指针可以大于队尾指针，也可以小于队尾指针。

（4）A）【解析】算法的空间复杂度是指执行这个算法所需要的内存空间。

这个内存空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。

（5）B）【解析】耦合性与内聚性是模块独立性的两个定性标准。

一般一个较优秀的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块内的内聚性，有利于提高模块的独立性。

（6）A）【解析】结构化设计方法的主要原则可以概括为自顶向下、逐步求精、模块化限制使用goto语句。

（7）C）【解析】N-S图把整个程序写在一个大框图内，这个大框图是由若干个小的基本框图构成的流程图。

E-R图即实体-联系图（Entity Relationship Diagram），提供了表示实体型、属性和联系的方法，用来描述现实世界的概念模型。

PAD是问题分析图，用二维树形结构的图表示程序的控制流，将这种图转换为程序代码比较容易。

自考数据结构02331历年试题及答案(2009--2015个人整理版)

自考数据结构02331历年试题及答案(2009--2015个人整理版)

自考数据结构02331历年试题及答案(2009--2015个人整理版)全国2009年1月自学考试数据结构试题一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.下列程序段的时间复杂度为( )9 s=0；for(i=1；i<n ；i++) for(j=1；j<n ；j++) s+=i*j ； A.O(1) B.O(n)C.O(2n)D.O(n 2)2.假设某个带头结点的单链表的头指针为head ，则判定该表为空表的条件是( )22 A.head==NULL ； B.head->next==NULL ； C.head!=NULL ； D.head->next==head ；3.栈是一种操作受限的线性结构，其操作的主要特征是( )32 A.先进先出 B.后进先出 C.进优于出 D.出优于进4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front 和rear 。

若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( ) A.(rear-front-1)％n B.(rear-front)％n C.(front-rear+1)％n D.(rear-front+n)％n5.判断两个串大小的基本准则是( )52 A.两个串长度的大小 B.两个串中首字符的大小 C.两个串中大写字母的多少 D.对应的第一个不等字符的大小6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为( )60 A.1012 B.1017 C.1034 D.10367.高度为5的完全二叉树中含有的结点数至少为( )72 A.16 B.17 C.31 D.328.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( ) A.5 B.8 C.11 D.189.下列所示各图中是中序线索化二叉树的是( A)81A10.已知含6个顶点(v 0，v 1，v 2，v 3，v 4，v 5)的无向图的邻接矩阵如图所示，则从顶点v 0出发进行深度优先遍历可能得到的顶点访问序列为( )108 A.(v 0，v 1，v 2，v 5，v 4，v 3) B.(v 0，v 1，v 2，v 3，v 4，v 5) C.(v 0，v 1，v 5，v 2，v 3，v 4) D.(v 0，v 1，v 4，v 5，v 2，v 3)11.如图所示有向图的一个拓扑序列是( ) A.ABCDEF B.FCBEADC.FEDCBAD.DAEBCF12.下列关键字序列中，构成大根堆的是( ) A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33 C.9，8，6，3，5，l ，2，7 D.9，8，6，7，5，1，2，313.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( )172A.1539B.1549 C.1551 D.1555 14.已知一个散列表如图所示，其散列函数为H(key)=key ％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( D )d 19715.数据库文件是由大量带有结构的( )206 A.记录组成的集合 B.字符组成的集合 C.数据项组成的集合 D.数据结构组成的集合二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。

(完整版),算法与数据结构题库及答案,推荐文档

(完整版),算法与数据结构题库及答案,推荐文档


A 问题规模是 n2
B 问题规模与 n2 成正比
C 执行时间等于 n2
D 执行时间与 n2 成正比
2、关于数据结构的描述，不正确的是（ ）。
A 数据结构相同，对应的存储结构也相同。
B 数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。
C 数据结构操作的实现与存储结构有关。
D 定义逻辑结构时可不考虑存储结构。
D O(nlog2n)
28、n 个结点的线索二叉树中，线索的数目是（ ）。
A n-1
B n+1
C 2n
D 2n-1
29、若数据元素序列{11,12,13,7,8,9,23,4,5}是采用下列排序方法之一得到的第二趟排序
后的结果，则该排序方法只能是（ ）。
A 插入排序 B 选择排序 C 交换排序 D 归并排序
A. n+1
B. n
C. n-1
11. 一个递归算法必须包括__________。
D. n-2
A. 递归部分 B. 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分
12. 从逻辑上看可以把数据结构分为__________两大类。
第 1 页，共 8 页
A．动态结构、静态结构
B．顺序结构、链式结构
二、填空题
1、算法效率的度量分为 事后测量
和
事前估 两种。
2、算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应当具有
输入、输出、确定性、 有穷性
可行性等特性。
3、一个抽象数据类型 ADT 包括
数据操作 和 对象
两个部分。
4、队列的插入操作是在 队尾 进行，删除操作是在 队头
进行。
数据结构真题2009年下半年

数据结构真题2009年下半年

数据结构真题2009年下半年(总分：124.98，做题时间：90分钟)一、{{B}}单项选择题{{/B}}(总题数：15，分数：30.00)1.按值可否分解，数据类型通常可分为两类，它们是 ( )（分数：2.00）A.静态类型和动态类型B.原子类型和表类型C.原子类型和结构类型√D.数组类型和指针类型解析：[解析] 按“值”是否可分解，可将数据类型划分为两类：原子类型，其值不可分解；结构类型，其值可分解为若干个成分。

2.对于三个函数f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008和h(n)=8888nlogn+3n2，下列陈述中不成立的是 ( )（分数：2.00）A.f(是O(g()B.g(是O(f()C.h(是O(nlog √D.h(是O(n2)解析：[解析] 当n充分大时，由题意可得：f(n)与n3是同阶的，g(n)与n3是同阶的，h(n)与n2是同阶的。

所以f(n)=O(g(n))，g(n)=O(f(n))，h(n)=O(n2)。

3.指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是( ) （分数：2.00）A.p—＞next=r; q—＞next=r—＞next; r—＞next=q; √B.p—＞next=r; r—＞next=q; q—＞next=r—＞next;C.r—＞next=q; q—＞next=r—＞next; p—＞next=r;D.r—＞next=q; p—＞next=r; q—＞next=r—＞next;解析：4.若进栈次序为a,b,e，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是 ( ) （分数：2.00）A.3B.5 √C.6D.7解析：5.假设以数组A[n]存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为 ( )（分数：2.00）A.rear==frontB.(front+1)%n==rearC.rear+1==frontD.(rear+1)%n==front √解析：[解析] 在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。