- 1、本文档共7页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
2006-2007-1数据结构 b
南 京 林 业 大 学 试 卷
课程 数据结构(B卷) 2006~2007学年第一学期
注意:请将正确答案写在答题纸上,答在试卷上不给分。
一.是非题:(每小题2分,共20分)
1.数据的物理结构是指数据在计算机内实际的存储形式。( )
2.顺序存储的线性表可以随机存取。( )
3.链表中的每个结点中都恰好包含一个指针。( )
4.线性表可以看成是广义表的特例,如果广义表中的每个元素都是原子,则广义表便成为线性表。( )
5.任意的一棵树转换成二叉树,其根结点的右子树总不为空。( )
6.简单模式匹配算法的最大特点是指示主串的指针不需回溯。( )
7.用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小与图中的边数有关。( )
8.任何有向图的拓扑排序结果是唯一的。( )
9.哈希表存储的基本思想是由记录关键字值决定记录的存储地址。( )
10.堆排序所需的时间与待排序的记录个数无关。( )
二.选择题(本大题共10小题,每小题2分,共20分)
在数据结构中,与所使用的计算机无关的是数据的______结构。A. 存储 B. 物理 C. 逻辑 D. 物理和逻辑
链表不具有的特点是______。A.可随机访问任一元素 B.插入删除不需要移动元素C.不必事先估计存储空间 D.所需空间与线性表长度成正比
一个顺序栈一旦被说明,所占用的空间大小________。A.不能固定 B.已固定 C.可以改变 D.随机变化
下列关于串的叙述中,正确的是________A.一个串的字符个数即该串的长度 B.一个串的长度至少是1C.空串是由一个空格字符组成的串 D.两个串的长度相等,则这两个串相等
下列广义表是线性表的是________。A. L=(x,y,(x,y),x) B. L=(a,(a,b)) C. L=(x,y,z) D.L=(x,L,y)
一棵二叉排序树,用______ 方法进行遍历,可得到各结点关键字值的递增序列。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历
设结点x和y是二叉树中的任意两个结点,在先序序列中x在y之前,在后序序列中x在y之后,则x和y的关系是________。A.x是y的左兄弟 B.x是y的右兄弟C.x是y的祖先 D.x是y的后代
对用邻接表表示的图进行广度优先遍历时,通常引入______来实现算法。A.栈 B.队列 C.图 D.树
顺序查找适合于存储结构为______的查找表。A.压缩存储 B.散列存储 C.索引存储 D.顺序存储或链式存储
一组记录的关键字为(46,79,56,38,40,84),利用快速排序的方法,以第一个记录为枢轴得到的一次划分结果为________。A.38,40,46,56,79,84 B. 40,38,46,79,56,84C. 40,38,46,56,79,84 D. 40,38,46,84,56,79
三.填空题:(每空2分,共20分)
根据数据元素之间关系的不同特性,通常有四类基本结构:集合结构, __(1)__结构,树形结构和__(2)__结构。
__(3)__是数据的基本单位。
设顺序栈存放在s.elem[0…m-1]中,栈顶指针为 s.top,栈底位置是m-1,则栈空条件是__(4)__,栈满条件是__(5)__。
三元组表是__(6)__的一种顺序存储结构。
m个叶子结点的哈夫曼树所具有的结点总数为__(7)__。
不存在拓扑序列的有向图是 __(8)__。
简单选择排序算法所执行的记录次数交换最少为__(9)__次。
__(10)__查找法的平均查找长度与元素个数无关。
四.算法阅读题(10分):
1. 下面是在不带头结点的单链表head的第一个结点之前插入一个新结点的算法,请补充完整。
单链表的存储结构为:
typedef struct Node {
ElemType data;
struct DuLNode * next;
}LNode,* LinkList;
void InsertNode(LinkList head, ElemType x)
{ s=( LNode * )malloc(sizeof(LNode));
s-data=x;
__ _(1)___;
__ _(2)___;
}
2.下面算法是利用插入排序方法将一个带头结
文档评论(0)