资源描述：
《2006-2007-1数据结构 b》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、南京林业大学试卷课程数据结构(B卷)2006~2007学年第一学期题号一二三四五六总分得分名姓号学号班注意：请将正确答案写在答题纸上，答在试卷上不给分。一．是非题：（每小题2分，共20分）1．数据的物理结构是指数据在计算机内实际的存储形式。（）2．顺序存储的线性表可以随机存取。（）3．链表中的每个结点中都恰好包含一个指针。（）4．线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。（）5．任意的一棵树转换成二叉树，其根结点的右子树总不为空。（）6．简单模式匹配算法的最大特点是指示主串的指针不需回溯。（
2、）7．用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的边数有关。（）8．任何有向图的拓扑排序结果是唯一的。（）9．哈希表存储的基本思想是由记录关键字值决定记录的存储地址。（）10．堆排序所需的时间与待排序的记录个数无关。（）二．选择题（本大题共10小题，每小题2分，共20分）1．在数据结构中，与所使用的计算机无关的是数据的______结构。A.存储B.物理C.逻辑D.物理和逻辑71．链表不具有的特点是______。A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性
3、表长度成正比2．一个顺序栈一旦被说明，所占用的空间大小________。A．不能固定B．已固定C．可以改变D．随机变化3．下列关于串的叙述中，正确的是________。A．一个串的字符个数即该串的长度B．一个串的长度至少是1C．空串是由一个空格字符组成的串D．两个串的长度相等，则这两个串相等4．下列广义表是线性表的是________。A．L=(x,y,(x,y),x)B．L=(a,(a,b))C．L=(x,y,z)D．L=(x,L,y)5．一棵二叉排序树，用______方法进行遍历，可得到各结点关键字值的递增序列。A．先序遍历B．中
4、序遍历C．后序遍历D．层次遍历6．设结点x和y是二叉树中的任意两个结点，在先序序列中x在y之前，在后序序列中x在y之后，则x和y的关系是________。A．x是y的左兄弟B．x是y的右兄弟C．x是y的祖先D．x是y的后代7．对用邻接表表示的图进行广度优先遍历时，通常引入______来实现算法。A．栈B．队列C．图D．树8．顺序查找适合于存储结构为______的查找表。A．压缩存储B．散列存储C．索引存储D．顺序存储或链式存储9．一组记录的关键字为(46,79,56,38,40,84)，利用快速排序的方法，以第一个记录为枢轴得到的一
5、次划分结果为________。A．38,40,46,56,79,84B.40,38,46,79,56,84C.40,38,46,56,79,84D.40,38,46,84,56,79三．填空题：（每空2分，共20分）1．根据数据元素之间关系的不同特性，通常有四类基本结构：集合结构，__(1)__结构，树形结构和__(2)__结构。2．__(3)__是数据的基本单位。3．设顺序栈存放在s.elem[0…m-1]中，栈顶指针为s.top，栈底位置是m-1,则栈空条件是__(4)__,栈满条件是__(5)__。4．三元组表是__(6)__
6、的一种顺序存储结构。5．m个叶子结点的哈夫曼树所具有的结点总数为__(7)__。71．不存在拓扑序列的有向图是__(8)__。2．简单选择排序算法所执行的记录次数交换最少为__(9)__次。3．__(10)__查找法的平均查找长度与元素个数无关。四．算法阅读题（10分）：1.下面是在不带头结点的单链表head的第一个结点之前插入一个新结点的算法，请补充完整。单链表的存储结构为：typedefstructNode{ElemTypedata;structDuLNode*next;}LNode,*LinkList;voidInsertNo
7、de(LinkList&head,ElemTypex){s=(LNode*)malloc(sizeof(LNode));s->data=x;___(1)___;___(2)___;}2．下面算法是利用插入排序方法将一个带头结点的无序的单链表转变成一个递减有序的单链表（单链表的存储结构同上题），请填空。voidsort(LinkListL){if(L->next!=NULL){p=L->next->next;L->next->next=NULL;while(___(3)___){q=p;p=p->next;s=L;while(s->n
8、ext!=NULL&&s->next->data>q->data)___(4)___;___(5)___;s->next=q;}}}7五．解答题（20分）：1．设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGH
